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