ПРИМЕР 8. Построить алгоритмы методов простой итерации, релаксации и Зейделя для решения разностной задачи
Вопрос №8
Стационарные итерационные методы
1 Метод простой итерации: =>
2 Метод релаксации: Строится с использованием расщепл матрицы: - параметр релаксации.
Будем рассматривать стац. итерационный метод: В
Если подставим погрешность в канон. Виде итерационной формуле.
=>
В
,
Покажем, что существует сходимость итерационного метода.
Теорема сходимости. Пусть т.е.
Предположим, что существует , тогда условие
Это условие является достаточным для сходимости, т.е. существует
.
Доказательство. Рассмотрим 2 выражения для рекуррентной формулы с погрешностью
, тогда
.
Обозначим: .
по усл. Из т.; т.о.
Получ. монотонно убыв к -> 0 последовательность положительных чисел. По теореме В-са она имеет предел, т.е. сущ. при этом
т.е.
значит
при этом из условия теоремы:
. ЧТД
Следствие 1 .
Критерием для останов итерац процесса для зад , по невязке
Док-воПо итер. фор-ле для погрешности:
Оба этих условия оц. им. по порядку малости
Потому что вел-на этих множителей не влияет на порядок
Следствие 2(усл. сх-ти мет. простых итерац.(МПИ))
МПИ при
Док-во((
Рассмотрим метод релаксации.
Следствие 3
Док-во Рассмотрим условие:
Для полож. матр. ее диаг. матр. будет полож.
Тогда
При этом при w=1 метод наз-ся методом Зейделя. а когда 1<w<2 – методом верхней релаксации. Метод нижней релаксации не нашел применения,т.к. там плохая сходимость.
Скорость сх-ти иттерац. метода
Рассмотрим только для стац. иттер. метода(простой иттер. и релаксации)
Рассм. выр-ие для погр.: где s оператором перхода от k-1 итерации к k-ой. Тогда выр-ие примет вид при рекурс . преобраз. к 0
Для оцен. погр-ти по ||.||
Если рас-м опер. s то он вкл. опер-р , кот. опр-ся не симметр. матр. (
Опр
наз-ся спектральным радиусом несимметричного оператора
;
.
Пример:
Пусть хотим уменьшить ||.|| погрешности нач. прибл. в 10 раз
Чтобы найти k, обеспеч. ее точность
Введем .
наз-ся ассимптотической скоростью сход-ти итерац процесса, а
наименьш число итераций, необх-х для достижения точности
.
Для сравн методов берут
При таких усл. опр-ют k> и для q опр-ют число операций
Экономичный метод – это метод, треб. для достиж.
Особенности алгоритмов.(точно не знаю надо ли)
Алгоритм МПИ (метода простых итераций) и МВР (метода верхних релаксаций).
.
(первые 2 слагаемых образуют оператор , третье –
, последние -
).
Оператор определяется пяти-диагональной матрицей.
МПИ:
;
Итерации в этом методе идут по совокупности координат.
МВР:
,
-параметр релаксации.
Метод имеет итерационную формулу по корд-ой итер. При такой записи т.е.на границе.
ПРИМЕР 8. Построить алгоритмы методов простой итерации, релаксации и Зейделя для решения разностной задачи.
Решение:
Найдем матрицу А:
= A
Форма записи метода Зейделя:
где
Найдем минимальное число итераций:
Метод простой итерации:
Здесь
Метод релаксации:
Надо найти :
т.е.
АХТУНГ: то, как находим в методе релаксации, - в наших лекциях этого не было! это есть в лекциях на емаксе за позапрошлый 4 курс, в виде отдельной теоремы. Так что он может спросить, откуда это взялось.