Ітераційні методи розв’язання СЛАР.

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

При великій кількості рівнянь прямі методи розв’язання СЛАР (за винятком методу прогонки) стають важко реалізованими на ЕОМ насамперед через складність зберігання й обробки матриць великої розмірності. У той же час характерною рисою багатьох СЛАР, що виникають у прикладних задачах є розрідженість матриць. Число ненульових елементів таких матриць є малим у порівнянні з їхньою розмірністю. Для розв’язання СЛАР з розрідженими матрицями краще використати ітераційні методи.

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

Розглянемо СЛАР (3.1) з невиродженою матрицею (det A ≠ 0). Розв’яжемо систему (3.1) щодо невідомих при ненульових діагональних елементах a_ii≠ 0, i= 1…n (якщо який-небудь коефіцієнт на головній діагоналі дорівнює нулю, досить відповідне рівняння поміняти місцями з будь-яким іншим рівнянням). Одержимо систему у вигляді

(3.26)

або у векторно-матричній формі X=β+αX.

Тут    .

Вирази для компонентів вектора β та матриці α еквівалентної системи:

(3.27)

При такому способі приведення вихідної СЛАР до еквівалентного вигляду метод простих ітерацій ще називають методом Якобі.

За нульове наближення X ⁽⁰⁾ вектора невідомих візьмемо вектор правих частин X ⁽⁰⁾=β або (x₁^(0),x₂⁽⁰⁾,…,x_n⁽⁰⁾)^*= (β₁,β₂,…,β_n)*. Тоді метод простих ітерацій набере вигляду

                      (3.28)

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

Визначення збіжності ітераційного процесу можна знайти в 2.3-2.5. З огляду на сформульовані там теореми, має місце достатня умова збіжності методу простих ітерацій для СЛАР.

Теорема. Метод простих ітерацій (3.28) збігається до єдиного розв’язку СЛАР(3.26)(а отже, й до розв’язку вихідної СЛАР (3.1)) при будь-якому початковому наближенні Х⁽⁰⁾, якщо яка-небудь норма матриці  еквівалентної системи менше одиниці ║ ║‹1.

Якщо ж розглядати СЛАР у вигляді (3.1), то достатньою умовою збіжності є діагональна перевага матриці А, тобто  (для кожного рядка матриці А модулі елементів, що розміщені на головній діагоналі, більше суми модулів недіагональних елементів). Очевидно, що в цьому випадку  менше одиниці й, отже, ітераційний процес (3.28) збігається.

При виконанні достатньої умови збіжності оцінка похибки розв’язку на k – й ітерації дається виразом

 ,    (3.29)

де X * - точний розв’язок СЛАР.

Процес ітерацій зупиняється при виконанні умови e ^(к) £ e, де e - задана точність розв’язку.

Беручи до уваги, що з (3.29) випливає нерівність

,

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

,

 звідки отримаємо апріорну оцінку числа ітерацій k при

.

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

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

Приклад.  Методом простих ітерацій розв’язати СЛАР з точністю ε =0,01.

Розв’язання. Приведемо СЛАР до еквівалентного вигляду

або X=β+αX, де

Визначимо . Отже, достатня умова збіжності методу простої ітерації виконана.

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

Таким чином, обчислювальний процес завершений за 4 ітерації. Відзначимо, що точний розв’язок СЛАР в цьому випадку відомий Х *=(1,1,1)^*. Звідси випливає, що задану точність ε=0,01 задовольняло наближення, отримане вже на третій ітерації.

Відзначимо, що апріорна оцінка необхідної кількості ітерацій дає k+ 1≥(-2+lg0,6-lg1,4)/lg0,4=5,95, тобто для досягнення точності ε=0,01, відповідно до апріорної оцінки, необхідно зробити не менше п'яти ітерацій, що ілюструє характерну для апріорної оцінки тенденцію до завищення числа ітерацій.