Метод Гаусса-Жордана

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

1) коли однорідна система має п рівнянь з п невідомими і її основний визначник Δ(А) дорівнює нулю;

2) коли кількість рівнянь неоднорідної системи не дорівнює кількості невідомих, а система рівнянь є сумісною;

3) коли кількість рівнянь дорівнює кількості невідомих та дорівнює п, система рівнянь сумісна г(А)=г( )=г, алег<п.

Видатний німецький математик, астроном, фізик і геодезист Карл Фрідріх Гаусc (30.04.1777-23.02.1855) розробив метод розв'язування таких систем лінійних алгебраїчних рівнянь. Суть метода Гаусса полягає в тому, що шляхом елементарних перетворень систему треба привести до трикутного вигляду, коли усі елементи головної діагоналі основної матриці системи дорівнюють 1, а елементи основної матриці, що знаходяться нижче її головної діагоналі, дорівнюють нулю. Такий вигляд системи дозволяє знайти усі невідомі. Метод Гаусса можна застосовувати і до систем лінійних алгебраїчних рівнянь, що мають єдиний розв'язок.

Щоб краще зрозуміти суть метода Гаусса, розглянемо декілька прикладів

Приклад 1. Розв'язати систему рівнянь

Розв'язування. Спочатку поміняємо місцями перше та друге рівняння, щоб елемент а₁₁ основної матриці дорівнював 1. Одержимо:

Тепер перше рівняння помножимо на (-2) і додамо до другого (щоб одержати а₂₁=0, а потім помножимо перше рівняння на (-3) і додамо до третього рівняння (щоб одержати а₃₁=0). Тоді будемо мати систему

Тепер друге рівняння поділимо на (-5), третє рівняння поділимо на 5 і поміняємо їх місцями. Одержимо систему трикутного вигляду

,

з якої після деяких перетворень одержимо

.

Таким чином, система має єдиний розв'язок (-1, 0, 1).

Зауваження. Елементарні перетворення доцільно виконувати не з усією системою, а з її розширеною матрицею. Розв'язування прикладу 1 у такий спосіб виглядає так:

.

Приклад 2. Розв'язати систему рівнянь

Розв'язування. Задана система 3-х рівнянь з 4-ма невідомими. Виконаємо елементарні перетворення з розширеною матрицею.

Звідси випливає, що основна та розширена матриці мають рівні ранги: г(А)=г( )=2. Знайдемо мінор другого порядку, який не дорівнює нулю.

Наприклад, таким мінором буде визначник другого порядку:

.

Мінор, який не дорівнює нулю, та має порядок, який дорівнює рангу г=г(А)=г( ), називають базисним мінором, тому обраний нами мінор – базисний.

Невідомі х₁ та х₂, для яких елементи базисного мінору є коефіцієнтами, називають базисними невідомими. Інші невідомі системи х₃ та х₄ – вільні. Останній вигляд розширеної матриці відповідає такій системі

Вільні невідомі перенесли у праву частину системи. Ми одержали базисні змінні х₁ та х₂ як функціїх₃ та х_4. Виконавши відповідні перетворення, одержимо:

Вільним невідомимх₃ та х₄ можна надавати будь-які значення, наприклад х₃=С₁,х₄=С₂, де С₁ та С₂ – довільні сталі. Отже, одержуємо нескінченну кількість розв'язків системи вигляду:

.

5.3.1. Поняття різновидів розв'язків

Розв'язки прикладу 2 приймають різні значення, якщо сталим C₁ та С₂ надавати конкретні значення.

Коли розв'язок розглядають залежним від будь-яких значень C₁ та С₂, тоді його називають загальним розв'язком відповідної системи лінійних алгебраїчних рівнянь.

Якщо взяти C₁=С₂= 0, то одержаний розв'язок називають базисним. У випадку прикладу 2 базисним розв'язком буде:

Якщо одній сталій надати значення 0, а іншій 1, тоді одержані розв'язки називають фундаментальними.

У системі прикладу 2 є два фундаментальні розв'язки:

.

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

Саме базисні, фундаментальні та опорні розв'язки систем найчастіше використовують економісти.

Головною метою дисципліни “Математичне програмування” є розробка методів знаходження опорних розв'язків та вибору оптимального розв'язку серед них.