Метод Гауса
Що таке метод виключення Гаусса
Метод Гаусса, або виключення Гаусса, — це техніка, що використовується для розв'язання систем \( n \) лінійних рівнянь з \( n \) невідомими. Процес передбачає ітераційне застосування послідовності операцій для виключення однієї змінної за раз, перетворюючи систему у форму, яку легко розв'язати. Розглянемо наступну систему рівнянь:
\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1 \\[0.5em] a_{21}x_1 + a_{22}x_2 + a_{23}x_3 = b_2 \\[0.5em] a_{31}x_1 + a_{32}x_2 + a_{33}x_3 = b_3 \end{cases} \]
Для застосування методу важливо, щоб система була квадратною, тобто вона повинна мати однакову кількість рівнянь і невідомих, як у системі \( 3 \times 3 \), показаній вище.
Процес включає наступні кроки:
- Виключити змінну \( x_1 \) з усіх рівнянь, крім першого.
- Виключити змінну \( x_2 \) з третього рівняння.
- Розв'язати третє рівняння, щоб знайти значення \( x_3 \).
- Рухатися у зворотному напрямку, щоб знайти значення решти змінних.
Коли алгоритм створює несумісне або невизначене рівняння, система не може рухатися далі: це сигналізує або про відсутність розв'язання, або про нескінченну множину розв'язків.
Зв'язок із матрицями
Метод виключення Гаусса перетворює матрицю на її ступінчасту форму. Мета полягає в тому, щоб переписати матрицю так, щоб кожна позиція головного елемента (на головній діагоналі) містила 1, а всі елементи нижче кожного головного елемента були 0. Наприклад, починаючи з загальної матриці:
\[ A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \quad \xrightarrow{\text{to}} \quad \begin{bmatrix} 1 & b_{12} & b_{13} \\ 0 & 1 & b_{23} \\ 0 & 0 & 1 \end{bmatrix} \]
Почнемо з виключення змінної \( x_1 \) з усіх рівнянь, крім першого.
Щоб виключити \( x_1 \) з другого рівняння, ми множимо перше рівняння на \( a_{21} \), а друге на \( a_{11} \). Потім ми віднімаємо два отриманих рівняння і замінюємо друге рівняння результатом. Отримуємо:
\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1 \\[0.5em] \left(a_{11}a_{22} – a_{21}a_{12}\right)x_2 + \left(a_{11}a_{23} – a_{21}a_{13}\right)x_3 = a_{11}b_2 - a_{21}b_1 \\[0.5em] a_{31}x_1 + a_{32}x_2 + a_{33}x_3 = b_3 \end{cases} \]
Щоб спростити обчислення, ми переписуємо друге рівняння як:
\[ a^\prime_{22} x_2 + a^\prime_{23} x_3 = b^\prime_2 \]
Система набуває вигляду:
\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1 \\[0.5em] a^\prime_{22} x_2 + a^\prime_{23} x_3 = b^\prime_2\\[0.5em] a_{31}x_1 + a_{32}x_2 + a_{33}x_3 = b_3 \end{cases} \]
Тепер ми множимо перше рівняння на \( a_{31} \), а третє рівняння на \( a_{11} \). Потім ми віднімаємо два отриманих рівняння і замінюємо третє рівняння результатом.
\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1 \\[0.5em] a^\prime_{22} x_2 + a^\prime_{23} x_3 = b^\prime_2\\[0.5em] \left(a_{11}a_{32} - a_{31}a_{12}\right)x_2 + \left(a_{11}a_{33} - a_{31}a_{13}\right)x_3 = a_{11}b_3 – a_{31}b_1 \end{cases} \]
Ми переписуємо третє рівняння як:
\[ a^\prime_{32}x_2 + a^\prime_{33}x_3 = b’_3 \]
Отримуємо:
\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1 \\[0.5em] a^\prime_{22} x_2 + a^\prime_{23} x_3 = b^\prime_2\\[0.5em] a^\prime_{32}x_2 + a^\prime_{33}x_3 = b’_3\end{cases} \]
Переходимо до другого кроку і виключаємо змінну \( x_2 \) з третього рівняння.
Ми множимо друге рівняння на \( a^\prime_{32} \), а третє рівняння на \( a^\prime_{22} \). Потім ми віднімаємо два отриманих рівняння і замінюємо третє рівняння результатом. Завершивши обчислення, як на першому кроці, система зводиться до наступного вигляду:
\[ \begin{cases} a_{11}x_1 + a_{12} x_2 + a_{13} x_3 = b_1 \\[0.5em] a^\prime_{22} x_2 + a^\prime_{23} x_3 = b^\prime_2 \\[0.5em] a^{\prime\prime}_{33} x_3 = b^{\prime\prime}_3 \end{cases} \]
Ми отримали трикутну систему. На цьому етапі ми можемо знайти \( x_3 \) з третього рівняння, отримавши: \[ x_3 = \frac{b^{\prime\prime_3}}{a^{\prime\prime_{33}}} \]
Тепер ми можемо визначити кожну змінну, починаючи з відомого значення \(x_3\).
Приклад
Розглянемо конкретний приклад методу Гаусса, застосований до системи 3×3. Розглянемо наступну систему лінійних рівнянь:
\[ \begin{cases} x + y + z = 6 \\[0.5em] 2x + 3y + z = 14 \\[0.5em] x + 2y + 3z = 14 \end{cases} \]
Щоб вилучити \( x \) з другого рівняння, віднімемо \( 2 \times \) рівняння 1 від рівняння 2:
\[ (2x + 3y + z) - 2(x + y + z) = 0x + y - z = 2 \]
Тепер вилучимо \( x \) з третього рівняння, віднявши рівняння 1 від рівняння 3:
\[ (x + 2y + 3z) - (x + y + z) = 0x + y + 2z = 8 \]
Система набуває вигляду:
\[ \begin{cases} x + y + z = 6 \\[0.5em] y – z = 2 \\[0.5em] y + 2z = 8 \end{cases} \]
Тепер використаємо друге рівняння як новий опорний елемент. Щоб вилучити \( y \) з третього рівняння, віднімемо рівняння 2 від рівняння 3:
\[ (y + 2z) - (y - z) = 3z = 6 \Rightarrow z = 2 \]
Підставимо значення назад, щоб знайти інші змінні. З рівняння 2: \[ y – z = 2 \rightarrow y = 2 + z = 2 + 2 = 4 \]
З рівняння 1: \[ x + y + z = 6 \Rightarrow x = 6 – y – z = 6 – 4 – 2 = 0 \]
Розв'язання:
\[ x = 0 \quad y = 4 \quad z = 2 \]