Rozwiązywanie układów równań liniowych metodą eliminacji Gaussa

Dany jest układ równań liniowych \(n\)-tego stopnia:
$$
\begin{matrix}
a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n = b_1 \\
a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n = b_2 \\
\vdots \\
a_{n1} x_1 + a_{n2} x_2 + \ldots + a_{nn} x_n = b_n
\end{matrix}
$$

lub w zapisie macierzowym: A•X = B
Należy rozwiązać układ równań, tzn. wyznaczyć niewiadome \(x_1, \ldots, x_n\).

Rozwiązanie teoretyczne

Do rozwiązania problemu zastosowany zostanie algorytm kolejnych eliminacji opracowany przez Carla Friedricha Gaussa. W tym celu oznaczamy układ wyjściowy numerem pierwszym: A⁽¹⁾•X = B⁽¹⁾

Odejmując od \(i\)–tego wiersza układu gdzie \(i = 2, 3, …, n\), pierwszy wiersz pomnożony przez \(\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}\) otrzymujemy układ A⁽²⁾•X = B⁽²⁾ postaci:

$$
\begin{array}{rl}
a_{11}^{(2)} x_1 + a_{12}^{(2)} x_2 + \ldots + a_{1n}^{(2)} x_n &= b_1^{(2)} \\
a_{22}^{(2)} x_2 + \ldots + a_{2n}^{(2)} x_n &= b_2^{(2)} \\
\vdots \\
a_{n2}^{(2)} x_2 + \ldots + a_{nn}^{(2)} x_n &= b_n^{(2)}
\end{array}
$$

W ten sposób pozbywamy się niewiadomej \(x_1\) z równań w wierszach \(2, 3, …, n\).

W podobny sposób eliminujemy niewiadomą \(x_2\) z wierszy \(3, 4, …, n\) odejmując od \(i\)-tego wiersza \((i = 3, 4, …, n)\) wiersz drugi pomnożony przez \(\frac{a_{i 2}^{(2)}}{a_{22}^{(2)}}\).

Po \(n-1\) kroków otrzymujemy układ A⁽ⁿ⁾•X = B⁽ⁿ⁾ w postaci:
$$
\begin{array}
a_{11}^{(n)} x_1 + a_{12}^{(n)} x_2 + \ldots+ a_{1n}^{(n)} x_n &= b_1^{(n)} \\
a_{22}^{(n)} x_2 + \ldots + a_{2n}^{(n)} x_n &= b_2^{(n)} \\
\vdots \\
a_{nn}^{(n)} x_n &= b_n^{(n)}
\end{array}
$$

Z ostatniego równania wyznaczamy niewiadomą \(x_n\), a następnie kolejne niewiadome według wzoru rekurencyjnego:
$$
x_i = \frac{b_i – a_{i n} x_n – \ldots – a_{ii+1} x_{i+1}}{a_ii} \\
gdzie ~~ i = n-1, n-2, …, 1
$$

Przedstawiona metoda pozwala rozwiązać układ równań \(n\)-tego rzędu wykonując \(n!\) działań. W przeciwieństwie do metody wyznacznikowej Cramera nie daje jednak informacji, czy układ równań jest układem oznaczonym, nieoznaczonym lub sprzecznym.