Eliminacja Gaussa

1

Bez wyboru elementu podstawowego

Przykład: rozwi ˛

a˙zmy układ równa´n

x + 2y + 2z

2x +

y + 2z

2x + 2y +

z

=
=
=

1

−1

0

(1)

Wyznacznik główny tego układu równy jest 5, a wi˛ec układ posiada jednoznaczne
rozwi ˛

azanie. Współczynnik w lewym górnym rogu wynosi 1, zatem przyst˛epu-

jemy do kolejnego kroku eliminacji Gaussa: Mno˙zymy pierwszy wiersz przez
współczynnik w pierwszej kolumnie, drugim wierszu i odejmujemy od drugiego
wiersza, mno˙zymy pierwszy wiersz przez współczynnik w pierwszej kolumnie,
trzecim wierszu i odejmujemy od trzeciego wiersza,

x + 2y + 2z

− 3y − 2z
− 2y − 3z

=
=
=

1

−3
−2

(2)

(Puste miejsca odpowiadaj ˛

a zerom.) w ten sposób pierwsza kolumna została

„wyczyszczona“. Dziel˛e drugi wiersz przez współczynnik diagonalny

x + 2y +

2z

y +

2
3

z

− 2y − 3z

=
=
=

1
1

−2

(3)

Mno˙z˛e drugi wiersz przez współczynnik w pierwszym wierszu, drugiej kolumnie
i odejmuj˛e od pierwszego, mno˙z˛e drugi wiersz przez współczynnik w trzecim
wierszu, drugiej kolumnie i odejmuj˛e od trzeciego:

x

+

2
3

z

y +

2
3

z

−

5
3

z

=
=
=

−1

1
0

(4)

1

Teraz „wyczyszczone“ s ˛

a dwie pierwsze kolumny. Ju˙z wida´c jakie jest rozwi ˛

aza-

nie tego układu równa´n, ale formalnie dokonajmy dwu kolejnych kroków elimi-
nacji Gaussa: Dziel˛e ostatnie z równa´n (4) przez współczynnik w trzecim wierszu
i trzeciej kolumnie; tak przekształcone równanie odejmuj˛e, po pomno˙zeniu przez
odpowiednie współczynniki, od pierwszego i drugiego równania. Otrzymuj˛e osta-
tecznie

x

y

z

=
=
=

−1

1
0

(5)

1.1

Eliminacja Gaussa–Jordana

Gdyby´smy w (3) odj˛eli odpowiednio przemno˙zony drugi wiersz tylko od wiersza
pierwszego, otrzymaliby´smy układ równa´n z macierz ˛

a trójk ˛

atn ˛

a górn ˛

a:

x + 2y +

2z

y +

2
3

z

−

5
3

z

=
=
=

1
1
0

(6)

Układ taki mo˙zna bardzo prosto rozwi ˛

aza´c metod ˛

a backubstitution, czyli id ˛

ac od

dołu do góry. Ogólnie taka forma eliminacji Gaussa, w której przekształca si˛e
tylko wiersze le˙z ˛

ace poni˙zej bie˙z ˛

acego, nazywa si˛e eliminacj ˛

a Gaussa–Jordana.

2

Element podstawowy

Spróbujmy zastosowa´c eliminacj˛e Gaussa do nast˛epuj ˛

acego układu równa´n:

x + 2y + 2z

2x + 4y + 2z
2x + 2y +

z

=
=
=

1

−1

0

(7)

Wyznacznik główny tego układu równa si˛e −4, a wi˛ec układ ma jednoznaczne
rozwi ˛

azanie. Po „wyczyszczeniu“ pierwszej kolumny otrzymujemy

x + 2y + 2z

− 2z

− 2y − 3z

=
=
=

1

−3
−2

(8)

w kolejnym kroku eliminacji Gaussa nale˙zy dzieli´c przez współczynnik stoj ˛

acy

w drugim wierszu i drugiej kolumnie przekształconego układu. Jednak współ-
czynnik ten wynosi zero i, jak si˛e wydaje, algorytm zawodzi. Sytuacj˛e mo˙ze
uratowa´c wła´sciwy wybór współczynnika, przez który nale˙zy w danym kroku
dzieli´c; współczynnik ten nazywa si˛e elementem podstawowym.

2

2.1

Cz˛e´sciowy wybór elementu podstawowego

Gdyby´smy w (8) zamienili miejscami drugi i trzeci wiersz,

x + 2y + 2z

− 2y − 3z

− 2z

=
=
=

1

−2
−3

(9)

sytuacja byłaby uratowana. Dalsze rozwi ˛

azywanie układu (9) daje [x, y, z] =

[1/2, −5/4, 3/2]. Przechodz ˛

ac z (8) do (9) tak przestawiali´smy wiersze układu,

aby dzieli´c przez element niezerowy, przy czym do dyspozycji były tylko wiersze
le˙z ˛

ace poni˙zej wiersza bie˙z ˛

acego (u˙zycie wierszy le˙z ˛

acych powy˙zej zniszczyłoby

„wyczyszczenie“ poprzednich kolumn). Gdyby do wyboru było wi˛ecej wierszy,
nale˙załoby wybra´c taki, w którym współczynnik w drugiej (bo bie˙z ˛

acy wiersz jest

drugi) kolumnie byłby najwi˛ekszy na moduł.

2.2

Pełny wybór elementu podstawowego

Czasami wygodne jest wybranie w charakterze elementu podstawowego najwi˛ek-
szego (na moduł) z wszystkich elementów le˙z ˛

acych w prawym dolnym rogu ma-

cierzy, nie za´s tylko w bie˙z ˛

acej kolumnie poni˙zej bie˙z ˛

acego wiersza. Nazywa si˛e

to pełnym wyborem elementu podstawowego. Przekształcaj ˛

ac w ten sposób (7)

dostajemy

4˜

x + 2˜

y + 2˜

z

2˜

x +

˜

y + 2˜

z

2˜

x + 2˜

y +

˜

z

=
=
=

−1

1
0

(10)

gdzie

˜

x = y , ˜

y = x , ˜

z = z .

(11)

w kolejnym kroku otrzymujemy

˜

x +

1
2

˜

y +

1
2

˜

z

˜

y

˜

z

=
=
=

−

1
4

1
2

3
2

(12)

co ju˙z mo˙zna bezpo´srednio rozwi ˛

aza´c otrzymuj ˛

ac [˜

x, ˜

y, ˜

z] = [−5/4, 1/2, 3/2].

Nale˙zy jeszcze odwróci´c transformacj˛e (11), co wynika z mieszania si˛e kolumn
w pełnym wyborze elementu podstawowego. Poniewa˙z dla bardziej zło˙zonych
układów odwikływanie tego typu transformacji mo˙ze by´c kosztowne, na ogół
ograniczamy si˛e do cz˛e´sciowego wyboru elementu podstawowego.

3

3

Niestabilno´s´c numeryczna

Rozwa˙zmy układ równa´n

x +

2y + 2z

2x + 4.001y + 2z
2x +

2y +

z

=
=
=

1

−1

0

(13)

Zastosowanie pierwszego kroku eliminacji Gaussa do tego układu daje

x +

2y + 2z

0.001y − 2z

−

2y − 3z

=
=
=

1

−3
−2

(14)

W odró˙znieniu od (8), układ (14) mo˙zna dalej rozwi ˛

azywa´c poprzez elimi-

nacj˛e Gaussa bez wyboru elementu podstawowego, jednak mo˙ze to prowadzi´c
do znacznego wzrostu bł˛edu zaokr ˛

aglenia, jako ˙ze wymagałoby dzielenia przez

liczb˛e mał ˛

a. Wybór elementu podstawowego (na ogół tylko cz˛e´sciowy) zapewnia

zmniejszenie bł˛edu zaokr ˛

aglenia poprzez wybieranie mo˙zliwie najwi˛ekszego (na

moduł) elementu w charakterze dzielinika.

4