czwartek, 31 marca 2016

Metoda eliminacji Gaussa

Metoda eliminacji Gaussa – 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.

Przykład

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}).
Autor: o

Brak komentarzy:

Prześlij komentarz

Subskrybuj: Komentarze do posta (Atom)