Метод Гаусса для чайників: приклади рішень

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

Що означає вирішити методом Гаусса?

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

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

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

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

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

Матриці, їхні властивості

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

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

Матриця має розмір. Її «ширина» - число рядків (m), «довжина» - число стовпчиків (n). Тоді розмір матриці A (для їх позначення зазвичай використовуються заголовні латинські літери) буде позначатися як A_{m ст.1n}. Якщо m = n, то ця матриця квадратна, і m = n - її порядок. Відповідно, будь-який елемент матриці A можна позначити через номер його рядка і стовпчика: a_xy; x - номер рядка, змінюється [1, m], y - номер стовпчика, змінюється [1, n].

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

Визначник

Ще у матриці є визначник. Це дуже важлива характеристика. З'ясовувати його сенс зараз не варто, можна просто показати, як він обчислюється, а потім розповісти, які властивості матриці він визначає. Найбільш простий спосіб знаходження визначника - через діагоналі. У матриці проводяться уявні діагоналі; елементи, що знаходяться на кожній з них, перемножуються, а потім отримані твори складаються: діагоналі з нахилом вправо - зі знаком «» плюс «», з нахилом вліво - зі знаком «» мінус «».

Вкрай важливо відзначити, що обчислювати визначник можна тільки у квадратної матриці. Для прямокутної матриці можна зробити наступне: з кількості рядків і кількості стовпчиків вибрати найменше (нехай це буде k), а потім у матриці довільним чином відзначити k стовпчиків і k рядків. Елементи, що знаходяться на перетині вибраних стовпчиків і рядків, складуть нову квадратну матрицю. Якщо визначник такої матриці буде числом, відмінним від нуля, то назветься базисним мінором первісної прямокутної матриці.

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

Класифікація систем

Існує таке поняття, як ранг матриці. Це максимальний порядок її визначника, відмінного від нуля (якщо згадати про базисний мінор, можна сказати, що ранг матриці - порядок базисного мінора).

По тому, як йдуть справи з рангом, СЛАУ можна розділити на:

• Спільні. У спільних системах ранг основної матриці (що складається тільки з коефіцієнтів) збігається з рангом розширеною (зі стовпчиком вільних членів). Такі системи мають рішення, але необов'язково одне, тому додатково спільні системи ділять на:
• - певні - мають єдине рішення. У певних системах дорівнює ранг матриці і кількість невідомих (або число стовпчиків, що є одне і те ж);
• - невизначені - з нескінченною кількістю рішень. Ранг матриць у таких систем менше кількості невідомих.
• Несумісні. У таких систем ранги основної і розширеної матриць не збігаються. Несумісні системи рішення не мають.

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

Елементарні перетворення

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

1. Перестановка рядків. Очевидно, що якщо в записі системи поміняти порядок рівнянь, то на рішення це ніяк не вплине. Отже, в матриці цієї системи також можна міняти місцями рядки, не забуваючи, звичайно, про стовпчик вільних членів.
2. Множення всіх елементів рядка на певний коефіцієнт. Дуже корисно! За допомогою нього можна скоротити великі числа в матриці або прибрати нулі. Безліч рішень, як зазвичай, не зміниться, а виконувати подальші операції стане зручніше. Головне, щоб коефіцієнт не дорівнював нулю.
3. Вилучення рядків з пропорційними коефіцієнтами. Це частково випливає з попереднього пункту. Якщо два або більше рядка матриці мають пропорційні коефіцієнти, то при множенні/ділення одного з рядків на коефіцієнт пропорційності отримуються два (або, знову ж таки, більше) абсолютно однакові рядки, і можна прибрати зайві, залишивши тільки один.
4. Вилучення нульового рядка. Якщо під час перетворень десь вийшов рядок, в якому всі елементи, включаючи вільний член, - нуль, то такий рядок можна назвати нульовим і викинути з матриці.
5. Додавання до елементів одного рядка елементів іншого (за відповідними стовпчиками), помножених на деякий коефіцієнт. Найбільш неочевидне і найважливіше перетворення з усіх. На ньому варто зупинитися детальніше.

Додавання рядка, помноженого на коефіцієнт

Для простоти розуміння варто розібрати цей процес за кроками. Беруться два рядки з матриці:

a₁₁ a₁₂ ... a_1n | b1

a₂₁ a₂₂ ... a_2n | b₂

Припустимо, необхідно до другої додати першу, помножену на коефіцієнт «» -2 «».

a'₂₁ = a₂₁ + -2×a₁₁

a'₂₂ = a₂₂ + -2×a₁₂

...

a'_2n = a_2n + -2×a_1n

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

a₁₁ a₁₂ ... a_1n | b1

a'₂₁ a'₂₂ ... a'_2n | b₂

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

У загальному вигляді

Нехай існує система. Вона має m рівнянь і n коріння-невідомих. Записати її можна наступним чином:

З коефіцієнтів системи складається основна матриця. До розширеної матриці додається стовпчик вільних членів і для зручності відокремлюється рисою.

Далі:

• перший рядок матриці множиться на коефіцієнт k = (-a₂₁/a₁₁);
• перший змінений рядок і другий рядок матриці складаються;
• замість другого рядка в матрицю вставляється результат додавання з попереднього пункту;
• тепер перший коефіцієнт у новому другому рядку дорівнює a₁₁ ст.1( -a₂₁/a₁₁) + a₂₁ = -a₂₁ + a₂₁ = 0.

Тепер виконується та ж серія перетворень, тільки беруть участь перший і третій рядки. Відповідно, в кожному кроці алгоритму елемент a₂₁ замінюється на a₃₁. Потім все повторюється для a₄₁,... a_m1. У результаті виходить матриця, де в рядках [2, m] перший елемент дорівнює нулю. Тепер потрібно забути про рядок номер один і виконати той же алгоритм, починаючи з другого рядка:

• коефіцієнт k = (-a₃₂/a₂₂);
• з «поточним» рядком складається другий змінений рядок;
• результат додавання підставляється в третій, четвертий і так далі рядки, а перший і другий залишаються незмінними;
• у рядках [3, m] матриці вже два перших елементи дорівнюють нулю.

Алгоритм треба повторювати, поки не з'явиться коефіцієнт k = (-a_{m, m-1}/a_mm). Це означає, що востаннє алгоритм виконувався тільки для нижнього рівняння. Тепер матриця схожа на трикутник, або має ступеневу форму. У нижній рядку є рівність a_mn ^ x_n = b_m. Коефіцієнт і вільний член відомі, і корінь виражається через них: x_n = b_m/a_mn. Отриманий корінь підставляється у верхній рядок, щоб знайти x_n-1 = (b_m-1 - a_{m-1, n} ­ (b_m/a_mn)) ­ a_{m-1, n-1}. І так далі за аналогією: у кожному наступному рядку знаходиться новий корінь, і, діставшись до "верху" "системи, можна відшукати безліч рішень [x₁,... x_n]. Воно буде єдиним.

Коли немає рішень

Якщо в одному з матричних рядків всі елементи, крім вільного члена, дорівнюють нулю, то рівняння, що відповідає цьому рядку, виглядає як 0 = b. Воно не має рішення. І оскільки таке рівняння укладено в систему, то і безліч рішень всієї системи - порожнє, тобто вона є виродженою.

Коли рішення нескінченна кількість

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

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

Для зручності матриця спочатку переписується назад у систему рівнянь. Потім в останньому з них, там, де точно залишилася тільки одна базисна змінна, вона залишається з одного боку, а все інше переноситься в інший. Так робиться для кожного рівняння з однією базисною змінною. Потім в інші рівняння, там, де це можливо, замість базисної змінної підставляється отриманий для неї вираз. Якщо в результаті знову з'явився вираз, що містить тільки одну базисну змінну, він звідти знову виражається, і так далі, поки кожна базисна змінна не буде записана у вигляді виразу з вільними змінними. Це і є спільне рішення СЛАУ.

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

Рішення на конкретних прикладах

Ось система рівнянь.

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

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

Далі необхідно так змінити другий і третій рядки, щоб перші елементи стали нулями. Для цього треба скласти їх з першої, помноженої їх на коефіцієнт:

другий рядок: k = (-a₂₁/a₁₁) = (-3/1) = -3

a'₂₁ = a₂₁ + k×a₁₁ = 3 + (-3)×1 = 0

a'₂₂ = a₂₂ + k×a₁₂ = -1 + (-3)×2 = -7

a'₂₃ = a₂₃ + k×a₁₃ = 1 + (-3)×4 = -11

b'₂ = b₂ + k×b₁ = 12 + (-3)×12 = -24

третій рядок: k = (-a₃₁/a₁₁) = (-5/1) = -5

a'₃₁ = a₃₁ + k×a₁₁ = 5 + (-5)×1 = 0

a'₃₂ = a₃₂ + k×a₁₂ = 1 + (-5)×2 = -9

a'₃₃ = a₃₃ + k×a₁₃ = 2 + (-5)×4 = -18

b'₃= b₃ + k×b₁ = 3 + (-5)×12 = -57

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

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

Варто також зауважити, що в третьому рядку всі елементи кратні трьом. Тоді можна скоротити рядок на це число, множачи кожен елемент на «-1/3» (мінус - заодно, щоб прибрати від'ємні значення).

Виглядає набагато приємніше. Тепер треба залишити в спокої перший рядок і попрацювати з другого і третього. Завдання - додати до третього рядка другий, помножену на такий коефіцієнт, щоб елемент a₃₂ став дорівнювати нулю.

k = (-a₃₂/a₂₂) = (-3/7) = -3/7 (якщо під час деяких перетворень у відповіді вийшло не ціле число, рекомендується для дотримання точності обчислень залишити його «» як є «», у вигляді звичайного дробу, а вже потім, коли отримані відповіді, вирішувати, чи варто округляти і переводити в іншу форму запису)

a'₃₂ = a₃₂ + k×a₂₂ = 3 + (-3/7)×7 = 3 + (-3) = 0

a'₃₃ = a₃₃ + k×a₂₃ = 6 + (-3/7)×11 = -9/7

b'₃ = b₃ + k×b₂ = 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

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

x₁ = -2/3, y = -65/9, z = 61/9.

Приклад невизначеної системи

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

х₁ + х₂ + х₃ + х₄ + х₅ = 7 (1)

3х₁ + 2х₂ + х₃ + х₄ - 3х₅ = -2 (2)

х₂ + 2х₃ + 2х₄ + 6х₅ = 23 (3)

5х₁ + 4х₂ + 3х₃ + 3х₄ - х₅ = 12 (4)

Сам вид системи вже насторожує, тому що кількість невідомих n = 5, а ранг матриці системи вже точно менше цього числа, тому що кількість рядків m = 4, тобто найбільший порядок визначника-квадрата - 4. Значить, рішень існує нескінченне безліч, і треба шукати його загальний вигляд. Метод Гаусса для лінійних рівнянь дозволяє це зробити.

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

Другий рядок: коефіцієнт k = (-a₂₁/a₁₁) = -3. У третьому рядку перший елемент - ще до перетворень, тому не треба нічого чіпати, треба залишити як є. Четвертий рядок: k = (-а₄₁/а₁₁) = -5

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

Як можна бачити, другий, третій і четвертий рядки складаються з елементів, пропорційних один одному. Друга і четверта взагалі однакові, тому одну з них можна прибрати відразу, а решту помножити на коефіцієнт «» -1 «» і отримати рядок номер 3. І знову з двох однакових рядків залишити один.

Вийшла така матриця. Поки ще не записана система, потрібно тут визначити базисні змінні - що стоять при коефіцієнтах a₁₁ = 1 і a₂₂ = 1, і вільні - всі інші.

У другому рівнянні є лише одна базисна змінна - x₂. Отже, її можна висловити звідти, записавши через змінні x₃, x₄, x₅, що є вільними.

Підставляємо отриманий вираз у перше рівняння.

Вийшло рівняння, в якому єдина базисна змінна - x₁. Зробимо з нею те ж, що і з x₂.

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

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

-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

І приводиться до ступеневого вигляду:

k₁ = -2k₂ = -4

1	1	-1	0
0	-3	1	-2
0	0	0	7

Після першого перетворення в третьому рядку міститься рівняння вигляду

0 = 7,

не має рішення. Отже, система несумісна, і відповіддю буде порожня безліч.

Переваги і недоліки методу

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

Застосування

Оскільки рішення методом Гаусса являє собою алгоритм, а матриця - це, фактично, почесний масив, його можна використовувати при програмуванні. Але оскільки стаття позиціонує себе, як керівництво «» для чайників «», слід сказати, що найпростіше, куди метод можна запхати - це електронні таблиці, наприклад, Excel. Знову ж таки, всякі СЛАУ, занесені в таблицю у вигляді матриці, Excel буде розглядати як почесний масив. А для операцій з ними існує безліч приємних команд: додавання (складати можна тільки матриці однакових розмірів!), множення на число, перемноження матриць (також з певними обмеженнями), знаходження зворотної і транспонованої матриць і, найголовніше, обчислення визначника. Якщо це трудомістке заняття замінити однією командою, можна набагато швидше визначати ранг матриці і, отже, встановлювати її сумісність або несумісність.