Метод Гаус для чайників: приклади рішень. Вирішити систему лінійних рівнянь методом Гауса самостійно, а потім переглянути рішення

Систему рівнянь (1.1) представимо у вигляді

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

Метод Гауса можна інтерпретувати як метод, у якому спочатку матриця приводиться до верхньої трикутної форми (прямий хід), а далі – до одиничної (зворотний хід). Очевидно, що якщо матриця поодинока, то x t = b r

Нехай матриця системи (1.3) – верхня трикутна, тому a tj= 0 при i > j,тобто всі елементи нижче головної діагоналі дорівнюють нулю. Тоді з останнього рівняння одразу визначаємо х п.Підставляючи х пв передостаннє рівняння, знаходимо х а _х і т. д. Загальні формули мають вигляд

При k > Iкоефіцієнти а ы = 0.

Наведемо матрицю системи (1.3) до верхньої трикутної. Віднімемо з другого рівняння системи (1.3) перше, помножене на таке число, при якому коефіцієнт при х хобернеться в нуль. Те саме зробимо з усіма іншими рівняннями. В результаті всі коефіцієнти першого стовпця, що лежать нижче за головну діагональ, звернуться в нуль. Потім, використовуючи друге рівняння, звернемо в нуль відповідні коефіцієнти другого стовпця. Послідовно продовжуючи цей процес, наведемо матрицю системи до верхньої трикутної форми.

Запишемо загальні формули методу Гауса. Нехай проведено виключення коефіцієнтів (А - 1)-го стовпця. Тоді залишаться рівняння з ненульовими елементами нижче за головну діагональ:

Помножимо k-юрядок на число з тк = т > kі віднімемо

з m-го рядка. Перший ненульовий елемент цього рядка обернеться в нуль, а інші зміняться за формулами

Провівши обчислення за цими формулами при всіх зазначених індексах, звернемо в нуль елементи k-roстовпця, що лежать нижче за головну діагональ. Аналогічна процедура наводить матрицю системи до верхньої трикутної форми, при цьому весь процес приведення називається ПРЯМИМ ХОДОМ МЕТОДУ ГАУСА. Обчислення невідомих за формулами (1.4) називають ЗВОРОТНИМ ХОДОМ методу.

Зворотний хід можна зробити інакше, якщо обернути на нуль і всі коефіцієнти, що лежать вище головної діагоналі. Наприклад, елементи п-го стовпця перетворюються на нуль, якщо ej^| помножити на (-a^V ax t = б| 2л) , де Ь^ п)- Коефіцієнти правої частини i-го рівняння після зазначених перетворень.

На деякому кроці прямого ходу може виявитися, що коефіцієнт aj*" * 0, але малий у порівнянні з іншими елементами матриці системи і, зокрема, малий у порівнянні з елементами першого стовпця. Розподіл коефіцієнтів системи на малу величину може призвести до значних помилок округлення .

Для зменшення помилок округлення надходять у такий спосіб. Серед елементів першого стовпця а^ кожної проміжної матриці вибирають найбільший за модулем (головний) елемент і шляхом перестановки i-го рядка з рядком, що містить головний елемент, домагаються того, що головний елемент стає провідним. Така модифікація методу виключення Гаусса називається методом Гаусса із вибором головного елемента. Випадок появи нульових елементів обходиться у своїй сам собою.

Для реалізації методу потрібно приблизно п 3/3 операцій типу множення та п 3/3 операцій типу складання. Корисно пам'ятати, що оцінка числа операцій визначається в основному операціями, що витрачаються при виконанні прямого перебігу методу Гаусса. Зворотний хід методу Гауса вимагає приблизно п 2операцій. Отже, якщо потрібно вирішити кілька систем лінійних рівнянь алгебри Ах = bз однією і тією ж матрицею та різними правими частинами, то загальна кількість операцій при вирішенні Sсистем оцінюватиметься величиною(2/3)п 3 + Sn 2 .У цьому випадку доцільно реалізувати алгоритм методу Гаусса у вигляді двох підпрограм: перша підпрограма повинна реалізовувати прямий хід алгоритму та отримувати на виході верхню трикутну матрицю, а друга підпрограма повинна, використовуючи отриману матрицю, обчислювати рішення системи довільної правої частини.

У цьому випадку, крім дотримання вимоги a kk0 при реалізації формул (6) накладаються додаткові вимоги, щоб провідний (головний) елемент у поточному стовпці у процесі перетворень вихідної матриці мав максимальне значення за модулем. Це також досягається перестановкою рядків матриці.

приклад. Як ілюстрацію переваги модифікованого методу Гауса, розглянемо систему третього порядку:

Прямий хід методу Гауса

Виключаємо х 1 з другого та третього рівнянь. Для цього перше рівняння множимо на 0,3 і складаємо з другим, а потім множимо перше рівняння на (-0,5) і складаємо з третім. В результаті отримуємо

(б)

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

Помножуючи друге рівняння на 25 і складаючи з третім, отримаємо

(в)

Зворотний хід методу Гауса

Виконуємо обчислення, починаючи з останнього рівняння в отриманій системі:

Підставляючи отримане рішення у вихідну систему, переконуємось у його істинності.

Тепер змінимо коефіцієнти системи таким чином, щоб зберегти колишнє рішення, але при обчисленні будемо використовувати округлення в рамках арифметики з плаваючою точкою, зберігаючи п'ять розрядів. Цьому буде відповідати така система

(г)

Прямий хід методу для системи ( г) повторимо за аналогічною технологією з вихідною системою ( а).

(д)

Після виключення х 2 третє рівняння набуде вигляду (інші – без зміни)

15005 х 3 = 15004. (е)

Виконуючи зворотний хід, отримаємо

Очевидно, що отримані рішення та [-0,35; -1,4; 0,99993] різні. Причиною цього є мала величина провідного елемента у другому рівнянні перетворення ( д). Щоб це виключити, переставимо в ( д) другий і третій рядки


(ж)

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

6,002 х 3 = 6,002. (з)

В даному випадку, виконуючи зворотний хід

ми отримаємо рішення системи ( г) , яке точно збігається з рішенням вихідної системи.

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

Розглянемо блок-схему модифікованого методу Гауса (рис. 2.1).

Мал. 2.1. Блок-схема модифікованого методу Гауса

Проведемо аналіз запропонованої схеми з прикладу системи n=3 (=0,001)

(8)

;. (*)

Блок 1. Введення вихідних даних: n- Порядок системи, A- матриця коефіцієнтів при невідомих, b- Вектор вільних членів.

Блок 2.I-й цикл прямого ходу (для k, Що змінюється від 1 до передостаннього значення, тобто. до n-1) забезпечує виняток із головної діагоналі матриці Аелемента a kk=0 завдяки пошуку максимального елемента a kkв поточному стовпці, що здійснюється в блоках 36 за допомогою циклуII.

Потім реалізуються розрахунки за формулами (6) прямого ходу Гауса в блоках циклів IVіV.

Проведемо побічний аналіз серед розглянутих циклів IVна прикладі (8).

Блок 3p =k = 1

Вхід у цикл II

Блок 4m =k+1 = 2 до n = 3

Блок 5a 11 = 2 <a 21 = 4 із (*)

Блок 6p= 2

Блок 4m= 2+1 = 3

Блок 5a 21 = 4 <a 31 = 6 із (*)

Блок 6p= 3

Вихід із циклу IIі вхід у циклIII, блоки 710 виконують перестановку рядків матриці Апоелементно

Блок 7j= 1 (jвід 1 до 3)

Блок 8 r = a 11 = 2 із (*)

Блок 9 a 11 = a 31 = 6

Блок 10 a 31 = r

Блок 7 j = 2

Блок 8 r = a 12 = 1

Блок 9 a 12 = a 32 = 5

Блок 10 a 32 = r = 1

Блок 7j= 3 та за аналогією r=a 13 ;a 13 =a 33 ;a 33 =r= −1.

Вихід із циклу IIIі вхід у Блок 11 і далі 1213 виконують аналогічну перестановку значень вільних членів

r=b 1 = 1;b 1 = b 3 = 14;b 3 = r = 1.

Вхід у цикл IVз зміненою системою

;; (**)

для перерахунку b 2 вектори

m=k+1 = 1 +1 = 2 до n= 3

c = a mk / a kk = a 21 / a 11 = 4/6 з (**)

b 2 =b 2 –c b 1 = 6 – 4/614 = −20/6 з (**)

Вхід у вкладений цикл V для перерахунку другого рядка

i = 1 (iвід 1 до 3); a 21 = a 21 – з  a 11 = 4 – 4/6  6 = 0;

i = 2; a 22 = a 22 – з  a 12 = 6 – 4/6  5 = 16/6;

i = 3; a 23 = a 23 – з  a 13 = 2 – 4/6  8 = −20/6.

Вихід із циклу Vі вхід у циклIV

m= 3;c=a 31 /a 11 = 2/6.

Вхід до Блок 16

b 3 =b 3 –c b 1 = 1 – 2/614 = −22/6.

Вихід із циклу IVі вхід у циклVі вхід у цикл Блок 17

i = 1 (iвід 1 до 3); a 31 = a 31 – з  a 11 = 2 – 2/6  6 = 0;

i = 2; a 32 = a 32 – з  a 12 = 1 – 2/6  5 = −4/6;

i = 3; a 33 = a 33 – з  a 13 = −1 – 2/6  8 = −22/6.

Вихід із циклу Vс перетвореною системою

;
; (***)

та вхід по лінії Ау циклI

k = 2;p =k = 2;m =k+1 = 3; Вхід до Блок 5

| a 22 | < |a 32 | = | 16/6 | > | 4/6 | з (***).

Вихід із циклу IIі вхід у циклIII

j = 2 (jвід 2 до 3);

r = a kj = a 22 = 16/6; a 22 = a 22 ; a 22 = r= 16/6; з (***)

r=a 23 = −20/6;a 23 =a 23 ;a 23 =r= −20/6; з (***)

В даному випадку на діагоналі виявився максимальний елемент, тому перестановка 2-го і 3-го рядків не виконується.

Вихід із циклу IIIі вхід у циклIв Блок 11

r=b 2 ;b 2 = b 2 ;b 2 = r = −20/6.

Вільний член b 2 залишається на своєму місці.

Вхід у цикл IV

m=k+1 = 2+1 = 3;

c = a mk / a kk = a 32 / a 22 = (-4/6) / (16/6); з (***)

b 3 =b 3 –c b 2 = −22/6 – (–1/4)(–20/6) = −27/6 з (***)

Вихід із циклу IVі вхід у циклV

i = 2 (iвід 2 до 3); a 32 = a 32 – з  a 22 = −4/6 – (–1/4)  16/6 = 0;

i= 3;a 33 =a 33 –зa 23 = −22/6 – (–1/4)(–20/6) = −27/6.

Вихід із циклу Vі вихід із циклуI.

Зворотний хід методу Гауса

У Блоки 1924 реалізуються формули (7).

У блоці 19 з останнього рівняння є значення x n (n= 3)

x 3 =b n / a nn =b 3 / a 33 = (–27/6) / (–27/6) = 1.

Вхід у цикл VI( Блок 20), в якому значення змінної циклу kзмінюється від n-1 до 1 з кроком (-1)

Блок 21s = 0

Вхід у цикл VII( Блок 22)

i = k+1 = 2+1 = 3; n = 3; s = s + a ki  x i = 0 + a 23 x 3 = −20/6 1 = −20/6.

Вихід із циклу VIIна Блок 24 цикл VI:

k = 2; x 2 = (b k– s)/ a nn = (b 2 – s)/ a 22 = (–20/6 +20/6)/a 22 = 0.

k=k–1 = 2–1 = 1;

i = k + 1 = 2; s = 0 + a 12 x 2 = 5  0 = 0;

i = k + 1 = 3; s = 0 + a 13 x 3 = 8  1 = 8;

x 1 = (b 1 –s)/ a 11 = (14 – 8) / 6 = 1.

Вихід із останнього циклу VII.

У блоці 25 (цикл опущений) виконується виведення на екран отриманого рішення СЛАУ вектора тобто. x i ,i=1, ...,n. У разі (1; 0; 1).

Розглянемо один із найпоширеніших методів вирішення систем лінійних рівнянь алгебри - метод Гаусса. Цей метод (який називають також методом послідовного виключення невідомих) відомий у різних варіантах вже понад 2000 років.

Обчислення за допомогою методу Гаусса складаються з двох основних етапів, званих прямим ходом та зворотним ходом (зворотною підстановкою). Прямий хід методу Гауса полягає у послідовному виключенні невідомих із системи (5.1) для перетворення її до еквівалентної системи з верхньою трикутною матрицею. Обчислення значень невідомих провадять на етапі зворотного ходу.

1. Схема єдиного поділу.

Розглянемо спочатку найпростіший варіант методу Гаусса, званий схемою єдиного поділу.

Прямий хід складається із кроків виключення.

1-й крок. Метою цього кроку є виключення невідомого з рівнянь з номерами Припустимо, що коефіцієнт називатимемо його головним (або провідним) елементом 1-го кроку.

Знайдемо величини

звані множниками 1 кроку. Віднімемо послідовно з другого, третього рівнянь системи (5.1) перше рівняння, помножене відповідно на Це дозволить звернути в

нуль коефіцієнти при всіх рівняннях, крім першого. В результаті отримаємо еквівалентну систему

у якій обчислюються за формулами

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

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

Тут коефіцієнти обчислюються за формулами

Аналогічно проводяться інші кроки. Опишемо ще один крок.

k-й крок. У припущенні, що головний (провідний) елемент кроку відмінний від нуля, обчислимо множники кроку

і віднімемо послідовно з рівнянь отриманої на попередньому кроці системи рівняння, помножене відповідно на

Після кроку виключення отримаємо систему рівнянь

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

Зворотній хід. З останнього рівняння системи (5.33) знаходимо Підставляючи знайдене значення передостаннє рівняння, отримаємо Здійснюючи зворотну підстановку, далі послідовно знаходимо Обчислення невідомих тут проводяться за формулами

Трудомісткість методу. Оцінимо кількість арифметичних операцій, необхідні реалізації схеми єдиного поділу.

Обчислення 1-го кроку виключення за формулами (5.29), (5.31) вимагають виконання розподілу, множень і віднімань, т. е. загальна кількість арифметичних операцій становить Аналогічно, на кроці потрібно операцій, але в кроці - операцій.

Підрахуємо тепер приблизно загальну кількість арифметичних операцій прямого ходу, вважаючи розмірність системи досить великою:

Як неважко бачити, для реалізації зворотного ходу за формулами (5.34) потрібно всього операцій, що з великих зневажливо мало проти числом операцій прямого ходу.

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

Приклад 5.7. Методом Гауса вирішимо систему

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

2 крок. Обчислимо множники Віднімаючи з третього та четвертого рівнянь системи (5.36) друге рівняння, помножене відповідно, приходимо до системи

3 крок. Обчислюючи множник і віднімаючи з четвертого рівняння системи (5.37) третє рівняння, помножене на приводимо систему до трикутного вигляду:

Зворотній хід. З останнього рівняння системи знаходимо Підставляючи значення третє рівняння, знаходимо

Результати обчислень можна звести до наступної таблиці.

Таблиця 5.2 (див. скан)

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

Приклад 5.8. Використовуючи метод Гауса, вирішимо систему рівнянь

на-розрядної десяткової ЕОМ.

Прямий хід. 1-й крок. Обчислюємо множники та перетворюємо систему на вигляд

Усі обчислення на цьому кроці виконуються без заокруглень.

2 крок. Після обчислення множника останнє рівняння системи має бути перетворено до виду де Однак на використовуваній ЕОМ буде отримано рівняння

Справді, коефіцієнт визначається точно, оскільки за його обчисленні немає чисел, мантиси яких мають понад 6 розрядів. У той самий час при обчисленні множення коефіцієнта 3.0001 дає 7-разрядное число 105003.5, після округлення якого до 6 розрядів вийде 105004. Обчислення 62) завершується виконанням операції віднімання: . Після заокруглення останнього числа до 6 розрядів мантиси приходимо до рівняння (5.41).

Зворотній хід. З рівняння (5.41) знаходимо і 1.00001. Порівняння з істинним значенням показує, що ця величина отримана з дуже високою для ЕОМ точністю. Подальші обчислення дають

Після округлення маємо.

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

У чому причина появи такої значної похибки? Говорити про накопичення помилок округлення годі й говорити, оскільки всього було виконано 28 арифметичних операцій і лише 4 випадках знадобилося округлення. Припущення про погану обумовленість системи не підтверджується; обчислення дає значення та 100.

Насправді причина полягає у використанні на кроці малого провідного елемента. Наслідком цього стала поява великого

множника та суттєве зростання коефіцієнта в останньому рівнянні системи.

Таким чином, викладений вище варіант методу Гауса (схема єдиного поділу) виявився некоректним і, отже, непридатним для обчислень ЕОМ. Цей метод може призвести до аварійного зупинення (якщо при деякому обчислення по ньому можуть виявитися нестійкими.

2. Метод Гауса з вибором головного елемента по стовпцю (схема часткового вибору).

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

Інтуїтивно ясно, що щоб уникнути сильного зростання коефіцієнтів системи і пов'язаних з цим помилок не можна допускати появи великих множників

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

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

Приклад 5.9. Розв'яжемо систему рівнянь (5.39) методом Гауса з вибором головного елемента по стовпцю на -розрядної десяткової ЕОМ.

Прямий хід. 1-й крок. Максимальний у першому стовпці елемент матриці знаходиться в першому рядку, тому перестановка рівнянь не потрібна. Тут перший крок проводиться так само, як і в прикладі 5.8.

2 крок. Серед елементів матриці системи (5.40) максимальний належить до третього рівняння. Змінюючи місцями друге та третє рівняння, отримаємо систему

Після обчислення останнє рівняння системи перетворюється на вигляд

Зворотній хід. З останнього рівняння знаходимо Далі, маємо У цьому випадку відповідь вийшла точною.

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

Обчислювальна стабільність схеми часткового вибору. Детальне дослідження методу Гауса показує, що справжньою причиною нестійкості схеми єдиного поділу є можливість необмеженого зростання елементів проміжних матриць у прямого ходу. Так як на кроці схеми часткового вибору 1, то для обчислених за формулами (5.42) елементів справедлива оцінка Отже, максимальне за модулем значення елементів матриці зростає на одному кроці не більше ніж у 2 рази і в самому несприятливому випадку крок прямого ходу дасть коефіцієнт зростання

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

Тут обчислене на ЕОМ рішення системи; його відносна похибка; число обумовленості матриці ем - машинне епсілон; нарешті, причому деяка функція, що повільно зростає, залежить від порядку системи (типу статечної функції з невеликим показником), коефіцієнт зростання.

Наявність в оцінці (5.43) множника вказує на те, що при великому схемі часткового вибору може виявитися погано обумовленою і можлива істотна втрата точності. Однак практика матричних обчислень показує, що суттєве зростання елементів матриці відбувається вкрай рідко. У переважній більшості випадків дійсне значення коефіцієнта зростання вбирається у 8-10. Якщо система добре обумовлена, то похибка обчисленого рішення виявляється, як правило, малою.

Іноді для перевірки якості наближеного рішення

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

де те саме, що і в оцінці (5.43). Зауважимо, що у нерівність (5.44) не входить кількість обумовленості.

3. Метод Гаусса із вибірок головного елемента по всій матриці (схема повного вибору).

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

На 1-му етапі методу серед елементів визначають максимальний за модулем елемент Перше рівняння системи та рівняння з номером змінюють місцями. Далі стандартним чином виключають невідомого х, з усіх рівнянь, крім першого. (що значно менше за відповідне значення для схеми часткового вибору). Підкреслимо, що досі ще не знайдено матриці, для якої повний вибір дав би значення. Таким чином, для добре обумовлених систем цей варіант методу Гауса є добре обумовленим.

Однак гарантія хорошої обумовленості досягається тут ціною значних витрат на вибір основних елементів. Для цього додатково до арифметичних дій потрібно зробити приблизно операцій порівняння, що може відчутно уповільнити процес розв'язання задачі на ЕОМ. Тому в більшості випадків на практиці перевага віддається все ж таки схемі часткового вибору. Як вже зазначено, ситуації, коли при використанні цього варіанта методу Гауса відбувається суттєве зростання елементів, трапляються надзвичайно рідко. Більше того, ці ситуації можуть бути легко виявлені за допомогою закладених у сучасних програмах ефективних методів стеження зростання елементів матриць.

4. Випадки, коли вибір основних елементів не потрібний.

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

Матриці, що задовольняють умові (5.45), такі, що в кожному з рядків модуль елемента розташованого на головній діагоналі більше суми модулів всіх інших елементів рядка.

5. Масштабування.

Перед початком рішення доцільно масштабувати систему те щоб її коефіцієнти були величинами порядку одиниці.

Існують два природні способи масштабування системи Перший полягає в множенні кожного з рівнянь на деякий множник, що масштабує Другий полягає в множенні на масштабуючий множник кожного стовпця матриці, що відповідає заміні змінних (фактично - це заміна одиниць вимірювання). У реальних ситуаціях найчастіше масштабування може бути виконано без суттєвих труднощів. Однак наголосимо, що у загальному випадку задовільного способу масштабування поки що не знайдено.

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

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

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

Метод Гауса (метод послідовного виключення невідомих) полягає в тому, що за допомогою елементарних перетворень система наводиться до еквівалентної системи східчастого вигляду. Спочатку за допомогою 1-го рівняння виключається x 1 з усіх наступних рівнянь системи. Потім за допомогою 2-го рівняння виключається x 2 з 3-го та всіх наступних рівнянь. Цей процес, званий прямим ходом методу Гауса, триває доти, доки в лівій частині останнього рівняння залишиться лише одне невідоме x n. Після цього проводиться зворотний хід методу Гауса– вирішуючи останнє рівняння, знаходимо x n; після цього, використовуючи це значення, з передостаннього рівняння обчислюємо x n-1 І т.д. Останнім знаходимо x 1 із першого рівняння.

Перетворення Гауса зручно проводити, здійснюючи перетворення з самими рівняннями, і з матрицями їх коефіцієнтів. Розглянемо матрицю:

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

Приклад 5.1.Вирішити систему методом Гауса:

Рішення. Випишемо розширену матрицю системи і, використовуючи перший рядок, після цього обнулятимемо інші елементи:

отримаємо нулі у 2-му, 3-му та 4-му рядках першого стовпця:

Тепер потрібно щоб усі елементи в другому стовпці нижче 2-го рядка дорівнювали нулю. Для цього можна помножити другий рядок на -4/7 і додати до 3-го рядка. Однак, щоб не мати справу з дробами, створимо одиницю у 2-му рядку другого стовпця і тільки

Тепер, щоб отримати трикутну матрицю, потрібно обнулити елемент четвертого рядка 3-го стовпця, для цього можна помножити третій рядок на 8/54 і додати його до четвертого. Однак щоб не мати справу з дробами поміняємо місцями 3-й і 4-й рядки і 3-й і 4-й стовпець і тільки після цього зробимо обнулення зазначеного елемента. Зауважимо, що з перестановці стовпців змінюються місцями, відповідні змінні і це пам'ятати; інші елементарні перетворення зі стовпцями (складання та множення на число) робити не можна!

Остання спрощена матриця відповідає системі рівнянь, еквівалентної вихідної:

Звідси, використовуючи зворотний хід методу Гауса, знайдемо з четвертого рівняння x 3 = -1; з третього x 4 = -2, з другого x 2 = 2 і з першого рівняння x 1 = 1. У матричному вигляді відповідь записується як

Ми розглянули випадок, коли система є певною, тобто. коли є лише одне рішення. Подивимося, що вийде, якщо система несумісна чи невизначена.

Приклад 5.2.Дослідити систему методом Гауса:

Рішення. Виписуємо та перетворюємо розширену матрицю системи

Записуємо спрощену систему рівнянь:

Тут, у останньому рівнянні вийшло, що 0=4, тобто. протиріччя. Отже, система немає рішення, тобто. вона несумісна. à

Приклад 5.3.Дослідити та вирішити систему методом Гауса:

Рішення. Виписуємо та перетворюємо розширену матрицю системи:

В результаті перетворень, в останньому рядку вийшли одні нулі. Це означає, що кількість рівнянь зменшилася на одиницю:

Отже, після спрощень залишилося два рівняння, а невідомих чотири, тобто. два невідомі "зайві". Нехай "зайвими", або, як то кажуть, вільними змінними, будуть x 3 та x 4 . Тоді

Вважаючи x 3 = 2aі x 4 = b, отримаємо x 2 = 1–aі x 1 = 2b–a; або в матричному вигляді

Записане подібним чином рішення називається загальним, оскільки, надаючи параметрам aі bрізні значення можна описати всі можливі рішення системи. à

Метод Гаусачудово підходить для вирішення систем лінійних рівнянь алгебри (СЛАУ). Він має низку переваг у порівнянні з іншими методами:

по-перше, немає потреби попередньо дослідити систему рівнянь на спільність;
по-друге, методом Гаусса можна вирішувати не тільки СЛАУ, в яких кількість рівнянь збігається з кількістю невідомих змінних та основна матриця системи невироджена, але й системи рівнянь, в яких кількість рівнянь не збігається з кількістю невідомих змінних чи визначник основної матриці дорівнює нулю;
по-третє, метод Гауса призводить до результату при порівняно невеликій кількості обчислювальних операцій.

Короткий огляд статті.

Спочатку дамо необхідні визначення та введемо позначення.

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

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

Навігація на сторінці.

Основні визначення та позначення.

Розглянемо систему з p лінійних рівнянь з n невідомими (p може дорівнювати n ):

Де – невідомі змінні, – числа (дійсні чи комплексні), – вільні члени.

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

Сукупність значення невідомих змінних , у яких всі рівняння системи перетворюються на тотожності, називається рішенням СЛАУ.

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

Якщо СЛАУ має єдине рішення, вона називається певною. Якщо рішень більше одного, то система називається невизначеною.

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

Ця система в матричній формізапису має вигляд , де - основна матриця СЛАУ; - матриця стовпець невідомих змінних; - матриця вільних членів.

Якщо до матриці А додати як (n+1)-ого стовпця матрицю-стовпець вільних членів, то отримаємо так звану розширену матрицюсистеми лінійних рівнянь Зазвичай розширену матрицю позначають буквою Т , а стовпець вільних членів відокремлюють вертикальною лінією від інших стовпців, тобто,

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

Слід зазначити наступний момент.

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

поміняти місцями два рівняння,
помножити обидві частини будь-якого рівняння на довільне та відмінне від нуля дійсне (або комплексне) число k ,
до обох частин якогось рівняння додати відповідні частини іншого рівняння, помножені на довільне число k ,

то вийде еквівалентна система, яка має такі ж рішення (або як і вихідна не має рішень).

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

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

Тепер можна переходити до опису методу Гаусса.

Рішення систем лінійних рівнянь алгебри, в яких число рівнянь дорівнює числу невідомих і основна матриця системи невироджена, методом Гаусса.

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

Деякі зробили б так.

Зауважимо, що додавши до лівої частини другого рівняння ліву частину першого, а до правої частини - праву, можна позбутися невідомих змінних x 2 і x 3 і відразу знайти x 1 :

Підставляємо знайдене значення x 1 =1 у перше та третє рівняння системи:

Якщо помножити обидві частини третього рівняння системи на -1 і додати їх до відповідних частин першого рівняння, ми позбудемося невідомої змінної x 3 і зможемо знайти x 2 :

Підставляємо отримане значення x 2 =2 в третє рівняння і знаходимо невідому змінну x 3 :

Інші вчинили б інакше.

Дозволимо перше рівняння системи щодо невідомої змінної x 1 і підставимо отриманий вираз у друге та третє рівняння системи, щоб виключити з них цю змінну:

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

З третього рівняння системи видно, що х 3 =3. З другого рівняння знаходимо , та якщо з першого рівняння отримуємо .

Знайомі способи рішення, чи не так?

Найцікавіше тут те, що другий спосіб рішення по суті і є методом послідовного виключення невідомих, тобто методом Гауса. Коли ми висловлювали невідомі змінні (спочатку x 1 , наступному етапі x 2 ) і підставляли в інші рівняння системи, тим самим виключали їх. Виняток ми проводили до того моменту, поки в останньому рівнянні не залишилася єдина невідома змінна. Процес послідовного виключення невідомих називається прямим ходом методу Гауса. Після завершення прямого ходу у нас з'являється можливість обчислити невідому змінну, яка знаходиться в останньому рівнянні. З її допомогою з передостаннього рівняння знаходимо наступну невідому змінну тощо. Процес послідовного знаходження невідомих змінних під час руху від останнього рівняння до першого називається зворотним ходом методу Гауса.

Слід зазначити, що коли ми виражаємо x 1 через x 2 і x 3 у першому рівнянні, а потім підставляємо отриманий вираз у друге та третє рівняння, то до такого ж результату наводять такі дії:

Справді, така процедура також дозволяє виключити невідому змінну x 1 із другого та третього рівнянь системи:

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

Наприклад, у СЛАУ у першому рівнянні відсутня невідома змінна x 1 (іншими словами, коефіцієнт перед нею дорівнює нулю). Тому ми можемо дозволити перше рівняння системи щодо x 1 , щоб унеможливити цю невідому змінну з інших рівнянь. Виходом із цієї ситуації є перестановка місцями рівнянь системи. Так як ми розглядаємо системи лінійних рівнянь, визначники основних матриць яких відмінні від нуля, то завжди існує рівняння, в якому є потрібна нам змінна, і ми це рівняння можемо переставити на потрібну нам позицію. Для нашого прикладу достатньо поміняти місцями перше та друге рівняння системи , Далі можна дозволити перше рівняння щодо x 1 і виключити її з інших рівнянь системи (хоча в другому рівнянні x 1 вже немає).

Сподіваємося, що суть Ви вловили.

Опишемо алгоритм методу Гауса.

Нехай нам потрібно вирішити систему з n лінійних рівнянь алгебри з n невідомими змінними виду і нехай визначник її основної матриці відмінний від нуля.

Вважатимемо, що , оскільки ми можемо цього домогтися перестановкою місцями рівнянь системи. Виключимо невідому змінну x 1 зі всіх рівнянь системи, починаючи з другого. Для цього до другого рівняння системи додамо перше, помножене на , до третього рівняння додамо перше, помножене на , і так далі, до n-го рівняння додамо перше, помножене на . Система рівнянь після таких перетворень набуде вигляду

де , а .

До такого ж результату ми дійшли б, якби висловили x 1 через інші невідомі змінні в першому рівнянні системи і отриманий вираз підставили у всі інші рівняння. Таким чином, змінна x 1 виключена зі всіх рівнянь, починаючи з другого.

Далі діємо аналогічно, але лише з частиною отриманої системи, яка зазначена на малюнку

Для цього до третього рівняння системи додамо друге, помножене на , до четвертого рівняння додамо друге, помножене на , і так далі, до n-го рівняння додамо друге, помножене на . Система рівнянь після таких перетворень набуде вигляду

де , а . Таким чином, змінна x 2 виключена зі всіх рівнянь, починаючи з третього.

Далі приступаємо до виключення невідомої x 3 при цьому діємо аналогічно з зазначеною на малюнку частиною системи

Так продовжуємо прямий хід методу Гаусса доки система не набуде вигляду

З цього моменту починаємо зворотний хід методу Гауса: обчислюємо x n з останнього рівняння як за допомогою отриманого значення x n знаходимо x n-1 з передостаннього рівняння, і так далі, знаходимо x 1 з першого рівняння.

Розберемо алгоритм з прикладу.

приклад.

методом Гауса.

Рішення.

p align="justify"> Коефіцієнт a 11 відмінний від нуля, так що приступимо до прямого ходу методу Гаусса, тобто, до виключення невідомої змінної x 1 з усіх рівнянь системи, крім першого. Для цього до лівої та правої частин другого, третього та четвертого рівняння додамо ліву та праву частини першого рівняння, помножені відповідно на , і :

Невідому змінну x 1 виключили, переходимо до виключення x 2 . До лівих та правих частин третього та четвертого рівнянь системи додаємо ліву та праву частини другого рівняння, помножені відповідно на і :

Для завершення прямого ходу методу Гауса нам залишилося виключити невідому змінну x 3 з останнього рівняння системи. Додамо до лівої та правої частин четвертого рівняння відповідно ліву та праву частину третього рівняння, помножену на :

Можна розпочинати зворотний хід методу Гаусса.

З останнього рівняння маємо ,
з третього рівняння отримуємо ,
з другого,
з першого.

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

Відповідь:

Нині ж наведемо рішення цього прикладу методом Гаусса в матричної формі записи.

приклад.

Знайдіть розв'язок системи рівнянь методом Гауса.

Рішення.

Розширена матриця системи має вигляд . Зверху над кожним стовпцем записані невідомі змінні, яким відповідають елементи матриці.

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

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

Далі отриману матрицю перетворимо так, щоб у другому стовпці всі елементи, починаючи з третього, стали нульовими. Це відповідатиме виключенню невідомої змінної x 2 . Для цього до елементів третього та четвертого рядків додамо відповідні елементи першого рядка матриці, помножені відповідно на і :

Залишилося виключити невідому змінну x 3 із останнього рівняння системи. Для цього до елементів останнього рядка отриманої матриці додамо відповідні елементи передостаннього рядка, помножені на :

Слід зазначити, що ця матриця відповідає системі лінійних рівнянь

яка була отримана раніше після прямого ходу.

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

стала діагональною, тобто, набула вигляду

де – деякі числа.

Ці перетворення аналогічні перетворенням прямого ходу методу Гаусса, але виконуються не від першого рядка до останнього, а від останнього до першого.

Додамо до елементів третього, другого та першого рядків відповідні елементи останнього рядка, помножені на , на та на відповідно:

Тепер додамо до елементів другого та першого рядків відповідні елементи третього рядка, помножені на і відповідно:

На останньому кроці зворотного ходу методу Гауса до елементів першого рядка додаємо відповідні елементи другого рядка, помножені на :

Отримана матриця відповідає системі рівнянь , звідки знаходимо невідомі змінні

Відповідь:

ЗВЕРНІТЬ УВАГУ.

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

приклад.

Розв'яжіть систему з трьох рівнянь методом Гауса .

Рішення.

Зазначимо, що в цьому прикладі невідомі змінні мають інше позначення (не x 1 x 2 x 3 а x, y, z). Перейдемо до звичайних дробів:

Виключимо невідому x з другого та третього рівнянь системи:

В отриманій системі у другому рівнянні відсутня невідома змінна y, а в третьому рівнянні y присутня, тому, переставимо місцями друге та третє рівняння:

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

Приступаємо до зворотного ходу.

З останнього рівняння знаходимо ,
з передостаннього

з першого рівняння маємо

Відповідь:

X = 10, y = 5, z = -20.

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

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

Зараз ми розберемося, як метод Гауса дозволяє встановити спільність чи несумісність системи лінійних рівнянь, а разі її спільності визначити всі рішення (чи одне єдине рішення).

У принципі, процес виключення невідомих змінних у разі таких СЛАУ залишається таким самим. Однак слід докладно зупинитись на деяких ситуаціях, які можуть виникнути.

Переходимо до найважливішого етапу.

Отже, припустимо, що система лінійних рівнянь алгебри після завершення прямого ходу методу Гаусса набула вигляду і жодне рівняння не звелося до (у цьому випадку ми зробили б висновок про несумісність системи). Виникає логічне питання: Що робити далі?

Випишемо невідомі змінні, які стоять на першому місці всіх рівнянь отриманої системи:

У прикладі це x 1 , x 4 і x 5 . У лівих частинах рівнянь системи залишаємо лише ті доданки, які містять виписані невідомі змінні x 1 , x 4 і x 5 , решту доданків переносимо у праву частину рівнянь із протилежним знаком:

Надамо невідомим змінним, які перебувають у правих частинах рівнянь, довільні значення , де - довільні числа:

Після цього у правих частинах всіх рівнянь нашої СЛАУ знаходяться числа і можна переступати до зворотного ходу методу Гаусса.

З останнього рівнянь системи маємо, з передостаннього рівняння знаходимо, з першого рівняння отримуємо

Рішенням системи рівнянь є сукупність значень невідомих змінних

Надаючи числам різні значення, ми будемо отримувати різні рішення системи рівнянь. Тобто наша система рівнянь має безліч рішень.

Відповідь:

де - Довільні числа.

Для закріплення матеріалу докладно розберемо рішення ще кількох прикладів.

приклад.

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

Рішення.

Виключимо невідому змінну x з другого та третього рівнянь системи. Для цього до лівої та правої частини другого рівняння додамо відповідно ліву та праву частини першого рівняння, помножені на , а до лівої та правої частини третього рівняння - ліву та праву частини першого рівняння, помножені на :

Тепер виключимо y із третього рівняння отриманої системи рівнянь:

Отримана СЛАУ рівносильна системі .

Залишаємо в лівій частині рівнянь системи тільки доданки, що містять невідомі змінні x і y, а доданки з невідомою змінною z переносимо в праву частину: