Розв'язування систем лінійних алгебраїчних рівнянь методом Гаусса

Нехай дана система т лінійних рівнянь з п невідомими A • X — Б. По­трібно знайти її загальний розв'язок, якщо вона сумісна, або встановити її не­сумісність.

Назвемо елементарними операціями наступні дії з матрицями:

• перестановка рядків;

• множення рядка на число, відмінне від нуля;

• додавання одного рядка до іншого, помноженого на довільне чис­ло.

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

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

Для застосування алгоритму потрібно, щоб у системі коефіцієнт а_іі був відмінний від нуля. Якщо це не так, то доцільно на перше місце поставити рів­няння з відмінним від нуля коефіцієнтом при х_і і перепозначити коефіцієнти. Щоб не нагромаджувати додаткових позначень, будемо вважати, що така зміна рядків уже зроблена, тобто а₁₁ Ф 0.

Ь і, Ь 2,

а1тХт а2тХт

ацХі + аі2 х₂ +... + ^а2і^Хі + ^а22 ^Х2 +... +

 

^апт^Хт

^апі^Хі + ^ап 2 ^Х2

Крок і: помножимо кожне рівняння, крім першого, на множник -^аіі, де і

^аіі

= Ь

+

+

номер рівняння у системі (номер рядка системи).

 

Ьі,

+

+

+

ацХі

аі2 Х2

^аіт^Хт

аіі а2і

аіі а2і

аіі _

аіі а2і

= Ь2

+

+

+

а2іХі

а22 Х2

а2тХт

а2і

аіі апі

аіі апі

аіі _

аіі апі

= Ь

+

+

+

апіХі

ап 2 Х2

аптХт

апі

 

Після даного кроку всі коефіцієнти при змінній х_і у всіх рівняннях дорі­внюють а_іі.

+

+

^аіі^Хі + ^аі2^Х2 +... + ^аіт^Хт = ^Ьі, ^аіі^Хі + ^а22 ^Х2 +... + ^а2 т^Хт = ^Ь2,

ь п

^аіі^Хі + ^ап 2 ^Х2 +... + ^ап т^Хт - "п Крок 2: Віднімемо з кожного рівняння системи, починаючи із другого, перше рівняння. Одержимо систему, у якій усі коефіцієнти при Х_і у всіх рівняннях, крім першого перетворились на нуль.

^аіі^Хі + ^аі2^Х2 +... + ^аіт^Хт = ^Ь1^,

" " — и"

^а2 2 ^Х2 +... + ^а2 т^Хт = ^Ь2^,

 

№ _ г №

+

+

ап 2 Х2

^апт^Хт = ^Ьп

Крок 3: Повторюємо кроки 1-2 для другого стовпця, починаючи із тре­тього рівняння й т.д.

Кроки 1-3 - називаються прямим ходом методу Гаусса. Прямий крок продовжується доти, доки не реалізується один із трьох можливих випадків: