Вопрос№42 Метод простой итерации решения систем линейных алгебраических уравнений. Условие сходимости.

Рассмотрим систему линейных алгебраических уравнений Ax =b (1); x_k+1=F(x₀,x₁,..., x_k, A,b), k=0, 1,...; x_k=(x₀⁽¹⁾,..., x_k-1⁽¹⁾); x_k+1=B_kx_k+g_k, k=0,1,....; (2) - общая формула линейных одношаговых нестационарных методов.

Требуют, чтобы после подстановки в (2) точного решения получалось тождество.

X=A^-1b (точное решение ) (*); A^-1b=B_kx_k+g_kg_k=(E-B_k)A^-1b, (E-B_k)A^-1=C_k.

x_k+1=B_kx_k+C_kb,

 B_k+C_kA=E (3)

Сходится ли приближенное решение к точному? C_k=(E-B_k)/A=(E-B_k)A^-1, x_k+1=B_kx_k+A^-1b- A^-1bB_k; Из левой и правой части вычтем точное решение (*):x_k+1 -x=B_k(x_k-A^-1b); Полагая k=0,1,..., m, получим: x_m+1 -x=B_mB_m-1....B₀(x₀-A^-1b), откуда следует оценка:

||x_m+1 -x ||(П(от i=0 до m)||B_i||)||x₀-A^-1b||;

Сходимость метода.

Теорема1. Для сходимости нестационарного метода простой итерации (3) достаточно, чтобы ||B_i||<1 i.

Рассмотрим линейный стационарный метод. x_k+1=Bx_k+Cb, B+CA=E (4). Отличие этого метода от нестационарного заключается в матрице В.

Теорема2. Для сходимости стационарного метода простой итерации (4) необходимо и достаточно, чтобы |(B)|<1.

Доказательство: Полагая последовательно k=0,1,...,m,..., получаем:x_m+1=B^m+1x₀+( B^m+B^m-1+...+B+E)*CB (5). Из последнего видно, что для сходимости необходимо и достаточно, чтобы сходился матричный ряд E+B+...+B^m+... Известно, что для сходимости суммы матричного ряда необходимо и достаточно, чтобы все собственные числа матрицы В по модулю были меньше 1. 

Следствие. Для сходимости стационарного метода (4) достаточно, чтобы какая-либо из норм матрицы В была меньше 1.

=( E+B+...+B^m+...)*Cb (6), вычтем из (5), (6):x_m+1-x =B^m+1x₀-(B^m+1+B^m+2+...+)*Cb. Отсюда получаем оценку: ||x_m+1-x || ||B^m+1||*||x₀||+[|| B^m+1||/(1-||B||)]*||C||*||b || (7);

||x_m+1-x || (в задачах выполняем действия до сих пор).

Очень часто в качестве критерия остановки берут следующее: ||x_m+1-x_m ||.

Вопрос№43 Метод простой итерации вычисления корня нелинейного уравнения. Условие сходимости. Метод Ньютона: формула, геометрическая интерпретация, условия сходимости.

Метод простой итерации: Допустим, что задача отделения корней решена. В окрестности корня перепишем уравнение f(x)=0 (1) в эквивалентном виде: x=j(x) (2). Устраиваем итерационный процесс x_k+1=j(x_k) (3) k=0,1,… Для сходимости (3) достаточно, чтобы в окрестности корня |j’(x)|£1(4). Справедлива оценка: |x_n-a|£q|x₀-a| или |x_n-a|£(q/1-q) *|x_n-x_n-1|. В качестве условия окончания расчетов может выступать неравенство: (x_n-x_n-1)²/|2x_n-1-x_n-x_n-2|£e. Самым простым переходом от f(x)=0 к эквивалентному виду x=j(x) является равенство x=x+t(x)f(x), где t(x) выбирается из соображений об уничтожении производной.

Метод Ньютона (метод касательных).

С помощью равенства x=x+t(x)f(x) перейдем от f(x)=0 (1) к эквивалентному виду x=j(x) (2). В качестве t возьмем t(x)=-1/f ‘(x). Тогда x_n+1=x_n-f(x_n)/f ‘(x_n), n=0,1,… . j(x)=x-f(x)/f ‘(x) Þ j ‘ (x)=f(x)*f »(x)/(f ‘(x))² и |j ‘(x)|£1, т.е. $ окрестность, где метод сходится.

Th (о единственности корня на отрезке): Пусть [a,b] такой, что f(a)*f(b)<0. Пусть f(x)ÎC²[a,b]. Пусть f ‘ (x) и f «(x)¹0 и сохраняет пост. знак на [a,b]. Тогда на [a,b] имеется ед. корень ур-я f(x)=0 и этот корень м.б. вычислен с " степенью точности по методу Ньютона, исходя из (.) x₀ Î [a.b], такой, что f(x₀)f «(x₀)>0.

Следствия из метода Ньютона: 1. метод секущих: x_n+1=x_n-f(x_n), f ‘(x_n)=(f(x_n)-f(x_n-1))/(x_n-x_n-1), (f(x_n)-f(x_n-1))/(x_n-x_n-1)=(x_n-1f(x_n)-x_n f(x_n-1))/(f(x_n)-f(x_n-1)); 2. метод хорд: x_n+1=(x₀f(x_n)-x_nf(x₀))/(f(x_n)-f(x₀)); 3. комбинированный метод: f(a)*f «(a)>0, x₀=?-f(a)/f ‘(a), x₁=(af(b)-bf(a))/f(b)-f(a). Далее, x_2n=x_2n-2-f(x_2n-2)/f ‘(x_2n-2), x_2n+1=(x_2n-2f(x_2n-1)-x_2n-1 f(x_2n-2))/(f(x_2n-1)-f(x_2n-2)).

Метод Ньютона для вычисления корней для нелинейной системы: необходимо в равенстве x_k+1=x_k-f_x^-1(`x<sub>k</sub>)*f(`x_k) k=0,1,…….перенести x_k влево и результат с обоих сторон домножить на матрицу Якоби. Итак, f_x(`x)(`x_k+1-`x<sub>k</sub>)=f(`x_k) или S(j от 1 до n) ¶f ⁱ (`x<sub>k</sub>)/¶x <sup>j</sup> (x<sub>k+1</sub>-x<sub>k</sub>)=-f <sup>i</sup>(`x_k) i=1,…,n; k=0,1,… S(j от 1 до n) ¶f ⁱ (`x<sub>k</sub>)/¶x <sup>j</sup> Dx<sub>k+1</sub><sup>j</sup>=-f <sup>i</sup>(`x_k), где Dx_k+1^j= xⁱ_k+1-xⁱ_k.(1) – система линейных алгебраических ур-ий. На каждом шаге решается относительно Dx_k+1^j.

Th (о сходимости метода Ньютона): Пусть в некоторой замкнутой выпуклой области n-мерного пр-ва, содержащей корень системы`f(`x)=0. Ф-ции f ⁱ (`x) непрерывно дифференцируемы (f <sup>i</sup> (`x)ÎС¹(G)) и в (.) корня матрица Якоби невырождена. Тогда метод Ньютона сходится. Замечание 1: Иногда используют аналоги ? метода Гаусса-Зейделя, а именно:

x¹_k+1=j¹(x¹_k….xⁿ_k)

x²_k+1=j²(x¹_k+1….xⁿ_k)

…………………….

xⁿ_k+1=jⁿ(x¹_k+1 , x²_k+1,….,xⁿ_k)

и

f ¹(x¹_k+1 , x²_k,….,xⁿ_k)=0

f ² (x¹_k+1 , x²_k+1,….,xⁿ_k)=0

……………………….

f ⁿ(x¹_k+1 , ….,xⁿ_k+1)=0

Замечание 2: Есть ещё итерационные методы, в кот. корень находится минимизацией нек. функционала. # рассмотрим Ф(x)= S(i от 1 до n) f ⁱ (`x)<sup>2</sup>=0. Очевидно, что его нулевой минимум достигается на точном решении системы`f(`x)=0, поэтому чтобы её решить достаточно найти min Ф.