Метод Гауса

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Початок алгоритму. 
\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 & 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]

Див. також[ред.ред. код]