Системи лінійних рівнянь

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

Означення системи лінійних рівнянь

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

$$ \begin{array}{ccccc} a_{11}x &+&a_{12}y &=& b_1\\ a_{21}x &+&a_{22}y &=&b_2\\ \end{array} $$

де $a_{11},…,a_{22}, b_1, b_2$ — задані дійсні числа, а x і y — змінні. Така система може мати різну кількість розв'язків — жодного, один або нескінченно багато, як і звичайне лінійне рівняння. Однак для системи лінійних рівнянь питання про кількість розв'язків і про їх пошук складніше, ніж для одного лінійного рівняння.

Означення системи лінійних рівнянь:

$$ \begin{array}{ccccccccc} a_{11}x_1&+&a_{12}x_2&+&\ldots&+&a_{1n}x_n&=&b_1\\ a_{21}x_1&+&a_{22}x_2&+&\ldots&+&a_{2n}x_n&=&b_2\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ a_{m1}x_1&+&a_{m2}x_2&+&\ldots&+&a_{mn}x_n&=&b_m\\ \end{array} $$

де $a_{11}, …, a_{mn}, b_1, …, b_m$ — дійсні числа. Таку систему називаємо системою m лінійних рівнянь із n невідомими x₁, …, x_n та коефіцієнтами $a_{11}, …, a_{mn}$. Конкретний приклад системи лінійних рівнянь може виглядати так:

$$ \begin{array}{ccccccccc} 3x_1&+&-2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&+&4x_2&+&2x_3&+&-10x_4&=&2\\ 11x_1&+&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

Якщо ж якесь a_ij від'ємне, прийнято писати так:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&+&4x_2&+&2x_3&-&10x_4&=&2\\ 11x_1&+&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

Проте й далі a₁₂ = −2 та a₂₄ = −10.

Матричний запис

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

$$ A= \begin{pmatrix} a_{11}&a_{12}&…&a_{1n}\\ a_{21}&a_{22}&…&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&…&a_{mn} \end{pmatrix}, \quad b= \begin{pmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{pmatrix}, \quad x= \begin{pmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{pmatrix} $$

Матриця A містить коефіцієнти початкових рівнянь, і ми називаємо її «матрицею системи», матриця b містить праві частини рівнянь, а матриця x — змінні. Тоді всю систему рівнянь можна записати як одне рівняння

$$Ax,=,b$$

Це рівняння має сенс, бо ліворуч маємо добуток двох матриць, а праворуч — матрицю, причому їхні розміри збігаються. Спробуймо помножити ліву частину. Множимо матрицю типу m × n на матрицю типу n × 1, тож результат буде матрицею типу m × 1: m рядків і один стовпець. Поки що все гаразд.

Тепер виконаймо класичний алгоритм множення матриць: візьмемо перший рядок матриці A і перший стовпець матриці x (іншого стовпця там немає). Отримаємо:

$$a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n$$

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

$$a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n = b_1$$

Ми отримали саме перше рівняння нашої системи. Так само діємо для решти рядків. Означимо ще розширену матрицю системи — це матриця системи, до якої дописано матрицю b ось так:

$$ B=(A|b)= \begin{pmatrix} a_{11}&a_{12}&…&a_{1n}&b_1\\ a_{21}&a_{22}&…&a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{m1}&a_{m2}&…&a_{mn}&b_m \end{pmatrix} $$

Далі нас цікавитиме ранг цієї розширеної матриці системи. Ранг початкової, нерозширеної матриці системи позначимо $\operatorname{rank}(A)$, ранг розширеної — $\operatorname{rank}(A|b)$. Який зв'язок між цими рангами? Якщо до матриці A дописати стовпець b, можливі дві ситуації: якщо цей новий стовпець є лінійною комбінацією стовпців матриці A, ранг не зміниться. Якщо ж він не був лінійною комбінацією, ранг буде на одиницю більшим.

Теорема Кронекера–Капеллі

Ранг розширеної матриці буде для нас важливим, бо справджується важлива теорема — теорема Кронекера–Капеллі (в чеській літературі її називають теоремою Фробеніуса): Система рівнянь Ax = b має розв'язок тоді й лише тоді, коли ранг матриці системи дорівнює рангу розширеної матриці системи: $\operatorname{rank}(A) = \operatorname{rank}(A|b)$.

Спробуймо показати, що ця теорема справджується принаймні в одному напрямку: якщо x = β є розв'язком рівняння Ax = b, то $\operatorname{rank}(A) = \operatorname{rank}(A|b)$. Щоб ці ранги були рівні, стовпець b має бути лінійною комбінацією стовпців матриці A. Розпишемо це. Матриця β має вигляд:

$$ \beta=\begin{pmatrix} \beta_1\\ \beta_2\\ \vdots\\ \beta_n \end{pmatrix} $$

І ми стверджуємо, що коли замість x₁ підставити β₁ і так далі, то всі рівняння системи стануть правильними рівностями:

$$ \begin{array}{ccccccccc} a_{11}\beta_1&+&a_{12}\beta_2&+&\ldots&+&a_{1n}\beta_n&=&b_1\\ a_{21}\beta_1&+&a_{22}\beta_2&+&\ldots&+&a_{2n}\beta_n&=&b_2\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ a_{m1}\beta_1&+&a_{m2}\beta_2&+&\ldots&+&a_{mn}\beta_n&=&b_m\\ \end{array} $$

Тепер трохи перепишемо рівняння. Якщо глянути на перший стовпчик, побачимо, що там завжди стоять значення $a_{11}, a_{21}, …, a_{m1}$, які множаться на те саме значення β₁. Якщо виокремити стовпчик в окрему матрицю, можна винести за дужки значення β₁ перед матрицею, і вийде:

$$ \begin{pmatrix} a_{11}\beta_1\\ a_{21}\beta_1\\ \vdots\\ a_{m1}\beta_1 \end{pmatrix} =\beta_1 \begin{pmatrix} a_{11}\\ a_{21}\\ \vdots\\ a_{m1} \end{pmatrix} $$

Тепер так само можна переписати всю систему:

$$ \beta_1\begin{pmatrix} a_{11}\\ a_{21}\\ \vdots\\ a_{m1} \end{pmatrix} + \beta_2\begin{pmatrix} a_{12}\\ a_{22}\\ \vdots\\ a_{m2} \end{pmatrix} +…+ \beta_n\begin{pmatrix} a_{1n}\\ a_{2n}\\ \vdots\\ a_{mn} \end{pmatrix} \begin{pmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{pmatrix} $$

Щоб ця рівність виконувалася, матриця праворуч має бути лінійною комбінацією матриць-стовпців ліворуч, а значення β₁, …, β_n мають бути її коефіцієнтами.

Так ми довели: якщо матриця β є розв'язком системи рівнянь, то права частина системи, матриця b, має бути лінійною комбінацією стовпців матриці системи. А якщо стовпець із матриці b є лінійною комбінацією стовпців матриці A, то матриця A має такий самий ранг, як і матриця (A|b).

Водночас, якщо $\operatorname{rank}(A) = \operatorname{rank}(A|b) = k$ і k дорівнює кількості невідомих, тобто k = n, то система має рівно один розв'язок. Якщо ж k < n, то система має нескінченно багато розв'язків, і для їх запису знадобиться n − k параметрів.

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

З попередньої рівності також видно: якщо в матриці (A|b) виконувати елементарні перетворення рядків, розв'язок системи не зміниться. Якби ми додали до другого рядка перший, то отримали б рівняння:

$$ \beta_1\begin{pmatrix} a_{11}\\ a_{21}+a_{11}\\ \vdots\\ a_{m1} \end{pmatrix} + \beta_2\begin{pmatrix} a_{12}\\ a_{22}+a_{12}\\ \vdots\\ a_{m2} \end{pmatrix} +...+ \beta_n\begin{pmatrix} a_{1n}\\ a_{2n}+a_{1n}\\ \vdots\\ a_{mn} \end{pmatrix} \begin{pmatrix} b_1\\ b_2+b_1\\ \vdots\\ b_m \end{pmatrix} $$

Якщо розписати другий рядок, отримаємо:

$$\beta_1(a_{21}+a_{11})+\beta_2(a_{22}+a_{12})+\ldots+\beta_n(a_{2n}+a_{1n})=b_1+b_2$$

Розкриємо дужки:

$$\beta_1a_{21}+\beta_1a_{11}+\beta_2a_{22}+\beta_2a_{12}+\ldots+\beta_na_{2n}+\beta_na_{1n}=b_1+b_2$$

Тепер трохи переставимо доданки:

$$(\beta_1a_{11}+\beta_2a_{12}+\ldots+\beta_na_{1n})+(\beta_1a_{21}+\beta_2a_{22}+\ldots+\beta_na_{2n})=b_1+b_2$$

У першій дужці маємо, по суті, перший рядок, а в другій — початковий другий рядок. Ми знаємо, що перший рядок дорівнює b₁, а другий — b₂. Це відомо з початкових рівнянь. Тож замість першої дужки можна написати b₁, а замість другої — b₂:

$$b_1+b_2=b_1+b_2.$$

Подібно можна помножити цілий рядок на сталу c ≠ 0, і правильність системи рівнянь не порушиться. Але зауваж, що виконувати перетворення стовпців не можна.

Система з одним розв'язком

На прикладі покажемо, як розв'язати систему, що має рівно один розв'язок. Нехай маємо таку систему рівнянь:

$$ \begin{array}{ccccccc} 2x_1&+&3x_2&+&7x_3&=&47\\ 3x_1&+&8x_2&+&x_3&=&50\\ &&3x_2&+&3x_3&=&27\\ \end{array} $$

Матриця A виглядатиме так:

$$ A=\begin{pmatrix} 2&3&7\\ 3&8&1\\ 0&3&3 \end{pmatrix} $$

Тепер обчислимо ранг цієї матриці:

$$ \begin{pmatrix} 2&3&7\\ 3&8&1\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 6&16&2\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&7&-19\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&21&-57\\ 0&21&21 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&21&-57\\ 0&0&78 \end{pmatrix} $$

Бачимо, що $\operatorname{rank}(A) = 3$. Звідси також випливає, що $\operatorname{rank}(A|b) = 3$, бо матриця типу 3 × 4 може мати ранг щонайбільше три. Система має три невідомі, тож уся система має рівно один розв'язок. Як його знайти?

Метод Гаусса

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

Матриця (A|b) має вигляд:

$$ (A|b)=\begin{pmatrix} 2&3&7&47\\ 3&8&1&50\\ 0&3&3&27 \end{pmatrix} $$

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

$$\begin{eqnarray} \begin{pmatrix} 2&3&7&47\\ 3&8&1&50\\ 0&3&3&27 \end{pmatrix} &\sim& \begin{pmatrix} 6&9&21&141\\ 6&16&2&100\\ 0&3&3&27 \end{pmatrix} \\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&7&-19&-41\\ 0&3&3&27 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&21&-57&-123\\ 0&21&21&189 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&21&-57&-123\\ 0&0&78&312 \end{pmatrix}\\ \end{eqnarray}$$

Оскільки ми виконували елементарні перетворення рядків, ця матриця описує рівносильну систему рівнянь — систему з тією самою множиною розв'язків. Перепишемо систему з матричного запису у звичайний, використавши коефіцієнти з нашої останньої матриці:

$$ \begin{array}{ccccccc} 6x_1&+&9x_2&+&21x_3&=&141\\ &&21x_2&-&57x_3&=&-123\\ &&&&78x_3&=&312\\ \end{array} $$

Тепер почнемо з останнього рівняння. Воно каже нам, що 78x₃ = 312. Яке значення має мати x₃? Це просте лінійне рівняння, тож

$$\begin{eqnarray} 78x_3&=&312\\ x_3&=&\frac{312}{78}\\ x_3&=&4 \end{eqnarray}$$

Маємо значення першої змінної, x₃. Підставимо його в друге рівняння. Отримуємо рівняння:

$$\begin{eqnarray} 21x_2-57x_3&=&-123\\ 21x_2-57\cdot4&=&-123\\ 21x_2&=&-123+228\\ 21x_2&=&105\\ x_2&=&\frac{105}{21}\\ x_2&=&5 \end{eqnarray}$$

І нарешті обидва знайдені значення підставимо в перше рівняння:

$$\begin{eqnarray} 6x_1+9x_2+21x_3&=&141\\ 6x_1+9\cdot5+21\cdot4&=&141\\ 6x_1+45+84&=&141\\ 6x_1&=&12\\ x_1&=&2 \end{eqnarray}$$

Значення змінної x₁ дорівнює двом. Тепер розв'язок повний. Можемо записати, що x = (x₁; x₂; x₃) = (2; 5; 4). Як бачимо, метод Гаусса — простий, але дієвий спосіб розв'язати систему лінійних рівнянь.

Нескінченно багато розв'язків

Якщо $\operatorname{rank}(A) = \operatorname{rank}(A|b) = k$ і k менше за кількість невідомих, k < n, то система має нескінченно багато розв'язків. Розгляньмо простий приклад:

$$ \begin{array}{cccccc} 4x_1&+&x_2&=&5\\ 12x_1&+&3x_2&=&15\\ \end{array} $$

Бачимо, що друге рівняння дорівнює потроєному першому. Якщо помножити перше рівняння на мінус три й додати до другого рядка, отримаємо:

$$ \begin{array}{cccccc} 4x_1&+&x_2&=&5\\ 0x_1&+&0x_2&=&0\\ \end{array} $$

Тепер кількість змінних дорівнює двом, n = 2, ранг матриці системи дорівнює одиниці, $\operatorname{rank}(A) = 1$, і ранг розширеної матриці теж дорівнює одиниці, $\operatorname{rank}(A|b) = 1$. Виконується k < n, отже, система має нескінченно багато розв'язків. Як їх знайти?

Погляньмо на рівняння. Друге рівняння виконується для всіх x₁, x₂, тож цікавить нас лише перше. Насправді всі пари x₁, x₂, що задовольняють перше рівняння, утворять множину всіх розв'язків цієї системи. Тож розв'яжемо рівняння 4x₁ + x₂ = 5. Перетворимо його до вигляду x₂ = 5 − 4x₁.

Далі скористаймося параметром. Виберемо параметр t. Тепер спробуємо виразити пару x₁, x₂ через параметр t так, щоб можна було написати, наприклад, що всі пари вигляду (t; t + 2) є розв'язками системи. Тобто такі пари, як (1; 3) чи (14; 16). Суть у тому, щоб виразити значення однієї змінної через іншу так, аби знати: коли значення x₁ буде якимсь, то значення x₂ буде, скажімо, втричі більшим. Як відправну точку візьмемо x₁.

Запишемо рівність t = x₁. Якщо змінна x₁ матиме значення t, яке значення матиме змінна x₂? Це видно з попередньої рівності: x₂ = 5 − 4x₁. Тобто якщо x₁ = t, то x₂ = 5 − 4t. Тому можемо написати, що всі пари вигляду (t; 5 − 4t) є розв'язками системи рівнянь.

Перевіримо це. Якщо замість t підставити одиницю, маємо: x₁ = 1 і x₂ = 5 − 4 · 1 = 1. Підставимо ці значення в рівняння: 4 · 1 + 1 = 5, рівняння виконується.

Якщо замість t підставити п'ять, маємо: x₁ = 5, x₂ = 5 − 4 · 5 = −15. Після підстановки в рівняння маємо: 4 · 5 − 15 = 5. Виконується.

Загальний і частинний розв'язки

Розв'язок системи рівнянь, записаний за допомогою параметрів, називаємо загальним розв'язком. Конкретний розв'язок, тобто коли замість параметрів підставлено конкретні числа, називаємо частинним розв'язком.

Тож у попередньому прикладі (x₁; x₂) = (t; 5 − 4t) — загальний розв'язок системи рівнянь, а (1; 1) і (5; −15) — частинні розв'язки.

Якщо маємо матрицю системи A і розширену матрицю системи (A|b), а їхні ранги рівні, $\operatorname{rank}(A) = \operatorname{rank}(A|b) = k$, то для запису загального розв'язку потрібно n − k параметрів. Зауваж, що коли n = k, то потрібно нуль параметрів. Це випадок, коли система має рівно один розв'язок — параметр тоді не потрібен.

Приклад

Розв'яжи таку систему лінійних рівнянь:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&-&4x_2&+&2x_3&+&10x_4&=&2\\ 11x_1&-&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

Спершу обчислимо ранги матриць A і (A|b). Зведемо розширену матрицю до ступінчастого вигляду, з якого дізнаємося ранг обох матриць. Беремося до перетворень. (Перший рядок помножимо на два, потім додамо перший і другий рядки й цей результат віднімемо від третього рядка. Далі від другого рядка віднімемо перший, і наприкінці перший рядок поділимо назад на два.)

$$\begin{eqnarray} (A|b)=\begin{pmatrix} 3&-2&4&5&1\\ 5&-4&2&10&2\\ 11&-8&10&20&4 \end{pmatrix} &\sim& \begin{pmatrix} 6&-4&8&10&2\\ 5&-4&2&10&2\\ 11&-8&10&20&4 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&-4&8&10&2\\ 5&-4&2&10&2\\ 0&0&0&0&0 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&-4&8&10&2\\ -1&0&-6&0&0\\ 0&0&0&0&0 \end{pmatrix}\\ &\sim& \begin{pmatrix} 3&-2&4&5&1\\ -1&0&-6&0&0\\ 0&0&0&0&0 \end{pmatrix}\\ \end{eqnarray}$$

З цієї останньої матриці вже видно, що $\operatorname{rank}(A) = \operatorname{rank}(A|b) = k = 2$. Кількість невідомих при цьому n = 4, тож знадобиться n − k = 2 параметри. Запишемо рівняння за останньою матрицею:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ -x_1&&&-&6x_3&&&=&0\\ \end{array} $$

З другого рівняння отримуємо

$$\begin{eqnarray} -x_1-6x_3&=&0\\ -x_1&=&6x_3\\ x_1&=&-6x_3 \end{eqnarray}$$

Виберемо перший параметр, t = x₃. Тоді можемо написати, що x₁ = −6t. Підставимо це в перше рівняння:

$$\begin{eqnarray} 3(-6t)-2x_2+4t+5x_4&=&1\\ -18t-2x_2+4t+5x_4&=&1\\ -14t-2x_2+5x_4&=&1\\ -2x_2&=&1+14t-5x_4\\ x_2&=&-\frac12-7t+\frac52x_4 \end{eqnarray}$$

Введемо в гру другий параметр, s = x₄. Тоді можемо написати, що

$$x_2=-\frac12-7t+\frac52s$$

Так отримуємо загальний розв'язок системи:

$$(x_1; x_2; x_3; x_4) = (-6t; -\frac12-7t+\frac52s; t; s)$$

Спробуймо кілька частинних розв'язків. Наприклад, s = t = 0. Тоді маємо: $(x_1; x_2; x_3; x_4) = (0; -\frac12; 0; 0)$. Після підстановки у вихідні рівняння:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&-&4x_2&+&2x_3&+&10x_4&=&2\\ 11x_1&-&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

отримуємо рівняння:

$$ \begin{array}{ccccccccc} 0&-&2\cdot(-\frac12)&+&0&+&0&=&1\\ 0&-&4\cdot(-\frac12)&+&0&+&0&=&2\\ 0&-&8\cdot(-\frac12)&+&0&+&0&=&4\\ \end{array} $$

Прибравши нульові елементи й помноживши дроби, отримуємо:

$$\begin{eqnarray} 1&=&1\\ 2&=&2\\ 4&=&4 \end{eqnarray}$$

Спробуймо інший частинний розв'язок: s = 2, t = 1. Тоді отримуємо:

$$\begin{eqnarray} x_1&=&-6\\ x_2&=&-\frac12-7+5=-\frac52\\ x_3&=&1\\ x_4&=&2 \end{eqnarray}$$

Підставимо в рівняння:

$$ \begin{array}{ccccccccc} -18&-&2(-\frac52)&+&4&+&10&=&1\\ -30&-&4(-\frac52)&+&2&+&20&=&2\\ -66&-&8(-\frac52)&+&10&+&40&=&4\\ \end{array} $$

Спростимо:

$$ \begin{array}{ccccccccc} -4&+&5&=&1\\ -8&+&10&=&2\\ -16&+&20&=&4\\ \end{array} $$

І нарешті отримуємо:

$$\begin{eqnarray} 1&=&1\\ 2&=&2\\ 4&=&4 \end{eqnarray}$$

Схоже, що знайдений загальний розв'язок правильний.