Лабораторна робота №6. Рішення систем лінійних алгебраїчних рівнянь методом Зейделя

1. Мета роботи

Освоєння методу рішення систем лінійних алгебраїчних рівнянь. Вивчення та використання прикладних програм із бібліотеки програм ХТФ ОНПУ.

2. Теоретичні відомості

2.1. Метод простої ітерації

При великому числі невідомих лінійної системи схема метода Гауса, яка дає вірне рішення, робиться дуже громіздкою. У цьому випадку для знаходження коренів системи іноді краще користуватися приближеними обчислювальними методами – ітераційними. Привабливим у ітераційних методах є їх властивість самовиправлення та простота реалізації на ЕОМ.

Хай дана система лінійних алгебраїчних рівнянь.

A X = В(2.3)

з неособливою матрицею. Для того, щоб використати до неї метод ітерацій, необхідно довести її до вигляду

Х = С X + f(2.4)

де С– деяка матриця, аf– вектор-стовпець.

Ітераційний процес на початку обчислювання потребує завдання навчальних умов. Виходячи з довільного вектора Х

будуємо ітераційний процес:

X^(k+1) = С  X ^(k) + f, (k=0,1,2,....).(2.5)

Зробивши ітерації, отримаємо послідовність векторів Х⁽¹⁾, Х⁽²⁾, Х⁽³⁾,..., Х^(k).

Якщо послідовність приближення має границю, то ця границя є рішенням системи (2.3)

= C X^(к) + f(2.6)

Процес ітерації закінчується, коли |X^(к+1) – X^(к)| <, де– задана точність рішення.

Процес ітерації (2.5) добре збігається (тобто число приближень, необхідне для отримання коренів системи (2.3) із заданою точністю небагато), якщо елементи матриці Амалі по абсолютній величині. Іншими словами для успішного використання методу ітерацій модулі діагональних коефіцієнтів системи (2.3) повинні бути більш суми модулів останніх коефіцієнтів рівняння (вільні члені не враховується). Ця умова являєтьсяумовою сходження.

Відмітимо одну з важливих особливостей методу ітерацій. Ітераційний процес, що збігається, має властивості самовиправлення, тобто окрема помилка в обчисленнях не відображається на кінцевому результаті, так як помилкове приближення можна розглядати як нове початкове приближення.

Початковий вектор Хможе бути вибрано довільно. Іноді берутьX⁽⁰⁾ = f⁽⁰⁾. Найбільш доцільно як компоненту початкового вектора взяти приближене значення невідомих, отриманих грубою прикидкою. Чим ближче початкове приближення до значення коренів системи, тим скоріше зійдеться ітераційний процес .

Якщо матриця Анеособлива, то систему (2.3) за допомогою сукупності елементарних перетворень завжди можна привести до вигляду (2.4).

До елементарного перетворення матриць відносяться :

а)заміна рядків (стовпців);

б)множення усіх елементів якого-небудь рядка (стовпця) на одне і те ж число, відмінне від нуля;

в)додавання до елементів якого-небудь рядка (стовпця) відповідних елементів другого рядка (стовпця), множених на одне і те ж число.

Практично роблять так. З заданої системи виділяють рівняння з коефіцієнтами, модулі яких більше суми останніх коефіцієнтів рівняння. Кожне виділене рівняння виписують у такий рядок нової системи, щоб найбільший по модулю коефіцієнт став діагональним. Потім, використовуючи елементарні перетворення, складають останні рівняння нової системи. При цьому необхідно, щоб були використані у тому чи іншому сполученні усі рівняння початкової системи.

ПРИКЛАД: Для знаходження коефіцієнтів емпіричної залежності необхідно визначити наступну систему рівняння

2  x₁ – 0,5  x₂ + 4  x₃ = 22 (A)

3  x₁ + 3,5  x₂ + 3  x₃ = 35 (Б)

x₁ + 0,5  x₂ – x₃ = –1 (B)

У рівнянні (А) коефіцієнт прих₃по модулю більше суми модулів останніх коефіцієнтів, тому можна прийняти це рівняння за третє рівняння нової системи. Щоб отримати друге рівняння з максимальним по модулю коефіцієнтом прих₂, достатньо скласти різність (Б)–(А):

х₁ + 4  x₂ – x₃ = 13

При перетворенні початкової системи до вигляду (2.4) було використано рівняння (А) та рівняння (Б). Отже, у перше рівняння обов'язково повинно увійти рівняння (В), наприклад, використовуючи наступне перетворення

(А)+4  (В):

6  x₁ + 1,5  x₂ + 0  x₃ = 18.

Таким чином, отримана еквівалентна система рівнянь, котра задовольняє умовам збіжності:

6  x₁ + 1,5  x₂ = 18 (А1)

x₁ + 4  x₂ – x₃ = 13 (Б1)

2  x₁ – 0,5  x₂ + 4x₃ = 22 (В1)

Вирішуючи перше рівняння відносно х₁, друге – відноснох₂, третє – відноснох₃, отримаємо

x1 = 3 – 0,25  x2 x2 = 3,25 – 0,25  x1 + 0,25  x3 x3 = 5,5 – 0,5  x1 + 0,125  x2

(2.7)

Як початковий вектор Х⁽⁰⁾візьмемо елементи стовпця вільних членів, округляючи їх значення до одного знаку після коми:

x⁽⁰⁾₁ = 3; x⁽⁰⁾₂ = 3,3; x⁽⁰⁾₃ = 5,5.

Точність обчислювання = 0,01.

Послідовно обчислюємо:

при k=1:

x⁽¹⁾₁ = 3 – 0,25 3.3 = 2,175

x⁽¹⁾₂ = 3,25 – 0,25 3 + 0,25 5,5 = 3,875

x⁽¹⁾₃ = 5,5 – 0.5 3 + 0,125 3,3 = 4,413

при k=2:

x⁽²⁾₁ = 3 – 0,25 3,875 = 2,031

x⁽²⁾₂ = 3,25 – 0,25 2,175 + 0,25 4,413 = 3,810

x⁽²⁾₃ = 5,5 – 0,5 2,175 + 0,125 3,875 = 4,897 та т.д.

Результати подальших обчислювань наведені у таблиці.

k	0	1	2	3	4	5	6
x1	3	2,175	2,031	2,048	2,009	2,006	2,002
x2	3,3	3,875	3,810	3,966	3,978	3,991	3,997
x3	5,5	4,13	4,897	4,961	4,972	4,993	4,996

Так як модулі різницьзначеньХ^(к)приk=5 іk=6

| x⁽⁶⁾₁ – x⁽⁵⁾₁ | = 0,004; | x⁽⁶⁾₂ – x⁽⁵⁾₂ | = 0,006; | x⁽⁶⁾₃ – x⁽⁵⁾₃ | = 0,003;

менш заданої точності , то як рішення приймаємо:

х₁ = 2,002 ; х₂ = 3,997 ; х₃ = 4,9967.

Для порівняння точні значення невідомих: х₁ = 2; х₂ = 4; х₃ = 5.

2.2. Метод Зейделя

Метод Зейделя є модифікацією методу простої ітерації. Він полягає у тому, що при обчислюванні k-го приближення невідомогоx_iприi>1використовуються вже обчисленні ранішеk-ті приближення невідомихх₁, х₂,.., х_i–1. Таким чиномk-е приближення до рішення буде даватися наступною формулою:

x^(к)_i = (f_i – c_i1  x^(к)₁ –... – c_i,i–1  x^(к)_i–1 – c^(к-1)_i,i+1  x_i+1 – ... – c^(к–1)_i,n  x_n) /a_i,i ,

(i = 1, 2, ..., n)

Блок-схема методу приведена на рис. 2.4.

Умови збіжності для методу простої ітерації залишаються вірними також для методу Зейделя. Метод Зейделя дає кращу збіжність, ніж метод простої ітерації. Крім того, метод Зейделя більш зручніше при програмуванні, бо при обчислюванні x^(к)_iнема необхідності зберігати значенняx^(к–1)_i, ...., x^(к–1)_i–1 .

Рекомендації до застосування методу Зейделя залишаються тими ж, що і для методу простої ітерації.

ПРИКЛАД: Методом Зейделя вирішити попередній приклад.

Використаємо систему рівнянь (2.7) з тими ж початковими приближеннями. Проведемо ітерації методом Зейделя. При k=1:

x⁽¹⁾₁ = 3 – 0,25  3,3 = 2,175.

При обчислюванні х⁽¹⁾₂використовуємо вже отримане значенняx⁽¹⁾₁:

x⁽¹⁾₂ = 3,25 – 0,25  2,175 + 0,25  5,5 = 4,081.

При обчислюванні x⁽¹⁾₃використовуємо значенняx⁽¹⁾₁, x⁽¹⁾₂ :

x⁽¹⁾₃ = 5,5 – 0,5  2,175 + 0,125  4,081 = 4,923.

Аналогічним чином обчислюємо при k=2,k=3, ......

Результати подальших обчислювань наведені у таблиці.

k	0	1	2	3	4
x1	3	2,175	1,980	2,004	2,000
x2	3,3	4,081	3,986	4,001	4,000
x3	5,5	4,923	5,008	4,998	5,000

Рис. 2.4. Блок-схема методу Зейделя