POLITECHNIKA POZNA ´

NSKA

Metoda eliminacji Gaussa

Autorzy:
Mikołaj B

UDA

Filip W

I ´

SNIEWSKI

15 grudnia 2012

M. Buda i F. Wi´sniewski

Metoda eliminacji Gaussa

Mamy do rozwi ˛

azania układ równa ´n z trzema niewiadomymi postaci:







a + 2b + c = 2
3a + 8b + c = 12
4b + c = 2

Nasz układ równa ´n w ogólno´sci mo˙zemy zapisa´c jako:

Ax = b

Gdzie:

A

- współczynniki znajduj ˛

ace si ˛e przy niewiadomych,

x

- nasze niewiadome,

b

- rozwi ˛

azanie równa ´n znajduj ˛

ace si ˛e po prawej stronie znaku równo´sci.





a

11

a

12

a

13

a

21

a

22

a

23

a

31

a

32

a

33





|

{z

}

A

·





a

b
c





|

{z

}

x

=





2

12

2





|

{z

}

b

Zmienne a, b, c to nasze niewiadome, które musimy wyznaczy´c. Z pomoc ˛

a przychodzi metoda eli-

minacji Gaussa.

Pierwszym krokiem jest stworzenie macierzy, dla warto´sci znajduj ˛

acych si ˛e przy współczynnikach

a

, b, c, która b ˛edzie wygl ˛

ada´c tak:

A =





1

2

1

3

8

1

0

4

1





Wektor zawieraj ˛

acy rozwi ˛

azania trzech równa ´n z układu równa ´n b b ˛edzie wygl ˛

ada´c tak:

b =





2

12

2





Pierwszy element w macierzy A w lewym górnym rogu nazywany jest

elementem osiowym (ang.

pivot).

Naszym zadaniem jest wyeliminowanie wszystkich niezerowych elementów znajduj ˛

acych si ˛e pod

nim, czyli w tym przypadku trójki.

W tym celu mno˙zymy pierwszy wiersz macierzy przez warto´s´c −3 i dodajemy go do drugiego wier-

sza.





1

2

1

3

8

1

0

4

1





Strona 1

M. Buda i F. Wi´sniewski

Metoda eliminacji Gaussa

Po wymno˙zeniu macierzy i dodaniu wierszy macierz przyjmuje posta´c:

A =





1

2

1

3

8

1

0

4

1





→





1

2

1

0

2

−2

0

4

1





Kolejnym etapem jest zaznaczenie nast ˛epnego elementu osiowego, którego szukamy na diagonali

macierzy, czyli na głównej przek ˛

atnej macierzy. Jak wida´c jest nim 2 w drugim wierszu w drugiej kolum-

nie.

W

PRZYPADKU ROZWI ˛

AZYWANIA UKŁADÓW RÓWNA ´

N TWORZY SI ˛

E MACIERZE KWADRATOWE

,

KTÓRYCH GŁÓWNA PRZEK ˛

ATNA ZAWIERAJ ˛

ACA ELEMENTY O RÓWNYCH WSKA ´

ZNIKACH WIER

-

SZA I KOLUMNY NAZYWANA JEST DIAGONAL ˛

A

,

B ˛

AD ´

Z GŁÓWN ˛

A PRZEK ˛

ATN ˛

A MACIERZY

.





x

x

x

x

x

x

x

x

x





← diagonala

Post ˛epujemy podobnie i zerujemy wszystkie elementy znajduj ˛

ace si ˛e poni˙zej tego elementu osio-

wego. W tym przypadku musimy pozby´c si ˛e liczby 4.

Mno˙zymy drugi wiersz macierzy przez −2 i dodajemy do trzeciego. W efekcie otrzymujemy:

A =





1

2

1

3

8

1

0

4

1





→





1

2

1

0

2

−2

0

4

1





→





1

2

1

0

2

−2

0

0

5





= U

Otrzyman ˛

a macierz U nazywamy macierz ˛

a górnotrójk ˛

atn ˛

a, która zawiera same 0 pod główn ˛

a dia-

gonal ˛

a macierzy.

Te same kroki powtarzamy dla wektora b, czyli:

1. Mno˙zymy pierwsz ˛

a składow ˛

a przez −3 i dodajemy do drugiej składowej.

b =





2

12

2





→





2
6
2





2. Mno˙zymy drug ˛

a składow ˛

a przez −2 i dodajemy do trzeciej składowej.

b =





2

12

2





→





2
6
2





→





2
6

−10





Ostatecznie znaj ˛

ac posta´c macierzy U , oraz wektora b mo˙zemy zapisa´c uproszczony układ równa ´n:







a + 2b + c = 2
2b − 2c = 6
5c = −10

Strona 2

M. Buda i F. Wi´sniewski

Metoda eliminacji Gaussa

Rozwi ˛

azaniem układu równa ´n s ˛

a liczby a = 6, b = −1, c = −2

W celu usprawnienia oblicze ´n wektor b mo˙zna zapisa´c w macierzy A tworz ˛

ac now ˛

a kolumn ˛e po

prawej stronie i oddzielaj ˛

ac j ˛

a tak jak poni˙zej:

A =





1

2

1

|

2

3

8

1

|

12

0

4

1

|

2





Powstaje w ten sposób

macierz rozszerzona.

W momencie stosowania eliminacji Gaussa mo˙zemy jednocze´snie operowa´c na ostatniej kolumnie

znajduj ˛

ac tym samym warto´sci wektora b

W

PRZYPADKU

,

GDY ELEMENT OSIOWY DROG ˛

A ELIMINACJI STANIE SI ˛

E ZEREM

,

MUSIMY ZA

-

MIENI ´

C WIERSZ Z WIERSZEM ZNAJDUJ ˛

ACYM SI ˛

E PONI ˙

ZEJ I KONTYNUOWA ´

C

.

Macierze eliminacji

W opisanej wcze´sniej eliminacji macierzy A mo˙zna dostrzec pewn ˛

a prawidłowo´s´c. Ka˙zda kolejna

macierz powstaje przez pewne operacje, które wykonuje si ˛e na wierszach macierzy doprowadzaj ˛

ac

ostatecznie do postaci górnotrójk ˛

atnej.

Ka˙zd ˛

a operacj ˛e po´sredni ˛

a mo˙zemy przedstawi´c w postaci iloczynu tzw. macierzy eliminacji oraz

odpowiedniej macierzy, których iloczyn doprowadza do kolejnej postaci itd.

Mamy macierz A:

A =





1

2

1

3

8

1

0

4

1





Naszym pierwszym elementem osiowym jest 1 w pierwszej kolumnie w pierwszym wierszu.

Chcemy j ˛

a doprowadzi´c do postaci, która redukuje wszystkie liczby pod elementem osiowym do 0,

czyli:





1

2

1

0

2

−2

0

4

1





Nale˙zy zastanowi´c si ˛e jaka macierz doprowadzi nas do tej postaci, mo˙zemy symbolicznie zapisa´c:





x

x

x

x

x

x

x

x

x





·





1

2

1

3

8

1

0

4

1





=





1

2

1

0

2

−2

0

4

1





Strona 3

M. Buda i F. Wi´sniewski

Metoda eliminacji Gaussa

Nale˙zy dobra´c w macierzy po lewej stronie takie warto´sci, aby wymno˙zona przez macierz A dawała

macierz po prawej stronie.

Jak wida´c pierwszy wiersz pozostaje bez zmian, wi ˛ec pierwszy wiersz naszej nowej macierzy przyj-

mie warto´s´c:



1

0

0



"Bierzemy 1 raz piewszy wiersz i 0 razy dwa pozostałe"

Trzeci wiersz nowej macierzy te˙z nie zmienia si ˛e, wi ˛ec mo˙zemy go zapisa´c jako:



0

0

1



"Bierzemy 1 raz ostatni wiersz i 0 razy dwa pozostałe"

Aby wyzerowa´c liczby pod elementem osiowym, czyli w tym przypadku 3, musieli´smy wymno˙zy´c

pierwszy wiersz przez −3 i doda´c go do drugiego, co mo˙zna zapisa´c w nast ˛epiuj ˛

acy sposób:



−3

1

0



"Wymnó˙z pierwszy wiersz przez −3 i dodaj do drugiego"

W efekcie macierz, której szukamy wygl ˛

ada tak:

E

21

=





1

0

0

−3

1

0

0

0

1





Jest to macierz, która posłu˙zyła do eliminacji elementu pod 1, czyli liczby 3. Liczba 3 znajdowała si ˛e

w drugim wierszu w pierwszej kolumnie

Niech m = wiersz, a n = kolumna

Mo˙zemy wi ˛ec zapisa´c w skrócie, ˙ze szukana macierz to macierz eliminacji E

21

, gdy˙z wyeliminowała

liczb ˛e znajduj ˛

ac ˛

a si ˛e w drugim wierszu pierwszej kolumny.

Kolejny krok zwi ˛

azany jest z drugim elementem osiowym. W tym przypadku z liczb ˛

a 2. Nasze

kolejne równanie przyjmuje posta´c:





x

x

x

x

x

x

x

x

x





·





1

2

1

0

2

−2

0

4

1





=





1

2

1

0

2

−2

0

0

5





W tym kroku chcemy wyzerowa´c 4, czyli liczb ˛e w trzecim wierszu drugiej kolumny. Szukamy wi ˛ec

macierzy eliminacji E

32

Strona 4

M. Buda i F. Wi´sniewski

Metoda eliminacji Gaussa

Pierwszy wiersz pozostaje bez zmian, drugi równie˙z. ˙

Zeby uzyska´c trzeci wiersz z usuni ˛et ˛

a liczb ˛

a

pod elementem osiowym musimy wymno˙zy´c drugi wiersz przez −2 i doda´c do 3. W efekcie prost ˛

a

drog ˛

a utworzyli´smy szukan ˛

a macierz E

32

, która wygl ˛

ada tak:

E

32

=





1

0

0

0

1

0

0

−2

1





Aby przekształci´c macierz A do postaci U musieli´smy wi ˛ec dokona´c dwóch przekształce ´n, które

opisuj ˛

a macierze eliminacji E

21

i E

32

. Najpierw mno˙zyli´smy macierz A przez macierz eliminacji E

21

:

E

21

· A

Nast ˛epnie otrzymany wynik mno˙zyli´smy przez macierz eliminacji E

32

co ostatecznie dawało macierz

U

:

E

32

· (E

21

· A) = U

Pami ˛etaj ˛

ac o tym, ˙ze mno˙zenie macierzy jest ł ˛

aczne mo˙zemy wywnioskowa´c:

E

32

· E

21

· A = U

M

ACIERZE ELIMINACJI ZAWSZE ZAPISUJEMY OD OSTATNIEJ ZNALEZIONEJ KU PIERWSZEJ CO

WYNIKA Z TEGO

,

˙

ZE MNO ˙

ZENIE MACIERZY NIE JEST PRZEMIENNE

.

Permutacje

Macierze permutacji przekształcaj ˛

a macierze wzgl ˛edem kolumn lub wierszy w zale˙zno´sci po której

stronie równania wyst ˛epuj ˛

a.



a

b

c

d



·



0

1

1

0



=



b

c

d

a



Mno˙z ˛

ac macierz przez macierz permutacji

z prawej strony dokonujemy przekształce ´n kolumno-

wych. W efekcie w powy˙zszym przypadku pierwsz ˛

a kolumn ˛e zapisujemy w miejsce drugiej kolumny, a

drug ˛

a kolumn ˛e w miejsce pierwszej kolumny.

N

ALE ˙

ZY PAMI ˛

ETA ´

C

,

˙

ZE

MACIERZ PERMUTACJI MUSI MIE ´

C TEN SAM WYMIAR CO MACIERZ

,

NA

KTÓREJ DZIAŁAMY

.

Przykład dla macierzy 3x3:





4

8

9

5

2

3

4

9

1





·





1

0

0

0

0

1

0

1

0





=





4

9

8

5

3

2

4

1

9





Mno˙z ˛

ac macierz przez macierz permutacji

z lewej strony dokonujemy przekształce ´n wierszowych.



0

1

1

0



·



a

b

c

d



=



c

d

a

b



Strona 5

M. Buda i F. Wi´sniewski

Metoda eliminacji Gaussa

Pierwszy wiersz zapisujemy na miejscu drugiego wiersza, a drugi wiersz na miejscu pierwszego

wiersza.

Przykład dla macierzy 3x3:





1

0

0

0

0

1

0

1

0





·





4

8

9

5

2

3

4

9

1





=





4

8

9

4

9

1

5

2

3





P

RZYKŁADY TE S ˛

A DOWODEM NA TO

,

˙

ZE

MNO ˙

ZENIE MACIERZY NIE JEST PRZEMIENNE

.

Macierz odwrotna

We´zmy macierz E

21

z poprzednich stron:

E

21

=





1

0

0

−3

1

0

0

0

1





Jest to macierz permutacji, która mno˙zy pierwszy wiersz przez −3 i dodaje do drugiego. Szukaj ˛

ac

macierzy do niej odwrotnej sprowadzamy si ˛e do znalezienia macierzy, która cofa t ˛e operacj ˛e. B ˛edzie to
oczywi´scie macierz, która wymno˙zy pierwszy wiersz przez 3 i doda do drugiego, czyli:

E

−1

21

=





1

0

0

3

1

0

0

0

1





Sytuacja wygl ˛

ada analogicznie równie˙z przy innych macierzach permutacji:

E

32

=





1

0

0

0

1

0

0

−2

1





E

−1

32

=





1

0

0

0

1

0

0

2

1





I

LOCZYN MACIERZY I MACIERZY DO NIEJ ODWROTNEJ DAJE

MACIERZ IDENTYCZNO ´

SCIOW ˛

A

.





1

0

0

0

1

0

0

−2

1





·





1

0

0

0

1

0

0

2

1





=





1

0

0

0

1

0

0

0

1





= I

Strona 6