MN MiBM zaoczne wyklad 1 uklady rownan


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, interpolacja
5 Zadania do wykladu Uklady rownan liniowych
Wyklad 2 3 MACIERZE WYZNACZNIK UKLADY ROWNAN
wykład 11 układy równań liniowych
MN w1 Układy równań nieliniowych
układy równań liniowych, wykład
Budownictwo Ogolne II zaoczne wyklad 13 ppoz
uklady rownan (1)
uklady rownan liniowych
Układy równań zadania
Macierze i układy równań przykłady
Audyt 12 zaoczne wyklad 5
Budownictwo Ogolne I zaoczne wyklad 9 i 10 stropy b
uklady rownan
MiBM semestr 3 wykład 5
wykład 13 Równania Różniczkowe
C 02 Uklady równan

więcej podobnych podstron