prosta iterac(stud)

Метод простої ітерації.
Нехай дано лінійну систему
13 EMBED Equation.3 1415 (1)
Розглянемо матриці
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
Тоді систему (1) можна записати у вигляді матричного рівняння
13 EMBED Equation.3 1415 (2)
Будемо вважати, що діагональні коефіцієнти 13 EMBED Equation.3 1415 (і = 1, 2,, n).
Розв’яжимо перше рівняння системи (1) відносно х1, друге відносно х2 і т.д. Тоді одержимо еквівалентну систему
13 EMBED Equation.3 1415 , (3)
де 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415, при i
· j ; 13 EMBED Equation.3 1415, при i = j ;
13 EMBED Equation.3 1415; aii
· 0 ; 13 EMBED Equation.3 1415
Іноді кажуть, що система (3) зведена до нормального вигляду.
Введемо матриці ( та (
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
Систему (3) запишемо у вигляді
13 EMBED Equation.3 1415 (4)
Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів х(0) =
·. Далі послідовно будуємо матриці-стовпці:


13 EMBED Equation.3 1415 – перше наближення
13 EMBED Equation.3 1415 – друге наближення і т.д.
Будь-яке (k + 1)-е наближення обчислюється за формулою:
13 EMBED Equation.3 141513 EMBED Equation.3 1415, (k = 0, 1, 2, ) (5)
В розгорнутому вигляді 13 EMBED Equation.3 1415.
Якщо послідовність наближень х(0), х(1), , хk має границю
13 EMBED Equation.3 1415, (6)
то ця границя є розв’язком системи (3).
На практиці ітераційний процес припиняють, коли 13 EMBED Equation.3 1415, де ( – гранична абсолютна похибка.
Приклад. Розв’язати систему методом простої ітерації:
13 EMBED Equation.3 1415 (7)
Зведемо систему до нормального вигляду
13 EMBED Equation.3 1415 , (8)
або в матричній формі
13 EMBED Equation.3 1415 (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.
Таким чином , 13 EMBED Equation.3 1415 , (13 EMBED Equation.3 1415 ) – метод простої ітерації.
Умови збіжності ітераційного процесу
Нехай задана зведена до нормального вигляду система лінійних рівнянь
13 EMBED Equation.3 1415
Умова збіжності : якщо сума модулів елементів рядків або модулів елементів стовпців матриці
· менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень.
Для системи
13 EMBED Equation.3 1415 або 13 EMBED Equation.3 1415,
де 13 EMBED Equation.3 1415
– сума модулів по стовпцях
13 EMBED Equation.3 1415
Аналогічно можна було б перевірити виконання умови збіжності, беручи суми модулів елементів рядків.
Наведена вище умова являється достатньою, але не необхідною. Це означає, що якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним.
Для системи лінійних рівнянь, заданих у вигляді
А*Х = b,
метод простої ітерації збігається, якщо модулі діагональних коефіцієнтів аіі для кожного рівняння системи більші, ніж суми модулів всієї решти коефіцієнтів (не враховуючи вільних членів).
Приклад: 13 EMBED Equation.3 1415 (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 EMBED Equation.3 1415 (13)
Звідки вона береться? Відомо, що при зведенні системи А*x = b до вигляду 13 EMBED Equation.3 1415 кожне хі(k + 1) представляється у вигляді
13 EMBED Equation.3 1415 або
13 EMBED Equation.3 1415 (аіі ( 0).
Якщо зняти обмеження j ( i, то цю формулу можна переписати у такому вигляді
13 EMBED Equation.3 1415 .
Звідси випливає, що
13 EMBED Equation.3 1415.
Інший варіант одержання рівняння (13) такий:
Маємо для кожного і системи (1)
13 EMBED Equation.3 1415, або 13 EMBED Equation.3 1415;
додамо в ліву і праву частину по аі хі
13 EMBED Equation.3 1415
Звідси, 13 EMBED Equation.3 1415.

Метод Зейделя
Є система лінійних алгебраїчних рівнянь, що зведена до нормального вигляду
13 EMBED Equation.3 1415.

Тоді за методом Зейделя, вибираючи вектор початкових наближень
13 EMBED Equation.3 1415
(як правило, це стовпець вільних членів 13 EMBED Equation.3 1415 ), уточнення значень невідомих проводять наступним чином:
1) перше наближення:

13 EMBED Equation.3 1415

2) k + 1 наближення
13 EMBED Equation.3 1415
k = 0, 1, 2, .
Таким чином ітераційний процес подібний до методу простих ітерацій, однак уточнені значення хі(k+1) одразу ж підставляються в наступні рівняння:
13 EMBED Equation.3 1415 – метод Зейделя.

Іншими словами, метод Зейделя відрізняється від методу простої ітерації тим, що при обчисленні хі(k+1) на “k + 1”-му кроці враховуються значення х1(k+1), х2(k+1), хі-1(k+1), обчислені на цьому самому кроці.
Слід сподіватись, що ітерації за методом Зейделя дадуть при тому ж числі кроків більш точні результати, ніж за методом простої ітерації. Або така ж точність буде досягнута за менше число кроків, оскільки чергові значення невідомих визначаються тут більш точно ітераційний процес припиняється.
Якщо візьмемо систему
13 EMBED Equation.3 1415 ,
для якої точний розв’язок
13 EMBED Equation.3 1415
Обчислення проведемо згідно формул:
13 EMBED Equation.3 1415 .
За початкове наближення вибираємо вектор
13 EMBED Equation.3 1415
Результати обчислень наведемо в таблиці:
Ітерації
Метод простої інтерації
Метод Зейделя


х1
х2
х3
х1
х2
х3

0
0
0
0
0
0
0

1
2
3
4
5
6
1,0000
1,2750
1,1287
1,0187
0,9882
0,99105
1,5000
1,2000
1,0342
0,9922
0,98373
0,99547
0,4000
0,7600
0,9590
1,0394
1,0195
1,0056
1,0000
1,0500
0,9896
1,0010
1,0000
1,3333
0,9473
1,0050
0,9999
1,0000
1,1333
0,9889
0,9999
1,0000
1,0000

Достатні умови збіжності ітераційного методу Зейделя
13 EMBED Equation.3 1415 для всіх 13 EMBED Equation.3 1415
і якщо хоча б для одного і ця нерівність строга
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415.
Для системи (n = 3)
13 EMBED Equation.3 1415 корені 13 EMBED Equation.3 1415
при ( = 1(10–6
метод простої ітерації з попередньою нормалізацією системи дає значення коренів при числі ітерацій m = 18,
а при ( = 1(10–8 m = 23.
Для цієї ж системи метод Зейделя з попередньою нормалізацією дає такі результати:
1) ( = 1(10–6 m = 8;
2) ( = 1(10–8 m = 11.
Для n = 4
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
(з попередньою нормалізацію системи)
( = 1(10–8 метод простої ітерації m = 24;
( = 1(10–8 метод Зейделя m = 14.




Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 18467786
    Размер файла: 176 kB Загрузок: 0

Добавить комментарий