2. Методи Гауса

Найбільш відомими точними методами розв’язання системи лінійних алгебраїчних рівнянь (1) є методи Гауса, суть яких полягає в тому, що система рівнянь, яка розв’язується, зводиться до еквівалентної системи з верхньою (або нижньою) трикутною матрицею. Невідомі знаходяться послідовними підстановками, починаючи з останнього рівняння перетвореної системи. Точність результату та витрачений на його отримання час у більшості випадків залежить від алгоритму формування трикутної матриці системи. У загальному випадку алгоритми Гауса складаються з двох етапів – прямого та зворотного ходу.

Під час прямого ходу СЛАР (1.1) перетворюється в еквівалентну систему з верхньою трикутною матрицею коефіцієнтів виду:

(2.1)

Зворотній хід дозволяє визначити елементи вектора розв’язку, починаючи з останнього рівняння системи (2.1), шляхом підстановки відповідних елементів вектора невідомих, отриманих на попередньому кроці.

Нехай необхідно обчислити не вироджену, визначену систему (1.1).

,

(2.2)

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

,

(2.3)

де , а .

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

,

(2.4)

де , а . Далі продовжуємо аналогічно, поки система не прийме вигляд:

.

(2.5)

Тепер починаємо зворотній хід методу. Знаходимо значення із останнього рівняння . За допомогою знайденого отримуємо значення із передостаннього рівняння і т.д. Отже, після зворотного ходу Гауса обчислено розв’язок СЛАР (2.2).

На рис. 2.1. наведено алгоритм знаходження розв’язку системи лінійних рівнянь методом Гауса.

Число арифметичних операцій, необхідних для реалізації метода Гауса, визначаються наступною формулою:

де число – число невідомих.

Неважко помітити суттєвий недолік розглянутого методу Гауса з послідовним вибором елемента, який випливає з того, що однією з необхідних операцій є ділення на діагональний елемент. Якщо такий елемент виявиться досить малою за абсолютним значенням величиною, то операція ділення приводить до значної похибки у визначенні подальших коефіцієнтів – членів матриці. Для уникнення даної ситуацію використовують метод Гауса з вибором головного елемента (рис. 2.2.).

Для методу Гауса з вибором головного елемента необхідно виконати додаткові кроки:

1) в системі (2.2) необхідно знайти з k-го стовпця найбільший за абсолютним значенням коефіцієнт a_{k j} ;

2) переставити k-те рівняння з рівнянням у якому знаходиться цей максимальний коефіцієнт.

Таким чином досягають того, щоб діагональний елемент, на який будуть ділити, був якомога більшим за модулем.

Рисунок 2.1. – Схема алгоритму розв’язання СЛАР методом Гауса

Рисунок 2.2. – Схема алгоритму розв’язання СЛАР методом Гауса з вибором головного елемента