Математичне обгрунтування алгоритму

Постанова задачі

Методом  Зейделя  розв’язати систему лінійних  алгебраїчних рівнянь  вигляду АХ=В із точністю до 0,0001. Встановити вплив похибки вхідних даних на результат та дослідити систему на стійкість

[pic 1]

Математичне обгрунтування алгоритму

Метод простої ітерації  повільний . Тому використаємо  метод Зейделя. Метод Зейделя являється  модифікацією метода простої ітерації.

Нехай ми маємо систему :
[pic 2]
и відомо початкове наближення [pic 3]. Головна  ідея заключається в тому, що при вирішенні (k+1) - го наближення невідомої xi враховується вже обчислений раніше (k+1) - наближення невідомих x1, x2, .., xi-1.. Система має вигляд -

[pic 4]

Виберемо початкове наближення корнів [pic 5]. Далі, припускаючи , що k-е наближення [pic 6]корнів відомі, згідно Зейделю будемо будувати (k + 1)-е наближення корнів по формулі.

В цій системи бачимо, що Хk+1=β+BХk+1 +CХk , де В -  нижня трикутна матриця з діагональними елементами, що дорівнюють нулю, а C - верхня трикутна матриця з діагональними елементами, відмінними від нуля. Перетворимо систему Ax = B до вигляду x = Bx + D, тоді система буде мати вигляд:

, де[pic 7]

[pic 8]

Треба перевірити достатню умову збіжності ітераційного процесу для методу Зейделя.

Використовуючи метод діагональної переваги. Модуль елемента головної діагоналі повинен бути більшим за суму модулів інших елементів цього рядка, по формулі

 [pic 9].

Перший ряд:

|-0.82| > |-0.34|  +  |-0.12| + |0.15| ;  |-0.82| > 0.61  - виконується

Другий ряд:

|-0.77| > |0.11|  +  |-0.45| + |0.32| ;  |-0.77| < 0.88  -  не виконується

Третій ряд:

|-0.86| > |0.05|  +  |0.18| + |-0.12| ;  |-0.86| > 0.35  - виконується

Четвертій ряд:

|-1.00| > |0.08|  +  |0.06| + |0.12| ;  |-1.00| > 0.36  - виконується

Умова збіжності не виконується.

Умовою закінчення ітераційного процесу метода Зейделя є досягнення точності:

[pic 10]

де k – номер наближення, x – вектор наближення.

Почнемо розв’язувати систему:

Дізнаємося ранг матриць –

[pic 11]

Те що ранги однакові це свідчить  про те що ми маємо один розв’язок системи або безліч.

Розв’яжемо СЛАР:

[pic 12]

Далі треба зробити перевірку СЛАР на стійкість.

Стійкість або нестійкість положення рівноваги визначається знаками дійсних частин власних значень матриці A. Щоб знайти власні значення
λ, необхідно вирішити характеристичне рівняння:

[pic 13]

яке зводиться до алгебраїчного рівняння n-го ступеня:

[pic 14]

Я використав функцію eigenvalues() в MAPLE.

[pic 15]

Перевіримо:

λ1 = √((-1.077)2 + (0.141)2) = 1.086 > 1 умова не виконується.

λ2 = √((-1.077)2 + (-0.141)2) = 1.086 > 1 умова не виконується.

λ3 = √((-0.648)2 + (0.118)2) = 0.659 < 1 умова  виконується.

λ4 = √((-0.648)2 + (-0.117)2) = 0.658 < 1 умова  виконується.

СЛАР стійка але асимптотично не стійка.

Число обумовленості - величина, що характеризує точність розв'язку, отримано чисельним методом. Якщо точність велика, то дані добре обумовлені, інакше вони погано обумовлені.