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

 

Метод Гаусса

Розглянемо систему m лінійних рівнянь з n змінними х₁, х₂, …, х_n:

 

a₁₁ х₁ + а₁₂ х₂ + …а_1n х_n = b₁

а₂₁ х₁ + а₂₂ х₂ + …а_2n х_n = b₂ (1)

………………………………

а_m1 х₁+ а_m2 х₂ + …а_mn х_n = b_m .

 

 

Наприклад,

 

2х₁ – 3х₂ + 4х₃ = 2

х₁ – 2х₂ + х₃ = – 1 (2)

3х₁ – х₂ + 2х₃ = 0.

 

– це система трьох лінійних рівнянь з трьома змінними. Тут числові коефіцієнти а_ij мають два індекси: індекс i вказує рівняння, якому належить коефіцієнт, а індекс j змінну, при якій він стоїть. Коефіцієнти b_i називають вільними членами, тут і – номер відповідного рівняння.

Упорядкована сукупність n чисел, яка, будучі підставлена в систему (1) перетворює всі рівняння в правильні числові рівності, називається розв’язком системи (1). Розв’язати таку систему означає знайти всі її розв’язки або довести, що їх не існує. Систему (1) лінійних рівнянь називають сумісною, якщо вона має принаймні один розв’язок і несумісною в противному випадку. Сумісну систему лінійних рівнянь (СЛР) називають визначеною, якщо вона має єдиний розв’язок і невизначеною в противному випадку.

Елементарні операції над СЛР:

1. Переміна місцями двох рівнянь.
2. Множення обох частин рівняння на деяке число, відмінне від нуля.
3. Додавання (або віднімання) до обох частин деякого рівняння відповідних частин іншого рівняння, помножених на деяке число.

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

Метод послідовного виключення змінних, відомий як метод Гаусса, є найпоширенішим методом розв’язання систем лінійних рівнянь. Метод Гаусса дозволяє розв’язати будь – яку СЛР в результаті цілком визначеної послідовності елементарних операцій і отже це алгоритм, який можна застосувати на комп’ютері. Як і всі алгоритми чисельних методів, він складається з кількох кроків, на кожному з яких одна й та ж послідовність операцій застосовується до об’єкта, отриманого на попередньому кроці (окрім першого кроку, де об’єктом є задана СЛР). Є кілька модифікацій цього методу. Спочатку нагадаємо схему єдиного ділення, найбільш традиційну і відому, на прикладі (2).

Перш ніж безпосередньо перейти до цієї схеми, переставимо місцями перше і друге рівняння (елементарна операція номер 1). В результаті дістанемо таку СЛР:

 

х₁ – 2х₂ + х₃ = –1

2х₁ – 3х₂ + 4х₃ = 2 (3)

3х₁ – х₂ + 2х₃ = 0,

 

у якій a₁₁ = 1: це спростить подальші обчислення.

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

Отже, віднімаємо від другого рівняння перше, помножене на а₂₁ = 2 (елементарна операція номер 3). В результаті отримаємо СЛР:

х₁ – 2х₂ + х₃ = –1

х₂ + 2х₃ = 4

3х₁ – х₂ + 2х₃ = 0.

 

Аналогічно з третього рівняння віднімаємо перше, помножене на а₃₁ = 3. В результаті

х₁ - 2х₂ + х₃ = –1

х₂ + 2х₃ = 4

5х₂ – х₃ = 3.

 

На цьому завершено перший крок прямого ходу: його мета досягнута. Під першим рівнянням отримана система двох рівнянь з двома невідомими х₂ і х₃ :

х₂ + 2х₃ = 4

5х₂ – х₃ = 3.

Кількість як рівнянь, так і змінних зменшилась на одиницю у порівнянні з початковою СЛР (2). Ця система – новий об’єкт алгоритму і до неї знову застосуємо метод Гаусса. Мета другого кроку досягти того, щоби в результаті послідовності елементарних операцій під новим першим рівнянням у новому першому стовпці коефіцієнт при х₂ дорівнював нулю. Отже, від другого рівняння віднімаємо перше, помножене на коефіцієнт 5. В результаті отримаємо СЛР:

х₂ + 2х₃ = 4

– 11х₃ = –17,

 

тобто в цілому

х₁ – 2х₂ + х₃ = –1

х₂ +2х₃ = 4

–11х₃ = –17.

 

На цьому завершено другий крок прямого ходу: його мета досягнута. Під другим рядком тепер одне рівняння з одною змінною х₃ : знову кількість як рівнянь, так і змінних на одиницю зменшилась. На цьому завершується алгоритм прямого ходу в цілому: до одного рівняння з одною змінною застосувати його безглуздо. Результатом прямого ходу метода Гаусса стало зведення даної СЛР (2) до рівносильної їй системи трикутної форми.

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

Спочатку із третього рівняння знаходимо х₃ = . Тепер отримане значення х₃ = підставимо у друге рівняння і визначимо з нього х₂: х₂ = 4 – 2 ∙ = . Нарешті, отримані значення х₂ і х₃ підставимо у перше рівняння і визначимо з нього х₁: х₁ = – 1 + 2 ∙ – = – . Отже, трикутна система, а тому і рівносильна їй дана СЛР(2) мають єдиний розв’язок:

х₁ = –

х₂ =

х₃ = .

Таким чином система (2) сумісна і визначена.

Зауважимо, що тут перше і друге рівняння СЛР (2) були спочатку переставлені місцями лише для спрощення подальших обчислень. Без цього треба було б від другого рівняння відняти перше, помножене на , і отримати – х₂ – х₃ = – 2 з подальшим використанням дрібних чисел. Це байдуже для комп’ютера, проте у загальному випадку переміна рівнянь місцями буде необхідною при здійсненні алгоритму Гаусса, якщо a₁₁ = 0. В такому разі треба поміняти місцями перше рівняння і рівняння з номером i, для якого a_i1 ≠ 0. Якщо a_i1 = 0 для всіх i = 1, 2, …, m, то х₁ треба виключити з числа змінних СЛР. Так само треба діяти і на всіх подальших кроках алгоритму.