Метод простой итерации. Рассмотрим систему: Ax=b

а11 а12 а1n x1 b1

A=a21 a22 a2n X=x2 B= b2

an1 an2 ann xn bn

Преобразуем эту систему, предположив, что a_ii0,тогда

x₁=₁+₁₂x₂+…+_{1 n}x_n x_n=_n+_n1x₁+…+_{n n-1}x_n-1

_где _i=b_i/a_ii _ij= -a_{i j}/a_{i i} Введём новые матрицы:

11 12 1n 1

=21 22 2n =2

n1 n2 nn n X=x+

Эту систему будем называть методом последовательных приближений, за нулевое приближение можно взять,напр., столбец свободных членов, т.е. X⁽⁰⁾= x⁽¹⁾= x⁽⁰⁾+… x^(k+1)= x^(k)+ Если последовательность решений имеет предел, то этот предел является решением исходной системы: x⁽⁰⁾…x^(к+1)… Lim_k- x^(k+1)=x – решение. т.о. x_i⁽⁰⁾=_i _ii=0 - всегда

Достаточные условия сходимости процесса итерации: Если для приведенной системы x=x+ выполнено по крайней мере одно из условий:1) n 2) n

|_{I j}|<1 |_{I j}|<1

j=1 i=1

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

Следствие: n

Для исходной системы _{i j}x_j=b_i (i=1..n)

j=1

метод сходится если выполнимы неравенства:

|a_{i i}|> _iJ|a_{i j}|, т.е. все модули диагональных коэф для каждого уравн. > суммы модулей всех остальных коэф.

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

Этот метод явл модификацией метода простой итерации. Основная идея закл в том, что при вычислении (к+1) приближения неизвестной х_i учитывается уже раннее вычисленные (к+1) приближения неизвестных х₁…x_i-1. Пусть дана приведенная линейная система: x₁⁽⁰⁾…x_n⁽⁰⁾ – задано

Предположим, что катое приближение корнейx_i^(k) известны, вычислим x_i^(k+1) приближение.

Достаточные условия сходимости метода Зейделя:

Если для приведенной системы x=x+ выполнено по крайней мере одно из условий: 1) n 2) n

|_ij|<1 |_ij|<1

j=1 i=1

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

Следствие: n

Для исходной системы _i=1 _ijx_j=b_i (i=1..n) метод сходится если выполнимы неравенства: |a_ii|>_ij|a_ij|, т.е. все модули диагональных коэф-в для каждого уравнения больше суммы моделей всех остальных коэф-в.

3.Достаточное усл. сходимости процесса итерац.Под нормой матрицы A=||a_ij|| понимается действительное число удовлетворяющее св-ву: 1) ||A||=>0 2)||A||=|| ||A|| 3)||A+B||<=||A||+||B||

4) ||AB||<=||A||*||B|| Основные нормы: ||A||₁=max_i _j |a_{i j}| ||A||₂=max_j _i |a_{i j}| ||A||₃=_{i,, j} |a_{i j}|².

Теорема: Процесс итерации для системы х=x+ сх-ся к единственному решению, если какая-либо норма матрицы |||| <1 (ИЛИ) х^(к)=x^(к-1)+ сх-ся, если |||| <1.

Д-во:В высшей алгебре доказано,что указан- ные три нормы экв-ны. Построим послед-ть приближений x⁽⁰⁾, x⁽¹⁾= x⁽⁰⁾+,

x⁽²⁾= x⁽¹⁾+=(x⁽⁰⁾+)+=²x⁽⁰⁾++ …

x^(k)=x^(k-1)+ (или) x^(k)=(E++²+…+^(k-1))x⁽⁰⁾+ ^(k)x⁽⁰⁾

Т.к. ||||<1, то lim_k- ^(k)=0

lim_k-(E++²+…+^(k-1))= lim_k- ^(k)=(E-)^-1

Таким образом: x=lim_k-x^(k)=(E-)^-1, т.е. сходимость доказана.это равенство М запи- сать (E-)x= => x=x+

4. Отделение корней.

Теорема: Если непр-я ф-я f(x) принимает значения разных знаков на концах отрезка [a,b], т.е. f(a)*f(b)<0, то внутри этого отрезка наход-ся по меньшей мере один корень ур-я f(x)=0.

х* - точное значение корня.

Значение корня будет единично, если f’(x) сущ-ет и сохраняет знак внутри интервала [a,b]

5. Метод половинного деления.

Будем считать уравнение f(x)=0 на [a,b]. Известно, что f(a)*f(b)<0, т.е. нужно найти такое значение х: |x-x*|<. Метод состоит в последовательном построении интервалов [a_n,b_n], где n-0,1…, вложенных друг в друга и содержащих решение х*. Пусть a₀=a b₀=b. Пусть построена послед-ть интервалов [a_i,b_i], таких, что f(a_i)*f(b_i)<0. Тогда полагаем, что с_i=(a_i+b_i)/2. Если f(c_i)=0, то х*=с_i. Если f(c_i)0 то: 1) f(a_i)*f(c_i)<0 2)f(b_i)*f(c_i)<0

Если (1) – то a_i+1=a_i b_i+1=c_i. Если (2)- то a_i+1=с_i b_i+1=b_i.

В любом случае получен интервал вдвое меньше предыдущего и f(a_i+1)*f(b_i+1)<0 т.е. корень сод-ся в этом промежутке [a_i+1,b_i+1]. Процесс заканчивается либо когда f(c_i)=0 либо |b_n-a_n|<. Тогда х=с_i либо

х=(b_n+a_n)/2 очевидно b_n-a_n=(b-a)/2ⁿ Значение а₁,…а_n и b_1…b_n образуют последовательности которые в пределе выдают значение корня:

х=lim_n-a_n= lim_n-b_n х-a_n<=(b-a)/2ⁿ откуда число шагов k: k=log₂((b-a)/)+1