ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ. Розглядається система лінійних алгебраїчних рівнянь (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