Метод простої ітерації. Нехай дано лінійну систему (1) Розглянемо матриці
Тоді систему (1) можна записати у вигляді матричного рівняння (2) Будемо вважати, що діагональні коефіцієнти (і = 1, 2,…, n). Розв’яжимо перше рівняння системи (1) відносно х1, друге відносно х2 і т.д. Тоді одержимо еквівалентну систему , (3) де , при i ? j ; , при i = j ; ; aii ? 0 ; Іноді кажуть, що система (3) зведена до нормального вигляду. Введемо матриці ( та (
Систему (3) запишемо у вигляді (4) Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів х(0) = ?. Далі послідовно будуємо матриці-стовпці: – перше наближення – друге наближення і т.д. Будь-яке (k + 1)-е наближення обчислюється за формулою: , (k = 0, 1, 2, …) (5) В розгорнутому вигляді . Якщо послідовність наближень х(0), х(1), … , хk має границю , (6) то ця границя є розв’язком системи (3). На практиці ітераційний процес припиняють, коли , де ( – гранична абсолютна похибка. Приклад. Розв’язати систему методом простої ітерації: (7) Зведемо систему до нормального вигляду , (8) або в матричній формі (9) За нульові наближення коренів системи приймаємо х1(0) = 2; х2(0) = 3; х3(0) = 5. Підставляємо ці значення в праві частини рівняння (8). Одержимо перші наближення коренів х1(1) = 2 – 0,06*3 + 0,02*5 = 1,92; х2(1) = 3 – 0,03*2 + 0,05*5 = 3,19; х3(1) = 5 – 0,01*2 + 0,02*3 = 5,04. Далі знаходимо другі і треті наближення коренів х1(2) = 1,9094; х2(2) = 3,1944; х3(2) = 5,0446, х1(3) = 1,9023; х2(3) = 3,19495; х3(3) = 5,04485. Таким чином , , ( ) – метод простої ітерації. Умови збіжності ітераційного процесу Нехай задана зведена до нормального вигляду система лінійних рівнянь
Умова збіжності : якщо сума модулів елементів рядків або модулів елементів стовпців матриці ? менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень. Для системи або , де – сума модулів по стовпцях
Аналогічно можна було б перевірити виконання умови збіжності, беручи суми модулів елементів рядків. Наведена вище умова являється достатньою, але не необхідною. Це означає, що якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним. Для системи лінійних рівнянь, заданих у вигляді А*Х = b, метод простої ітерації збігається, якщо модулі діагональних коефіцієнтів аіі для кожного рівняння системи більші, ніж суми модулів всієї решти коефіцієнтів (не враховуючи вільних членів). Приклад: (10) 4х1 – х2 – 0,2х3 = 1 – 0,4х1 + 2х2 – 0,3х3 = 0,8 (11) 0,3х1+ 0,6х2 – 5х3 = 2 4 >( 1( + (0,2( 2 >(0,4( + (0,3( 5 >(0,3( + (0,6( Якщо система (1) така, що умова (10) не виконується, то за допомогою спеціальних перетворень можна домогтися їх виконання. Наприклад, 5х1+ х2 – 2х3 + х4 = 0, 2х1 + х2 – х3 + 6х4 = – 6, (12) х1 + х2 – 3х3 + х4 = – 6, х1 + 2х2 + х3 + х4 = 2 Умова (10) не виконується для (2), (3) та (4) рівнянь. Залишимо перше рівняння на місці, друге рівняння системи (12) переставимо на місце четвертого рівняння нової системи, для якого буде виконуватися умова (10). Щоб визначити: друге рівняння нової системи, множимо третє і четверте рівняння (12) відповідно на (– 1) та (– 3) і додаємо до другого рівняння системи (12). Одержуємо: – 2х1 – 6х2 – х3 + 2х4 = –6; третє рівняння нової системи: від третього рівняння (12) віднімаємо четверте. Матимемо систему: 5х1 + х2 – 2х3 + х4 = 0, – 2х1 – 6х2 – х3 + 2х4 = – 6, (12) – х2 – 4х3 = – 8, 2х1 + х2 – х3 + 6х4 = – 6, коефіцієнти якої задовольняють умови (10). Дещо простішій програмні реалізації піддається наступна формула методу простих ітерацій: (13) Звідки вона береться? Відомо, що при зведенні системи А*x = b до вигляду кожне хі(k + 1) представляється у вигляді або (аіі ( 0). Якщо зняти обмеження j ( i, то цю формулу можна переписати у такому вигляді . Звідси випливає, що . Інший варіант одержання рівняння (13) такий: Маємо для кожного і системи (1) , або ; додамо в ліву і праву частину по аі хі
Звідси, . Метод Зейделя Є система лінійних алгебраїчних рівнянь, що зведена до нормального вигляду . Тоді за методом Зейделя, вибираючи вектор початкових наближень
(як правило, це стовпець вільних членів ), уточнення значень невідомих проводять наступним чином: 1) перше наближення:
2) k + 1 наближення
k = 0, 1, 2, … . Таким чином ітераційний процес подібний до методу простих ітерацій, однак уточнені значення хі(k+1) одразу ж підставляються в наступні рівняння: – метод Зейделя. Іншими словами, метод Зейделя відрізняється від методу простої ітерації тим, що при обчисленні хі(k+1) на “k + 1”-му кроці враховуються значення х1(k+1), х2(k+1), хі-1(k+1), обчислені на цьому самому кроці. Слід сподіватись, що ітерації за методом Зейделя дадуть при тому ж числі кроків більш точні результати, ніж за методом простої ітерації. Або така ж точність буде досягнута за менше число кроків, оскільки чергові значення невідомих визначаються тут більш точно ітераційний процес припиняється. Якщо візьмемо систему , для якої точний розв’язок
Обчислення проведемо згідно формул: . За початкове наближення вибираємо вектор
Результати обчислень наведемо в таблиці: Ітерації Метод простої інтерації Метод Зейделя
Достатні умови збіжності ітераційного методу Зейделя для всіх і якщо хоча б для одного і ця нерівність строга . Для системи (n = 3) корені при ( = 1(10–6 метод простої ітерації з попередньою нормалізацією системи дає значення коренів при числі ітерацій m = 18, а при ( = 1(10–8 m = 23. Для цієї ж системи метод Зейделя з попередньою нормалізацією дає такі результати: 1) ( = 1(10–6 m = 8; 2) ( = 1(10–8 m = 11. Для n = 4
(з попередньою нормалізацію системи) ( = 1(10–8 метод простої ітерації m = 24; ( = 1(10–8 метод Зейделя m = 14.
