У даній статті метод розглядається як спосіб розв’язання систем лінійних рівнянь (СЛАР). Метод є аналітичним, тобто дозволяє написати алгоритм розв’язання в загальному вигляді, а потім вже підставляти туди значення з конкретних прикладів. На відміну від матричного методу або формул Крамера, при розв’язанні системи лінійних рівнянь методом Гаусса можна працювати і з тими, що мають нескінченно багато рішень. Або не мають його зовсім.
Що означає розв’язати методом Гаусса?
Для початку необхідно нашу систему рівнянь записати у вигляді матриці. Виглядає це наступним чином. Береться система:
Коефіцієнти записуються у вигляді таблиці, а праворуч окремим стовпчиком – вільні члени. Стовпець з вільними членами відділяється для зручності вертикальною рискою. Матриця, що включає в себе цей стовпець, називається розширеною.
Далі основну матрицю з коефіцієнтами потрібно привести до верхньої трикутної форми. Це основний момент рішення системи методом Гаусса. Простіше кажучи, після певних маніпуляцій матриця повинна виглядати так, щоб у її лівій нижній частині стояли одні нулі:
Тоді, якщо записати нову матрицю знову як систему рівнянь, можна помітити, що в останньому рядку вже міститься значення одного з коріння, яке потім підставляється в рівняння вище, знаходиться ще один корінь, і так далі.
Це опис розв’язання методом Гаусса в самих загальних рисах. А що вийде, якщо раптом у системи немає рішення? Або їх нескінченно багато? Щоб відповісти на ці та ще безліч питань, які необхідно розглянути окремо всі елементи, що використовуються при вирішенні методом Гаусса.
Матриці, їх властивості
Ніякого прихованого змісту в матриці немає. Це просто зручний спосіб запису даних для подальших операцій з ними. Боятися їх не треба навіть школярам.
Матриця завжди прямокутна, тому що так зручніше. Навіть у методі Гаусса, де все зводиться до побудови матриці трикутного вигляду, в запису фігурує прямокутник, тільки з нулями на тому місці, де немає чисел. Нулі можна не записувати, але вони маються на увазі.
Матриця має розмір. Її ширина – число рядків (m), “довжина” – число стовпців (n). Тоді розмір матриці A (для їх позначення зазвичай використовуються великі латинські літери) буде позначатися як Am×n. Якщо m=n, то ця матриця квадратна, і m=n – її порядок. Відповідно, будь-який елемент матриці A можна позначити через його номер рядка та стовпця: axy; x – номер рядка, змінюється [1, m], y – номер стовпця, змінюється [1, n].
У методі Гаусса матриці – це не основний момент рішення. В принципі, всі операції можна виконувати безпосередньо з самими рівняннями, проте запис вийде куди більш громіздка, і в ній буде набагато легше заплутатися.
Визначник
Ще у матриці є визначник. Це дуже важлива характеристика. З’ясовувати його сенс зараз не варто, можна просто показати, як він обчислюється, а потім розповісти, які властивості матриці він визначає. Найбільш простий спосіб знаходження визначника – через діагоналі. У матриці проводяться уявні діагоналі; елементи, що знаходяться на кожній з них, перемножуються, а потім отримані твори складаються: діагоналі з нахилом вправо – зі знаком “плюс”, з нахилом вліво – зі знаком “мінус”.
Вкрай важливо відзначити, що обчислювати визначник можна тільки у квадратної матриці. Для прямокутної матриці можна зробити наступне: з кількості кількості рядків і стовпців вибрати найменше (нехай це буде k), а потім в матриці довільним чином відзначити k k рядків і стовпців. Елементи, що знаходяться на перетині виділених рядків і стовпців та складуть нову квадратну матрицю. Якщо такий визначник матриці буде числом, відмінним від нуля, то називається базисним мінором первісної прямокутної матриці.
Перед тим як приступити до розв’язання системи рівнянь методом Гауса, не заважає порахувати визначник. Якщо він виявиться нульовим, то відразу можна говорити, що у матриці кількість рішень або нескінченно, або їх взагалі немає. В такому сумному випадку треба йти далі і дізнаватися про ранг матриці.
Класифікація систем
Існує таке поняття, як ранг матриці. Це максимальний порядок її визначника, відмінного від нуля (якщо згадати про базисний мінор, можна сказати, що ранг матриці – порядок базисного мінору).
По тому, як йдуть справи з рангом, СЛАР можна розділити на:
- Спільні. У спільних систем ранг основної матриці (складається тільки з коефіцієнтів) збігається з рангом розширеної (зі стовпцем вільних членів). Такі системи мають рішення, але необов’язково одне, тому додатково спільні системи поділяють на:
- – певні – мають єдине рішення. У певних системах рівні ранг матриці і кількість невідомих (або кількість стовпців, що є одне і те ж);
- – невизначені – з нескінченною кількістю рішень. Ранг матриці у таких систем менше кількості невідомих.
- Несумісні. У таких систем ранги основної і розширеної матриць не збігаються. Несумісні системи рішення не мають.
Метод Гаусса хороший тим, що дозволяє в ході вирішення отримати однозначне доказ несумісних системи (без обчислення визначників великих матриць), або рішення в загальному вигляді для системи з нескінченним числом рішень.
Елементарні перетворення
До того як приступити безпосередньо до вирішення системи, можна зробити її менш громіздкою і більш зручною для обчислень. Це досягається за рахунок елементарних перетворень – таких, що їх виконання ніяк не змінює кінцевий відповідь. Слід зазначити, що деякі з наведених елементарних перетворень дійсні тільки для матриць, першоджерелом яких послужили саме СЛАР. Ось список цих перетворень:
Додавання рядка, помноженого на коефіцієнт
Для простоти розуміння варто розібрати цей процес по кроках. Беруться два рядки з матриці:
a11 a12 … a1n | b1
a21 a22 … a2n | b2
Припустимо, необхідно до другої додати першу, помножену на коефіцієнт “-2”.
a’21 = a21 + -2×a11
a’22 = a22 + -2×a12
…
‘2n = a2n + -2×a1n
Потім в матриці друга рядок замінюється на нову, а перша залишається без змін.
a11 a12 … a1n | b1
a’21 a’22 … ‘2n | b2
Необхідно зауважити, що коефіцієнт множення можна підібрати таким чином, щоб у результаті складання двох рядків один з елементів нової рядки був рівний нулю. Отже, можна одержати рівняння в системі, де на одну невідому буде менше. А якщо отримати два таких рівняння, то операцію можна проробити ще раз і отримати рівняння, яке буде містити вже на дві невідомих менше. А якщо кожен раз перетворювати у нуль один коефіцієнт у всіх рядків, що стоять нижче вихідної, то можна, як по сходинках, спуститися до самого низу матриці і отримати рівняння з однією невідомою. Це і називається розв’язати систему методом Гаусса.
В загальному вигляді
Нехай існує система. Вона має m рівнянь і n коренів-невідомих. Записати її можна наступним чином:
З коефіцієнтів системи складається основна матриця. В розширену матрицю додається стовпець вільних членів і для зручності відділяється рисою.
Далі:
- перший рядок матриці множиться на коефіцієнт k = (-a21/a11);
- перша змінений рядок і другий рядок матриці складаються;
- замість другого рядка в матрицю вставляється результат додавання з попереднього пункту;
- тепер перший коефіцієнт у новій другий рядку дорівнює a11 × (-a21/a11) + a21 = -a21 + a21 = 0.
Тепер виконується та ж серія перетворень, тільки беруть участь перша і третя рядка. Відповідно, в кожному кроці алгоритму елемент a21 замінюється на a31. Потім все повторюється для a41, … am1. У результаті виходить матриця, де в рядках [2, m] перший елемент дорівнює нулю. Тепер треба забути про рядку номер один і виконати той же алгоритм, починаючи з другого рядка:
- коефіцієнт k = (-a32/a22);
- з “поточної” рядком складається друга змінений рядок;
- результат додавання підставляється в третю, четверту і так далі рядка, а перша і друга залишаються незмінними;
- у рядках [3, m] матриці вже два перших елемента дорівнюють нулю.
Алгоритм треба повторювати, поки не з’явиться коефіцієнт k = (-ам,m-1/amm). Це означає, що в останній раз алгоритм виконувався тільки для нижнього рівняння. Тепер матриця схожа на трикутник, або має ступінчасту форму. У нижній сходинці є рівність amn × xn = bm. Коефіцієнт і вільний член відомі, і корінь виражається через них: xn = bm/amn. Отриманий корінь підставляється у верхній рядок, щоб знайти xn-1 = (bm-1 – am-1,n×(bm/amn))÷am-1,n-1. І так далі по аналогії: в кожному наступному рядку знаходиться новий корінь, і, діставшись до “верху” системи, можна відшукати безліч рішень [x1, … xn]. Воно буде єдиним.
Коли немає рішень
Якщо в одного з матричних рядків всі елементи, крім вільного члена, дорівнюють нулю, то рівняння, відповідне цьому рядку, виглядає як 0 = b. Воно не має рішення. І оскільки таке рівняння укладена в систему, то і безліч рішень всієї системи – пусте, тобто вона є вырожденной.
Коли рішень нескінченну кількість
Може вийти так, що в наведеній трикутної матриці немає рядків з одним елементом-коефіцієнтом рівняння, і одним – вільним членом. Є тільки такі рядки, які при переписуванні мали б вигляд рівняння з двома або більше змінними. Значить, у системи є нескінченне число рішень. У такому разі відповідь можна дати у вигляді спільного рішення. Як це зробити?
Всі змінні в матриці поділяються на базисні та вільні. Базисні – це ті, які стоять “з краю” рядків у ступінчастої матриці. Решта – вільні. В загальному рішенні базисні змінні записуються через вільні.
Для зручності матриця спочатку переписується назад в систему рівнянь. Потім в останньому з них, там, де точно залишилася тільки одна базисна змінна, вона залишається з одного боку, а все інше переноситься в іншу. Так робиться для кожного рівняння з однієї базисної змінної. Потім в інші рівняння, там, де це можливо, замість базисної змінної підставляється отримане для неї вираз. Якщо в результаті знову з’явилося вираз, який містить тільки одну базисну змінну, вона звідти знову виражається, і так далі, поки кожна базисна змінна не буде записана у вигляді виразу з вільними змінними. Це і є загальний розв’язок СЛАР.
Можна також знайти базисне рішення системи – дати вільним змінним будь-які значення, а потім для цього конкретного випадку порахувати значення базисних змінних. Приватних рішень можна навести нескінченно багато.
Рішення на конкретних прикладах
Ось система рівнянь.
Для зручності краще відразу скласти її матрицю
Відомо, що при вирішенні методом Гаусса рівняння, відповідне першому рядку, в кінці перетворень залишиться незмінним. Тому вигідніше буде, якщо лівий верхній елемент матриці буде найменшим – тоді перші елементи інших рядків після операцій звернуться в нуль. Значить, складеної матриці вигідно буде на місце першого рядка поставити другу.
Далі слід так змінити другу і третю рядка, щоб перші елементи стали нулями. Для цього треба скласти їх з першою, помноженої їх на коефіцієнт:
другий рядок: k = (-a21/a11) = (-3/1) = -3
a’21 = a21 + k×a11 = 3 + (-3)×1 = 0
a’22 = a22 + k×a12 = -1 + (-3)×2 = -7
a’23 = a23 + k×a13 = 1 + (-3)×4 = -11
b’2 = b2 + k×b1 = 12 + (-3)×12 = -24
третій рядок: k = (-a31/a11) = (-5/1) = -5
a’31 = a31 + k×a11 = 5 + (-5)×1 = 0
a’32 = a32 + k×a12 = 1 + (-5)×2 = -9
a’33 = a33 + k×a13 = 2 + (-5)×4 = -18
b’3= b3 + k×b1 = 3 + (-5)×12 = -57
Тепер, щоб не заплутатися, необхідно записати матрицю з проміжними результатами перетворень.
Очевидно, що таку матрицю можна зробити більш зручною для сприйняття з допомогою деяких операцій. Наприклад, із другого рядка можна прибрати всі “мінуси”, множачи кожен елемент на “-1”.
Варто також зауважити, що в третьому рядку всі елементи кратні трьом. Тоді можна скоротити рядок на це число, множачи кожен елемент на “-1/3” (мінус – заодно, щоб прибрати негативні значення).
Виглядає набагато приємніше. Тепер треба залишити в спокої перший рядок і попрацювати з другої і третьої. Завдання – додати до третьої рядку другу, помножену на такий коефіцієнт, щоб елемент a32 став дорівнює нулю.
k = (-a32/a22) = (-3/7) = -3/7 (якщо в ході деяких перетворень у відповіді вийшло не ціле число, рекомендується для дотримання точності обчислень залишити його “як є”, у вигляді звичайного дробу, а вже потім, коли отримані відповіді, вирішувати, чи варто округляти і перекладати в іншу форму запису)
a’32 = a32 + k×a22 = 3 + (-3/7)×7 = 3 + (-3) = 0
a’33 = a33 + k×a23 = 6 + (-3/7)×11 = -9/7
b’3 = b3 + k×b2 = 19 + (-3/7)×24 = -61/7
Знову записується матриця з новими значеннями.
| 1 | 2 | 4 | 12 |
| 0 | 7 | 11 | 24 |
| 0 | 0 | -9/7 | -61/7 |
Як видно, отримана матриця вже має ступінчастий вигляд. Тому подальші перетворення системи за методом Гауса не потрібні. Що тут можна зробити, так це прибрати з третього рядка загальний коефіцієнт “-1/7”.
Тепер все красиво. Справа за малим – записати матрицю знову у вигляді системи рівнянь і обчислити корені
x + 2y + 4z = 12 (1)
7y + 11z = 24 (2)
9z = 61 (3)
Той алгоритм, за яким зараз будуть перебувати коріння, називається зворотним ходом методу Гауса. В рівнянні (3) міститься значення z:
z = 61/9
Далі повертаємося до другого рівняння:
y = (24 – 11×(61/9))/7 = -65/9
І перше рівняння дозволяє знайти x:
x = (12 – 4z – 2y)/1 = 12 – 4×(61/9) – 2×(-65/9) = -6/9 = -2/3
Таку систему ми маємо право назвати спільної, та ще і визначеною, тобто має єдине рішення. Відповідь записується в наступній формі:
x1 = -2/3, y = -65/9, z = 61/9.
Приклад невизначеної системи
Варіант вирішення певної системи методом Гаусса розібраний, тепер необхідно розглянути випадок, якщо система невизначена, тобто для неї можна знайти нескінченно багато рішень.
х1 + х2 + х3 + х4 + х5 = 7 (1)
3х1 + 2х2 + х3 + х4 – 3х5 = -2 (2)
х2 + 2х3 + 2х4 + 6х5 = 23 (3)
5х1 + 4х2 + 3х3 + 3х4 – х5 = 12 (4)
Сам вигляд системи вже насторожує, тому що кількість невідомих n = 5, а ранг матриці системи вже точно менше цього числа, тому що кількість рядків m = 4, тобто найбільший порядок визначника-квадрата – 4. Значить, рішень існує нескінченна безліч, і треба шукати його загальний вигляд. Метод Гаусса для лінійних рівнянь дозволяє це зробити.
Спочатку, як зазвичай, складається розширена матриця.
Другий рядок: коефіцієнт k = (-a21/a11) = -3. У третьому рядку перший елемент – ще до перетворень, тому не треба нічого чіпати, треба залишити як є. Четвертий рядок: k = (-а41/а11) = -5
Помноживши елементи першого рядка на кожен їх коефіцієнтів по черзі і склавши їх з відповідними рядками, отримуємо матрицю такого вигляду:
Як можна бачити, друга, третя і четверта рядки складаються з елементів, пропорційні один одному. Друга і четверта взагалі однакові, тому одну з них можна видалити відразу, а решту помножити на коефіцієнт “-1” і отримати рядок номер 3. І знову з двох однакових рядків залишити одну.
Вийшла така матриця. Поки ще не записана система, тут потрібно визначити базисні змінні – стоять при коефіцієнтах a11 = 1 і a22 = 1, і вільні – всі інші.
У другому рівнянні є тільки одна базисна змінна x2. Значить, її можна виразити звідти, записавши через змінні x3, x4, x5, які є вільними.
Підставляємо отримане вираження в перше рівняння.
Вийшло рівняння, в якому єдина базисна змінна x1. Проробимо з нею те ж, що і з x2.
Всі базисні змінні, яких дві, виражені через три вільні, тепер можна записувати відповідь у загальному вигляді.
Також можна вказати одне з приватних рішень системи. Для таких випадків в якості значень вільних змінних вибирають, як правило, нулі. Тоді відповіддю буде:
-16, 23, 0, 0, 0.
Приклад несовместной системи
Рішення несумісних систем рівнянь методом Гауса – найшвидше. Воно закінчується відразу ж, як тільки на одному з етапів виходить рівняння, що не має рішення. Тобто етап з обчисленням коренів, досить довгий і тоскний, відпадає. Розглядається наступна система:
x + y – z = 0 (1)
2x – y – z = -2 (2)
4x + y – 3z = 5 (3)
Як зазвичай, складається матриця:
| 1 | 1 | -1 | 0 |
| 2 | -1 | -1 | -2 |
| 4 | 1 | -3 | 5 |
І приводиться до ступінчастому увазі:
k1 = -2k2 = -4
| 1 | 1 | -1 | 0 |
| 0 | -3 | 1 | -2 |
| 0 | 0 | 0 | 7 |
Після першого ж перетворення в третьому рядку міститься рівняння вигляду
0 = 7,
не має рішення. Отже, система несовместна, і відповіддю буде порожня множина.
Переваги і недоліки методу
Якщо вибирати, яким методом розв’язувати СЛАР на папері ручкою, то метод, який був розглянутий у цій статті, виглядає найбільш привабливо. В елементарних перетвореннях набагато важче заплутатись, ніж в тому трапляється, якщо доводиться шукати вручну визначник або якусь хитру зворотну матрицю. Однак, якщо використовувати програми для роботи з даними такого типу, наприклад, електронні таблиці, то виявляється, що у таких програмах вже закладені алгоритми обчислення основних параметрів матриць – визначник, мінори, зворотна і транспонована матриці і так далі. А якщо бути впевненим в тому, що машина вважатиме ці значення сама і не помилиться, доцільніше використовувати матричний метод або формул Крамера, тому що їх застосування починається і закінчується обчисленням визначників і зворотними матрицями.
Застосування
Оскільки рішення методом Гаусса являє собою алгоритм, а матриця – це, фактично, двовимірний масив, його можна використовувати при програмуванні. Але оскільки стаття позиціонує себе, як керівництво “для чайників”, слід сказати, що найпростіше, куди метод можна запхати – це електронні таблиці, наприклад, Excel. Знову ж, всякі СЛАУ, занесені в таблицю у вигляді матриці, Excel буде розглядати як двовимірний масив. А для операцій з ними існує безліч приємних команд: додавання (складати можна лише матриці однакових розмірів!), множення на число, множення матриць (також з певними обмеженнями), знаходження оберненої і транспонованої матриці і, найголовніше, обчислення визначника. Якщо це трудомістке заняття замінити однією командою, можна набагато швидше визначати ранг матриці і, отже, встановлювати спільність або несовместность.
