Metody numeryczne
skrót wykładu
dr inż. Anna Barcz
Zakład Matematyki Stosowanej
kontakt: pokój 28
[e-mail]
konsultacje: środa 12.15 - 14.00
1
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Zagadnienia
Macierze specjalne.
Równoważność układów i operacje elementarne.
Normy i ich zastosowanie.
Klasyfikacja metod rozwiązywania układów równań liniowych.
Metoda eliminacji Gaussa.
Metoda eliminacji Jordana.
Rozkład LU.
Rozkład QR.
Metoda iteracji prostej.
Metoda Gaussa-Seidla.
Obliczanie wyznacznika i odwracanie macierzy.
Poprawianie rozwiązań.
2
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Rozwiązywanie układów algebraicznych równań liniowych
a11 a12 �ą a1n x1 b1
a11 x1�ąa12 x2�ą�ą�ąa1n xn=b1
a21 a22 �ą a2n �" x2 = b2
a21 x1�ąa22 x2�ą�ą�ąa2n xn=b2
�ą �ą �ą �ą �ą �ą
�ą�ą
śą źąśą źą śą źą
{
am1 am2 �ą amn xn bm
am1 x1�ąam2 x2�ą�ą�ąamn xn=bm
�ą �ą �ą
A x b
A x=b
A  macierz o m wierszach i n kolumnach,
b  wektor m danych liczb (wektor wyrazów wolnych),
x  wektor n niewiadomych.
oznaczony  dokładnie jedno rozwiązanie,
nieoznaczony  wiele rozwiązań,
sprzeczny  brak rozwiązań.
3
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Rozwiązywanie układów algebraicznych równań liniowych
A x=b B x=d
Dwa układy i są równoważne, jeśli mają
identyczne rozwiązania.
Operacje elementarne:
przestawianie dwóch równań w układzie,
pomnożenie obu stron równania przez liczbę różną od
zera,
dodanie stronami do równania wielokrotności innego
równania
Twierdzenie
Jeśli układ równań wynika z innego układu przez ciąg
skończony operacji elementarnych, to te dwa układy są
równoważne.
4
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Rozwiązywanie układów algebraicznych równań liniowych
Przyczyny błędów:
błąd spowodowany niedokładnymi wartościami
współczynników układu równań (błąd wejściowy),
błąd powstający na skutek popełniania błędów podczas
numerycznego wykonywania działań arytmetycznych (błąd
zaokrągleń),
błąd wyznaczania rozwiązania spowodowany sposobem
działania metody (błąd metody) normy wektorów i
macierzy.
5
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Normy wektorów i macierzy  pojęcia podstawowe
W przestrzeni wektorowej V norma jest funkcją ||.|| określoną na
V, o wartościach rzeczywistych nieujemnych, która ma trzy
własności:
%"x%"ą0 dla x`"0, x"V
%"�ą x%"=#"�ą#"%"x%" dla �ą"! , x"V
%"x�ą y%"ąą%"x%"�ą%"y%" dla x , y"V
%"x%" - długość albo wielkość wektora x
6
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Normy wektorów i macierzy  pojęcia podstawowe
Normy w przestrzeni Rn, której elementami są wektory x=[x1, x2, ..., xn]T:
%"x%"1=#"x1#"�ą#"x2#"�ą�ą�ą#"xn#"
1
2
%"x%"2=śą x1�ąx2�ą�ą�ąx2źą2 -> norma euklidesowa
2 n
%"x%""=max {#"x1#"�ą#"x2#"�ą�ą�ą#"xn#"}
dla dowolnego wektora obowiązują nierówności:
%"x%""ąą%"x%"2ąą%"x%"1ąą n%"x%"2ąąn%"x%""
ćą
7
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Normy wektorów i macierzy  pojęcia podstawowe
w szczególności dla macierzy A obowiązują normy:
m
%"A%"1= max #"aij#"
"
maksymalna suma modułów w kolumnie
j=1,2 ,�ą , n
i=1
1
%"A%"2=śąmax eig śą AT Aźąźą2
największa wartość własna, norma spektralna
n
%"A%""= max #"aij#"
"
maksymalna suma modułów w wierszu
i=1,2 ,�ą, m
j=1
n m
norma Frobeniusa
%"A%"F= #"aij#"2
""
ćą
j=1 i=1
8
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Normy wektorów i macierzy  pojęcia podstawowe
Wykorzystanie norm:
analiza błędów rozwiązania,
określenie współczynnika uwarunkowania
cond śą Aźą=%"A%"�"%"A-1%"
9
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metody rozwiązywania układów równań liniowych
Metody dokładne:
metoda podstawiania,
metoda przeciwnych współczynników,
wzory Cramera,
metody eliminacji Gaussa,
metody wykorzystujące rozkład macierzy A.
Metody przybliżone:
metoda iteracji prostej (metoda Jacobiego),
metoda Gaussa-Seidela,
metoda nadrelaksacji,
metoda Czebyszewa,
metoda Richardsona.
10
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Rozwiązywanie układów algebraicznych równań liniowych
Metody dokładne
rozwiązanie układu równań Ax=b polega na takim
przekształcaniu danych A i b, że przy założeniu dokładnie
wykonywanych działań arytmetycznych po skończonej
liczbie działań otrzymujemy rozwiązanie,
mała liczba obliczeń,
dla zadań z
le uwarunkowanych numerycznie wyznaczone
rozwiązanie może być obarczone dużym błędem,
nie dają błędu metody, ale mogą być niestabilne ze
względu na błędy zaokrągleń,
obciążają pamięć.
11
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metody dokładne  metoda eliminacji Gaussa
Etap pierwszy  eliminacja zmiennych
a11 x1�ąa12 x2�ą�ą�ąa1n xn=b1
a22 x2�ą�ą�ąa2n xn=b2
�ą�ą
{
ann xn=bn
Etap drugi  postępowanie odwrotne
bn
xn=
ann
bi-ai n xn-�ą-aii�ą1 xi�ą1
xi= , i=n-1,n-2,�ą,1
aii
12
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metody dokładne  metoda eliminacji Gaussa
modyfikacja: częściowy wybór elementu podstawowego
Element podstawowy: element za pomocą którego eliminujemy
zmienną z dalszych równań.
element k-tej kolumny w k-tej macierzy, który ma największy
moduł
13
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metody dokładne  metoda eliminacji Gaussa
Metoda eliminacji Gaussa z częściowym wyborem elementu
podstawowego  metoda Gaussa-Crouta
metoda niezawodna  przy założeniu dokładnych działań
arytmetycznych nie nastąpi zatrzymanie procesu obliczeń z
powodu dzielenia przez zero w przypadku gdy istnieje
jednoznaczne rozwiązanie.
14
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metody dokładne  metoda eliminacji Gaussa
Koszt  eliminacja Gaussa
1 1 1 1 5
M = n3�ąn2- n D= n3�ą n2- n
3 3 3 2 6
Koszt  wzory Cramera  wyznaczenie jednego wyznacznika
M =śąn�ą1źą!
15
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metody dokładne  metoda eliminacji Gaussa
Twierdzenie
Jeżeli macierz A jest nieosobliwa i diagonalnie dominująca
kolumnowo, to przy eliminacji Gaussa z wyborem elementu
podstawowego nie ma potrzeby przestawiania wierszy.
Macierz A nazywamy diagonalnie dominującą, jeżeli moduły elementów na
diagonali są nie mniejsze od sumy modułów pozostałych elementów stojących w
tym samym wierszu.
n
#"aii#"�ą #"aik#", i=1,2 ,�ą,n
"
k =1
k `"i
Macierz A nazywamy diagonalnie dominującą kolumnowo, jeżeli AT jest
diagonalnie dominująca.
16
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metody dokładne  metoda eliminacji Jordana
a11 x1�ąa12 x2�ą�ą�ąa1n xn=b1
Pierwsze równanie dzielimy obustronnie przez
a11, od i-tego (i=2,3,...n) wiersza odejmujemy
a21 x1�ąa22 x2�ą�ą�ąa2n xn=b2
wiersz pierwszy pomnożony przez ai1
�ą�ą
{
an1 x1�ąan2 x2�ą�ą�ąann xn=bn
x1�ąa12 x2�ą�ą�ąa1n xn=b1 Drugie równanie dzielimy obustronnie przez
a22, od i-tego (i=1,3,4,...,n) wiersza odejmujemy
a22 x2�ą�ą�ąa2n xn=b2
wiersz drugi pomnożony przez ai2
�ą�ą
{
an2 x2�ą�ą�ąann xn=bn
x1�ąa13 x3�ą�ą�ąa1n xn=b1
x2�ąa23 x3�ą�ą�ąa2n xn=b2
�ą�ą
{
an3 x3�ą�ą�ąann xn=bn
Po (n-1) eliminacjach otrzymujemy
x1 =b1
rozwiązanie.
x2 =b2
�ą�ą 1 1 1
{
M = n3�ą1 n2 D= n3-
xn=bn
2 2 2 2
17
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Rozkład LU
A=L�"U
zastosowanie eliminacji Gaussa,
metoda Doolittle'a / metoda Crouta / rozkład Cholesky'ego
(Banachiewicza)
l11 0 �ą 0
u11 u12 �ą u1n
l21 l22 �ą 0 0 u22 �ą u2n
L=
U =
�ą �ą �ą �ą
�ą �ą �ą �ą
śą źą
śą źą
ln1 ln2 �ą lnn
0 0 �ą unn
Rozkład LU jest jednoznaczny jeśli zostaną ustalone elementy na
diagonali w macierzy L lub macierzy U.
18
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Rozkład LU
Twierdzenie
Jeśli wszystkie minory główne macierzy kwadratowej A są
nieosobliwe, to ma ona rozkład LU.
Twierdzenie  rozkład Cholesky'ego
Jeśli macierz A jest rzeczywista, symetryczna i dodatnio
określona, to ma ona jedyny rozkład na czynniki A=LLT, gdzie L
jest macierzą trójkątną dolną o elementach dodatnich na głównej
przekątnej.
19
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Rozkład QR
A=Q�"R
r11 r12 �ą r1n
Q  macierz ortogonalna
0 r22 �ą r2n
QQT=QTQ=E
R=
�ą �ą �ą �ą
Q -1 = QT
śą źą
0 0 �ą rnn
QT Qk=0, " j , k śą1,nźą , j`"k
j
Rozkład QR otrzymujemy przez zastosowanie przekształceń
ortogonalnych:
odpowiednio dobranych obrotów Givensa,
przekształceń Householdera
20
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżone metody rozwiązywania układów równań liniowych
Metody przybliżone
ciąg wektorów zbieżny do rozwiązania,
obliczenia przerywamy gdy przybliżone rozwiązanie
osiągnęło wymaganą dokładność albo po ustalonej liczbie
iteracji,
dla dużych układów (tysiące równań) szybsze niż metody
dokładne,
efektywne dla układów rzadkich,
stabilne, błędy zaokrągleń są wygaszane w dalszych
iteracjach.
21
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Metoda iteracji prostej
śąk�ą1źą śąk źą
X =W�"X �ąZ
Warunek zbieżności metody:
%"W%""ą1
n
%"W%""=max #"wij#" "i śą1, nźą
"
j=1
n
%"W%"1=max #"wij#" " śą1, nźą
"
j
i=1
22
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Zbieżność metod przybliżonych
Twierdzenie
Jeśli macierz A jest dominująca przekątniowo, to dla dowolnego
wektora początkowego metoda iteracji prostej oraz metoda
Gaussa-Seidela tworzy ciąg zbieżny do rozwiązania układu Ax=b.
Twierdzenie
Jeśli macierz A nie jest dominująca przekątniowo, to metody
iteracji prostej i Gaussa-Seidela nie muszą tworzyć ciągu
rozbieżnego do rozwiązania układu Ax=b.
23
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Obliczanie wyznacznika i odwracanie macierzy
reguły rozwijania względem kolumny lub wiersza,
reguła Sarrusa
Koszt obliczenia wyznacznika n-tego stopnia na podstawie
rozwijania względem wierszy  n! mnożeń.
przekształcenie macierzy do macierzy trójkątnej
a11 0 �ą 0
a21 a22 �ą 0
A=
det śą Aźą=a11�"a22�"�ą�"ann
�ą �ą �ą �ą
śą źą
an1 an2 �ą ann
24
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Obliczanie wyznacznika i odwracanie macierzy
metoda Dolittle'a
u11 u12 �ą u1n
1 0 �ą 0
l21 1 �ą 0
0 u22 �ą u2n
L= U =
�ą �ą �ą �ą
�ą �ą �ą �ą
śą źą
śą źą
ln1 ln2 �ą 1
0 0 �ą unn
A=LU �! det śą Aźą=det śą LU źą=det śą Lźą det śąU źą=det śąU źą
metoda Crouta
l11 0 �ą 0
1 u12 �ą u1n
l21 l22 �ą 0
0 1 �ą u2n
L=
U =
�ą �ą �ą �ą
�ą �ą �ą �ą
śą źą śą źą
ln1 ln2 �ą lnn
0 0 �ą 1
A=LU �! det śą Aźą=det śą LU źą=det śą Lźą det śąU źą=det śą Lźą
25
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Macierze specjalne
macierze trójdiagonalne,
macierze wstęgowe,
macierze rzadkie,
macierze blokowe.
b1 c1 0 �ą p1
b1 c1 0 �ą 0
a2 b2 c2 �ą 0
a2 b2 c2 �ą 0
A=
A= 0 a3 b3 �ą 0
0 a3 b3 �ą 0
0 �ą �ą �ą cn-1
0 �ą �ą �ą cn-1
śą źą
śą źą
q1 0 �ą an bn
0 0 �ą an bn
26
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08