Метод Гауса

Ме́тод Га́уса — алгоритм розв'язку системи лінійних алгебраїчних рівнянь.

Початок алгоритму. $\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}{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 & 7 \\ -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 & 7 \\ 0 & 2 & 1 & 5 \end{array}\right]$

Переходимо до наступного стовпчика. Множимо другий рядок на 2, щоб отримати другий діагональний елемент 1:

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

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

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

Переходимо до наступного стовпчика. Множимо останній рядок на −1, щоб отримати третій діагональний елемент 1:

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

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

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

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

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

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

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

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

$\left[\begin{array}{ccc|c} 1 & 0 & 0 & 20 \\ 0 & 1 & 0 & -9 \\ 0 & 0 & 1 & 23 \end{array}\right]$

Див. також

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