Metody Numeryczne
Wykład 1
Operacje macierzowe
oraz
metody rozwiązywania układów równań
dr inż. Mirosław Dziewoński
e-mail: miroslaw.dziewonski@polsl.pl
Pok. 151
Wykład 1/1
Metody Numeryczne
Podręcznik:
Ewa Majchrzak, Bohdan Mochnacki
Metody numeryczne.
Podstawy teoretyczne,
aspekty praktyczne i algorytmy
Treść wykładów oraz dodatkowe informacje:
www.kwmimkm.polsl.pl
Wykład 1/2
Warunki zaliczenia
Zaliczenie z przedmiotu:
Ocena końcowa z przedmiotu metody numeryczne jest średnią
ważoną oceny z kartkówek i oceny z laboratorium (50% kartkówki,
50% laboratorium).
Wszystkie oceny (z laboratorium i z kartkówek) muszą być pozytywne
(min. 2,86)
Obecność na zajęciach laboratoryjnych jest obowiązkowa.
Wykład 1/3
Wykład 1/
Wykład 1/3
Czym są metody numeryczne?
Metody numeryczne są jedną z dziedzin matematyki stosowanej.
Metody numeryczne mają ogromne zastosowanie w praktyce
inżynierskiej, w szczególności w czasie tworzenia programów
komputerowych mających na celu przeprowadzanie obliczeń
matematycznych.
Znajomość metod numerycznych umożliwia nam nie tylko
odpowiedzieć na pytanie: Jaki jest wynik? , ale również
pozwala na udzielenie odpowiedzi: W jaki sposób wynik został
osiągnięty oraz czy uzyskany wynik jest wiarygodny?
Wykład 1/4
Tematyka wykładów
Tematami kolejnych wykładów w ramach przedmiotu
Metody numeryczne będą:
Operacje macierzowe
Metody rozwiązywania układów równań liniowych
Aproksymacja funkcji jednej zmiennej
Interpolacja funkcji
Całkowanie numeryczne
Metody rozwiązywania równań liniowych
Wykład 1/5
Operacje macierzowe
Wykład 1/6
Operacje macierzowe
Podstawowe operacje macierzowe:
Dodawanie i odejmowanie macierzy
Mnożenie macierzy
Obliczanie wyznacznika macierzy
Odwracanie macierzy
Wykład 1/7
Mnożenie macierzy
Rozważamy dwie macierze A [m, n] i B [n, k]:
a1,1 a1,2 a1,n b1,1 b1,2 b1,k
ł ł
ęa ęb
a2,2 a2,n ś b2,2 b2,k ś
2,1 2,1
ę ś, B = ę ś
A =
ę ś ę ś
ęa ęb
am,2 am,n ś bn,2 bn,k ś
m,1 n,1
Iloczyn macierzy C = A B obliczymy następująco:
n
ci, j =
a bs, i =1,2, m, j =1,2, k
i,s j
s=1
Wykład 1/8
Odwracanie macierzy
Bierzemy po uwagę macierz kwadratową A o wymiarach nn
a1,1 a1,2 a1,n
ł
ęa
a2,2 a2,n ś
2,1
ęś
A =
ęś
ęa
an,2 an,n ś
n,1
Wykład 1/9
Odwracanie macierzy
Tworzymy macierz B rozbudowując macierz A o macierz jednostkową E
a1,1 a1,2 a1,n
1 0 0
ł
ęa
a2,2 a2,n
0 1 0ś
2,1
ę
ś
B =
ę
ś
ęa
an,2 an,n
0 0 1ś
n,1
E
A
Wykład 1/10
Odwracanie macierzy
Aby uzyskać macierz odwrotną musimy tak przekształcać macierz B
by w miejsce podmacierzy A otrzymać macierz jednostkową. Po
takich przekształceniach w miejscu macierzy E otrzymamy macierz
odwrotną A-1.
1,1 1,2 1,n
1 0 0 ł
ę0 1
2,1 2,2 2,n ś
0
ś
ę
B =
ś
ę
ę0 0
n,1 n,2 n,n ś
1
E
A-1
Wykład 1/11
Odwracanie macierzy
Znalezć macierz odwrotną do macierzy:
7 2
ł
A =
ę3 0ś
Tworzymy macierz B:
7 2 1 0
ł
B =
ę3 0 0 1ś
Wykład 1/12
Odwracanie macierzy
Elementy pierwszego wiersza dzielimy przez 7, a następnie mnożymy
razy 3 i odejmujemy od wiersza drugiego:
7 2 1 0 1 2/ 7 1/ 7 0 1 2/ 7 1/ 7 0
ł ł ł
B =
ę3 0 0 1ś ę3 0
0 1ś ę0 -6/ 7 -3/ 7 1ś
W drugim kroku elementy wiersza drugiego dzielimy przez -6/7, a
następnie mnożymy razy 2/7 i odejmujemy od wiersza pierwszego:
2 1 2 1 1
1 ł 1 0 0 ł
0ł 1 0
ę ś ę ś ę ś
7 7 7 7 3
B =
ę ś ę ś ę ś
ę0 -6 -3 1ś ę0 1 1 -7 ś ę0 1 1 - 7 ś
ę ś ę ś ę
7 7 2 6 2 6ś
Wykład 1/13
Odwracanie macierzy
Macierz odwrotna do A jest następująca
1
0 ł
ęś
3
A-1 =
ęś
ę1 - 7ś
ę26ś
Szczegółowy algorytm znajdziemy w literaturze!
Wykład 1/14
Rozwiązywanie układów
równań liniowych
Wykład 1/15
Metody rozwiązywania układów równań
Metody rozwiązywania układów równań liniowych można podzielić na
dwie grupy:
Ł Metody dokładne
ą metoda dla macierzy jednoprzekątniowej
ą metoda dla macierzy trójkątnej
ą metoda Thomasa
ą metoda eliminacji Gaussa
Ł Metody iteracyjne
ą metoda iteracji prostej
ą metoda Gaussa Seidla
ą metoda nadrelaksacji
Wykład 1/16
Metody rozwiązywania układów równań
Rozpatruje się układ n - równań liniowych zawierających n niewiadomych
a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
.............................................
an1x1 + an2x2 + ... + annxn = bn
który można zapisać w postaci macierzowej
AX = B
Wykład 1/17
Metody rozwiązywania układów równań
a11 a12 ... a1n x1 b1
ł ł ł
ę ęx ś ęb ś
a21 a22 ... a2n ś
2 2
ęś ę ś ę ś
A = X = B =
ęś ę ś ę ś
...................
ę ęx ś ęb ś
an1 an2 ... ann ś
n n
Układ równań posiada jedno rozwiązanie wtedy i tylko wtedy gdy jest
oznaczony, tzn. że macierz główna układu równań A nie jest osobliwa
(wyznacznik z tej macierzy jest różny od zera).
X = A-1 B
Wykład 1/18
Układ równań z elementami na głównej przekątnej macierzy A
Układ równań, w którym tylko główna przekątna macierzy A posiada
elementy niezerowe:
a11x1 = b1
a22x2 = b2
... ...
annxn = bn
rozwiązuje się natychmiastowo :
bi
xi = , aii ą 0, i =1,2,...,n
aii
Wykład 1/19
Trójkątny układ równań
Jeżeli układ równań ma następującą postać:
a11x1 + a12x2 + ... + a1nxn = b1
a22x2 + ... + a2nxn = b2
... ...
annxn = bn
nazywamy go układem trójkątnym.
Wykład 1/20
Trójkątny układ równań
Rozwiązanie takiego układu jest stosunkowo proste. Z ostatniego równania
wyznaczamy xi, z przedostatniego xi-1 itd.:
bn
xn =
ann
n
bi - ai s xs
( )
s=i+1
xi = , i = n -1,n - 2, ... ,1
aii
przy założeniu, że
aii ą 0 , i =1, 2, ... , n
Wykład 1/21
Trójkątny układ równań
Przykład 1:
Rozwiązać następujący układ równań
x1 + 2x2 + x3 = 8
2x2 - x3 =1
2x3 = 6
Wykład 1/22
Trójkątny układ równań
Macierz główna układu i wektor wyrazów wolnych mają postać
1 2 1 8
ł ł
ę0 2 -1ś ę1ś
A = B =
ę ś ę ś
ę ę
0 0 2 ś 6ś
Z ostatniego równania wyznaczamy
b3 6
x3 = = = 3
a33 2
Wykład 1/23
Trójkątny układ równań
a następnie
b2 - a23 x3 1- (-1)3
x2 = = = 2
a22 2
b1 - a12 x2 - a13 x3 8 - 22 -13
x1 = = =1
a11 1
Wykład 1/24
Metoda eliminacji Gaussa
Układ równań liniowych
a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
.............................................
an1x1 + an2x2 + ... + annxn = bn
zapisuje się w postaci macierzy C, w której macierz główną A uzupełnia się
dodatkową kolumną zawierającą wektor wyrazów wolnych B.
Wykład 4/25
Metoda eliminacji Gaussa
czyli:
a11 a12 a1n b1,n+1 c11 c12 c1n c1,n+1
ł ł
ęa
a22 a2n b2,n+1ś ęc21 c22 c2n c2,n+1ś
21
ę ś ę ś
C ==
ę ś ę ś
ęa
an2 ann bn,n+1ś ęcn1 cn2 cnn cn,n+1ś
n1
n pierwszych kolumn stanowią elementy macierzy A
n+1 kolumnę stanowią elementy wektora B
Wykład 4/26
Metoda eliminacji Gaussa
Wariant podstawowy metody eliminacji Gaussa polega na przekształceniu
macierzy C, tak aby otrzymać równoważny układ równań, w którym
n pierwszych kolumn macierzy C tworzyło macierz trójkątną, a następnie
rozwiązać ten układ równań odpowiednią metodą (przedstawioną
wcześniej).
Wykład 4/27
Metoda eliminacji Gaussa
W pierwszym kroku algorytmu odejmujemy pierwsze równanie pomnożone
przez ci1/c11 od i tego równania (i = 2, 3, ... , n) i po wykonaniu obliczeń
otrzymujemy następujący układ równań:
c11x1 + c12x2 + c13x3 + ... + c1nxn = c1,n+1
(1) (1) (1) (1)
c22 x2 + c23 x3 + ... + c2n xn = c2,n+1
(1) (1) (1) (1)
c32 x2 + c33 x3 + ... + c3n xn = c3,n+1
...................................................
(1) (1) (1) (1)
cn2 x2 + cn3 x3 + ... + cnn xn = cn,n+1
Wykład 4/28
Metoda eliminacji Gaussa
który odpowiada sprowadzeniu macierzy C do C1
c11 c12 c13 c1n c1,n+1
ł
ę (1) (1) (1) (1)
0 c22 c23 c2n c2,n+1ś
ęś
(1) (1) (1) (1)
0 c32 c33 c3n c3,n+1
ęś
C1 =
ęś
ęś
(1) (1) (1) (1)
ęś
0 cn2 cn3 cnn cn,n+1
za pomocą wzorów określających nowe współczynniki
ci 1
ci(1) = ci j - c1 j dla i = 2, 3, ... , n oraz j = 2, 3, ... , n +1
j
c11
Wykład 4/29
Metoda eliminacji Gaussa
W drugim kroku odejmujemy drugie równanie pomnożone przez ci2(1)/c22(1)
od i tego równania (i = 3, 4, ... , n) i po wykonaniu obliczeń otrzymujemy
kolejny układ równań:
c11x1 + c12x2 + c13x3 + ... + c1nxn = c1,n+1
(1) (1) (1) (1)
c22 x2 + c23 x3 + ... + c2n xn = c2,n+1
(2 ( (2
c33)x3 + ... + c32)xn = c3,n)+1
n
........................................
( (2 ( )
cn2)x3 + ... + cnn)xn = cn2n+1
3 ,
Wykład 4/30
Metoda eliminacji Gaussa
który odpowiada sprowadzeniu macierzy C do C1
c11 c12 c13 c1n c1,n+1
ł
ę (1) (1) (1) (1)
0 c22 c23 c2n c2,n+1ś
ęś
(2 ( (2
00 c33) c32) c3,n)+1
ęś
C2 =
n
ęś
ęś
( (2 ( )
ęś
00 cn2) cnn) cn2n+1
3 ,
za pomocą wzorów określających nowe współczynniki
ci(1)
2
(
ci(2) = ci(1) - c21j) dla i = 3, 4, ... , n oraz j = 3, 4, ... , n +1
j j
1
(
c22)
Wykład 4/31
Metoda eliminacji Gaussa
Kontynuując takie postępowanie, po wykonaniu n kroków dochodzimy do
trójkątnego układu równań
c11x1 + c12x2 + c13x3 + ... + c1nxn = c1,n+1
(1) (1) (1) (1)
c22 x2 + c23 x3 + ... + c2n xn = c2,n+1
(2 ( (2
c33)x3 + ... + c32)xn = c3,n)+1
n
.......................................
( ( -1)
cnn-1)xn = cnnn+1
n ,
Wykład 4/32
Metoda eliminacji Gaussa
któremu odpowiada przekształcona macierz Cn-1
c11 c12 c13 c1n c1,n+1
ł
ę (1) (1) (1) (1)
0 c22 c23 c2n c2,n+1 ś
ęś
(2 ( (2
00 c33) c32) c3,n)+1
ęś
Cn-1 =
n
ęś
ęś
(n ( -1)
ęś
0 0 0 cnn-1) cnnn+1
,
Tak zbudowany układ równań rozwiązuje się przedstawioną wcześniej
metodą dla układów trójkątnych zakładając, że
n pierwszych kolumn macierzy Cn -1 stanowi macierz A, a kolumna n +1
jest wektorem B.
Wykład 4/33
Metoda eliminacji Gaussa
Przejście od układu równań liniowych do układu trójkątnego realizowane
jest zatem za pomocą następującego wzoru iteracyjnego:
s =1 , 2 , ... , n -1
i = s +1 , s + 2 , ... , n
c(s) = ci(s-1) - ci(s-1) cssj-1) , j = s +1,s + 2, ... , n +1
s
(
i j j
(
csss-1)
Wykład 4/34
Metoda eliminacji Gaussa
Przykład:
Rozwiązać następujący układ równań metodą eliminacji Gaussa
2x1 - x2 + 3x3 = 1
3x1 - 2x2 + x3 = 2
+ 3x2 - 2x3 = 3
-x1
Macierz główna układu i wektor wyrazów wolnych mają postać:
2 -1 3 1
ł ł
ęś ę2ś
A = 3 -2 1 B =
ęś ę ś
ęś
ę
-1 3 -2 3ś
Wykład 4/35
Metoda eliminacji Gaussa
Macierz główna układu i wektor wyrazów wolnych mają postać:
2 -1 3 1
ł ł
ęś ę2ś
A = 3 -2 1 B =
ęś ę ś
ęś
ę
-1 3 -2 3ś
Tworzymy macierz C
2 -1 3 1
ł
ę
C = 3 -2 1 2ś
ęś
ęś
-1 3 -2 3
Wykład 4/36
Metoda eliminacji Gaussa
Obliczamy elementy macierzy C1:
ci1
ci(1) = ci j - c1 j dla i = 2,3 oraz j = 2,3,4
j
c11
c21 3
(1)
c22 = c22 - c12 = -2 - -1 = -0.5
( )
c11 2
(1) (1) (1) (1) (1)
c23 = -3.5 c24 = 0.5 c32 = 2.5 c33 = -0.5 c34 = 3.5
i otrzymujemy:
2 -1 3 1
ł
ę0 -0.5 -3.5 0.5ś
C1 =
ęś
ęś
0 2.5 -0.5 3.5
Wykład 4/37
Metoda eliminacji Gaussa
Obliczamy elementy macierzy C2
ci(1)
2
(
ci(2) = ci(1) - c21j) dla i = 3 oraz j = 3, 4
j j
1
(
c22)
(2) (
c33 = -18, c32) = 6
4
i otrzymujemy:
2 -1 3 1
ł
ę0 -0.5 -3.5 0.5ś
C2 =
ęś
0 -18 6
ęś
0
Wykład 4/38
Metoda eliminacji Gaussa
Macierz C2 przedstawia teraz następujący trójkątny układ równań:
2x1 - x2 + 3x3 =1
-0.5x - 3.5x3 = 0.5
2
-18x3 = 6
który można zapisać następująco:
2 -1 3 1
ł ł
ę0 -0.5 -3.5ś ę0.5ś
A = B =
ęś ę ś
0 -18 6
ęś ę ś
0
Wykład 4/39
Metoda eliminacji Gaussa
b3 61
x3 = = = -
a33 -18 3
1 7 1
ć ć
b2 - a23 x3 2 - - 2 - 3
1
Ł ł Ł ł
x2 = = =1
1
a22 3
-
2
11
-
b1 - a12 x2 - a13 x3 1- (-1)13 - 3ć 3 2
Łł
x1 = = =1
a11 23
Wykład 4/40
Metoda Thomasa
Algorytm Thomasa (zwany metodą progonki) stosowany jest między innymi
dla trójprzekątniowego układu równań:
b1 c1 0 0 0 0 0 x1 d1
ł ł ł
ęa b2 c2 0 0 ś ę ś ę ś
0 0 x2 d2
2
ę ś ę ś ę ś
ę 0 a3 b3 c3 0 0 0 ś ę x3 ś ę d3 ś
=
ę ś ę ś ę ś
. . . . . . . . .
ę ś ę ś ę ś
ę ś ę ś ę ś
0 0 0 0 an-1 bn-1 cn-1 xn-1 dn-1
ę
0 0 0 0 0 an bn ś ę xn ś ę dn ś
ę ś ę ś ę ś
który można zapisać również w następujący sposób
ai xi-1 + bi xi + ci xi+1 = di , a1 = 0, cn = 0, i =1, 2, ... ,n Ś
Wykład 1/41
Metoda Thomasa
Rozwiązanie tego układu równań poszukuje się w postaci
xi = bi xi+1 + gi ć
lub inaczej zapisując
xi-1 = bi-1 xi + gi-1
gdzie bi i gi są nieznanymi współczynnikami.
Wykład 1/42
Metoda Thomasa
Po podstawieniu ć do Ś i uporządkowaniu otrzymujemy:
ci
bi =-
ai bi-1 + bi
di - ai gi-1
gi =
ai bi-1 + bi
Wykład 1/43
Metoda Thomasa
Z danych przedstawionych w równaniu Ś można wyznaczyć wartości
początkowe (dla i = 1)
c1 d1
b1 = - , g1 =
b1 b1
oraz wartość ostatniej niewiadomej (dla i = n)
dn - an g
n-1
xn == g
n
an bn-1 + bn
Po wyznaczeniu wartości xn kolejne niewiadome obliczamy z równania ć
dla i = n-1, n-2, ... , 1
Wykład 1/44
Metoda Thomasa
Przykład 3:
Rozwiązać następujący układ równań metodą Thomasa
Rozwiązać następujący układ równań metodą Thomasa
x1 + 3x2 =1
x1 + 2x2 + x3 = 2
x + 2x3 + x4 = 3
2
x + 2x4 + x5 = 4
3
3x4 + x5 = 5
Wykład 14/45
Metoda Thomasa
Macierz główną układu i wektor wyrazów wolnych można zapisać
następująco:
1 3 0 0 0 1
ł ł
ę1 2 1 0 0ś ę2ś
ę ś ę ś
A = 0 1 2 1 0 D = 3
ę ś ę ś
ę0 0 1 2 1ś ę4ś
ę ś ę ś
ę ś ę
0 0 0 3 1 5ś
Obliczamy wartości początkowe współczynników
c1 d1
b1 = - = -3 , g1 = =1
b1 b1
Wykład 1/46
Metoda Thomasa
Następnie wyznaczamy pozostałe wartości współczynników dla i = 2, ..., n
ci di - ai gi-1
bi = - , gi =
ai bi-1 + bi ai bi-1 + bi
-31
ł ł
ę ś ę ś
1 -1
ę ś ę ś
b = g =
ę-0.333ś ę1.333ś
ę ś ę ś
-0.6 1.6
ę ś ę ś
ę ś ę
0
-0.25ś
Wykład 1/47
Metoda Thomasa
Obliczamy wartość ostatniej niewiadomej xn
xn = gn x5 = -0.25
oraz pozostałe wartości niewiadomych i = n-1, n-2, ... , 1:
xi = bi xi+1 + gi
1.75
ł
ęś
ę-0.25ś
x = 0.75
ęś
ęś
1.75
ęś
ę
-0.25ś
Wykład 1/48
Wyszukiwarka
Podobne podstrony:
MN MiBM zaoczne wyklad 2 aproksymacja, interpolacja5 Zadania do wykladu Uklady rownan liniowychWyklad 2 3 MACIERZE WYZNACZNIK UKLADY ROWNANwykład 11 układy równań liniowychMN w1 Układy równań nieliniowychukłady równań liniowych, wykładBudownictwo Ogolne II zaoczne wyklad 13 ppozuklady rownan (1)uklady rownan liniowychUkłady równań zadaniaMacierze i układy równań przykładyAudyt 12 zaoczne wyklad 5Budownictwo Ogolne I zaoczne wyklad 9 i 10 stropy buklady rownanMiBM semestr 3 wykład 5wykład 13 Równania RóżniczkoweC 02 Uklady równanwięcej podobnych podstron