Метод Гаусса

Ме́тод Га́усса (англ. Gaussian elimination) — алгоритм розв'язування систем лінійних алгебраїчних рівнянь. Зазвичай під цим алгоритмом розуміють деяку послідовність операцій, що виконують над відповідною матрицею коефіцієнтів, для приведення її до трикутного вигляду, з наступним вираженням базисних змінних через небазисні. Цей метод також можливо використовувати для знаходження рангу матриці, для обчислення визначника матриці, а також для обчислення обернення невиродженої квадратної матриці. Цей метод названо на честь Карла Фрідріха Гаусса (1777—1855), хоча китайські математики знали його ще 179 року н. е. (див. розділ про історію).

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

• Заміна двох рядків.
• Множення рядка на не нульове число.
• Додавання одного рядка до іншого.

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

Цю послідовність перетворення матриці іноді називають спрощенням або скороченням матриці.

Опис алгоритму

Початок алгоритму

${\begin{cases}a_{11}\cdot x_{1}+a_{12}\cdot x_{2}+...+a_{1n}\cdot x_{n}=b_{1}&I\\a_{21}\cdot x_{1}+a_{22}\cdot x_{2}+...+a_{2n}\cdot x_{n}=b_{2}&II\\...&...\\a_{m1}\cdot x_{1}+a_{m2}\cdot x_{2}+...+a_{mn}\cdot x_{n}=b_{m}&M\end{cases}}$

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

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

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

$\left[{\begin{array}{rrr|r}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{array}}\right]$

Операції над рядками

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

1. Заміна позиції двох рядків.
2. Множення рядка на не нульове скалярне значення.
3. Додавання до одного рядка іншого рядка помноженого на скаляр.

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

Рядкова ступінчаста форма

У кожному рядку матриці, якщо рядок не складається із самих нулів, не нульове входження, яке знаходиться лівіше від усіх називають провідним коефіцієнтом цього рядка. Тому якщо два провідних коефіцієнти знаходяться в одному стовпці, тоді можна застосувати операцію над рядком типу 3 (див. вище) аби один з цих коефіцієнтів став нульовим. Далі, використавши операцію заміни рядків, завжди можна впорядкувати рядки таким чином, що для кожного не нульового рядка, провідний коефіцієнт знаходитиметься праворуч від провідного коефіцієнта рядка, що знаходиться вище. Якщо це так для всіх рядків, то говорять що матриця знаходиться у рядковій ступінчастій формі. Таким чином ліва нижня частина матриці містить лише нулі, і всі нульові рядки знаходяться нижче не нульових рядків. Слово «ступінчаста» використовується тут тому, оскільки можна вважати, що рядки матриці впорядковані за їх розміром, так що найбільший рядок знаходиться зверху, а найменший рядок — знизу.

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

$\left[{\begin{array}{cccc}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{array}}\right]$

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

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

Приклад

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

$\left\{{\begin{array}{ccc}2x+y-z&=&8\\-3x-y+2z&=&-11\\-2x+y+2z&=&-3\end{array}}\right.$

Запишімо розширену матрицю системи:

$\left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$

Припустимі операції для кожного рядка

• переставляння рядків;
• множення та ділення на число (окрім нуля);
• додавання та віднімання іншого рядка (можливо помноженого чи поділеного на число).

Мета цих дій — звести квадратну матрицю, в цьому прикладі розміру 3 × 3, (розташовану ліворуч від вертикальної лінії) до одиничної матриці. Тоді стовпчик праворуч від лінії й буде розв'язком системи рівнянь.

Алгоритм прямого ходу

Переберімо стовпчики матриці й здійснимо рядкові операції, щоб у кожному стовпчику:

• діагональний елемент став дорівнювати одиниці;
• елементи під діагональним стали дорівнювати нулеві.

Поділімо перший рядок на 2, щоб отримати 1 як перший діагональний елемент:

$\left[{\begin{array}{ccc|c}1&1/2&-1/2&4\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$

Додаймо до другого рядка перший, помножений на 3, щоб отримати піддіагональний елемент 0:

$\left[{\begin{array}{ccc|c}1&1/2&-1/2&4\\0&1/2&1/2&1\\-2&1&2&-3\end{array}}\right]$

Додаймо до третього рядка перший, помножений на 2, щоб отримати другий піддіагональний елемент 0:

$\left[{\begin{array}{ccc|c}1&1/2&-1/2&4\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]$

Перейдімо до наступного стовпчика.

Помножимо другий рядок на 2, щоб отримати другий діагональний елемент 1:

$\left[{\begin{array}{ccc|c}1&1/2&-1/2&4\\0&1&1&2\\0&2&1&5\end{array}}\right]$

Віднімімо від третього рядка другий, помножений на 2, щоб отримати піддіагональний елемент 0:

$\left[{\begin{array}{ccc|c}1&1/2&-1/2&4\\0&1&1&2\\0&0&-1&1\end{array}}\right]$

Перейдімо до наступного стовпчика.

Помножимо останній рядок на −1, щоб отримати третій діагональний елемент 1:

$\left[{\begin{array}{ccc|c}1&1/2&-1/2&4\\0&1&1&2\\0&0&1&-1\end{array}}\right]$

Алгоритм зворотного ходу

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

Віднімімо від другого рядка третій, щоб отримати наддіагональний елемент 0:

$\left[{\begin{array}{ccc|c}1&1/2&-1/2&4\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

Додаймо до першого рядка третій, поділений на 2, щоб отримати другий наддіагональний елемент 0:

$\left[{\begin{array}{ccc|c}1&1/2&0&7/2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

Перейдімо до наступного стовпчика.

Віднімімо від першого рядка другий, поділений на 2, щоб отримати наддіагональний елемент 0:

$\left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

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

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

Розрахунок визначника

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

• Переставлення двох рядків призводить до множення визначника на −1.
• Множення рядка на ненульовий скаляр помножує визначник на той самий скаляр.
• Додавання до одного рядка іншого рядка помноженого на скаляр не змінює детермінант.

Якщо при застосуванні Гауссового скорочення до квадратної матриці A утворено рядкову ступінчасту матрицю B, нехай d є добутком скалярів, на які було помножено детермінант, при використанні наведених вище правил. Тоді визначник матриці A є добутком елементів діагоналі матриці B розділених на коефіцієнт d: det(A) = ∏diag(B) / d.

Складність обчислення цим методом для матриці n×n, оцінюється лише в O(n³) необхідних арифметичних операцій, в той час як при вирішенні елементарними методами необхідно буде здійснити O(2ⁿ) або O(n!) операцій. Навіть для швидкого комп'ютера, елементарні методи стають не практичними при n більше 20.

Знаходження оберненої матриці

Для знаходження оберненої матриці, якщо така існує застосовують різновид методу Гаусса, який називають методом Гаусса — Жордана. Якщо A є квадратною матрицею n на n, тоді спершу праворуч до неї доповнюють одиничну матрицю n на n, так, що утворюється блочна матриця n на 2n [A | I]. Тепер, за допомогою елементарних матричних перетворень, знаходимо скорочену рядкову ступінчасту форму цієї n на 2n матриці. Матриця A може бути оберненою тоді й тільки тоді, коли лівий блок може бути скорочений до одиничної матриці I; в такому випадку правий блок утвореної в результаті матриці є обернена матриця A⁻¹. Якщо за допомогою алгоритму не вдається скоротити лівий блок до I, тоді A не може бути оберненою.

Наприклад, розглянемо наступну матрицю

$A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}$.

Щоб знайти обернену матрицю, доповнимо її одиничною матрицею праворуч, і над утвореною матрицею 3 на 6 будемо застосовувати метод скорочення Гаусса:

$[A|I]=\left[{\begin{array}{rrr|rrr}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right]$.

Виконавши операції перетворення, отримаємо скорочену рядкову ступінчасту форму цієї доповненої матриці:

$[I|B]=\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\[3pt]0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\[3pt]0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right]$.

Кожну операцію можна розглядати як лівий добуток на елементарну матрицю. Позначивши добуток цих елементарних матриць як B, ми показали, ліворуч, що BA = I, і таким чином, B = A⁻¹. Ця процедура знаходження оберненої матриці буде працювати для квадратних матриць будь-якого розміру.

Обчислення рангів та базисів

Алгоритм Гаусса для скорочення матриці можна застосувати до будь-якої $m\times n$ матриці $A$. У такому випадку, наприклад, деякі матриці $6\times 9$ можна перетворити у матрицю, що має рядкову ступінчасту форму наступного вигляду

$T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}}$

де * є довільними входженнями і a, b, c, d, e є не нульовими входженнями. Ця ступінчаста матриця $T$ містить в собі багато корисної інформації про $A$: ранг матриці $A$ дорівнює 5 оскільки існує 5 не нульових рядків в $T$; векторний простір, на який поширюються стовпці матриці $A$ має базис, що складається із першого, третього, четвертого, сьомого і дев'ятого стовпців $A$ (стовпці із a, b, c, d, e у $T$), а значення * вказують як можуть бути записані у вигляді лінійної комбінації базових стовпців інші стовпці із $A$. Це є наслідком дистрибутивності скалярного добутку при вираженні лінійного відображення у вигляді матриці.

Все це застосовується і у випадку скороченої рядкової ступінчастої форми, що є частковим випадком рядкової ступінчастої форми.

Історія

Метод Гауссового скорочення матриці описано у восьмому розділі китайського трактату «Математика в дев'яти книгах» під назвою «Прямокутні масиви». Його застосовано у вісімнадцяти задачах, при розв'язанні від двох до п'яти рівнянь. Перша згадка про книгу із такою назвою датується 179 роком н. е., але деякі її розділи було написано раніше, приблизно 150 року до н. е. У III столітті н. е. Лю Хуей подав коментарі до книги.

У Європі метод з'явився у записах Ісаака Ньютона. 1670 року він написав, що в усіх книжках з алгебри, які були йому відомі, бракувало методу для вирішення систем рівнянь, які тоді давав Ньютон. Після того, як Ньютон полишив академічну роботу, університет Кембріджу опублікував нотатки під назвою Arithmetica Universalis (1707). Нотатки розповсюдилися, і до кінця XVIII століття метод, який зараз називають Гауссовим скороченням, став стандартним у книжках з алгебри. 1810 року Карл Фрідріх Гаусс розробив систему нотації для симетричного скорочення. Вона набула поширення в XIX столітті для вирішення нормальних рівнянь методом найменших квадратів, які розраховували професійні обчислювачі. Алгоритм, який викладається у школі, було названо на честь Гаусса лише в 1950-х, внаслідок плутанини щодо історії предмету.

Псевдокод

Як описувалося вище, метод Гауссового скорочення записує дану $m$ × $n$ матрицю $A$ унікальним способом як добуток оберненої $m$ × $m$ матриці $S$ і рядкової ступінчастої матриці $T$. Тут, $S$ це добуток матриць, що відповідає виконаній операції перетворення.

Формальний алгоритм для розрахунку $T$ із $A$ є таким. Записуємо $A[i,j]$, що є елементом у рядку $i$, стовпці $j$ матриці $A$, де перший індекс елемента дорівнює 1. Перетворення відбувається поверх: це означає, що початкова матриця $A$ не зберігається і успішно заміняється матрицею $T$.

 for k = 1 ... min(m,n):
   /* Знайти k-ий поточний елемент: */
   i_max  := argmax (i = k ... m, abs(A[i, k]))
   if A[i_max, k] = 0
     помилка "Матриця є сингулярною!"
   замінити місцями рядки(k, i_max)
   /* Виконати для всіх наступних рядків: */
   for i = k + 1 ... m:
     f := A[i, k] / A[k, k]
     /* Виконати для всіх елементів, що залишилися в даному рядку: */
     for j = k + 1 ... n:
       A[i, j]  := A[i, j] - A[k, j] * f
     /* Заповнити нижню трикутну матрицю нулями: */
     A[i, k]  := 0

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

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

Програмна реалізація мовою Python

Нижче наведено одну з можливих реалізацій методу Гауса мовою Python. Код використовує EPS як задану точність для обчислень.

import numpy as np
EPS = 1e-10  # Задаємо точність обчислень

def unit_A(n):
    A_inv = [[0] * n for _ in range(n)]
    for i in range(n):
        A_inv[i][i] = 1
    return A_inv

def method_gauss(A, b):
    n = len(b)
    det = 1
    A_inv = unit_A(n)
    A = A.copy()
    b = b.copy()
    for j in range(n):
        if abs(A[j][j]) < EPS:
            for i in range(j + 1, n):
                if abs(A[i][j]) > EPS:
                    # Перестановка рядків
                    A[j], A[i] = A[i], A[j]
                    b[j], b[i] = b[i], b[j]
                    A_inv[j], A_inv[i] = A_inv[i], A_inv[j]
                    det = det * -1  # Зміна знаку
                    break

        # Перевірка на виродженість
        if abs(A[j][j]) < EPS:
            raise ValueError("Матриця вироджена, det(A) = 0")
        det = det * A[j][j]

        # Прямий хід 
        for i in range(j + 1, n):
            factor = A[i][j] / A[j][j]
            for k in range(n):
                A[i][k] = A[i][k] - A[j][k] * factor
                A_inv[i][k] = A_inv[i][k] - A_inv[j][k] * factor
            b[i] = b[i] - b[j] * factor

    # Зворотній хід
    for j in range(n - 1, -1, -1):
        b[j] /= A[j][j]
        for k in range(n):
            A_inv[j][k] /= A[j][j]
        for i in range(j - 1, -1, -1):
            factor = A[i][j]
            b[i] -= b[j] * factor
            for k in range(n):
                A[i][k] -= A[j][k] * factor
                A_inv[i][k] -= A_inv[j][k] * factor

    return b, det, A_inv

Див. також

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

Посилання

• Метод Гауса // Вища математика в прикладах і задачах / Клепко В.Ю., Голець В.Л.. — 2-ге видання. — К. : Центр учбової літератури, 2009. — С. 31. — 594 с.
• Гантмахер Ф. Р. Теорія матриць. — 2024. — 400+ с.(укр.)
• Гельфанд И. М. Лекции по линейной алгебре. — 5-е. — Москва : Наука, 1998. — 320 с. — ISBN 5791300158.(рос.)
• Ланкастер П.. Теория матриц. — 2. — Москва : Наука, 1982. — 272 с.(рос.)
• Р.Хорн, Ч.Джонсон. Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)