Metoda eliminacji Gaussa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Metoda eliminacji Gaussa – w algebrze liniowej algorytm rozwiązywania układów równań liniowych, obliczania rzędu macierzy, obliczania macierzy odwrotnej oraz obliczania wartości wyznacznika, wykorzystujący operacje elementarne; jego nazwa pochodzi od nazwiska matematyka niemieckiego Carla Friedricha Gaussa.

Obliczanie rzędu macierzy[edytuj | edytuj kod]

Obliczając rząd macierzy metodą Gaussa, należy za pomocą operacji elementarnych na wierszach sprowadzić macierz do macierzy schodkowej. Wtedy wszystkie niezerowe wiersze są liniowo niezależne i można łatwo odczytać rząd macierzy.

Przykład[edytuj | edytuj kod]

Przykładowo: macierz A poprzez dokonanie operacji elementarnych:

A=\begin{bmatrix}
1 & -1 & 2 & 2 \\
2 & -2 & 1 & 0 \\
-1 & 2 & 1 & -2 \\
2 & -1 & 4 & 0
\end{bmatrix}\sim

odjęcia wielokrotności 1. wiersza od 2., 3. i 4. wiersza,


\sim\begin{bmatrix}
1 & -1 & 2 & 2 \\
0 & 0 & -3 & -4 \\
0 & 1 & 3 & 0 \\
0 & 1 & 0 & -4\end{bmatrix}\sim

zamiany 2. i 3. wiersza,


\sim\begin{bmatrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 1 & 0 & -4\end{bmatrix}\sim

odjęcia wiersza 2. od wiersza 4.


\sim\begin{bmatrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 0 & -3 & -4\end{bmatrix}\sim

odjęcia 3. wiersza od 4. wiersza


\sim\begin{bmatrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 0 & 0 & 0\end{bmatrix}

sprowadzono do macierzy schodkowej. Rząd tej macierzy łatwo odczytać, bowiem jest on równy liczbie jej "schodków", czyli liczbie wierszy pomniejszonej o liczbę wierszy zerowych. W tym przypadku rząd macierzy A równy jest 3.

Rozwiązywanie układów równań liniowych[edytuj | edytuj kod]

Rozwiązując układ m równań liniowych z n niewiadomymi należy, za pomocą operacji elementarnych wyłącznie na wierszach, sprowadzić macierz rozszerzoną układu równań liniowych do postaci schodkowej. Następnie należy rozstrzygnąć istnienie rozwiązań układu z pomocą twierdzenia Kroneckera-Capellego. Jeżeli układ nie jest sprzeczny, to zbiór rozwiązań układu wyjściowego jest równy zbiorowi rozwiązań układu reprezentowanego przez powstałą schodkową macierz rozszerzoną.

Przykład[edytuj | edytuj kod]

Układ wyjściowy:

\left\{\begin{matrix}
x_1 & - & x_2 & + & 2x_3 & + & 2x_4 & = 0 \\
2x_1 & - & 2x_2 & + & x_3 & & & = 1 \\
-x_1 & + & 2x_2 & + & x_3 & - & 2x_4 & = 1 \\
2x_1 & - & x_2 & + & 4x_3 & & & = 2
\end{matrix}\right.

Macierz rozszerzona tego układu:

U=\left[\left.\begin{matrix}
1 & -1 & 2 & 2 \\
2 & -2 & 1 & 0 \\
-1 & 2 & 1 & -2 \\
2 & -1 & 4 & 0
\end{matrix}\right|\begin{matrix}0\\1\\1\\2\end{matrix}\right]

Sprowadzając do postaci schodkowej (za pomocą operacji kolejno: odjęcia wielokrotności 1. wiersza od 2., 3. i 4. wiersza, zamienienia 2. i 3. wiersza, odjęcia 2. wiersza od 4. wiersza, odjęciu 3. wiersza od 4. wiersza):

U\sim\left[\left.\begin{matrix}
1 & -1 & 2 & 2 \\
0 & 0 & -3 & -4 \\
0 & 1 & 3 & 0 \\
0 & 1 & 0 & -4
\end{matrix}\right|\begin{matrix}0\\1\\1\\2\end{matrix}\right]\sim\left[\left.\begin{matrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 1 & 0 & -4
\end{matrix}\right|\begin{matrix}0\\1\\1\\2\end{matrix}\right]\sim\atop\sim\left[\left.\begin{matrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 0 & -3 & -4
\end{matrix}\right|\begin{matrix}0\\1\\1\\1\end{matrix}\right]\sim\left[\left.\begin{matrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 0 & 0 & 0
\end{matrix}\right|\begin{matrix}0\\1\\1\\0\end{matrix}\right]

Rząd macierzy głównej

\begin{bmatrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 0 & 0 & 0
\end{bmatrix}

jest równy 3 czyli równy rzędowi macierzy rozszerzonej

\left[\left.\begin{matrix}
1 & -1 & 2 & 2 \\
0 & 1 & 3 & 0 \\
0 & 0 & -3 & -4 \\
0 & 0 & 0 & 0
\end{matrix}\right|\begin{matrix}0\\1\\1\\0\end{matrix}\right]

oraz mniejszy od liczby szukanych niewiadomych.
Z twierdzenia Kroneckera-Capellego wynika, że układ ma nieskończenie wiele rozwiązań zależnych od jednego parametru. Rozwiązujemy układ:

\begin{cases}
x_1 - x_2 + 2x_3 + 2x_4 = 0\\
x_2 + 3x_3 = 1\\
-3x_3 - 4x_4 = 1\end{cases}

Przyjmując parametr t\, za x_4\, i rozwiązując układ od dołu uzyskujemy:

\begin{matrix}x_4=t\end{matrix}
\begin{matrix}x_3=-\frac{1}{3}\left(1+4x_4\right)=-\frac{4}{3}t-\frac{1}{3}\end{matrix}
\begin{matrix}x_2=1-3x_3=-1+3\left(-\frac{4}{3}t-\frac{1}{3}\right)=4t+2\end{matrix}
\begin{matrix}x_1=x_2-2x_3-2x_4=4t+2-2\left(-\frac{4}{3}t-\frac{1}{3}\right)-2t=\frac{14}{3}t+\frac{8}{3}\end{matrix}

Zatem rozwiązaniem układu są czwórki:

\left(\frac{14}{3}t+\frac{8}{3},\ 4t+2,\ -\frac{4}{3}t-\frac{1}{3},\ t\right)\,,

gdzie t\, jest dowolnym elementem z ciała, w którym szuka się rozwiązania (na przykład, \mathbb{R}).

Obliczanie macierzy odwrotnej[edytuj | edytuj kod]

Aby obliczyć macierz odwrotną macierzy nieosobliwej o stopniu n należy, za pomocą operacji elementarnych wyłącznie na wierszach, sprowadzić macierz blokową \left[\left.A\right|I\right] do postaci \left[\left.I\right|B\right]. Powstała macierz B jest szukaną macierzą odwrotną do macierzy A. Symbolicznie można zapisać: \left[\left.A\right|I\right]\sim\left[\left.I\right|A^{-1}\right]

Przykład[edytuj | edytuj kod]

Wyjściowa macierz:

A = \begin{bmatrix}7 & 4 \\ 3 & 2\end{bmatrix}

Jej wyznacznik jest równy 2, czyli macierz odwrotna istnieje. Macierz blokowa \left[\left.A\right|I\right] ma postać:

\left[\left.A\right|I\right] = \left[\left.\begin{matrix}7 & 4 \\ 3 & 2\end{matrix}\right|\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right]

Wykonując następujące operacje elementarne na wierszach:

(1) W2 – 3/7·W1   (od drugiego wiersza odjąć pomnożony przez 3/7 wiersz pierwszy),
(2) 1/7·W1   (pierwszy wiersz pomnożyć przez 1/7),
(3) 7/2·W2   (drugi wiersz pomnożyć przez 7/2),
(4) W1 – 4/7·W2   (od pierwszego wiersza odjąć pomnożony przez 4/7 wiersz drugi);

przedstawione poniżej:

 \sim \left[ \left. \begin{matrix} 7 & 4 \\ 3-\frac{3}{7}\cdot7 & 2-\frac{3}{7}\cdot4 \end{matrix} \right| \begin{matrix} 1 & 0 \\ 0-\frac{3}{7} & 1-\frac{3}{7}\cdot0 \end{matrix} \right] = \left[ \left. \begin{matrix} 7 & 4 \\ 0 & \frac{2}{7} \end{matrix} \right| \begin{matrix} 1 & 0 \\ -\frac{3}{7} & 1 \end{matrix} \right] \sim
 \sim \left[ \left. \begin{matrix} 1 & \frac{4}{7} \\ 0 & 1 \end{matrix} \right| \begin{matrix} \frac{1}{7} & 0 \\ -\frac{3}{2} & \frac{7}{2} \end{matrix} \right] \sim   ← po operacjach (2) i (3)
 \sim \left[ \left.\begin{matrix} 1 - \frac{4}{7}\cdot0 & \frac {4}{7} - \frac{4}{7}\cdot1 \\ 0 & 1 \end{matrix} \right| \begin{matrix} \frac{1}{7} + \frac{4}{7}\cdot\frac{3}{2} & 0 - \frac{4}{7}\cdot\frac{7}{2} \\ -\frac{3}{2} & \frac{7}{2} \end{matrix} \right] = \left[ \left. \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right| \begin{matrix} 1 & -2 \\ -\frac{3}{2} & \frac{7}{2} \end{matrix} \right] = \left[ \left. I \right| A^{-1} \right]

lub w inny sposób (w 3. operacjach elementarnych):

(1) W1 – 2·W2   (od pierwszego wiersza odjąć pomnożony przez 2 wiersz drugi),
(2) W2 – 3·W1   (od drugiego wiersza odjąć pomnożony przez 3 wiersz pierwszy);
(3) 1/2·W2   (wiersz drugi pomnożyć przez 1/2);

otrzymujemy macierz:

\begin{bmatrix}1 & -2 \\ -\frac{3}{2} & \frac{7}{2}\end{bmatrix}   ,

która jest macierzą odwrotną do macierzy wyjściowej.