Файл: 20-24.docx

Стационарная двухслойная схема. Теорема Самарского об условии ее сходимости.

При решении систем уравнений используя итерации (приближения), при которых находится не само решение системы, а находится некоторая последовательность, которая сходится к решению за конечное число шагов.

И важнейшей особенностью этого метода является то, что эти методы сходятся не для любой схемы, но любую схему можно привести к такому виду, чтобы итерационный метод сходился при любом приближении.

Каждый следующий член итерационной последовательности выражается через предыдущие, уже известные.

При обсуждении итерационных методов решения СЛАУ мы ограничимся линейными одношаговыми алгоритмами, которые обычно записывают в стандартной канонической форме:

для системы Ax=Y

B_k (x_k+1-x_k + Ax_k)₌ Y

_k+1

где ,.

В такой записи процесс характеризуется последовательностью матриц и числовых параметров, которые называют итерационными параметрами. Если матрицыи параметрыне меняются в процессе итераций, т. е. не зависят от индекса, то итерационный процесс называетсястационарным.

Приведем данную формулу к виду

B_kx_k+1=Z_k, где Z_k=(B-A)x_k+Y

Требования к:

1)схема должна сходиться

2) сходимость должна быть быстрой

Требования к B:

1. Матрица должна быть общего вида

2. Должна быть легко обратимой

Рассмотрим стационарный итерационный процесс, когда матрица и итерационный параметрне зависят от индекса, и докажем следующую теорему о достаточных условиях его сходимости.

Теорема Самарского

Пусть дано Ax=Y, A=A^T, A>0, - положительно определенная матрица, - положительное число,.

Тогда стационарная двухслойная схема сходится к точному решению из любого начального приближения.

Оценка погрешностей выполнения арифметических операций с парами чисел.

Сложение:

a=x1+x2

x1=x1*+1, 1

x2=x2*+2, 2

даны 2 числа х1и х2 с точными значением х1* и х2* и погрешностями 1, 2

и их сумма a.

тогда a= (x1*+1)+ (x2*+2)=(x1*+x2*)+(1+2)=a*+

значит абсолютная погрешность суммы не превосходит суммы абсолютной погрешности слагаемых.

||12

Вычитание:

Вычитанию соответствует аналогичный случай что и сложению, но неизвестно возрастет она или уменьшится

Умножение:

a=(x1*+1)(x2*+2)=x1*x2*+x1*2+x2*1+12=a*+ x1*2 +x2*1+12

Видно, что погрешность может увеличиваться, а моожет и уменьшиьтся.

|x1*|2+|x2*|+12, где 12 очень мало, а значит |x1*|2+|x2*|1

Деление:

a=x1/x2

=-a*+a=a-a*=x1 – x1* =x1*+1 – x1* = (x1*+1)x2* - (x2*+2)x1* =

x2 x2* x2*+2 x2* (x2+2)x2*

= x1*x2* +1x2* - x1*x2*-2x1* = 1x1* - 2x1*x2*1+x1*2

(x2*+)x2* (x2*+)x2* (x2*)²

(x2*)² - влияет на величину погрешности. Погрешность тем меньше, чем больше знаменатель.

Значит при делении величина погрешности уменьшается при увеличении знаменателя.

Метод Зейделя, метод верхней релаксации, методы факторизации, доказательство их сходимости для стационарных двухслойных схем.

Метод Зейделя

Пусть решается система уравнений Ax =b , все диагональные элементы которой ненулевые. В итерационном методе Зейделя последовательно уточняются компоненты решения, причем k-я компонента находится из k –го уравнения. Именно, если xⁿ = (xⁿ_1,......,xⁿ_m)^T,то следующее приближение определяется из системы соотношений

a₁₁ xⁿ⁺¹₁ + a₁₂ xⁿ₂ +.........+ a_1mxⁿ_m = b₁ ,

a₂₁ xⁿ⁺¹₁ + a₂₂ xⁿ⁺¹₂ + a₂₃ xⁿ₃.........+ a_2mxⁿ_m = b_2,

_{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .}

a_m1 xⁿ⁺¹₁ + a_m2 xⁿ⁺¹₂+.........+ a_mm xⁿ⁺¹_m = b_m.

Эту систему можно представить в виде

Bxⁿ⁺¹ + Cxⁿ = b,

где

a₁₁ 0 0 . . . 0 0 a₁₂ a_{13 . . .} a_1m

B= a₂₁ a₂₂ 0 . . . 0 , C= 0 0 a_{23 . . .} a_2m

. . . . . . . . . . . . . .

a_m1 a_m2 a_m3 . . .a_mm0 0 0 . . . 0

Отсюдаполучаем

xⁿ⁺¹ = -B^-1Cxⁿ + B^-1b

Таким образом, метод Зейделя эквивалентен некоторому методу простой итерации; поэтому для его сходимости при любом начальном приближении необходимо и достаточно, чтобы все собственные значения матрицы B^-1C по модулю были меньше 1.

Метод верхней релаксации

Модифицируем метод Зейделя. С этой целью введем параметр и запишем

. (1)

В данном случае

,. (2)

Примы возвращаемся к методу Зейделя.

Соотношению (1) можно придать вид

. (3)

Такая форма записи показывает, что параметр влияет на диагональ матрицы.

Для построения алгоритма вычисления очередной итерации нужно разделить в левой части рекуррентной формулы (2) члены, содержащие и, и придать ей форму:

. (4)

Если перейти от векторной записи к записи в виде отдельных уравнений, то можно получить для компонент очередной итерации формулы:

,. (5)

Исследуем условия сходимости метода верхней релаксации при дополнительном предположении, что матрица удовлетворяет условиям теоремы Самарского(А=А^т>0 –самосопряженная положительно определенная). Самосопряженность матрицы означает, что,. Отсюда следует

. (6)

Составим для рассматриваемого случая матрицу . Согласно (2)

. (7)

Запишем условие ее положительной определенности

. (8)

Второе слагаемое в выражении (7) не дает вклада в квадратичную форму (8) в силу соотношения(6).

Матрица является, по предположению, положительно определенной. Следовательно, все ее диагональные элементы строго положительны:,. Это означает положительную определенность матрицы:. В результате знак выражения (8) определяется знаком первого множителя, так что достаточное условие для сходимости итерационной последовательности метода верхней релаксации принимает вид:

Метод Зейделя, соответствующий случаю , удовлетворяет этому условию.

Методы факторизации

Факторизованное представление матрицы - представление матрицы в виде произведения матриц, они более простые, чем исходная.

B(x₁ -x₀)/τ + Ax₀ = Y; (1)

B= τAτA(x₁ -x₀) /τ + A x₀ =Y;

Ax₁ - Ax₀ + Ax₀ = Y;

Ax₁ = Y;

Требования к матрице В:

1. матрица В должна быть как можно ближе к матрице А, если они будут совпадать, то итерационный процесс сойдется за одну итерацию

2. должна быть легко обратимой

факторизованное представление:

A=A₁ + A₂ ; A₁ = A₂^T;

A₁ = A₁ + 1/2D;

=0+ +

0

A₂= A₂+ 1/2D;

AA₁ DA₂

рассмотрим матрицу В:

B=(E- τ/2 A₁ ) (E+ τ/2 A₂ );

утверждение:

схема (1) сходится из любого начального приближения при такой матрице В,длялюбх значений τ

Метод Эйлера

   Пусть требуется найти приближенное решение дифференциального уравнения y' = f(x,y), удовлетворяющее начальному условию y(x₀) = y₀. При решении задачи методом Эйлера приближенное значение y₁ решения y(x) в точке x вычисляется по формуле y₁ = y₀ + (x-x₀)f(x₀,y₀). Приближенные значенияy_i решения уравнения y(x) в точках x_i = x₀ +ih, i=1,2,...,n вычисляются по формулам y_i+1 = y_i + hf(x_i,y_i). Метод Эйлера является одношаговым методом первого порядка. Локальная погрешность метода Эйлера равна O(h²)