Материал: Вища математика для економістів - Навчальний посібник ( Барковський В.В.)


5.3. методи гаусса та гаусса-жордана

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

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

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

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

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

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

 

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

 

2 х

-4 У

+3 г

= 1

< х

-2у

+4 г

= 3

3 х

у

+5 г

=2

 

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

 

х

-2у

+4г

=3

< 2 х

-4у

+3г

=1

3 х

+5г

=2

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

x  -2 у  +4 z   = 3 ^ =-5. 5 у   -7 z = -7

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

 

2 У

+4 ^

=3

x =

3

у

7

5 Z

= 7 = 5

у =

7 • 1

5

 

z

=1

z =

1

x   -2у   +4 z    = 3      |х =     3    -4 • 1  +2 • 0

_ 7 5

 

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

Г x = -1

У = 0 z = 1

 

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

 

Подпись: -11

3

52

Ґ1 0 0

{2 -4 3 1 -2 4 3 -1

24

5 -7 0 -5

Ґ1

2

3

3 1

7

5

 

2 4 1

Ґ1

31

1

2

2

1

 

-

Ґ

1 -2

00 05

31

7

5

1

4 5 7

31

5 7

 

-

 

 

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

 

2х1

+X 2

Х3

Х4

= 2

< 4 х1

 

+Х 3

—3 Х 4

= 3

 

2 Х 2

—3 Х3

+Х4

= 1

 

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

 

Г 2

1

1

1

2 ^

 

Г 2

ГГ0

1

1

1

2 ^

 

ГГ0

1

1

1

2

4

0

1

3

3

 

2

3

1

—1

-

 

2

3

1

—1

0

2

3

1

1)

 

0

V

2

3

1

1 )

 

0

V

0

0

0

0

 

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

Ф 0

2 1 0 -2

Мінор, який не дорівнює нулю, та має порядок, рівний рангу

г = г(А) = г( А ), називають базисним мінором, тому обраний нами мінор базисний.

Невідомі х1 та х2, для яких елементи базисного мінора є кое­фіцієнтами, називають базисними невідомими. Інші невідомі систе­ми х3 та х4 вільні. Останній вигляд розширеної матриці відповідає такій системі

 

2 Х

 

2 Хс 2   13 Хс 3

Х А

~Х А

 

= —1

2      і ХХ ■

2 Х3

— 3

+Х,

Х А

+2 +1

 

Вільні невідомі перенесли у праву частину системи. Ми одержа­ли базисні змінні х1 та х2 як функції х3 та х4:

 

 

 

+х4

 

00 о     001

2 3    2 4

+2 -О

1

 

Подпись: 3
4
1
00 л     00 о     І    001 І

І

1       4 3    4 4 4

1_

2 °4

 

Вільним невідомим х3 та х4 можна надавати будь-які значення: х3 = Ср х4 = С2, де С1 та С2 довільні сталі. Отже, одержуємо нескінчен­ну кількість розв'язків системи вигляду:

 

С 3 Сп 3 —+ —+ —

 

X

3^_ + 1 2     2 2

 

V 00 4 У

С1

С2

 

 

 

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

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

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

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

 

С 31 4 1 2 0

V 0 у

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

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

 

 

 

ХФ,і

{ 3 ^ 2 0

0

V1 у

 

ХФ,2

 

2

2 1

V 0 у

 

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

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

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

 

5.3.2. Метод Гаусса-Жордана з використанням розрахункових таблиць

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

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

Перетворення Гаусса-Жордана дозволяють розв'язувати довільні системи лінійних алгебраїчних рівнянь, знаходити ранг матриці, обер­нену матрицю.

При розв'язуванні довільних систем лінійних алгебраїчних рівнянь методом Гаусса-Жордана треба послідовно зробити декілька кроків перетворення Гаусса-Жордана з певним правилом переходу від однієї таблиці до іншої.

Кроком перетворення Гаусса-Жордана називають елементарні перетворення (множення рівнянь на число, алгебраїчна сума різних рівнянь), за допомогою яких задана система зводиться до еквівалент­ної системи.

 

Алгоритм кроку перетворення Гаусса-Жордана

Обираємо розв'язивальний елемент аіі Ф 0 .

Елементи і-го рядка (його називають розв'язувальним) ділимо на а{]і запишемо в і рядок розрахункової таблиці.

В розв'язувальному ^ стовпці замість апишуть одиницю, а

замість інших елементів цього стовпця пишуть нулі.

Усі інші елементи розрахункової таблиці, в тому числі і конт­рольного стовпця, знаходять за формулою

 

аи =~  

а (1)

к = 1,2,ш; і = 1,2,н; к Ф і, ] Ф і.

Обчислення елементів аи за формулою (1) доцільно виконувати з використанням схеми прямокутника

 

5. Роблять перевірку правильності розрахунків шляхом порівнян­ня суми елементів рядка з відповідним елементом контрольного стовпця.

■ Приклад 3. Виконати крок перетворень Гаусса-Жордана з ви­користанням розрахункової таблиці для системи

 

4 x1

-5 x 2

+2 x3

= —12

< 3x1

+2 x 2

—2 X3

= 13

—2 x1

+3 X 2

+4x3

= —8

 

^> Розв'язання. Запишемо задану систему у вигляді розрахунко­вої таблиці 1.

Елементи останнього контрольного стовпця повинні дорівнюва­ти сумі елементів відповідного рядка таблиці.

За алгоритмом кроку перетворень Гаусса-Жордана зробимо пе­рехід до розрахункової таблиці 2:

обираємо розв'язувальний елемент а13 = 2;

елементи першого рядка таблиці (розв'язувального) ділимо на 2 і запишемо у перший рядок таблиці 2.

у третьому (розв'язувальному) стовпці ä13 = 1, а інші елемен­ти дорівнюють нулю;

 

 

 

 

 

 

 

4) решту елементів таблиці 2 обчислюємо за формулою (1) з ви­користанням схеми прямокутника:

_ _ 3• 2-4-(-2) _ 6 + 8 _ _

«21 _       2       _   2   _ 7

 

_(-2)-2-4-4 _ 4-16

_ 2• 2-(-2)-(-5) _ 4-10 __3

біпп   —          —        — О.

22        2 2

Аналогічно знаходимо:

а?24 — 1;    а^25 — 5;    а^з2 — 13;    а^з4 —16?    а^з5 — 19. 5) перевіримо правильність розрахунків 2 5/2 + 1 6 = -11/2; -11/2 = -11/2; 7 3 + 1 = 5;   5 = 5;

-10 + 13 + 16 = 19;        19 = 19.

 

Рекомендації для скорочення розрахунків

Розв'язувальним елементом доцільно обирати одиницю, тоді формули (1) спрощуються.

Якщо у розв'язувальному стовпці розрахункової таблиці є нуль, то відповідний рядок з цієї таблиці переписують без змін.

Якщо в розв'язувальному рядку розрахункової таблиці є нуль, то відповідний стовпець переписуємо без змін.

Наприклад, в і розв'язувальному рядку аа = 0, тоді 1-й стовпець таблиці переписуємо без змін.

Якщо в таблиці є два пропорційних рядки, то один з них мож­на викреслити.

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

Після послідовного виконання максимально можливого числа кроків перетворення Гаусса-Жордана, наприклад г, одержимо систе­му, яка може бути записана у вигляді таблиці 3.

Система, що записана у таблиці 3, зветься системою у базисно­му вигляді.

Можливі такі випадки:

г = п, тоді система має єдиний розв'язок xk = ck, k = 1, 2,..., п.

г < m < п, тоді система має множину розв'язків. Загальний розв'язок системи буде

 

-Ьіг+1 • хг+1

' Ь1пхп

 

C2        Ь2 г+1 ' хг+1        •••    Ь2 пхп

(2)

 

х

 

ьгг+1 ' хг+1

" • brnXn

Невідомі х1, х2...., хг, відносно яких система розв'язана, називають базисними, а невідомі хг +1, хг +2 xn, називають вільними або неба-зисними.

Якщо у загальному розв'язку (2) усі вільні невідомі прирівняти нулю, то одержимо базисний розв'язок системи:

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

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

3) При перетворенні системи одержали рівняння, усі коефіцієн­ти якого дорівнюють нулю, а права частина с. не дорівнює нулю. В цьому випадку система несумісна.

 

■ Приклад 4. Розв'язати методом Гаусса-Жордана систему

 

х1

+х 2

+ х 3

+х 4

+Х5

= 7

3

+2 х2

+ Х3

+х4

 

= 2

 

 

+2 х 3

+2Х4

+6 х5

=23

5 х1

+4 х2

+3 х 3

+3х4

Х5

= 12

^> Розв'язання. Розв'язання будемо проводити з використанням розрахункової таблиці 4 та формул (1).

Отже, задана система сумісна і має множину розв'язків. Базисні

х1 та х2, вільні невідомі х3, х4 та х5. Загальним розв'язком заданої системи буде

Г хх 1 — 16 + -Х3 + -Х4 + 5 -Х5

 

— 23 2x^3

2 Х4       6 Х5

 

Базисним розв'язком системи буде

(-161

23

 

X =

0 0 0

 

Фундаментальних розв'язків три:

 

 

Е =

(-151 21 1 0 0

 

е2 =

(-151

21 0 1 0

 

Ез =

(-111 17

0 0

V 1 у

 

При базисних невідомих х1 та х2 базисний розв'язок Хь не є опор­ним (перша компонента від'ємна).

Але при розв'язуванні системи можна взяти інші розв'язуванні елементи і одержати базисними інші невідомі, наприклад, х2 та х3. При цих базисних невідомих базисний розв'язок можливо буде опорним.

 

Вправи до розділу 5.3

Розв'язати методом Гауса-Жордана системи:

 

 

 

3 х1

5 х2

+2 х3

+4 х4

= 2

5. -

7 х1

-4 х 2

+х 3

+3 х4

= 5. 6

 

5 х1

+7 х 2

-4 х3

-6 х4

= 3

 

 

 

 

2 х1

-4 х2

+3 х3

=1

7. -

х1

-2 х2

 

= 3

 

3 х1

х2

-5 х3

=2