Metoda eliminacji Gaussa

metoda dokładna rozwi

ą

zywania

układu równa

ń

liniowych

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

,

1

1

3

1

3

2

1

2

1

1

1

1

2

1

2

3

1

23

2

1

22

1

1

21

1

1

1

1

3

1

13

2

1

12

1

1

11













=

⋅

+

+

⋅

+

⋅

+

⋅

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

=

⋅

+

+

⋅

+

⋅

+

⋅

=

⋅

+

+

⋅

+

⋅

+

⋅

n

n

nn

n

n

n

n

n

n

n

b

x

a

x

a

x

a

x

a

b

x

a

x

a

x

a

x

a

b

x

a

x

a

x

a

x

a

K

K

K

Metoda eliminacji Gaussa

A x = b det A

≠

0

Dwa etapy:

- eliminacji w przód (k – indeks kroku eliminacji w przód, k = 0, 1, 2, …, n-1)

- podstawiania wstecz

(1)

Krok pierwszy eliminacji w przód

( )

0

1

11

≠

a

Zakładamy,

ż

e

Pierwsze równanie układu równa

ń

(1) mno

ż

ymy kolejno przez współczynnik

( )
( )

,

,

,

3

,

2

dla

,

1

11

1

1

1

n

i

a

a

l

i

i

L

=

=

(2)

i odejmujemy stronami od równania o numerze i tego układu równa

ń

.

Otrzymujemy równanie

( )

( )

2

2

b

x

A

=

⋅

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

,

2

2

3

2

3

2

2

2

2

2

2

2

3

2

23

2

2

22

1

1

1

1

3

1

13

2

1

12

1

1

11












=

⋅

+

+

⋅

+

⋅

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

=

⋅

+

+

⋅

+

⋅

=

⋅

+

+

⋅

+

⋅

+

⋅

n

n

nn

n

n

n

n

n

n

b

x

a

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

x

a

K

K

K

(3)

Krok drugi eliminacji w przód

Zakładamy,

ż

e

( )

0

2

22

≠

a

Drugie równanie układu równa

ń

(3) mno

ż

ymy kolejno przez współczynnik

( )
( )

,

,

,

4

,

3

dla

,

2

22

2

2

2

n

i

a

a

l

i

i

L

=

=

I odejmujemy stronami od równania o numerze i tego układu równa

ń

Otrzymujemy układ równa

ń

( )

( )

3

3

b

x

A

=

⋅

(4)

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

,

3

3

3

3

3

3

3

3

3

3

3

33

2

2

2

2

3

2

23

2

2

22

1

1

1

1

3

1

13

2

1

12

1

1

11

















=

⋅

+

+

⋅

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

=

⋅

+

+

⋅

=

⋅

+

+

⋅

+

⋅

=

⋅

+

+

⋅

+

⋅

+

⋅

n

n

nn

n

n

n

n

n

n

n

b

x

a

x

a

b

x

a

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

x

a

K

K

K

K

(5)

Krok k (k

≤

n-1) etapu eliminacji w przód

Zakładamy,

ż

e

( )

0

≠

k

kk

a

Równanie o numerze k przekształconego w poprzednim kroku układu równa

ń

wymna

ż

amy przez współczynnik

( )
( )

,

,

,

2

,

1

dla

,

n

k

k

i

a

a

l

k

kk

k

ik

ik

L

+

+

=

=

(6)

i odejmujemy stronami od równania o numerze i układu równa

ń

z poprzedniego

kroku

Otrzymujemy równanie

( )

( )

1

1

+

+

=

⋅

k

k

b

x

A

Po wykonaniu n-1 kroków eliminacji w przód otrzymamy układ równa

ń

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )

( )












=

⋅

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

−

=

⋅

+

+

⋅

+

⋅

=

⋅

+

+

⋅

+

⋅

+

⋅

n

n

n

n

nn

n

n

n

n

b

x

a

b

x

a

x

a

x

a

b

x

a

x

a

x

a

x

a

2

2

2

2

3

2

23

2

2

22

1

1

1

1

3

1

13

2

1

12

1

1

11

L

L

(7)

Koniec etapu eliminacji w przód

Etap podstawiania wstecz

Krok 1

Z ostatniego wiersza równania (7) wyznaczamy

( )

( )

n

nn

n

n

n

a

b

x

=

(8)

Krok 2

Otrzyman

ą

warto

ść

*

n

n

x

x

=

podstawiamy w przedostatnim wierszu za

n

x

i wyznaczamy

1

−

n

x

Krok n

Po podstawieniu do pierwszego równania wyznaczonych poprzednio warto

ś

ci

*

2

*

1

*

,

,

,

x

x

x

n

n

L

−

Obliczamy warto

ść

*

1

x

Na tym ko

ń

czy si

ę

etap podstawiania wstecz i rozwi

ą

zywania równania

Uwagi

W rozwi

ą

zywanym równaniu elementy macierzy A na głównej przek

ą

tnej

musz

ą

by

ć ≠

0

Je

ż

eli ten warunek nie jest spełniony, to nale

ż

y pozamienia

ć

wiersze miejscami

Na przek

ą

tnej głównej wskazane jest umie

ś

ci

ć

wyrazy macierzy A o najwi

ę

kszej

bezwzgl

ę

dnej warto

ś

ci

Wybór elementu podstawowego – skrypt

Rozwi

ą

zanie układu składaj

ą

cego si

ę

z n równa

ń

liniowych

metod

ą

eliminacji Gaussa wymaga wykonania

3

3

2

3

n

n

n

−

+

działa

ń

mno

ż

enia i dzielenia

i

n

n

n

6

5

2

3

2

3

−

+

działa

ń

dodawania i odejmowania

Przykład

)

1

(

3

)

1

(

2

)

1

(

1

)

1

(

)

1

(

3

)

1

(

2

)

1

(

1

)

1

(

)

1

(

3

)

1

(

2

)

1

(

1

)

1

(

5

2

1

1

6

1

2

1

5

1

1

2

=

+

+

=

+

+

=

+

+

x

x

x

x

x

x

x

x

x