Розділ 2. Методи розв’язку систем лінійних рівнянь

Короткі теоретичні відомості

Система лінійних алгебраїчних рівнянь (СЛАР) у загальному випадку має вигляд:

(2.1)

де - коефіцієнти системи, - вільні члени системи, - невідомі, які необхідно визначити.

Вводячи матрицю коефіцієнтів системи

,

та вектор-стовпчик вільних членів , ф також вектор-стовпчик невідомих , систему (2.1) можна подати у матричній формі:

. (2.2)

Якщо всі вільні члени , то СЛАР називається однорідною. Із курсу лінійної алгебри відомо, що неоднорідна СЛАР має єдиний розв’язок у випадку, коли , де - визначник матриці .

 

Метод Гаусса

Метод Гаусса або метод послідовного виключення невідомих – один з найвідоміших та широко застосовуваних прямих методів розв’язування СЛАР. Процес розв’язання даним методом поділяють на два етапи: перший – це зведення системи (2.3) до трикутного вигляду(2.4) (прямий хід):

(2.3)

(2.4)

Другий етап – це визначення невідомих за формулами (2.5) (зворотний хід);

(2.5)

На практиці обчислення методом Гаусса зручно проводити, скориставшись схемою єдиного ділення, яку подано в табл. 2.1.

Таблиця 2.1.

Хід	Етапи	Коефіцієнти при	Вільні члени	Контрольні суми
Прямий	I
II
III
Зворотний	IV

Наприклад: Скориставшись схемою єдиного ділення розв’язати систему лінійних рівнянь методом Гаусса.

Розв’язок:

Використовуючи схему єдиного ділення складемо таблицю:

Хід	Етапи	Коефіцієнти при	Вільні члени	Контрольні суми
Прямий	I
II
III
Зворотний	IV

Відповідь: х₁ =1; х₂ =2; х₃ =3.

Метод прогонки

Даний метод реалізується у випадку, коли матриця - трьохдіаганальна.

Матрицю можна записати у розгорнутому вигляді як:

, , , (2.6)

Якій відповідає розширена матриця:

(2.7)

Якщо до (2.7) застосувати алгоритм прямого ходу метода Гаусса, то матриця буде замінена на матрицю :

(2.8)

Враховуючи, що останній стовпчик цієї матриці відповідає правій частині матриці , та переходячи до системи яка включає невідомі, маємо рекурентну формулу:

, . (2.9)

Співвідношення (2.9) є формулою оберненого ходу, а коефіцієнти , - називаються прогоночними та визначаються:

, , . (2.10)

Обернений хід метода прогонки починається з обчислення . Для цього використовують останнє рівняння, коефіцієнти якого визначено у прямому ході:

, .

Звідси , тобто .

Інші значення невідомих знаходять рекурентно за формулою (2.9).

Алгоритм метода прогонки називається коректним, якщо для всіх , та стійким, якщо , .

Достатньою умовою коректності та стійкості даного метода є умова преобладания діагональних елементів у матриці , в якій та :

(2.11)

та у (2.11) має місце строга нерівність хоча б при одному .

Наприклад: Дана система лінійних алгебраїчних рівнянь яка складається з трьох діагональної матриці :

. Розв’язати дану систему методом прогонки.

 

 

Розв’язання.

Перевіримо систему на умову преобладания діагональних елементів (2.11): у першому рівнянні ; у другому рівнянні ; у третьому ; у четвертому , отже умова (2.11) виконується.

Запишемо дане рівняння у вигляді матриці:

.

Прямий хід:

Обчислимо прогоночні коефіцієнти:

; ;

; .

Так як , то виходячи з (2.6) у другому доданку візьмемо від’ємний знак:

; .

Обернений хід:

;

;

;

.

Відповідь: .

 

Метод LU – декомпозицій

У цьому методі матриця коефіцієнтів А подається у вигляді добутку матриць L та U:

A = LU, (2.12)

де L – нижня трикутна матриця; а U – верхня трикутна матриця, усі діагональні елементи якої дорівнюють 1:

. (2.13)

 

Метод LU -факторизації складається з двох етапів:

1) етапу факторизації матриці A;

2) етапу отримання розв’язку X.

Вектор В у процесі факторизації не змінюється.

Із виразів (2.12) та (2.13) випливає, що для i > j елементи матриці A можна виразити через елементи матриць L та U:

(2.14)

Із рівнянь (2.14) випливає, що факторизація матриці A виконується за n стадій. На кожній j -й стадії послідовно обчислюють елементи l_ij чергового j -го стовпчика матриці L за формулою

, (2.15)

та елементи u_ji чергового j -го рядка матриці U за формулою

. (2.16)

Із формул (2.15), (2.16) випливає, що на першій стадії елементи , а .

На практиці елементи матриць L та U в процесі розкладання розміщуються на місцях елементів матриці А, причому елементи не запам’ятовуються. Таким чином, факторизована форма матриці А має вигляд

.

Після факторизації матриці A система буде мати вигляд

LUX = B. (2.17)

Позначимо Y = UX, тоді із (2.17) маємо рівняння

LY = B. (2.18)

Оскільки L – нижня трикутна матриця, то розв’язок системи (2.18) отримуємо прямою підстановкою:

.

Після цього залишається розв’язати ще систему з верхньою трикутною матрицею U, всі діагональні елементи якої дорівнюють 1:

UX = Y. (2.19)

Розв’язавши систему (2.19), остаточно отримаємо шуканий вектор X:

.

Наприклад: Розв’язати систему лінійних алгебраїчних рівнянь методом LU-декомпозицій.

Розв’язок:

Виконаємо операцію факторизації:

:

при

при

при .

В результаті маємо дві трикутні матриці:

, .

Розважимо систему :

або

Звідси маємо:

Розважимо систему :

або

Звідси маємо:

Відповідь: .

 

Метод простих ітерацій

Розв’яжемо перше рівняння системи (2.1) відносно , друге відносно і так далі. В результаті отримаємо систему рівнянь еквівалентну системі (2.1):

(2.20)

де , при , при .

Використовуючи позначення

, ,

систему (2.20) можна записати у матричному вигляді . Таким чином, метод простої ітерації є частковим випадком методу коли матриця С дорівнює:

Для розв’язання системи за допомогою формули необхідно вибрати початкове наближення . В якості такого наближення можна вибрати .

На практиці при застосуванні методу простої ітерації за критерій зупинки обчислень вибирають збіжність за аргументом:

, (2.21)

де D — задана абсолютна похибка обчислень або:

, (2.22)

де ‑ задана відносна похибка обчислень.

Для збіжності ітераційного процесу методу простої ітерації достатньо, щоб матриця системи була діагонально домінуючою:

. (2.23)

Наприклад: Нехай необхідно розв’язати систему рівнянь методом простої ітерації з абсолютною похибкою не більше 1%:

(2.24)

Перевіримо виконання умови (2.23):

Умова (2.23) виконується, отже система (2.24) може бути розв’язана методом простої ітерації. Ітераційна формула відповідно до має вигляд:

.

Виконаємо ітерацію.

.

Використовуючи норми , перевіримо досягнуту похибку розв’язку:

Потрібна точність не досягнута, виконуємо наступну ітерацію:

.

Потрібна точність не досягнута, виконуємо наступну ітерацію:

.

Необхідна точність досягнута. Для порівняння, точний розв’язок системи .