Метод Гаусса

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

У методі Гауса для спрощення матриці, використовують послідовні елементарні операції перетворення матриці для модифікації матриці доки нижній лівий кут матриці не буде заповнено нулями, настільки наскільки це можливо. Існує три типи елементарних перетворень матриці: 1) Заміна двох рядків, 2) Множення рядка на не нульове число, 3) Додавання одного рядка до іншого. Використовуючи ці операції, матрицю завжди можна перетворити на верхню трикутну матрицю, а фактично і у скорочену рядкову ступінчасту форму. Як тільки всі перші коефіцієнти (ті що знаходяться ліворуч і є не нульовими входженням в кожному рядку) стають рівними 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 року до н. е. В третьому столітті н. е. коментарі до неї давав Лю Хуей.

Цей метод в Європі з'являється із записів Ісаака Ньютона. В 1670, він написав, що в всіх книжках з алгебри, які були йому відомі бракувало уроку для вирішення спільних рівнянь, які тоді надавав Ньютон. Університет Кембріджу зрештою опублікував нотатки під назвою Arithmetica Universalis в 1707 набагато пізніше, після того як Ньютон вже полишив академічне життя. Нотатки широко розповсюдилися, що вже до кінця 18-го століття зробило те, що зараз називають Гаусовим скороченням, стандартним уроком у книжках із алгебри. Карл Фрідріх Гаусс в 1810 виробив систему нотації для симетричного скорочення, що була широко прийнята в 19-му столітті для вирішення нормальних рівнянь задачі найменших квадратів, яку розраховували професійні обчислювачі. Алгоритм, який викладається у вищій школі був названий на честь Гауса лише в 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, які використовують можливості апаратного забезпечення і особливості структури матриці для вибору найкращого алгоритму автоматичним чином.

Див. також

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

Посилання

• Метод Гауса // Вища математика в прикладах і задачах / Клепко В.Ю., Голець В.Л.. — 2-ге видання. — К. : Центр учбової літератури, 2009. — С. 31. — 594 с.