2 Умови збіжності ітераційних методів розв’язання рівнянь і систем

2.1 Системи лінійних алгебраїчних рівнянь

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

Розглянемо систему лінійних алгебраїчних рівнянь

, , (2.1)

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

, (2.2)

де - квадратна матриця розмірності , ;

- вектор-стовпець правих частин системи (2.1), ;

- вектор-стовпець невідомих.

Ідея самих простих ітераційних методів розв’язання системи (2.2) полягає в наступному. За допомогою еквівалентних перетворень система (2.2) зводиться до системи вигляду

, (2.3)

де - квадратна матриця ; - відомий вектор-стовпець.

Потім задається деяке початкове наближення (наприклад, в якості береться вектор , або нульовий вектор , або деяке наближене розв’язання системи (2.3), отримане будь-яким методом). Інші наближення послідовно знаходяться за рекурентною формулою

, , (2.4)

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

Виникає питання, при яких умовах на матрицю послідовність { } збігається до точного розв’язку . Достатні умови збіжності { } можна отримати із принципу стискаючих відображень.

В даному випадку маємо відображення -вимірного простору векторів в себе, яке задається системою лінійних рівнянь

, , (2.5)

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

Розглянемо три варіанти метричних просторів, повнота яких була встановлена в розділі 1.

1. Простір , тобто метрика має вигляд

.

Очевидне наступне перетворення нерівностей

.

Звідси умова стискаючості відображення

<1 або <1. (2.6)

2. Простір , тобто .

Очевидно,

.

Таким чином – стискюче відображення, якщо

<1 або <1. (2.7)

3. Простір з метрикою

.

На основі нерівності Коші-Буняковського маємо

.

Таким чином умова стискаючості відображення

<1. (2.8)

Резюмуючи сказане, можна стверджувати, що, якщо виконано хоча б одну з умов (2.6)-(2.8), то послідовні наближення (2.4) збігаються до точного розв’язку системи (2.3) у відповідному метричному просторі (по відповідній нормі), а, на основі наслідків із теореми 1.4, і в двох інших метричних просторах (по всім іншим нормам).

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

Теорема 2.1. Нехай система (2.3) має єдине розв’язок. Послідовні наближення (2.4) збігаються до розв’язку системи (2.3) при будь-якому початковому наближенні тоді і лише тоді, коли всі власні значення матриці по модулю менші одиниці.

Повернемося тепер до вихідної системи лінійних алгебраїчних рівнянь (2.1) або (2.2).

Існують різні способи приведення (2.2) до форми (2.3). Розглянемо найпростіший з них, який зводить до ітераційного методу Якобі⁶ розв’язання системи лінійних алгебраїчних рівнянь.

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

, . (2.9)

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

, .

Кожне наступне наближення знаходиться за формулами

, , . (2.10)

Для забезпечення збіжності необхідно значне домінування діагональних елементів матриці над іншими елементами. Так, нерівності (2.6)-(2.8) будуть виконані, якщо для елементів матриці відповідно виконуються наступні нерівності

, _,

1, ,

<1

(переконайтесь в цьому самостійно).

Системі (2.9) можна надати матричну форму виду (2.3), якщо представити матрицю у вигляді суми

, (2.11)

де - нижня трикутна матриця з нульовою головною діагоналлю;

- діагональна матриця з елементами , , на головній діагоналі;

- верхня трикутна матриця з нульовою головною діагоналлю.

В припущенні , , існує , яка також являється діагональною з елементами на головній діагоналі. Тоді (2.9) в матричній формі приймає вигляд

або

.

Рекурентне відношення (2.10) в матричній формі має вигляд

, .

Таким чином метод Якобі еквівалентний простій ітерації з матрицею і вектором .

Популярний також ітераційний метод Зейделя⁷, який полягає в наступному. Аналогічно методу Якобі, система (2.1) зводиться до вигляду (2.9) і вибирається деяке початкове наближення . Однак рекурентне відношення для будується по іншому.

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

. (2.12)

Використовуючи розкладення матриці у вигляді (2.11) відношенню (2.12) можна надати наступну матричну форму

звідки

,

,

і остаточно

.

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

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

Теорема 2.2 Якщо матриця симетрична і додатньо визначена, то метод Зейделя збігається.

Доведення Перш за все відмітимо, що із симетричності матриці слідує . Тепер, у відповідності з теоремою 2.1, необхідно лише перевірити, що при виконанні умов всі власні значення матриці

по модулю менше одиниці.

Нехай і - два деяких власних значення цієї матриці, а і - відповідні їм власні вектори. Тоді можна записати:

звідки

Розглянемо скалярні добутки і .

У відповідності до (2.13) вони представляються у вигляді

_(2.14)

Використовуючи властивості скалярного добутку⁸, можна отримати (перевірте безпосередньо):

,

,

(лінія означає число, комплексно-спряжене даному).

Тому другу із рівностей (2.14) можна переписати у вигляді

або

_(2.15)

Розв’язуючі (2.15) і першу з рівностей (2.14) відносно і , отримаємо:

Тоді

Покладаючи, що тут , знаходимо:

.

Звідки

_(2.16)

Оскільки матриця додатньо визначена, то для будь-якого квадратична форма і всі діагональні елементи матриці додатні. Тому

Тепер права частина (2.16) може бути лише невід’ємною, причому рівність нулю можлива лише у випадку, коли 1. Покажемо, що 1 не являється власним значенням матриці . Дійсно, якби існував такий ненульовий вектор , що

то ми мали б

або

а ця рівність можлива лише при , так як існує обернена матриця .

Значить права частина (2.16) може бути лише додатньою, а, відповідно, і , тобто для всіх власних значень матриці . Теорему доведено. 

Метод послідовних наближень можна застосовувати і для знаходження обернених матриць. Розглянемо один із алгоритмів уточнення оберненої матриці до матриці , отриманої на попередньому етапі будь-яким способом (наприклад, методом Гаусса).

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

_(2.17)

менше одиниці, . Створюємо тоді послідовності

При цьому

(2.18)

Маємо, , тобто матриця дуже швидко прямує до нульової матриці. Оцінимо норму різниці . Маємо (враховуючи (2.17) і (2.18)): (2.19)

Таким чином, матриця швидко збігається до матриці .