1
Bez wyboru elementu podstawowego
Przykład: rozwiążmy układ równań
x + 2y + 2z =
1
2x +
y + 2z = −1
(1)
2x + 2y +
z =
0
Wyznacznik główny tego układu równy jest 5, a więc układ posiada jednoznaczne rozwiązanie. Współczynnik w lewym górnym rogu wynosi 1, zatem przystępu-jemy do kolejnego kroku eliminacji Gaussa: Mnożymy pierwszy wiersz przez współczynnik w pierwszej kolumnie, drugim wierszu i odejmujemy od drugiego wiersza, mnożymy pierwszy wiersz przez współczynnik w pierwszej kolumnie, trzecim wierszu i odejmujemy od trzeciego wiersza, x + 2y + 2z =
1
− 3y − 2z = −3
(2)
− 2y − 3z = −2
(Puste miejsca odpowiadają zerom.) w ten sposób pierwsza kolumna została
„wyczyszczona“. Dzielę drugi wiersz przez współczynnik diagonalny x + 2y +
2z =
1
y +
2 z =
1
(3)
3
− 2y − 3z = −2
Mnożę drugi wiersz przez współczynnik w pierwszym wierszu, drugiej kolumnie i odejmuję od pierwszego, mnożę drugi wiersz przez współczynnik w trzecim wierszu, drugiej kolumnie i odejmuję od trzeciego: x
+
2 z = −1
3
y +
2 z =
1
(4)
3
− 5 z =
0
3
1
Teraz „wyczyszczone“ są dwie pierwsze kolumny. Już widać jakie jest rozwiązanie tego układu równań, ale formalnie dokonajmy dwu kolejnych kroków eliminacji Gaussa: Dzielę ostatnie z równań (4) przez współczynnik w trzecim wierszu i trzeciej kolumnie; tak przekształcone równanie odejmuję, po pomnożeniu przez odpowiednie współczynniki, od pierwszego i drugiego równania. Otrzymuję osta-tecznie
x
= −1
y
=
1
(5)
z =
0
1.1
Eliminacja Gaussa–Jordana
Gdybyśmy w (3) odjęli odpowiednio przemnożony drugi wiersz tylko od wiersza pierwszego, otrzymalibyśmy układ równań z macierzą trójkątną górną: x + 2y +
2z = 1
y +
2 z = 1
(6)
3
− 5 z = 0
3
Układ taki można bardzo prosto rozwiązać metodą backubstitution, czyli idąc od dołu do góry. Ogólnie taka forma eliminacji Gaussa, w której przekształca się tylko wiersze leżące poniżej bieżącego, nazywa się eliminacj ˛
a Gaussa–Jordana.
2
Element podstawowy
Spróbujmy zastosować eliminację Gaussa do następującego układu równań: x + 2y + 2z =
1
2x + 4y + 2z = −1
(7)
2x + 2y +
z =
0
Wyznacznik główny tego układu równa się −4, a więc układ ma jednoznaczne rozwiązanie. Po „wyczyszczeniu“ pierwszej kolumny otrzymujemy x + 2y + 2z =
1
− 2z = −3
(8)
− 2y − 3z = −2
w kolejnym kroku eliminacji Gaussa należy dzielić przez współczynnik stojący w drugim wierszu i drugiej kolumnie przekształconego układu. Jednak współ-
czynnik ten wynosi zero i, jak się wydaje, algorytm zawodzi. Sytuację może uratować właściwy wybór współczynnika, przez który należy w danym kroku dzielić; współczynnik ten nazywa się elementem podstawowym.
2
Częściowy wybór elementu podstawowego Gdybyśmy w (8) zamienili miejscami drugi i trzeci wiersz, x + 2y + 2z =
1
− 2y − 3z = −2
(9)
− 2z = −3
sytuacja byłaby uratowana. Dalsze rozwiązywanie układu (9) daje [x, y, z] =
[1/2, −5/4, 3/2]. Przechodząc z (8) do (9) tak przestawialiśmy wiersze układu, aby dzielić przez element niezerowy, przy czym do dyspozycji były tylko wiersze leżące poniżej wiersza bieżącego (użycie wierszy leżących powyżej zniszczyłoby
„wyczyszczenie“ poprzednich kolumn). Gdyby do wyboru było więcej wierszy, należałoby wybrać taki, w którym współczynnik w drugiej (bo bieżący wiersz jest drugi) kolumnie byłby największy na moduł.
2.2
Pełny wybór elementu podstawowego
Czasami wygodne jest wybranie w charakterze elementu podstawowego największego (na moduł) z wszystkich elementów leżących w prawym dolnym rogu ma-cierzy, nie zaś tylko w bieżącej kolumnie poniżej bieżącego wiersza. Nazywa się to pełnym wyborem elementu podstawowego. Przekształcając w ten sposób (7) dostajemy
4˜
x + 2˜
y + 2˜
z = −1
2˜
x +
˜
y + 2˜
z =
1
(10)
2˜
x + 2˜
y +
˜
z =
0
gdzie
˜
x = y , ˜
y = x , ˜
z = z .
(11)
w kolejnym kroku otrzymujemy
˜
x +
1 ˜
y +
1 ˜
z = − 1
2
2
4
˜
y
=
1
(12)
2
˜
z =
3
2
co już można bezpośrednio rozwiązać otrzymując [˜
x, ˜
y, ˜
z] = [−5/4, 1/2, 3/2].
Należy jeszcze odwrócić transformację (11), co wynika z mieszania się kolumn w pełnym wyborze elementu podstawowego. Ponieważ dla bardziej złożonych układów odwikływanie tego typu transformacji może być kosztowne, na ogół
ograniczamy się do częściowego wyboru elementu podstawowego.
3
Niestabilność numeryczna
Rozważmy układ równań
x +
2y + 2z =
1
2x + 4.001y + 2z = −1
(13)
2x +
2y +
z =
0
Zastosowanie pierwszego kroku eliminacji Gaussa do tego układu daje x +
2y + 2z =
1
0.001y − 2z = −3
(14)
−
2y − 3z = −2
W odróżnieniu od (8), układ (14) można dalej rozwiązywać poprzez eliminację Gaussa bez wyboru elementu podstawowego, jednak może to prowadzić do znacznego wzrostu błędu zaokrąglenia, jako że wymagałoby dzielenia przez liczbę małą. Wybór elementu podstawowego (na ogół tylko częściowy) zapewnia zmniejszenie błędu zaokrąglenia poprzez wybieranie możliwie największego (na moduł) elementu w charakterze dzielinika.
4