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

План

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

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

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

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

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

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

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

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

.

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

.

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

(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

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

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

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

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

(6)

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

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

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

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

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

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

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

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

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

(7)

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

Таблиця 4

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

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

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

(8)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

Розв’язавши цю систему, знайдемо . Це означає, що підприємство щоденно виробляє 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 країн виділено кошти у кількостях . Нехай частка , яку та країна витрачає на закупівлю товарів у тої країни. Вважатимемо, що всі виділені кошти кожної країни витрачаються або на внутрішньому ринку, або на імпорт товарів. Остання умова забезпечує рівність , . Матрицю з елементів називають структурною матрицею торгівлі:

.

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

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

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

, або .

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

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

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

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

, або

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

Дата добавления: 2014-01-04; Просмотров: 3748; Нарушение авторских прав?; Мы поможем в написании вашей работы!