За аналогією з (2.1) систему (5.1) можна подати у наступній еквівалентній формі:

де g(x) – ітераційна вектор-функція векторного аргументу. Системи нелінійних рівняньчасто виникають безпосередньо у вигляді (5.2) (наприклад, у чисельних схемах для диференціальних рівнянь), у цьому випадку жодних додаткових зусиль для перетворення рівнянь (5.1) на систему (5.2) не потрібно. Якщо продовжити аналогію з методом простої ітерації одного рівняння, то ітераційний процес, заснований на рівнянні (5.2), можна організувати так:

• 1) вибирається деякий початковий вектор х ((,) е 5 (х 0 , а)(передбачається, що х* е 5„(х 0 , а));
• 2) наступні наближення обчислюються за формулою

то ітераційний процес завершено і

Як і раніше, нам необхідно з'ясувати, за яких умов

Обговоримо це питання, виконавши простий аналіз. Спочатку ми введемо помилку /г-го наближення як е (^ = x(i) - х *. Тоді ми можемо записати

Підставимо ці вирази (5.3) і розкладемо g(x* + e (/i)) за ступенями е (до>в околиці х* як функцію векторного аргументу (припускаючи, що всі похідні приватні функції g(x) безперервні). Враховуючи також, що х* = g(x*) ми отримаємо

або в матричній формі

В = (b nm)= I (х *) 1 - ітераційна матриця.

Якщо норма помилки ||е®|| досить мала, то другий доданок у правій частині виразу (5.4) можна знехтувати, і тоді воно збігається з виразом (2.16). Отже, умова збіжності ітераційного процесу (5.3) поблизу точного рішення описується теоремою 3.1.

Схожість методу простої ітерації. Необхідна та достатня умова для збіжності ітераційного процесу (5.3):

та достатня умова:

Ці умови мають радше теоретичне, ніж практичне значення, оскільки ми не знаємо х'. За аналогією з (1.11) отримаємо умову, яка може бути корисною. Нехай х * е 5 про (х 0, а)та матриця Якобі для функції g(x)

існує для всіх x e S n (x 0 a) (зауважимо, що C(x*) = В). Якщо елементи матриці С(х) задовольняють нерівність

для всіх х е 5„(х 0 , а),тоді достатня умова (5.5) також виконується для будь-якої матричної норми.

Приклад 5.1 (метод простої ітерації) Розглянемо таку систему рівнянь:

Одна з можливостей подати цю систему в еквівалентній формі (5.2) – висловити Хз першого рівняння та х 2з другого рівняння:

Тоді ітераційна схема має вигляд

Точне рішення х* е 5„((2, 2), 1). Виберемо початковий вектор х (0) = (2,2) та ? р =КТ 5 . Результати обчислень представлені у табл. 5.1.

Таблиця 5.1

Ці результати показують, що збіжність є досить повільною. Щоб отримати кількісну характеристику збіжності, проведемо простий аналіз, вважаючи х (1/) точним рішенням. Матриця Якобі С(х) для нашої ітераційної функції має вигляд

тоді матриця приблизно оцінюється як

Легко перевірити, що умова (5.5), ні умова (5.6) не задовольняються, але збіжність має місце, оскільки 5(B) ~ 0.8.

Часто можна прискорити збіжність методу простої ітерації, трохи змінивши процес обчислень. Ідея такої модифікації дуже проста: для обчислення п-й компоненти вектора х (А+1)можна використовувати не тільки (т = п,..., N), але також вже обчислені компоненти вектора наступного наближення х до ^ (/= 1,п - 1). Таким чином, модифікований метод простої ітерації може бути представлений у вигляді наступної ітераційної схеми:

Якщо наближення, що генеруються ітераційним процесом (5.3), сходяться, то ітераційний процес (5.8) сходиться, як правило, швидше за рахунок повнішого використання інформації.

Приклад 5.2 (модифікований метод простої ітерації) Модифікована проста ітерація системи (5.7) подається у вигляді

Як і раніше, виберемо початковий вектор х (0) = (2, 2) та р р = = 10 -5. Результати обчислень представлені у табл. 5.2.

Таблиця 5.2

I Теболина зміна порядку обчислень призвела до зменшення кількості ітерацій у два рази, а значить, і до зменшення кількості операцій у два рази.

Метод простих ітераційзаснований на заміні вихідного рівняння еквівалентним рівнянням:

Нехай відоме початкове наближення до кореня х = х 0. Підставивши його в праву частинурівняння (2.7), отримаємо нове наближення потім аналогічним чином отримаємо і т.д.:

. (2.8)

Не за всіх умов ітераційний процес сходиться до кореня рівняння х. Розглянемо цей процес докладніше. На рис.2.6 наведено графічна інтерпретаціяодностороннього схожого і розбіжного процесу. На рис.2.7 зображені двосторонній схожий і розбіжний процеси. Розбіжний процес характеризується швидким наростанням значень аргументу та функції та аварійним завершенням відповідної програми.

При двосторонньому процесі можливе зациклювання, тобто нескінченне повторення тих самих значень функції та аргументу. Зациклювання відокремлює розбіжний процес від того, що сходить.

З графіків видно, що при односторонньому, і при двосторонньому процесі збіжність до кореня визначається нахилом кривої поблизу кореня. Чим менший нахил, тим краще збіжність. Як відомо, тангенс кута нахилу кривої дорівнює похідної кривої в даній точці.

Отже, що менше поблизу кореня, то швидше сходиться процес.

Для того щоб ітераційний процес був схожим, необхідно в околиці кореня виконання наступної нерівності:

Перехід від рівняння (2.1) до рівняння (2.7) можна здійснити у різний спосібзалежно від виду функції f(x).За такого переходу необхідно побудувати функцію те щоб виконувалася умова збіжності (2.9).

Розглянемо один із загальних алгоритмів переходу від рівняння (2.1) до рівняння (2.7).

Помножимо ліву та праву частини рівняння (2.1) на довільну константу bі додамо до обох частин невідоме х.При цьому коріння вихідного рівняння не зміниться:

Введемо позначення і перейдемо від співвідношення (2.10) до рівняння (2.8).

Довільний вибір константи bдозволить забезпечити виконання умови збіжності (2.9). Критерієм закінчення ітераційного процесу буде умова (2.2). На рис.2.8 наведено графічна інтерпретація методу простих ітерацій при описаному способі уявлення (масштаби по осях X та Y різні).

Якщо функцію вибрано у вигляді, то похідна від цієї функції буде. Максимальна швидкість збіжності буде при , тоді та ітераційна формула (2.11) переходить у формулу Ньютона. Таким чином, метод Ньютона має саму високий ступіньзбіжності з усіх ітераційних процесів.

Програмна реалізація методу простих ітерацій виконана у вигляді процедури-підпрограми Iteras(ПРОГРАМА 2.1).

Вся процедура практично складається з одного циклу Repeat... Until, що реалізує формулу (2.11) з урахуванням умови припинення ітераційного процесу (формула (2.2)).

У процедуру вбудовано захист від зациклювання шляхом підрахунку числа циклів за допомогою змінної Niter. на практичних заняттяхнеобхідно переконатися шляхом прогону програми у тому, як позначається вибір коефіцієнта bта початкового наближення на процесі пошуку кореня. При зміні коефіцієнта bхарактер ітераційного процесу досліджуваної функції змінюється. Він стає спочатку двостороннім, та був зациклюється (рис.2.9). Масштаби по осях Xі Yрізні. Ще більше значення модуля b призводить до процесу, що розходиться.

Порівняння методів наближеного розв'язування рівнянь

Порівняння описаних вище методів чисельного рішеннярівнянь проводилося за допомогою програми, що дозволяє на екрані ПЕОМ спостерігати процес знаходження кореня в графічному вигляді. Процедури, що входять до цієї програми та реалізують порівнювані методи, наведено нижче (ПРОГРАМА 2.1).

Рис. 2.3-2.5, 2.8, 2.9 є копіями екрана ПЕОМ після закінчення ітераційного процесу.

Як досліджувану функцію у всіх випадках було взято квадратне рівняння x 2 -x-6 = 0, що має аналітичне рішення х 1 = -2 і х 2 = 3. Похибка та початкові наближення приймалися для всіх методів рівними. Результати пошуку кореня х= 3 представлені на малюнках, такі. Найбільш повільно сходиться метод дихотомії – 22 ітерації, найшвидший – метод простих ітерацій при b = -0.2 – 5 ітерацій. Тут немає суперечності із твердженням, що метод Ньютона є найшвидшим.

Похідна досліджуваної функції у точці х= 3 дорівнює -0.2, тобто розрахунок у разі вівся практично методом Ньютона з величиною похідної у точці кореня рівняння. При зміні коефіцієнта bшвидкість збіжності падає і процес, що поступово сходить, спочатку зациклюється, потім стає розбіжним.

Замінимо вихідне рівняння на еквівалентне і будуватимемо ітерації за правилом . Таким чином метод простої ітерації – це однокроковий ітераційний процес. Для того, щоб розпочати цей процес, необхідно знати початкове наближення . З'ясуємо умови збіжності методу та вибір початкового наближення.

Білет №29

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

Метод Зейделя (іноді званий методом Гаусса-Зейделя) є модифікацією методу простої ітерації, що полягає в тому, що при обчисленні чергового наближення x (k+1) (див. формули (1.13), (1.14)) його вже отримані компоненти x 1 ( k+1) , ...,x i - 1 (k+1) відразу ж використовуються для обчислення x i (k+1) .

У координатній формі запису метод Зейделя має вигляд:

X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k ) + d n
де x(0) – деяке початкове наближення до рішення.

Таким чином i-та компонента (k+1)-го наближення обчислюється за формулою

Умова закінчення ітераційного процесу Зейделя при досягненні точності в спрощеній формі має вигляд:

|| x(k+1) - x(k) || ≤ ε.

Білет №30

Метод прогонки

Для розв'язання систем A x = b з тридіагональною матрицею найчастіше застосовується метод прогонки, що є адаптацією методу Гауса до цього випадку.

Запишемо систему рівнянь

d 1 x 1 + e 1 x 2 = b 1
c 2 x 1 + d 2 x 2 + e 2 x 3 = b 2
c 3 x 2 + d 3 x 3 + e 3 x 4 = b 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c n x n-1 + d n x n = b n

у матричному вигляді: A x = b де

A=

Випишемо формули методу прогонки у порядку їх застосування.

1. Прямий хід методу прогонки (обчислення допоміжних величин):

2. Зворотній хідметоду прогонки (знаходження рішення):

Білет №31

Метод простих ітерацій

Суть методу простих ітерацій полягає у переході від рівняння

f(x)= 0 (*)

до еквівалентного рівняння

x=φ(x). (**)

Цей перехід можна здійснити різними способами, в залежності від виду f(x). Наприклад, можна покласти

φ(x) = x+bf(x),(***)

де b= const, у своїй коріння вихідного рівняння не изменятся.

Якщо відомо початкове наближення до кореня x 0, то нове наближення

x 1=φx(0),

тобто. загальна схема ітераційного процесу:

x k+1=φ(x k).(****)

Найбільш простий критерій закінчення процесу

|x k +1 -x k |<ε.

Критерій збіжностіметоду простих ітерацій:

якщо поблизу кореня | φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого x, то ітерації сходяться за будь-якого початкового наближення.

Досліджуємо вибір константи bз погляду забезпечення максимальної швидкості збіжності. Відповідно до критерію збіжності найбільша швидкість збіжності забезпечується при |? / (x) | = 0. При цьому, виходячи з (***), b = -1/f / (x),та ітераційна формула (****) переходить у x i = x i-1 -f(x i-1)/f/ (x i-1).-тобто. у формулу методу Ньютона. Таким чином, метод Ньютона є окремим випадком методу простих ітерацій, що забезпечує найвищу швидкість збіжності з усіх можливих варіантів вибору функції φ(x).

Білет №32

Метод Ньютона

Основна ідея методу полягає в наступному: задається початкове наближення поблизу ймовірного кореня, після чого будується дотична досліджуваної функції в точці наближення, для якої знаходиться перетин з віссю абсцис. Ця точка і береться як наступне наближення. І так далі, поки не буде досягнуто необхідної точності.

Нехай - певна на відрізку та диференційована на ньому речовиннозначна функція. Тоді формула ітеративного обчислення наближень може бути виведена таким чином:

де α - кут нахилу дотичної в точці.

Отже шуканий вираз має вигляд:

Білет №33

Метод золотого перерізу
Метод золотого перерізу дозволяє виключати інтервали, обчислюючи лише одне значення функції кожної ітерації. В результаті двох розглянутих значень функції визначається інтервал, який має використовуватись надалі. Цей інтервал міститиме одну з попередніх точок і наступну точку, що міститься симетрично їй. Точка ділить інтервал на дві частини так, що відношення цілого до більшої частини дорівнює відношенню більшої частини до меншої, тобто так званому «золотому перерізу».

Розподіл інтервалу на нерівні частини дозволяє знайти ще ефективніший метод. Обчислимо функцію на кінцях відрізка [ a,b] і покладемо a=x 1 , b=x 2 . Обчислимо також функцію у двох внутрішніх точках x 3 , x 4 . Порівняємо всі чотири значення функції та виберемо серед них найменше. Нехай, наприклад, найменшим виявилося f(x 3). Очевидно, що мінімум перебувати в одному з прилеглих до нього відрізків. Тому відрізок [ x 4 ,b] можна відкинути та залишити відрізок .

Перший крок зроблено. На відрізку знову треба вибрати дві внутрішні точки, обчисливши в них і на кінцях значення функції та зробити наступний крок. Але на попередньому етапі обчислень ми вже знайшли функцію на кінцях нового відрізка і в одній його внутрішній точці x 4 . Тому достатньо вибрати всередині ще одну точку x 5визначити у ній значення функції та провести необхідні порівняння. Це вчетверо зменшує обсяг обчислень однією етапі процесу. Як вигідно розміщувати точки? Щоразу залишок відрізок ділитися на три частини і потім відкидається один із крайніх відрізків.
Позначимо початковий інтервал невизначеності через D.

Так як у загальному випадку може бути відкинутий будь-який відрізок Х 1 ,Х 3або Х 4 ,Х 2то оберемо крапки Х 3і Х 4так, щоб довжини цих відрізків були однакові:

x 3 -x 1 =x 4 -x 2.

Після відкидання вийде новий інтервал невизначеності довжини D′.
Позначимо ставлення D/D′літерою φ:

тобто припустимо, де - наступний інтервал невизначеності. Але

по довжині дорівнює відрізку, відкинутому на попередньому етапі, тобто

Тому отримаємо:

.
Це призводить до рівняння або, що те саме
.

Позитивний корінь цього рівняння дає

.

Білет №34

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

p align="justify"> Метод простої ітерації, званий також методом послідовного наближення, - це математичний алгоритм знаходження значення невідомої величини шляхом поступового її уточнення. Суть цього у тому, що, як очевидно з назви, поступово висловлюючи з початкового наближення наступні, отримують дедалі більше уточнені результати. Цей метод використовується для пошуку значення змінної заданої функції, а також при вирішенні систем рівнянь, як лінійних, так і нелінійних.

Розглянемо, як цей метод реалізується під час вирішення СЛАУ. Метод простої ітерації має такий алгоритм:

1. Перевірка виконання умови збіжності у вихідній матриці. Теорема про збіжність: якщо вихідна матриця системи має діагональне переважання (тобто, у кожному рядку елементи головної діагоналі повинні бути більшими за модулем, ніж сума елементів побічних діагоналей за модулем), то метод простих ітерацій - схожий.

2. Матриця вихідної системи який завжди має діагональне переважання. У разі систему можна перетворити. Рівняння, задовольняють умові збіжності, залишають недоторканими, і з незадовольняючими становлять лінійні комбінації, тобто. множать, віднімають, складають рівняння між собою до отримання потрібного результату.

Якщо в отриманій системі на головній діагоналі знаходяться незручні коефіцієнти, то до обох частин такого рівняння додають доданки з i * x i, знаки яких повинні збігатися зі знаками діагональних елементів.

3. Перетворення отриманої системи до нормального вигляду:

x - =β - +α*x -

Це можна зробити безліччю способів, наприклад, так: з першого рівняння виразити х 1 через інші невідомі, з другого-х 2, з третього-х 3 і т.д. При цьому використовуємо формули:

α ij = -(a ij / a ii)

i = b i /a ii
Слід знову переконатися, що одержана система нормального вигляду відповідає умові збіжності:

∑ (j=1) |α ij |≤ 1, причому i= 1,2,...n

4. Починаємо застосовувати, власне, сам спосіб послідовних наближень.

x (0) - початкове наближення, виразимо через нього х (1), далі через х (1) виразимо х (2). Загальна формула в матричному вигляді виглядає так:

x(n) = β - +α*x (n-1)

Обчислюємо, доки не досягнемо необхідної точності:

max |x i (k)-x i (k+1) ≤ ε

Отже, давайте розберемо практично метод простої ітерації. Приклад:
Вирішити СЛАУ:

4,5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 з точністю ε=10 -3

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

Ми бачимо, що умовою збіжності задовольняє лише третє рівняння. Перше і друге перетворимо, до першого рівняння додамо друге:

7,6x1+0.6x2+2.4x3=3

З третього віднімемо перше:

2,7x1+4.2x2+1.2x3=2

Ми перетворили вихідну систему на рівноцінну:

7,6x1+0.6x2+2.4x3=3
-2,7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4

Тепер наведемо систему до нормального вигляду:

x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3 = 0.8511-0.383x1-0.5319x2

Перевіряємо збіжність ітераційного процесу:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383 + 0.5319 = 0.9149 ≤ 1, тобто. умова виконується.

0,3947
Початкове наближення х(0) = 0,4762
0,8511

Підставляємо дані значення рівняння нормального вигляду, отримуємо наступні значення:

0,08835
x(1) = 0,486793
0,446639

Підставляємо нові значення, отримуємо:

0,215243
x(2) = 0,405396
0,558336

Продовжуємо обчислення до того моменту, поки не наблизимося до значень, що задовольняють задану умову.

x(7) = 0,441091

Перевіримо правильність отриманих результатів:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0,1880+2.3*0,441-1.1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

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

Як бачимо, метод простої ітерації дає досить точні результати, проте на вирішення цього рівняння нам довелося витратити багато часу й зробити громіздкі обчислення.

Ітераційні методи

В ітераційних методах передбачається здійснення трьох наступних етапів: побудова для обчислення послідовних наближень ітераційного процесу, що сходить до точного рішення (тобто побудова послідовності векторів, що сходить до точного рішення) ; визначення критерію збіжності цього процесу, що дозволяє визначити момент досягнення необхідної точності; дослідження швидкості збіжності та оптимізації ітераційного процесу з метою зменшення кількості операцій, необхідних для досягнення необхідної точності.

Ітераційні методи дозволяють отримати рішення з заданою точністю, якщо доведена збіжність методу. Строго точного рішення ітераційні методи не дають, оскільки воно досягається як межа послідовності векторів. Прямий метод, взагалі кажучи, дає точне рішення, але через помилки округлення, що мають місце на будь-яких комп'ютерах, воно не може бути досягнуто, і a prioriнавіть важко оцінити, наскільки це рішення відрізняється від точного. У зв'язку із зазначеним ітераційні методи іноді дозволяють отримати рішення з більшою точністю, ніж прямі.

Розглянемо кілька ітераційних методів розв'язання лінійних рівнянь.

Метод простої ітерації

У методі простої ітерації система (2.1) лінійних рівнянь алгебри Ax = bнаводиться до еквівалентної системи виду

Рішення системи (2.9) і, отже, рішення вихідної системи (2.1) шукається як межа послідовності векторів при :

k = 0, 1, 2, ...,(2.10)

де - Початкове наближення для вектора рішення.

Достатня умова збіжності методу простої ітерації визначається наступною теоремою.

ТЕОРЕМА 1. Якщо будь-яка норма матриці , узгоджена з аналізованої нормою вектора , менше одиниці (), то послідовність у методі простої ітерації сходиться до точного рішення системи (2.9) зі швидкістю, не меншою швидкості геометричної прогресії зі знаменником за будь-якого початкового наближення .

ДОВЕДЕННЯ. Для доказу теореми введемо похибку. Віднімаючи із співвідношення рівність (2.10), отримуємо . Переходячи до норм, маємо

Зазначимо, що нерівність з попереднього виразу є умовою узгодженості норми матриці та вектора. Якщо , то за будь-якого векторі початкової похибки (чи інакше – за будь-якого початковому векторі ) норма похибки прагне нулю не повільніше геометричної прогресії зі знаменником .

Якщо як норма матриці вибрати норму або то для вирішення питання про збіжність методу простої ітерації можна скористатися наслідком теореми 1: метод простої ітерації сходиться, якщо для матриці виконується одна з наступних умов:

, i = 1,2, …, n,

j = 1, 2, …, n.(2.11)

Найпростішим та найпоширенішим способом приведення системи Ax = bдо виду (2.9), зручному для ітерацій, є виділення діагональних елементів, причому кожне i-ерівняння дозволяється щодо i-гоневідомого:

, i = 1, 2, …, n, (2.12)

та метод простої ітерації запишеться у вигляді

Матриця має вигляд

.

Елемент цієї матриці можна записати як де – символ Кронекера. У цьому випадку достатня умова збіжності методу простої ітерації може бути сформульована як умова переважання діагональних елементів матриці А, Що випливає з (2.11) та запису матриці , тобто.

i = 1, 2, …, n.

Ще раз підкреслимо, що розглянуті форми умови збіжності методу ітерації лише достатніми. Їх виконання гарантує збіжність методу, та їх невиконання у випадку означає, що метод простий ітерації розходиться. Необхідною та достатньою умовою збіжності методу простої ітерації є умова того, що ціла частина (де -максимальне за модулем власне значення матриці А); ця умова рідко використовується у практиці обчислень.

Перейдемо до питання оцінки похибки рішення. Цікаві два співвідношення оцінки похибки рішення: перше пов'язує норму похибки з нормою різниці двох послідовних наближень і може бути використане для оцінки похибки тільки в процесі обчислень; друге пов'язує норму похибки з нормами вектора початкового наближення та вектора вільного члена у системі (2.9). Необхідні співвідношення надаються наступними двома теоремами.

ТЕОРЕМА 2. Якщо будь-яка норма матриці , узгоджена з аналізованою нормою вектора х

. (2.13)

ДОВЕДЕННЯ. Віднімемо з рівності рівність (2.10):

Віднімаючи з обох частин значення наближення, перетворимо це співвідношення до виду

Перейшовши до норм, отримаємо

Оскільки за умовою теореми, то

Використовуючи співвідношення з якого випливає, що остаточно отримаємо:

ТЕОРЕМА 3. Якщо будь-яка норма матриця , узгоджена з аналізованої нормою вектора х, менше одиниці (), то має місце така оцінка похибки:

Зробимо два зауваження. По-перше, співвідношення (2.13) може бути записане у вигляді

що дозволяє отримати оцінку похибки за результатами двох перших ітерацій. По-перше, при використанні методу ітерацій як оцінку похибки обчислень іноді рекомендується використовувати норму різниці двох послідовних наближень. Зі співвідношень для похибки випливає, що у випадку це не так. Якщо норма близька до одиниці, то коефіцієнт може бути досить великим.

Похибки послідовних ітерацій пов'язані з співвідношенням

тобто. похибка змінюється на кроці лінійно. Кажуть, що метод має лінійну збіжністьчи перший порядок збіжності. Разом про те кількість ітерацій, необхідне досягнення необхідної точності, залежить від значення і початкового наближення .

Отже, на прикладі методу простої ітерації продемонстровано три етапи ітераційних методів: побудова послідовності векторів, що породжується формулою (1.10); визначення умови збіжності за теоремою 1 та оцінка швидкості збіжності за допомогою теорем 2 та 3.

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

У методі простої ітерації не використовується очевидна можливість поліпшення збіжності ітераційного процесу – негайне введення до уваги новообчислених компонент вектора . Ця можливість використовується в ітераційному методі Зейделя. Ітераційний процес для системи (2.9) виконується при цьому за співвідношенням

i = 1, 2, …, n (2.14)

або для системи (1.1)

Не вдаючись до подробиць, відзначимо, що метод ітерацій Зейделя часто дійсно призводить до більш швидкої збіжності, ніж метод простої ітерації. Однак можливі випадки, коли метод ітерацій Зейделя сходиться повільніше методу простої ітерації, і навіть випадки, коли метод простої ітерації сходиться, а метод ітерацій Зейделя розходиться.

Відмітимо, що метод Зейделя сходиться,якщо матриця Апозитивно визначена та симетрична.

Покажемо, що метод ітерацій Зейделя еквівалентний деякому методу простої ітерації зі спеціально побудованою матрицею і вектором у співвідношенні (2.10). Для цього запишемо систему (2.14) у вигляді де F-верхня трикутна матриця з коефіцієнтів матриці , а перепишемо систему у вигляді де E-одинична матриця. Матриця (Е-Н)- нижня трикутна матриця з діагональними елементами, рівними одиниці. Отже, визначник цієї матриці відмінний від нуля (рівний одиниці) і має зворотну матрицю . Тоді

Зіставляючи це співвідношення з рішенням (2.10), можемо зробити висновок, що дійсно метод ітерацій Зейделя еквівалентний методу простої ітерації в тому сенсі, що для встановлення умови та критерію збіжності методу ітерацій Зейделя можна скористатися теоремами, наведеними для методу простої ітерації, Ітераційний процес для системи (2.12) записують і більш загальної формі, саме