ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ
АЛГЕБРАЇЧНИХ РІВНЯНЬ.
Розглядається система лінійних алгебраїчних рівнянь
(1)
де - квадратна матриця вимірності
- вектор - стовпець правих частин системи;
- вектор - стовпець невідомих.
Ідея найпростіших ітераційних методів розв’язання системи (1) полягає
у наступному. За допомогою еквівалентних перетворень система (1) зводиться
до системи вигляду
(2)
де -квадратна матріця
-відомий вектор.
А потім задається деяке початкове наближення (наприклад, у
якості береться вектор , або деякий розв’язок системи (1),
який одержується іншим методом з деякою похибкою). Інші наближення
послідовно знаходяться за рекурентною формулою
(3)
доки на деякому кроці не буде досягнута задана точність
обчислення значення невідомого вектору .
Виникає питання, за яких умов на послідовність
збігається (у певному розумінні) до точного розв’язку .
Не зупиняючись на подробицях (дивись спецкурс ‘Додаткові розділи
чисельного аналізу’), дамо деякі достатні умови, за яких
або
або
Швидкість збіжності оцінюється нерівністю
де - відстань між векторами та , що може бути заданою:
коли виконується умова (4);
коли виконується умова (5);
коли виконується умова (6).
Задаючи потрібну точність можна з рівності
одержати необхідну кількість ітерацій , щоб досягти задане .
Наведені умови є достатніми для збіжності методу ітерацій, але аж
ніяк не необхідними. Необхідні і достатні умови збіжності методу ітерацій
дає наступна теорема, яку сформулюємо без доведення.
ТЕОРЕМА: Нехай система (2) має єдиний розв’язок. Послідовні
наближення (3) збігаються до розв’язку системи (2) за довільного
початкового наближення тоді та й тільки тоді, коли усі власні
значення матриці за модулем менше одиниці.
Повернемось зараз до способів приведення (1) до форми (2). Запишемо
(1) у розгорнутій формі
Якщо для усіх , то можна (7) зобразити
у вигляді
Звідси два найпростіших ітераційних метода.
Метод Якобі, який задається рекурентним співвідношенням:
Метод Зейделя, де вже знайдені компоненти беруться у правій частині
співвідношення з (n+1)-го наближення, а інші- з n-го наближення:
Можна дати матричну форму методів Якобі і Зейделя.
Нехай матрицю А наведено у вигляді:
де -нижня трикутна матриця з нульовою головною діагоналлю;
D - діагональна матриця з на головній діагоналі;
-верхня трикутна матриця з нульовою головною діагоналлю.
За припущенням існує
Тоді зображенню у формі (8) відповідає
або
Таким чином, методу Якобі відповідає ітераційна процедура
Методу Зейделя відповідає
Використовуючи сформульовані раніш достатні умови збіжності ,
самостійно переконайтесь, що достатніми умовами збіжності методу Якобі є
або
тобто діагональне переваження матриці А.
Можна довести, що за вказаних умов збігається і метод Зейделя.
Покажемо, що до форми (2), що задовольняє умовам збіжності, може бути
зведена довільна система (1) з
Дійсно,візьмемо матрицю де -матриця з достатньо малими
за модулем елементами. Множачи (1) зліва на С маємо
тобто одержали форму (2) з
За рахунок вибору достатньо малих можна задовольнити умовам
збіжності.
Процес ітерації, що збігається, володіє властивістю стійкості, тобто
окрема похибка у обчисленнях не позначається на кінцевому результаті, тому
що хибне наближення можна розглядати як новий початковий вектор.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
