METODY NUMERYCZNE
Wykład 6.
Rozwiązywanie układów równań liniowych
dr hab. inż. Katarzyna Zakrzewska, prof. AGH
1
Met.Numer. wykład 6
Plan
" Metody dokładne
" Metoda eliminacji Gaussa
" Metoda Gaussa-Seidla
" Rozkład LU
2
Met.Numer. wykład 6
Układ równań liniowych
Układ równań liniowych:
Ax = b
gdzie:
" A  macierz o m wierszach i n kolumnach
" x  wektor o n niewiadomych
" b  wektor m danych liczb
możliwe rozwiązania:
" Nieskończenie wiele rozwiązań
" Dokładnie jedno rozwiązanie
" Brak rozwiązania (układ sprzeczny)
3
Met.Numer. wykład 6
Pojęcie normy
T
x = [x1, x2, ..., xn]
W przestrzeni Rn, której elementami są wektory:
x = x1 + x2 +...+ xn
1
1/ 2
2 2 2
x = (x1 + x2 + ...+ xn )
2
x = max{x1 , x2 , ..., xn }
"
Dla dowolnego wektora x T Rn, obowiązują nierówności:
x d" x d" x d" n x d" n x
" 2 1 2 "
4
Met.Numer. wykład 6
Metody rozwiązywania układów
algeraicznych równań liniowych
Metody dokładne - definicja
Jeśli rozwiązanie układu równań Ax=b polega na
takim przekształceniu danych A i b, że przy
założeniu dokładnie wykonywanych działań
arytmetycznych po skończonej liczbie działań
otrzymujemy rozwiązanie, to taką metodę
rozwiązania nazywamy metodą dokładną.
5
Met.Numer. wykład 6
Metody dokładne
Metody dokładne - cechy
" Mała liczba obliczeń potrzebnych do wyznaczenia
rozwiązania
" Jeśli zadanie jest z
le uwarunkowane numerycznie, to
wyznaczone rozwiązanie może być obarczone dużym
błędem.
" Mogą być niestabilne ze względu na błędy zaokrągleń
" Przekształcenie macierzy A obciąża w dużym stopniu
pamięć maszyny, zwłaszcza jeśli początkowe dane A i b
należy przechować celem ostatecznego sprawdzenia
6
Met.Numer. wykład 6
Metody dokładne - przykład
Przykład  wzory Cramera Sposób 1:
a22b1 - a12b2 a11b2 - a21b1
a11x1 + a12x2 = b1
x1 =
x2 =
a11a22 - a21a12
a11a22 - a21a12
a21x1 + a22x2 = b2
Zakładamy dokładność do 2 cyfr dziesiętnych , każdy wynik przed
dalszymi obliczeniami jest zaokrąglany
0,99x1 + 0,70x2 = 0,54
0,70x1 + 0,50x2 = 0,38
a11a22 = 0,99�"0,50 = 0,4950 = 0,50
a21a12 = 0,70�"0,70 = 0,4900 = 0,49
a11a22 - a21a12 = 0,50 - 0,49 = 0,01
7
Met.Numer. wykład 6
Metody dokładne - przykład
a22b1 - a12b2 = 0,50�"0,54 - 0,70�"0,38
= 0,2700 - 0,2660 = 0,27 - 0,27 = 0
a11b2 - a21b1 = 0,99�"0,38 - 0,70�"0,54
= 0,3762 - 0,3780 = 0,38 - 0,38 = 0
0
x1 = = 0
0,01
0
x2 = = 0
0,01
Dokładne rozwiązanie tego układu równań daje wynik:
x1 = 0,80
x2 = -0,36
8
Met.Numer. wykład 6
Metody dokładne  przykład cd.
Sposób 2: metoda eliminacji Gaussa
0,99x1 + 0,70x2 = 0,54
0,70x1 + 0,50x2 = 0,38
Eliminujemy niewiadomą x1 z drugiego równania układu równań.
W tym celu mnożymy pierwsze równanie przez:
a21 0,70
= = 0,7070 E" 0,71
a11 0,99
Otrzymujemy:
0.70x1 + 0,4949x2 = 0,3818
0,70x1 + 0,50x2 = 0,38
Odejmując równania stronami po wcześniejszym zaokrągleniu do 2
cyfr:
0,00x2 = 0,00
czyli układ nieoznaczony, posiadający nieskończenie wiele
rozwiązań.
9
Met.Numer. wykład 6
Układy równań z macierzą trójkątną
Macierz trójkątna  definicja
Macierz trójkątną nazywamy macierzą trójkątną dolną (górną),
jeżeli wszystkie elementy nad (pod) diagonalą są równe
zeru.
Macierz trójkątna dolna Macierz trójkątna górna
10
Met.Numer. wykład 6
Układy równań z macierzą trójkątną
Obliczenie wyznacznika macierzy trójkątnej sprowadza się
do wymnożenia elementów leżących na głównej
przekątnej:
n
det(L) = = l1,1 �"l2,2 �"...ln,n
"li,i
i=1
n
det(U ) = = u1,1 �"u2,2 �"...un,n
"ui,i
i=1
11
Met.Numer. wykład 6
Układy równań z macierzą trójkątną
Jeżeli macierz A układu n równań z n niewiadomymi Ax=b
jest macierzą trójkątną (dolną lub górną), to rozwiązanie x
takiego układu równań można uzyskać wykonując małą liczbę
działań arytmetycznych i przy małych błędach zaokrągleń
a11x1 + a12x2 +...+ a1,n-1xn-1 + a1nxn = b1
a22x2 + ...+ a2,n-1xn-1 + a2nxn = b2
.....................................................
an-1,n-1xn-1 + an-1,nxn = bn-1
bn
annxn = bn
xn =
Ogólnie
ann
bi - ainxn -...- aii+1xi+1
xi =
i = n -1, n - 2, ..., 1
aii
12
Met.Numer. wykład 6
Układy równań z macierzą trójkątną
Koszt obliczeniowy:
Dla wyznaczenia wektora x należy wykonać M
mnożeń i dzieleń oraz D dodawań:
1 1
M = n2 + n
2 2
1 1
D = n2 + n
2 2
13
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Etap pierwszy (zwany etapem eliminacji  do przodu
zmiennych)
a11x1 + a12x2 + a13x3 + ... + a1nxn = b1
a21x1 + a22x2 + a23x3 + ... + a2nxn = b2
.....................
an1x1 + an2x2 + an3x3 + ... + annxn = bn
Wymaganych jest n-1 kroków eliminacji
14
14
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Krok 1. Od drugiego wiersza odejmujemy pierwszy podzielony przez
a11 i pomnożony przez a21
a21
a11x1 + a12x2 + a13x3 + ...+ a1nxn = b1
a11
a21 a21 a21
a21x1 + a12x2 + ... + a1nxn = b1
a11 a11 a11
a21x1 + a22x2 + a23x3 +...+ a2nxn = b2
Otrzymujemy:
�# ś# �# ś#
a21 a21 a21
ś#
ś#a22 - a11 a12 ź# + ... + ś# ź#xn
ź#x2 ś#a2n - a11 a1n ź# = b2 - a11 b1
�# # �# #
15
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Podobnie postępujemy z pozostałymi wierszami:
a11x1 + a12x2 + a13x3 + ... + a1nxn = b1
' ' ' '
a22x2 + a23x3 + ... + a2nxn = b2
' ' ' '
a32x2 + a33x3 + ... + a3nxn = b3
.....................
' ' ' '
an2x2 + an3x3 + ... + annxn = bn
a21
'
gdzie:
a22 = a22 - a12
a11
.
.
.
a21
'
a2n = a2n - a1n
a11
16
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Krok 2. Powtarzamy procedurę kroku 1 dla trzeciego
wiersza
a'32
' ' ' '
a22x2 + a23x3 + ... + a2nxn = b2
a'22
' ' '
a32 a32 a32 '
' ' '
a32x2 + a23 ' x3 + ... + a2n ' xn = b2
'
a22 a22 a22
' ' ' '
a32x2 + a33x3 + ... + a3nxn = b3
Otrzymujemy:
�# ś# �# ś#
a'32 a'32 a'32
'
ś#
ś#a33 - a'22 a'23 ź# + ...+ ś# ź#xn
ź#x3 ś#a'3n - a'22 a'2n ź# = b'3- a'22 b'2
�# # �# #
17
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Po kroku 2 otrzymujemy
' ' ' '
a22x2 + a23x3 + ... + a2nxn = b2
" " "
a33x3 + ... + a3nxn = b3
.....................
" " "
an3x3 + ... + annxn = bn
18
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Pod koniec kroku n-1 układ równań przybiera postać:
a11x1 + a12 x2 + a13x3 + ... + a1n xn = b1
' ' ' '
a22x2 + a23x3 + ... + a2nxn = b2
" " "
a33x3 + ... + a3nxn = b3
.....................
(n
ann-1)xn = bn(n-1 )
19
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Po przeprowadzeniu n-1 kroków eliminacji zmiennych
otrzymane równania możemy zapisać w postaci
macierzy:
a11 a12 a13 L a1n x1 b1
Ą# ń#Ą# ń# Ą# ń#
ó# '
0 a' a' L a' Ą#ó#x2Ą# ó# b2 Ą#
22 23 2n
ó# Ą#ó# Ą# ó# Ą#
"
ó# 0 0 a" L a"n Ą#ó#x3Ą# = ó# b3 Ą#
33 3
ó# Ą#ó# Ą# ó# Ą#
M M M L M M M
ó# Ą#ó# Ą# ó# Ą#
(n (n-1
ó# Ą#ó# Ą# ó# Ą#
0 0 0 0 ann-1 )Ś#Ł#xn Ś# Ł#bn )Ś#
Ł#
Otrzymana macierz jest macierzą trójkątną!
20
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Etap drugi zwany postępowaniem odwrotnym
(podstawieniem wstecznym)
Ponieważ otrzymana macierz jest macierzą trójkątną korzystamy
ze wzorów:
(
bnn-1)
xn =
(n
ann-1)
-1)
bi(i-1) - ai(ii-1)xi+1 - ai(ii-1)xi+2 -...- ai(in xn
, +1 , +2 ,
xi =
dla i = n -1,...,1
(
aiii-1)
n
(
bi(i-1) - aiji-1)xj
"
j=i+1
xi = dla i = n -1,...,1
(
aiii-1)
21
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Metoda eliminacji Gaussa  koszt obliczeniowy
A
ączna ilość mnożeń i dzieleń:
1 1
M = n3 + n2 - n
3 3
A
ączna ilość dodawań:
1 1 5
D = n3 + n2 - n
3 2 6
22
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
Przykład:
Czas t Prędkość
(s) (m/s)
5 106.8
8 177.2
12 279.2
Prędkość rakiety została przybliżona wielomianem:
2
v(t) = a1t + a2t + a3 ,
5 d" t d" 12.
Znalez
ć współczynniki a1, a2, a3 metodą eliminacji Gaussa i
prędkość w chwili t = 6 s
23
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
2
v(t ) = a1t + a t + a , 5 d" t d" 12.
2 3
Ą# ń#
t12 t1 1 a v1
Ą# ń# Ą# ń#
1
ó# Ą#
Ą# ó# Ą#
2
t 1Ą# ó# a = v
2 2 2
ó#t 2
ó# Ą# ó# Ą#
2
ó#t3
ó# Ą# ó# Ą#
t3 1Ą# Ł# a v
3 3
Ś# Ł# Ś#
Ł# Ś#
t1 = 5 s , v (5 ) = 106 ,8 m / s
t = 8 s , v (8 ) = 177 ,2 m / s
2
t3 = 12 s , v (12 ) = 279 ,2 m / s
25 5 1 a1 106 .8
Ą# ń# Ą# ń# Ą# ń#
ó# ó#177 .2 Ą#
64 8 1Ą# ó#a2 Ą# =
ó# Ą# ó# Ą# ó# Ą#
ó# Ą# Ą#
3
Ł#144 12 1Ś# ó# Ą# ó#
Ł#a Ś# Ł#279 .2Ś#
24
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
25 5 1 M 106.8
Ą# ń#
Podzielić równanie 1
64
ó#
= 2.56
64 8 1 M 177.2Ą# przez 25 i pomnożyć
ó# Ą#
25
przez 64
ó# Ą#
Ł#144 12 1 M 279.2Ś#
[25 5 1 M 106.8]� 2.56 = [64 12.8 2.56 M 273.408]
[64 8 1 M 177.2]
Odjąć wynik od równania nr 2
-[64 12.8 2.56 M 273.408]
[0 - 4.8 -1.56 M - 96.208]
25 5 1 M 106.8
Ą# ń#
ó#
Otrzymujemy
0 - 4.8 -1.56 M - 96.208Ą#
ó# Ą#
ó# Ą#
1 M 279.2
Ł#144 12 Ś#
25
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
25 5 1 M 106.8
Ą# ń#
Podzielić równanie 1
144
ó#
= 5.76
0 - 4.8 -1.56 M - 96.208Ą#
przez 25 i pomnożyć
ó# Ą#
25
przez 144
ó# Ą#
1 M 279.2
Ł#144 12 Ś#
[25 5 1 M 106.8]�5.76 = [144 28.8 5.76 M 615.168]
.
[144 12 1 M 279.2]
Odjąć wynik od równania
-[144 28.8 5.76 M 615.168]
nr 3
[0 -16.8 - 4.76 M - 335.968]
25 5 1 M 106.8
Ą# ń#
Po pierwszym kroku eliminacji
ó# Ą#
0 - 4.8 -1.56 M - 96.208
ó# Ą#
ó# Ą#
0 -16.8 - 4.76 M - 335.968Ś#
Ł#
26
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
Podzielić równanie 2 -16.8
25 5 1 M 106.8
Ą# ń#
= 3.5
przez -4.8 i
ó# Ą#
- 4.8
0 - 4.8 -1.56 M - 96.208
ó# Ą#
pomnożyć przez -
ó# Ą#
0 -16.8 - 4.76 M - 335.968Ś#
16.8
Ł#
[0 - 4.8 -1.56 M - 96.208]�3.5 = [0 -16.8 - 5.46 M - 336.728]
[0 -16.8 - 4.76 M 335.968]
Odjąć wynik od równania
-[0 -16.8 - 5.46 M - 336.728]
nr 3
[0 0 0.7 M 0.76]
25 5 1 M 106.8
Ą# ń#
Po drugim kroku eliminacji
ó#
0 - 4.8 -1.56 M - 96.208Ą#
ó# Ą#
ó# Ą#
0 0 0.7 M 0.76
Ł# Ś#
27
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
25 5 1 M 106.8 25 5 1 a1 106.8
Ą# ń# Ą# ń# Ą# ń# Ą# ń#
ó# ó# ó#
0 - 4.8 -1.56 M - 96.2Ą# �! 0 - 4.8 -1.56Ą# ó#a2 Ą# = 96.208Ą#
ó# Ą# ó# Ą# ó# Ą# ó#- Ą#
ó# Ą# ó# Ą# ó# Ą# ó# Ą#
0 0 0.7 M 0.7 0 0 0.7 0.76
3
Ł# Ś# Ł# Ś# Ł#a Ś# Ł# Ś#
Eliminacja wsteczna
Obliczanie a3
0.7a3 = 0.76
0.76
a3 =
0.7
a3 = 1.08571
28
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
25 5 1 a1 106.8
Ą# ń# Ą# ń# Ą# ń#
ó# ó#
0 - 4.8 -1.56Ą# ó#a2 Ą# = 96.208Ą#
ó# Ą# ó# Ą# ó#- Ą#
ó# Ą# ó# Ą# ó# Ą#
0 0 0.7 0.76
3
Ł# Ś# Ł#a Ś# Ł# Ś#
Obliczanie a2
- 4.8a2 -1.56a3 = -96.208
- 96.208 +1.56a3
a3 = 1.08571
a2 =
- 4.8
- 96.208 +1.56�1.08571
a2 =
- 4.8
a2 =19.6905
29
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
25 5 1 a1 106.8
Ą# ń# Ą# ń# Ą# ń#
ó# ó#
0 - 4.8 -1.56Ą# ó#a2 Ą# = 96.2Ą#
ó# Ą# ó# Ą# ó#- Ą#
ó# Ą# ó# Ą# ó# Ą#
0 0 0.7 0.76
3
Ł# Ś# Ł#a Ś# Ł# Ś#
a3 = 1.08571
a2 = 19.6905
Obliczanie a1
25a1 + 5a2 + a3 =106.8
106.8 - 5a2 - a3
a1 =
25
106.8 - 5�19.6905 -1.08571
=
25
= 0.290472
30
Met.Numer. wykład 6
Metoda eliminacji Gaussa - przykład
25 5 1 a1 106 .8
Ą# ń# Ą# ń# Ą# ń#
ó# ó#177 .2 Ą#
64 8 1Ą# ó#a2 Ą# =
ó# Ą# ó# Ą# ó# Ą#
ó#144 12 1Ą# ó#a3 Ą# ó#279 .2Ą#
Ł# Ś# Ł# Ś# Ł# Ś#
Rozwiązanie:
a1 0.290472
Ą# ń# Ą# ń#
ó#a Ą# ó# Ą#
= 19.6905
2
ó# Ą# ó# Ą#
ó# Ą# ó# Ą#
1.08571
3
Ł#a Ś# Ł# Ś#
v(t)= a1t2 + a2t + a3 = 0.290472t2 +19.6905t +1.08571, 5 d" t d" 12
2
v(6)= 0.290472(6) +19.6905(6)+1.08571 =129.686 m/s.
31
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Wady metody:
" Może nastąpić zatrzymanie procesu obliczeń w powodu
dzielenia przez zero.
" Jest szczególnie podatna na narastanie błędu zaokrąglenia.
Zalety metody:
" Liczba wykonywanych działań w metodzie eliminacji Gaussa
jest bez porównania mniejsza niż przy pomocy wzorów
Cramera
W przypadku 15 równań:
M=1345 mnożeń w metodzie eliminacji Gaussa i M=5"1012 dla
wzorów Cramera
Maszyna cyfrowa wykonująca 106 mnożeń na sekundę:
0,01 s w metodzie eliminacji Gaussa i ponad rok dla wzorów Cramera
32
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Dzielenie przez zero może wystąpić podczas każdego
kroku eliminacji zmiennych
12 10 - 7 x1 15
12 10 - 7 x1 15
Ą# ń# Ą# ń# Ą# ń#
Ą# ń# Ą# ń# Ą# ń#
ó# ó#6.5Ą#
ó# Ą# ó#x Ą# ó#14Ą#
0 0 6.5Ą# ó#x2Ą# =
6 5 3 =
2
ó# Ą# ó# Ą# ó# Ą#
ó# Ą# ó# Ą# ó# Ą#
ó# Ą# ó# Ą# ó# Ą#
0 - 21 19
ó#24 -1 5 Ą# ó#x3Ą# ó#28Ą#
3
Ł# Ś# Ł#x Ś# Ł#- 2Ś#
Ł# Ś# Ł# Ś# Ł# Ś#
w następnym kroku, dzielenie przez zero
33
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Układ równań:
20 15 10 x1 45
Ą# ń# Ą# ń# Ą# ń#
ó# Ą# ó#x Ą# ó#1.751Ą#
=
2
ó#- 3 - 2.249 7 Ą# ó# Ą# ó# Ą#
ó# 5 1 3 Ą# ó#x3Ą# ó# 9 Ą#
Ł# Ś# Ł# Ś# Ł# Ś#
Rozwiązanie z
Rozwiązanie z
dokładnością
Rozwiązanie
dokładnością
5 cyfr dziesiętnych
dokładne
6 cyfr dziesiętnych
w każdym kroku
w każdym kroku
x1 1
x1 0.9625 x1 0.625
Ą# ń# Ą# ń#
Ą# ń# Ą# ń# Ą# ń# Ą# ń#
ó#x Ą# ó#1Ą#
ó#x Ą# ó# Ą#
ó#x Ą# ó# Ą#
=
= 1.05 = 1.5
2
2 2
ó# Ą# ó# Ą#
ó# Ą# ó# Ą#
ó# Ą# ó# Ą#
ó# x3Ą# ó#1Ą#
ó# Ą# ó#
Ł# Ś# Ł# Ś# ó#x3Ą# ó#0.999995Ą#
3 Ś#
Ł# Ś# Ł# Ś# Ł#x Ś# Ł#0.99995Ą#
34
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Metoda eliminacji Gaussa-Crouta (ang. partial pivoting)
- z częściowym wyborem elementu podstawowego
" Zapobiega dzieleniu przez zero.
" Zmniejsza błąd numeryczny.
Elementem podstawowym nazywamy ten element macierzy A,
za pomocą którego eliminujemy zmienną z dalszych równań.
Dotychczas jako elementy podstawowe wybieraliśmy element
leżący na diagonali
akk
Stosując częściowy wybór elementu podstawowego wybieramy
ten z elementów k-tej kolumny w k-tej macierzy, który ma
największy moduł. Przez zmianę kolejności wierszy w macierzy
można uzyskać element podstawowy leżący na diagonali
35
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Przykład :
25 5 1 a1 106.8
Ą# ń# Ą# ń# Ą# ń#
ó# ó#177.2Ą#
64 8 1Ą# ó#a2 Ą# =
ó# Ą# ó# Ą# ó# Ą#
ó# Ą#
3
Ł#144 12 1Ś# ó# Ą# ó# Ś#
Ł#a Ś# Ł#279.2Ą#
25, 64 , 144
Wartości w pierwszej kolumnie to:
25 5 1 M 106.8
Ą# ń#
144 12 1 M 279.2
Ą# ń#
ó#
ó#
64 8 1 M 177.2Ą#
�! 64 8 1 M 177.2Ą#
ó# Ą#
ó# Ą#
ó# Ą#
ó# Ą#
25 5 1 M 106.8Ś#
Ł#144 12 1 M 279.2Ś#
Ł#
Zamiana wiersza trzeciego z pierwszym
36
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Przykład :
25 5 1 a1 106.8
Ą# ń# Ą# ń# Ą# ń#
ó# ó#177.2Ą#
64 8 1Ą# ó#a2 Ą# =
ó# Ą# ó# Ą# ó# Ą#
ó# Ą#
3
Ł#144 12 1Ś# ó# Ą# ó# Ś#
Ł#a Ś# Ł#279.2Ą#
25, 64 , 144
Wartości w pierwszej kolumnie to:
25 5 1 M 106.8
Ą# ń#
144 12 1 M 279.2
Ą# ń#
ó#
ó#
64 8 1 M 177.2Ą#
�! 64 8 1 M 177.2Ą#
ó# Ą#
ó# Ą#
ó# Ą#
ó# Ą#
25 5 1 M 106.8Ś#
Ł#144 12 1 M 279.2Ś#
Ł#
Zamiana wiersza trzeciego z pierwszym
37
Met.Numer. wykład 6
Metoda Gaussa  Crouta w obliczaniu
wyznaczników
25 5 1
Obliczyć wyznacznik macierzy [A] Ą# ń#
ó#
[A]= 64 8 1Ą#
ó# Ą#
ó# Ą#
Ł#144 12 1Ś#
25 5 1
Ą# ń#
Po eliminacji Gaussa
ó#
[B]= 0 - 4.8 -1.56Ą#
ó# Ą#
ó# Ą#
0 0 0.7
Ł# Ś#
Użyteczne twierdzenie: Jeżeli macierz B powstaje z
macierzy A przez dodanie lub odjęcie od jednego
wiersza innego wiersza pomnożonego przez liczbę to
nie zmienia to wyznacznika
det(A)=det(B)=25 (-4,8) (0.7)=-84,00
38
Met.Numer. wykład 6
Metoda Gaussa  Crouta w obliczaniu
wyznaczników
Po zastosowaniu metody częściowego
144 12 1
Ą# ń#
wyboru elementu podstawowego
ó#
[C]= 0 2.917 0.8264Ą#
otrzymaliśmy macierz[C]
ó# Ą#
ó# Ą#
0 0 - 0.2
Ł# Ś#
Użyteczne twierdzenie: Jeżeli macierz B powstaje z
macierzy A przez przestawienie jednego wiersza z
drugim to zmienia się tylko znak wyznacznika
det(C)=(-)(-)det(B)=144 (2.917) (-0.2)=-84,00
tu wystąpiło dwukrotne
przestawienie wierszy
39
Met.Numer. wykład 6
Metoda eliminacji Gaussa
144 12 1 M 279.2
Ą# ń#
Podzielić równanie 1
64
ó#
= 0.4444
64 8 1 M 177.2Ą#
przez 144 i pomnożyć
ó# Ą#
144
przez 64
ó# Ą#
25 5 1 M 106.8Ś#
Ł#
[144 12 1 M 279.2]�0.4444=[63.99 5.333 0.4444 M 124.1]
[64 8
1 M 177.2]
Odjąć rezultat od
-[63.99 5.333 0.4444 M 124.1]
równania nr 2
[ 0 2.667 0.5556 M 53.10]
144 12 1 M 279.2
Ą# ń#
ó#
0 2.667 0.5556 M 53.10Ą#
ó# Ą#
ó# Ą#
25 5 1 M 106.8Ś#
Ł#
40
Met.Numer. wykład 6
Metoda eliminacji Gaussa
144 12 1 M 279.2
Ą# ń#
Podzielić równanie 1 25
ó#
= 0.1736
0 2.667 0.5556 M 53.10Ą#
przez 144 i pomnożyć
ó# Ą#
144
ó# Ą#
25 5 1 M 106.8Ś# przez 25
Ł#
[144 12 1 M 279.2]� 0.1736 = [25.00 2.083 0.1736 M 48.47]
[25 5
1 M 106.8]
Odjąć rezultat od
-[25 2.083 0.1736 M 48.47]
równania nr 3
[ 0 2.917 0.8264 M 58.33]
144 12 1 M 279.2
Ą# ń#
ó#
0 2.667 0.5556 M 53.10Ą#
ó# Ą#
ó# 0 2.917 0.8264 M 58.33Ą#
Ł# Ś#
41
Met.Numer. wykład 6
Metoda eliminacji Gaussa
Nie mo żna o becnie w y świetlić teg o o b r azu .
Wartości w drugiej kolumnie drugiego i trzeciego
wiersza to:
2.667, 2.917
Maksimum to 2.917 w trzecim wierszu
Zamiana wiersza trzeciego z drugim
144 12 1 M 279.2 144 12 1 M 279.2
Ą# ń# Ą# ń#
ó# ó#
0 2.667 0.5556 M 53.10Ą# �! 0 2.917 0.8264 M 58.33Ą#
ó# Ą# ó# Ą#
ó# Ą# ó# Ą#
0 2.917 0.8264 M 58.33Ś# Ł# 0 2.667 0.5556 M 53.10Ś#
Ł#
42
Met.Numer. wykład 6
Metoda eliminacji Gaussa
144 12 1 M 279.2
Ą# ń#
Podzielić równanie 2
2.667
ó#
0 2.917 0.8264 M 58.33Ą# przez 2.917 i pomnożyć
= 0.9143.
ó# Ą#
przez 2.667
2.917
ó# Ą#
0 2.667 0.5556 M 53.10Ś#
Ł#
[0 2.917 0.8264 M 58.33]� 0.9143 = [0 2.667 0.7556 M 53.33]
[0 2.667 0.5556 M 53.10]
Odjąć rezultat od
-[0 2.667 0.7556 M 53.33]
równania nr 3
[0 0 - 0.2 M - 0.23]
144 12 1 M 279.2
Ą# ń#
ó#
0 2.917 0.8264 M 58.33Ą#
ó# Ą#
ó# Ą#
0 0 - 0.2 M - 0.23Ś#
Ł#
43
Met.Numer. wykład 6
Metoda eliminacji Gaussa
144 12 1 a1 279.2
Ą# ń# Ą# ń# Ą# ń#
ó# ó#
0 2.917 0.8264Ą# ó#a2 Ą# = 58.33Ą#
ó# Ą# ó# Ą# ó# Ą#
ó# 0 0 - 0.2 Ą# ó#a3 Ą# ó#- 0.23Ą#
Ł# Ś# Ł# Ś# Ł# Ś#
Obliczanie a2
2.917a2 + 0.8264a3 = 58.33
58.33- 0.8264a3
a2 =
2.917
58.33- 0.8264�1.15
=
2.917
=19.67
44
Met.Numer. wykład 6
Metoda eliminacji Gaussa
144 12 1 a1 279.2
Ą# ń# Ą# ń# Ą# ń#
ó# ó#
0 2.917 0.8264Ą# ó#a2 Ą# = 58.33Ą#
ó# Ą# ó# Ą# ó# Ą#
ó# 0 0 - 0.2 Ą# ó#a3 Ą# ó#- 0.23Ą#
Ł# Ś# Ł# Ś# Ł# Ś#
Obliczanie a1
144a1 +12a2 + a3 = 279.2
279.2 -12a2 - a3
a1 =
144
279.2 -12�19.67 -1.15
=
144
= 0.2917
45
Met.Numer. wykład 6
Metoda eliminacji Gaussa
25 5 1 a1 106 .8
Ą# ń# Ą# ń# Ą# ń#
ó# ó#177 .2 Ą#
64 8 1Ą# ó#a2 Ą# =
ó# Ą# ó# Ą# ó# Ą#
ó# Ą# ó# Ą#
3
Ł#144 12 1Ś# ó# Ą# Ł#279 .2Ś#
Ł#a Ś#
Rozwiązanie to:
a1 0.2917
Ą# ń# Ą# ń#
ó#a Ą# ó# Ą#
= 19.67
2
ó# Ą# ó# Ą#
ó# Ą# ó# Ą#
1.15
3
Ł#a Ś# Ł# Ś#
46
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Układ n równań z n niewiadomymi:
a11x1 + a12x2 + a13x3 + ... + a1nxn = b1
a21x1 + a22x2 + a23x3 +...+ a2nxn = b2
.
.
.. .
..
..
an1x1 + an2x2 + an3x3 + ... + annxn = bn
47
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Przekształcenie równań do postaci:
b1 - a12x2 - a13x3KK- a1nxn
z równania 1
x1 =
a11
b2 - a21x1 - a23x3KK- a2nxn
x2 =
z równania 2
a22
z n-1
M M M
bn-1 - an-1,1x1 - an-1,2x2 KK- an-1,n-2xn-2 - an-1,nxn
xn-1 =
an-1,n-1
bn - an1x1 - an2x2 -KK- an,n-1xn-1
xn =
z równania n
ann
48
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Postać ogólna dla i - tego równania
n
bi - aijxj
"
j=1
j`"i
xi = ,i =1,2,K,n.
aii
Jest to metoda iteracyjna
49
Met.Numer. wykład 6
Metoda Gaussa  Seidla
x1
Ą# ń#
Zakładamy początkowe wartości od x1 do xn i
ó# Ą#
podstawiamy je do wcześniej przekształconych równań
x2
ó# Ą#
ó# Ą#
M
Obliczamy błąd względny uzyskanych nowych wartości: ó# Ą#
ó#xn-1Ą#
ó# Ą#
xn
Ł# Ś#
xinew - xiold
"a i = �100
xinew
Procedurę powtarzamy iteracyjnie aż do uzyskania
odpowiedniego wartości o zadawalającym błędzie.
50
Met.Numer. wykład 6
Metoda Gaussa - Seidla
Przykład:
Czas t Prędkość
(s) (m/s)
5 106.8
8 177.2
12 279.2
Prędkość rakiety została przybliżona wielomianem:
2
v(t) = a1t + a2t + a3 ,
5 d" t d" 12.
Znalez
ć współczynniki a1, a2, a3 metodą Gaussa-Seidla i prędkość
w chwili t = 6 s
51
Met.Numer. wykład 6
Metoda Gaussa  Seidla
2
Ą# ń#
t1 t1 1 a1 v1
Ą# ń# Ą# ń#
Postać równania:
ó# Ą#
Ą# ó#v Ą#
2
ó#t2 t2 1Ą# ó#a2 Ą# = ó# 2 Ą#
ó#
2
ó#t3 t3 1Ą# ó# 3 Ą# ó# 3 Ą#
Ł#a Ś# Ł#v Ś#
Ł# Ś#
25 5 1 a1 106.8
Ą# ń# Ą# ń# Ą# ń#
Po wstawieniu
ó# ó#177.2Ą#
64 8 1Ą# ó#a2 Ą# =
danych: ó# Ą# ó# Ą# ó# Ą#
ó# Ą#
3
Ł#144 12 1Ś# ó# Ą# ó# Ś#
Ł#a Ś# Ł#279.2Ą#
a 1
Ą# ń# Ą# ń#
1
Wartości przyjęte do
ó#a Ą# ó#2Ą#
=
2
pierwszej iteracji: ó# Ą# ó# Ą#
ó# Ą# ó#
3
Ł#a Ś# Ł#5Ą#
Ś#
52
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Przekształcenie równań:
106.8 - 5a - a
2 3
a =
1
25
25 5 1 a1 106.8
Ą# ń# Ą# ń# Ą# ń#
177.2 - 64a1 - a3
ó# ó#177.2Ą#
64 8 1Ą# ó#a2 Ą# =
a2 =
ó# Ą# ó# Ą# ó# Ą#
8
ó# Ą#
3
Ł#144 12 1Ś# ó# Ą# ó# Ś#
Ł#a Ś# Ł#279.2Ą#
279.2 -144a1 -12a2
a3 =
1
53
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Pierwsza iteracja:
a 1
106.8 - 5(2) - (5)
Ą# ń# Ą# ń#
1
a1 = = 3.6720
ó#a Ą# ó#2Ą#
25
=
2
ó# Ą# ó# Ą#
ó# Ą# ó#
3
Ł#a Ś# Ł#5Ą#
Ś#
177.2 - 64(3.6720)-(5)
a2 = = -7.8510
8
279.2 -144(3.6720)-12(- 7.8510)
a3 = = -155.36
1
54
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Znajdowanie błędu względnego pierwszej iteracji:
xinew - xiold
Wyniki pierwszej iteracji:
"a i = �100
xinew
a1 3.6720
Ą# ń# Ą# ń#
ó#a Ą# ó#
=
3.6720 -1.0000 2
ó# Ą# ó#- 7.8510Ą#
Ą#
"a 1 = �100 = 72.76%
ó# Ą# ó#-155.36Ś#
Ą#
3.6720
3
Ł#a Ś# Ł#
- 7.8510 - 2.0000
"a 2 = �100 = 125.47%
Maksymalny
- 7.8510
błąd względny
to 125.47%
-155.36 - 5.0000
"a 3 = �100 = 103.22%
-155.36
55
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Druga iteracja:
a 3.6720
Ą# ń# Ą# ń#
1
106.8 - 5(- 7.8510)-155.36
a1 =
ó#a Ą# ó# = 12.056
=
2
25
ó# Ą# ó#- 7.8510Ą#
Ą#
ó# Ą# ó#-155.36Ś#
Ą#
3
Ł#a Ś# Ł#
177.2 - 64(12.056)-155.36
a2 = = -54.882
Wyniki pierwszej
8
iteracji:
279.2 -144(12.056)-12(- 54.882)
a3 = = -798.34
1
56
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Znajdowanie błędu względnego drugiej iteracji:
12.056 - 3.6720
a1 12.056
Ą# ń# Ą# ń#
"a 1 = x100 = 69.543%
12.056
ó#a Ą# ó#
=
2
ó# Ą# ó#- 54.882Ą#
Ą#
ó# Ą# ó# Ą#
3
Ł#a Ś# Ł#- 798.54Ś#
- 54.882 -(- 7.8510)
"a 2 = x100 = 85.695%
- 54.882
Maksymalny
błąd względny
- 798.34 -(-155.36)
to 85.70%
"a 3 = x100 = 80.540%
- 798.34
57
Met.Numer. wykład 6
Metoda Gaussa  Seidla
" %
a
"a 3 %
Iteracja a1 " % a2 a3
2
a
1
1 3.6720 72.767 -7.8510 125.47 -155.36 103.22
2 12.056 69.543 -54.882 85.695 -798.34 80.540
3 47.182 74.447 -255.51 78.521 -3448.9 76.852
4 193.33 75.595 -1093.4 76.632 -14440 76.116
5 800.53 75.850 -4577.2 76.112 -60072 75.963
6 3322.6 75.906 -19049 75.972 -24958 75.931
0
a1 0.29048
Ą# ń# Ą# ń#
Wyniki kolejnych iteracji różnią się ó#a Ą# ó# Ą#
= 19.690
2
ó# Ą# ó# Ą#
zacznie od prawidłowych:
ó# Ą# ó# Ą#
1.0857
3
Ł#a Ś# Ł# Ś#
Kiedy zatem ta metoda jest zbieżna?
58
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Jeżeli macierz jest silnie diagonalnie dominująca to
metoda Gaussa-Seidla jest zbieżna
n
dla wszystkich i
aii e" aij
"
j=1, j`"i
n
przynajmniej dla jednego i
aii > aij
"
j=1, j`"i
59
Met.Numer. wykład 6
Metoda Gaussa  Seidla
Przykład macierzy diagonalnie dominującej
12 3 - 5
Ą# ń#
ó# Ą#
1 5 3
ó# Ą#
ó# Ą#
3 7 13
Ł# Ś#
a11 e" a12 + a13 = 8
a22 e" a21 + a23 = 4
a33 e" a31 + a32 = 10
60
Met.Numer. wykład 6
Rozkład LU
Rozkład LU to kolejny sposób na rozwiązanie układu n
równań z n niewiadomymi
Ax = b
Macierz A można przedstawić jako:
A = LU
gdzie:
L  dolna macierz trójkątna
U  górna macierz trójkątna
61
Met.Numer. wykład 6
Rozkład LU
Zapisując układ równań:
[A] [X ]= [C]
[L] [U ] [X ]= [C]
Zakładając że:
[A]= [L][U]
-1 -1
-1
Mnożąc przez:
[L] [L] [U] [X ]= [L] [C]
[L]
-1
[L] [C]= [Z]
-1
-1
ale: [L] [L]= [I] [I][U][X ]= [L] [C] [L] [Z]= [C]
[U] [X]= [Z]
ale:
[I ][U ]= [U ]
macierz
jednostkowa -1
zatem:
[U][X ]= [L] [C]
62
Met.Numer. wykład 6
Rozkład LU
-1
[U][X ]= [L] [C]
-1
[U] [X]= [Z]
[L] [C]= [Z]
Można zapisać
[L] [Z]= [C]
63
Met.Numer. wykład 6
Rozkład LU
Jeśli dany jest układ równań:
[A] [X ]= [C]
Należy dokonać dekompozycji macierzy A na macierze
L oraz U
Rozwiązać układ równań w poszukiwaniu macierzy Z:
[L] [Z]= [C]
Rozwiązać układ równań w poszukiwaniu macierzy X:
[U ] [X]= [Z]
64
Met.Numer. wykład 6
Rozkład LU
Dekompozycja macierzy A na L oraz U:
1 0 0 u11 u12 u13
Ą# ń#Ą# ń#
ó#l
[A]= [L][U]= 1 0Ą#ó# 0 u22 u23 Ą#
21
ó# Ą#ó# Ą#
ó# Ą#ó# Ą#
l 1Ś#Ł# 0 0 u33 Ś#
31 32
Ł#l
U  jest macierzą wyznaczaną podczas pierwszego
etapu eliminacji Gaussa
L  jest macierzą współczynników użytych podczas
pierwszego etapu eliminacji Gaussa
65
Met.Numer. wykład 6
Rozkład LU
Znajdowanie macierzy U:
25 5 1
Ą# ń#
ó#
64 8 1Ą#
ó# Ą#
ó# Ą#
Ł#144 12 1Ś#
25 5 1
Ą# ń#
wiersz1
Ą# ń#
ó#
wiersz2 - �(64) = 0 - 4.8 -1.56Ą#
ó# Ą#
ó# Ą#
25
Ł# Ś#
ó# Ą#
1
Ł#144 12 Ś#
25 5 1
Ą# ń#
wiersz1
Ą# ń#
ó#
wiersz3- �(144) = 0 - 4.8 -1.56Ą#
ó# Ą#
ó# Ą#
25
Ł# Ś#
ó# Ą#
0 -16.8 - 4.76Ś#
Ł#
66
Met.Numer. wykład 6
Rozkład LU
Znajdowanie macierzy U cd:
25 5 1
Ą# ń#
ó#
0 - 4.8 -1.56Ą#
ó# Ą#
ó# Ą#
0 -16.8 - 4.76Ś#
Ł#
25 5 1
Ą# ń#
wiersz2
Ą# ń#
ó#
wiersz3 - �(-16.8) = 0 - 4.8 -1.56Ą#
ó# Ą#
ó# Ą#
- 4.8
Ł# Ś#
ó# Ą#
0 0 0.7
Ł# Ś#
25 5 1
Ą# ń#
ó#
[U]= 0 - 4.8 -1.56Ą#
ó# Ą#
ó# Ą#
0 0 0.7
Ł# Ś#
67
Met.Numer. wykład 6
Rozkład LU
Znajdowanie macierzy L:
1 0 0
Ą# ń#
ó#l
a21 64
1 0Ą#
21
l = = = 2.56
ó# Ą#
21
a11 25
z pierwszego
ó# Ą#
l 1Ś#
Ł#l 31 32
kroku znajdowania
a31
144
l31 = = = 5.76
macierzy U
a11 25
z drugiego kroku
a32 -16.8
l = = = 3.5
znajdowania 32
a22 - 4.8
macierzy U
68
Met.Numer. wykład 6