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

План

1. Основні поняття.

2. Дії з матрицями.

3. Обернена матриця.

4. Ранг матриці.

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

1. Основні поняття

Розглянемо ще один математичний об’єкт, пов’язаний із системою рівнянь (1.1).

Означення. Матрицею називається прямокутна таблиця чисел, яка має m рядків і n стовпців. Якщо повернутися до системи рівнянь (1.1), то коефіцієнти при невідомих у лівій частині якраз і утворюють таку прямокутну таблицю:

.

Числа називаються елементами матриці, а запис означає її розмір. Зауважимо, що на першому місці в цьому запису зазначено кількість рядків матриці, а на другому — кількість стовпців. Наприклад, запис розміру матриці означає, що в ній п’ять рядків і три стовпці. Якщо кількість рядків матриці дорівнює кількості її стовпців, то матриця називається квадратною.

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

Елементи з двома однаковими індексами a11, a22, a33, ... ann утворюють головну діагональ матриці. Якщо , то матриця називається симетричною.

Квадратна матриця, в якої елементи головної діагоналі дорівнюють одиниці, а всі інші нулю, називається одиничною матрицею:

.

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

Кожній квадратній матриці можна поставити у відповідність визначник, який складається з тих самих елементів.

.

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

 

2. Дії з матрицями

1. Сумою матриць одного й того самого порядку і називається матриця ; , будь-який елемент якої дорівнює сумі відповідних елементів матриць
А і В: . Наприклад обидві матриці , мають розмір , тому за означенням можна утворити їх суму — матрицю

.

2. Добутком матриці на деяке число називається така матриця С, кожен елемент якої утворюється множенням відповідних елементів матриці А на , .

Приклад. , .

Очевидно, що для суми матриць і добутку матриць на число виконуються рівності:

1) ;

2) 2) ;

3) 3) ;

4) 4) ,

5) 5) .

Добутком матриці розміру на матрицю розміру називається така матриця розміру , , кожний елемент можна знайти за формулою:

.

Кожний елемент матриці С утворюється як сума добутків відповідних елементів і-го рядка матриці А на відповідні елементи j-го стовпця матриці В, тобто за схемою:

Зазначимо, що в результаті множення дістанемо матрицю розміру .

Приклад. Нехай , . Знайдіть добутки та (якщо це можливо).

.

Добуток не існує, оскільки число стовпців матриці не співпадає з числом рядків матриці .

Приклад.Нехай, . Знайти добутки і (якщо це можливо).

.

.

З наведених вище прикладів зрозуміло, що в загальному випадку .

Переставними називають матриці і , якщо для них виконується умова .

 

Повернемось до системи рівнянь (1.1) і утворимо матриці: А — коефіцієнтів при невідомих, Х — невідомих, В — вільних членів:

, , .

Тоді згідно з означенням добутку матриць систему рівнянь (1.1) можна записати в матричному вигляді:

, (1.5)

який значно скорочує запис системи рівнянь.

 

2. Обернена матриця

Матриця називається оберненою для квадратної матриці , якщо де Е - одинична матриця.

Для будь якої квадратній матриці можна поставити у відповідність визначник, який позначається .

Невиродженою називається матриця , якщо . Якщо матриця невироджена, то існує єдина обернена до неї матриця , до того ж,

,

де - приєднана матриця, - алгебраїчне доповнення елемента матриці А.

Для того щоб скласти матрицю П слід замінити елементи матриці відповідними алгебраїчними доповненнями і транспонувати отриману матрицю.

 

Властивості оберненої матриці:

1. 1. .

2. .

3.

Приклад 12. Знайдіть матрицю, обернену до даної .

Виконаємо наступні кроки:

1) Знайдемо: : .

Оскільки, ,то матриця існує.

2) Знайдемо алгебраїчні доповнення до всіх елементів матриці А:

; ;

;

3) Запишемо матрицю П:

.

4) Знайдемо матрицю :

.

Легко перевірити, що

Повернемось тепер до виразу (1.5) — запису системи рівнянь у матричному вигляді АХ = В. Припустимо, що система складається з n лінійних рівнянь з n невідомими, матриця А — квадратна і — матриця невироджена. Тоді для матриці А побудуємо обернену А1 — вона за тих припущень, які щойно зроблено, існує. Помноживши тепер матричну рівність АХ = В зліва на матрицю А1, дістанемо:

,

або остаточно .

Останній вираз — це розв’язок системи лінійних рівнянь. Зауважимо, що в такому вигляді можна записати розв’язок будь-якого матричного рівняння, якщо матриця А задовольняє умови існування А–1.

 

4. Ранг матриці

Розглянемо матрицю А розміром

і введемо ще одне важливе поняття.

Означення. Рангом матриці А розміром називається найвищий порядок відмінного від нуля мінора, утвореного з елементів цієї матриці. Зрозуміло, що , а най-
більший можливий ранг матриці може дорівнювати меншому з чисел m і n.

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

Означення. Елементарними перетвореннями матриці А називаються такі її перетворення:

1) заміна місцями двох рядків або двох стовпців матриці;

2) множення рядка або стовпця матриці на довільне відмінне від нуля число;

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

Теорема. Елементарні перетворення не змінюють рангу матриці.

Далі матриці, які мають рівні ранги, називатимемо еквівалентними матрицями. Еквівалентні матриці об’єднуватимемо знаком «~» («тильда»).

 

Розв’язувати будь-які системи лінійних алгебраїчних рівнянь (СЛАР) можна методами Гаусса (виключення невідомих) та Гаусса-Жордана.

Суть методу Гаусса – зведення системи шляхом елементарних перетворень до такого вигляду системи, коли усі коефіцієнти, що знаходяться нижче головної діагоналі основної матриці, дорівнюють нулю.

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

Розв’язання.Щоб виключити невідоме з другого та третього рівняння, віднімемо від них перше рівняння і одержимо систему

В останній системі виключимо із третього рівняння шляхом множення другого рівняння на і додаванням до третього рівняння. Одержимо

Вважаємо (стала), тоді з третього рівняння одержимо .

Підставимо це значення та в друге рівняння і одержимо:

.

Тепер підставимо в перше рівняння та і одержимо

.

Таким чином, задана система трьох лінійних рівнянь з чотирма невідомими має одну вільну невідому . Розв’язком цієї системи буде

(4)

Зауваження: Метод Гаусса часто спрощують, перетворюючи не усю систему, а лише її розширену матрицю.

Поняття різновидів розв’язків

Якщо в розв’язку попереднього прикладу сталій надавати конкретні числові значення, то одержимо відповідні частинні розв’язки.

Коли розв’язок системи розглядають залежним від значень сталої , тоді його називають загальним розв’язком системи. Якщо взяти , то одержаний розв’язок називають базисним. При розв’язок називають фундаментальним. В попередньому прикладі розв’язок виду (4) – загальний розв’язок системи. Базисним та фундаментальним розв’язком будуть

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

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

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

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

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

1. Обираємо розв’язувальний елемент ;

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

3. В розв’язувальному стовпці замість пишуть одиницю, а замість інших елементів цього стовпця пишуть нулі;

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

(5)

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

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

Приклад:Скласти розрахункову таблицю і виконати крок перетворень Гаусса-Жордана для системи

Розв’язування.Запишемо задану систему у вигляді розрахункової таблиці 1 при цьому в тий стовпець записують коефіцієнти, що стоять перед , в стовпець записують вільні члени системи.

Таблиця 1

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

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

1. Обираємо розв’язувальний елемент ;

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

3. У другому (розв’язувальному) стовпці , а інші елементи дорівнюють нулю.

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

 

Таблиця 2

3/2 3/2 5/2 13/2
-5/2 7/2 9/2 11/2
1/2 15/2 17/2 33/2

; ;

; ;

; ;

; ;

 

5. Перевіряємо правильність розрахунків:

; ; .

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

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

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

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

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

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

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

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

 

Таблиця 3

x1 x2 хк xr xr+1 xn b1 k
… … …   … … … … … b1r+1 b2r+1 ... … brr+1     b1n b1n ... … brn c1 c2 ... … cr k1 k2 ... … kr

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

1. r = n, тоді система має єдиний розв’язок хк = ск , k = 1,2,…,n;

2. r m < n, тоді система має множину розв’язків.

Загальним розв’язком буде:

(6)

Невідомі , відносно яких система розв’язана, називають базисними, а невідомі , , … , називають вільними або небазисними.

Кожне базисне невідоме входить лише в одне рівняння системи з коефіцієнтом 1.

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

, ,…, , = =…= =0.

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

Базисний невід’ємний розв’язок системи називають опорним розв’язком цієї системи.

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

В цьому випадку система несумісна.

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

(7)

Розв’язування.Будемо проводити з використанням розрахункової таблиці, формул (5) та рекомендацій до скорочення розрахунків.

Таблиця 4

x1 x2 x3 x4 x5 b1 k
-3 -1 -2
-1 -1 -2 -2 -2 -6 -6 -23 -23 -34 -34
-1 -1 -5 -16 -22

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

Із останньої таблиці видно, що система (7) сумісна і має множину розв’язків. Базисні невідомі та , вільні невідомі .

Загальний розв’язок системи (7) має вигляд

(8)

 

Базисним розв’язком цієї системи буде

Фундаментальних розв’язків система (7) має три:

 

6.Застосування методу Гаусса для обчислення оберненої матриці.

Метод Гаусса є універсальним у разі розв’язуванні систем лінійних рівнянь. Цей метод можна застосувати для обчислення оберненої матриці, що набагато простіше за спосіб, розглянутий у п. 2.5.

Щоб знайти обернену матрицю, потрібно виконати такі дії:

1) до даної матриці А справа дописати одиничну матрицю Е;

2) елементарними перетвореннями над рядками матриці (А|E) матрицю А звести до одиничної матриці.

У результаті на місці даної матриці А буде сформовано одиничну матрицю, а на місці дописаної справа одиничної матриці Е знаходитиметься обернена матриця А-1, тобто замість матриці (A|E) дістанемо матрицю (E|A-1).

Приклад.Знайдемо матрицю, обернену до матриці

До даної матриці А справа допишемо одиничну матрицю Е. За допомогою елементарних перетворень над рядками матриці (A|E) матриця А зводиться до одиничної матриці:

Отже, обернена матриця

Правильність виконання обчислень легко безпосередньо перевірити за означенням АА-1 = А-1А = Е

7. Економічні задачі, що зводяться до систем лінійних рівнянь

Приклад.Для випуску виробів трьох видів (α,β,γ) підприємство використовує сировину 3-х типів (S1, S2, S3). Норми витрат кожного з типів сировини на один виріб і обсяг витрат сировини за один день задано таблицею:

Вид сировини Норми витрат на один виріб, ум. од. Витрати сировини за 1 день, ум. од.
α β γ
S1
S2
S3

Знайти щоденний обсяг випуску кожного виду виробів

Розв’язування.Припустимо, підприємство щодня виробляє х1 одиниць виробів виду α, х2 одиниць – β і х3 одиниць виробів виду γ. Тоді відповідно з витратами сировини кожного виду, маємо систему

;

Розв’язавши цю систему, знайдемо . Це означає, що підприємство щоденно виробляє 100 виробів виду α, 200 виробів виду β, 300 виробів виду γ.

 

 

Приклад.Два заводи виробляють апарати для двох підприємств. Підприємствам необхідно отримати 120 і 80 апаратів відповідно. Перший завод випустив 150 апаратів, а другий 50. Витрати на перевезення апаратів кожного із заводів кожного підприємства такі:

Завод Витрати на перевезення, грош. од.

Мінімальні витрати на перевезення становлять 2850 грош. од. Знайти оптимальний план перевезення апаратів.

Розв’язування.Позначимо – кількість апаратів, що надходять з і-го заводу до j-го підприємства. Тоді ми можемо скласти таку систему:

Розв’язавши систему, наприклад методом Гаусса, знайдемо .

 

Модель Леонтьєва міжгалузевого балансу.

Валову продукцію кожної галузі n- галузевої економіки позначимо (і = 1,2,…, n). Частина цієї продукції може використовуватись для міжгалузевих потреб, позначимо її (j = 1,2,…,n) (обсяг продукції і-тої галузі, використаної в j-й галузі), а інша частина – для задоволення скінченного ринкового попиту уі (товарна продукція і-ї галузі. Цей розподіл валового продукту можна описати таблицею міжгалузевих зв’язків:

Галузь матеріального виробництва Обсяг валової продукції Міжгалузеві потоки в галузі Кінцевий продукт
1 2 … n
x1 у1
x2 у2
… … … …
n xn yn

та системою балансових рівнянь:

кожне з яких відображає міжгалузеві зв’язки галузевої економіки.

Нормативні коефіцієнти, що дорівнюють кількості продукції ї галузі, використаної на виробництво одиниці продукції ї галузі, позначимо . Вони утворюють матрицю прямих витрат А:

Цю матрицю також називають технологічною матрицею галузевої економіки. Для незмінної технології виробництва матриця прямих витрат стала і завжди відома на запланований період.

Враховуючи те, що , балансові рівняння набувають вигляду:

У матричному вигляді одержимо балансове співвідношення моделі Леонтьєва:

де – вектор валового продукту, – вектор товарної продукції

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

Матрицю називають продуктивною, якщо для довільно скінченного вектору існує невід’ємний розв’язок системи . У цьому випадку і модель Леонтьєва називають ефективною, а економіку – рентабельною. Одним із критеріїв продуктивності матриці А є:

Матриця А з невід’ємними елементами продуктивна, якщо максимум сум елементів її стовпців не перевищує одиниці, причому хоча б для одного стовпця сума елементів строго менша одиниці.

Рівняння міжгалузевого балансу можна використовувати у двох задачах. У першій, коли відомий вектор валового випуску Х, потрібно знайти вектор попиту Y. У другій рівняння міжгалузевого балансу використовується з метою планування: на деякий період(наприклад рік) потрібно знайти валовий випуск продукції кожної галузі для задоволення міжгалузевих потреб та запланованого вектору попиту Y.

Приклад.Таблиця 5 містить дані балансу трьох галузей промисловості за деякий період, умов. грош. од. Треба знайти обсяг валового випуску продукції, якщо кінцевий продукт по галузях збільшити відповідно до 200, 70, 100 од.

 

 

Таблиця 5

Галузь виробництва Споживання Вектор попиту Валовий випуск

Розв’язування.Користуючись формулою для коефіцієнтів прямих витрат знайдемо матрицю прямих витрат

Далі записуємо матрицю Е-А: і знаходимо обернену до неї матрицю повних витрат . Визначник матриці Е-А , отже

Валовий випуск необхідний для забезпечення нового товарного продукту одержимо із співвідношення

.

Отже, валовий випуск у першій галузі треба збільшити на 103,4 умов. од., у другій – на 32,9 умов. од. і у третій на 38,7 умов. од.

 

Лінійна модель обміну (модель міжнародної торгівлі)

Припустимо, що на встановлення торгівельних зв’язків з бюджетів n країн виділено кошти у кількостях . Нехай частка , яку та країна витрачає на закупівлю товарів у тої країни. Вважатимемо, що всі виділені кошти кожної країни витрачаються або на внутрішньому ринку, або на імпорт товарів. Остання умова забезпечує рівність , . Матрицю з елементів називають структурною матрицею торгівлі:

.

Для тої країни виторг дорівнює

Бездефіцитність торгівлі для кожної країни забезпечується умовою , . З економічної точки зору нерівність неможлива (всі країни не можуть одночасно отримувати прибуток), тому умова збалансованої торгівлі набуває вигляду , .

Нехай , тоді умову збалансованої торгівлі можна записати у матричній формі:

, або .

Остання рівність дозволяє визначити Х.

Приклад.Структурна матриця торгівлі трьох країн має вигляд:

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

Розв’язування.Розв’яжемо рівняння . Маємо:

, або

Використовуємо метод Гаусса для знаходження розв’язку одержаної однорідної системи рівнянь. Одержимо: , , . Це означає, що збалансованість торгівлі даних країн може бути досягнута тільки у випадку коли бюджети знаходяться у відношенні . Підставимо знайдені значення у задану суму бюджетів, щоб визначити величину . Звідси остаточно одержимо шукані величини коштів країн за умови бездефіцитної торгівлі: , , .