ПРИМЕР 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 курс, в виде отдельной теоремы. Так что он может спросить, откуда это взялось.