МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Лабораторна робота № 3 з курсу " Комп’ютерні методи дослідження інформаційних процесів та систем " Львів – 2007 Мета роботи – ознайомлення з ітераційними методами розв’язування систем лінійних алгебраїчних рівнянь. 1.Короткі теоретичні відомості. Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь
До ітераційних методів належать: метод простої ітерації, метод Зейделя, метод верхньої релаксації та інші. Метод простої ітерації. Нехай дано лінійну систему
(1) Розглянемо матриці


Тоді систему (1) можна записати у вигляді матричного рівняння
(2) Будемо вважати, що діагональні коефіцієнти
(і = 1, 2,…, n). Розв’яжемо перше рівняння системи (1) відносно
, друге відносно
і т.д. Тоді одержимо еквівалентну систему
(3) де

, при
;
, при
;
;
;
Іноді кажуть, що система (3) зведена до нормального вигляду. Введемо матриці ( та (

Систему (3) запишемо у вигляді
(4) Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів
. Далі послідовно будуємо матриці-стовпці:
– перше наближення
– друге наближення і т.д. Будь-яке (k + 1)-е наближення обчислюється за формулою:
, (k = 0, 1, 2, …) (5) В розгорнутому вигляді
. Якщо послідовність наближень
має границю
, (6) то ця границя є розв’язком системи (3). На практиці ітераційний процес припиняють, коли
, де ( – гранична абсолютна похибка. Приклад. Розв’язати систему методом простої ітерації:
. Зведемо систему до нормального вигляду
(7) або в матричній формі
(8) За нульові наближення коренів системи приймаємо
. Підставляємо ці значення в праві частини рівняння (7). Одержимо перші наближення коренів
Далі знаходимо другі і треті наближення коренів

Таким чином,
, (
) – метод простої ітерації. Умови збіжності ітераційного процесу Нехай задано зведена до нормального вигляду система лінійних рівнянь
Умова збіжності: якщо сума модулів елементів рядків або модулів елементів стовпців матриці α менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень. Для системи
або
, де
– сума модулів по стовпцях
Аналогічно можна було б перевірити виконання умови збіжності, беручи суми модулів елементів рядків. Наведена вище умова являється достатньою, але не необхідною. Це означає, що якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним. Для системи лінійних рівнянь, заданих у вигляді
, метод простої ітерації збігається, якщо модулі діагональних коефіцієнтів
для кожного рівняння системи більші, ніж суми модулів всієї решти коефіцієнтів (не враховуючи вільних членів). Приклад:
(9)
(10)
(11) Дещо простішій програмній реалізації піддається наступна формула методу простих ітерацій:
(13) Звідки вона береться? Відомо, що при зведенні системи
до вигляду
кожне
представляється у вигляді
або

. Якщо зняти обмеження j ( i, то цю формулу можна переписати у такому вигляді
. Звідси випливає, що
. 2.ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ Розв’язати систему лінійних алгебраїчних рівнянь методами простої ітерації або Зейделя.

,


3. Блок-схема алгоритму програми. 4. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення. 5. Остаточно відлагоджений текст програми.