Wykład pierwszy
Metody rozwiązywania
układów równań liniowych
Sem. 2 EiT, 2014/2015
2
Poszukujemy rozwiązania układu równań liniowych Ax = b det A `" 0
x*
Rozwiązaniem jest wektor
*
ł
x1
ęx* ś
2
ę ś
x* = A x* = b
ę ś
ę ś
*
ę ś
Metody dokładne:
xn
Cramera, Gaussa-Jordana, eliminacji Gaussa, dekompozycji LU
Otrzymujemy rozwiązanie po określonej liczbie działań arytmetycznych,
która zależy od liczby równań w układzie równań - n
Metody iteracyjne (przybliżone):
Jacobiego, Gaussa-Seidla
Nie potrafimy określić ile kolejnych iteracji k należy wykonać, żeby oszacować
wektor
zbliżony do wektora x*
x(k +1) = f (x(k )) k = 0,1,2,....
3
Metody iteracyjne (przybliżone)
54 5e + 5O = 0
Algorytm
- operacje do wykonania 5e(5X+1) = 5:5e + 5P 5X = 0, 1, 2, 3, &
5X
- wartość wektora początkowego
- warunki zakończenia obliczeń, np.
5S(5e(5X+1) < 5 5Q5Y5N 5S 5e = 0
STOP dla k = M
Problem zbieżność algorytmu
4
Algorytm
Algorytm to przepis postępowania, zbiór pewnych reguł,
- wszystkie czynności,
- kolejność ich wykonywania.
Realizacja algorytmu wykonanie wszystkich czynności
z zachowaniem ich kolejności.
5
Algorytm
w matematyce oraz informatyce to:
skończony, uporządkowany zbiór jasno zdefiniowanych czynności,
koniecznych do wykonania pewnego zadania.
Słowo "algorytm" pochodzi od nazwiska Muhammed ibn Musa Alchwarizmi
(JE21'H.D' I3HE F( /E-E 'DDG /(9 H(#)
matematyka perskiego z IX wieku i początkowo oznaczało w Europie sposób
obliczeń oparty na dziesiętnym systemie liczbowym.
Zadanie:
Algorytm ma przeprowadzić system z pewnego stanu początkowego
do pożądanego stanu końcowego.
Realizacja:
Algorytm może zostać zaimplementowany w postaci programu
komputerowego lub innego urządzenia.
Przykład stosowanego w życiu codziennym algorytmu
przepis kulinarny
6
Zapis algorytmu karta następstw, sieć działań
Symbole:
kierunek działania
początek, koniec
operator, operacja do wykonania
operator wejścia, wyjścia, np. wprowadzanie danych
do pamięci, wyprowadzanie danych z pamięci
element decyzyjny
połączenia poszczególnych
symboli
łącznik
7
CZYTAJ a, b, c
START
DRUKUJ x, y
STOP
TAK
A > B
k= k + 1
NIE
x (k+1) = f (x (k))
8
Sieć działań
Ax + b = 0
Karta następstw START
Dane wejściowe: x0, a, b,
k = 0
M - liczba
Obliczenia: xk+1 = f (xk)
TAK
Drukuj xk+1
NIE
k = k + 1
NIE
STOP
k = M
TAK
9
Metoda dekompozycji LU
metoda dokładna rozwiązywania
układów równań liniowych
10
Metoda dekompozycji LU
A x = b det A `" 0
A x = b [L U] x = b A = L U
L macierz trójkątna dolna, otrzymana z macierzy A,
U macierz trójkątna górna, otrzymana z macierzy A
L y = b
(1)
wyznaczamy y
wyznaczamy x
(2)
U x = y
Najpierw musimy obliczyć macierz L i macierz U
11
Macierz U
(1 (1
1 a12) a13) L a1(1) ł
n
ę ś
(2 (
n
ę0 1 a23) L a22)ś
(3)
U =
(
ę0 0 1 L a33)ś
n
ęM M ś
M
ę0 0 0 O M ś
L 1
Macierz L
(1
a11) 0 0 L 0 ł
ę ś
(1) (2
21
ęa a22) 0 L 0 ś
(4)
(1 (2 (3
L =
ęa31) a32) a33) L 0 ś
ę ś
M M M O M
ę ś
(1) ( ( (n
ęan1 an2) an3) L ann)ś
2 3
12
Algorytm Crouta
Przykład dla n = 4
l11 0 0 0 1 u12 u13 u14 a11 a12 a13 a14
ł ł ł
ęl ś ę0 1 u23 u24 ś ęa
l22 0 0 a22 a23 a24 ś
21 21
ę ś ę ś ę ś
=
(5)
ę ś ę ś ę ś
l31 l32 l33 0 0 0 1 u34 a31 a32 a33 a34
ę ś ś ę ś
l42 l43 l44 ę0 0 0 1 a42 a43 a44
41 41
l a
Pomocnicza macierz Q
l11 u12 u13 u14
ł
ęl
l22 u23 u24 ś
21
(6)
ę ś
Q =
ę ś
l31 l32 l33 u34
ęl
l42 l43 l44 ś
41
13
Elementy macierzy Q, dla n = 4, są obliczane w kolejności zaznaczonej
w poniższej tablicy
1 5 6 7
ł
ę2 8 11 12ś
l11 u12 u13 u14
ł
ę ś
ęl l22 u23 u24 ś
21
ę ś
Q =
ę ś
3 9 13 15
ę ś
l31 l32 l33 u34
ę ś
ę ś
l42 l43 l44
4 10 14 16 l41
Numer oznacza kolejność obliczania elementów.
Najpierw obliczamy elementy macierzy L (pierwsza kolumna),
potem elementy macierzy U (pierwszy wiersz, bez pierwszego elementu
macierzy U, który jest równy 1),
potem elementy macierzy L (druga kolumna, bez pierwszego elementu,
który jest równy 0),
potem elementy macierzy U (drugi wiersz, ale bez pierwszego i drugiego
elementu macierzy U, które są odpowiednio równe 0 i 1),
14
potem elementy macierzy L, itd.
Biorąc pod uwagę zależność (5), wykonujemy obliczenia
dla kolejnego elementu
aij
w postaci iloczynu i-tego wiersza macierzy L i j-tej kolumny macierzy U
l11 0 0 0 1 u12 u13 u14 a11 a12 a13 a14
ł ł ł
ęl ś ę0 1 u23 u24 ś ęa
l22 0 0 a22 a23 a24 ś
21 21
ę ś ę ś ę ś
=
ę ś ę ś ę ś
l31 l32 l33 0 0 0 1 u34 a31 a32 a33 a34
ę ś ś ę ś
l42 l43 l44 ę0 0 0 1 a42 a43 a44
l41 a41
l11 u12 u13 u14
ł
ęl l22 u23 u24 ś
21
ę ś
Q =
ę ś
l31 l32 l33 u34
ę ś
l42 l43 l44
l41
15
Biorąc pod uwagę zależność (5), wykonujemy obliczenia
dla kolejnego elementu
aij
w postaci iloczynu i-tego wiersza macierzy L i j-tej kolumny macierzy U
a11 = l11 1 l11 = a11,
a21 = l21 1 l21 = a21,
a31 = l31 1 l31 = a31,
a41 = l41 1 l41 = a41,
l11 u12 u13 u14
ł
ęl l22 u23 u24 ś
21
ę ś
Q =
ę ś
l31 l32 l33 u34
ę ś
a12
l42 l43 l44
l41
a12 = l11 u12 ,
u12 =
l11
a13
l11 0 0 0 1 u12 u13 u14 a11 a12 a13 a14
ł ł ł
a13 = l11 u13 u13 = ,
ęl l22 0 0 ś ę0 1 u23 u24 ś ęa a22 a23 a24 ś
l11 21 21
ę ś ę ś ę ś
=
ę ś ę ś ę ś
l31 l32 l33 0 0 0 1 u34 a31 a32 a33 a34
a14
ęl l42 l43 l44 ś ę0 0 0 1 ś ęa a42 a43 a44 ś
a14 = l11 u14 u14 = , 41 41
l11
16
l11 u12 u13 u14
ł
ęl l22 u23 u24 ś
21
ę ś
Q =
ę ś
l31 l32 l33 u34
ę ś
l42 l43 l44
l41
a22 = l21 u12 + l22 l22 = a22 -l21 u12,
a32 = l31 u12 + l32 l32 = a32 -l31 u12 ,
a42 = l41 u12 + l42 l42 = a42 -l41 u12,
a23 - l21 u13
a23 = l21 u13 + l22 u23 u23 = ,
l22
a24 - l21 u14
a24 = l21 u14 + l22 u24 u24 = ,
l22
17
a33 = l31 u13 + l32 u23 + l33 l33 = a33 -l31 u13 -l32 u23 ,
a43 = l41 u13 + l42 u23 + l43 l43 = a43 -l41 u13 -l42 u23 ,
a34 - l31 u14 - l32 u24
a34 = l31 u14 + l32 u24 + l33 u34 u34 = ,
l33
l11 u12 u13 u14
ł
ęl
a44 = l41 u14 + l42 u24 + l43 u34 + l44
l22 u23 u24 ś
21
ę ś
Q =
l44 = a44 -l41 u14 -l42 u24 -l43 u34 .
ę ś
l31 l32 l33 u34
ęl
l42 l43 l44 ś
41
18
L y = b y
l11 0 0 y1 b1
ł ł ł
ęl ś ęy ś ęb ś
l22 0 =
21 2 2
ę ś ę ś ę ś
ę ś ę ś ę ś
l32 l33 y3 b3
31
l
1 u12 u13 x1 y1
ł ł ł
ę0 1 u23ś ęx ś ęy ś
=
2 2
ę ś ę ś ę ś
U x = y x
ę ś ę ś ę ś
1 y3
3
0 0 x
l11 u12 u13
ł
ęl
Q = l22 u23ś
21
ę ś
Przykład dla n = 3
ę ś
l32 l33
31
l
19
Metoda dekompozycji LU - przykład
Ax = b A = LU LUx = b
2x1 +1x2 +1x3 = 5
1x1 + 2x2 +1x3 = 6
L y = b U x = y
1x1 +1x2 + 2x3 = 5
l11 u12 u13
ł
l11 0 0
ł
1 u12 u13
ł
ęl
ęl ś
ę0 1 u23ś
Q = l22 u23ś
L = l22 0
21
21 U =
ę ś
ę ś
ę ś
ę ś ę ś
l32 l33 l32 l33
ę
31 31
l l
0 0 1 ś
a12
1
1 4 5 l11 = a11 = 2
ł
u12 = =
l11 2
ę2 6 8ś
l21 = a21 = 1
ę ś
a13
1
u13 = =
ę ś
3 7 9
l31 = a31 = 1
l11 2
1 4 -1 3
l22 = a22 - l21 u12 = 2 -1 = =
2 2 2
1 1 1
l32 = a32 - l31 u12 = 1-1 = 1- =
2 2 2
1
a23 - l21 u13 1-1 2
1 2 1
u23 = = = =
3
l22 2 3 3
2
1 1 1 1 1 12 3 +1 8
ć
l33 = a33 - l31 u13 - l32 u23 = 2 -1 - = 2 - + = - =
2 2 3 2 6 6 6 6
Ł ł
1 1
1 ł
ł
1 1
ę 2 ł
ę2 0 0ś
2 2ś
ę
ę
2 2ś
ę ś
1ś
3
ę ś
ę
U = 0 1 ś 3 1
L = 1 0
ę ś
ę
Q = 1 ś
3ś
2
ę
ę ś
2 3ś
ę
ę0 0 1ś
ę1 1 8ś
ę1 1 8 ś
ę ś
ę ś
ę
2 6ś 2 6
5
2 y1 = 5
y1 =
Ly = b
2
3
1 y1 + y2 = 6
2
1 8
1 y1 + y2 + y3 = 5
2 6
3 5 7
5 3
y2 = 6 - y2 =
1 + y2 = 6
2 2 3
2 2
5 1 7 8 8 30 15 7 8
ć
1 + + y3 = 5 y3 = - + = y3 = 1
2 2 3 6 6 6 6 6 6
Ł ł
1 1 5
1 x1 + x2 + x3 =
Ux = y
2 2 2
1 7
1 x2 + x3 =
3 3
x3 = 1
1 x3 = 1
1 7 7 1 6
x2 + 1 = x2 = - = = 2 x2 = 2
3 3 3 3 3
1 1 5 5 1
1 x1 + 2 + 1 = x1 = -1- = 1 x1 = 1
2 2 2 2 2
Zadania do rozwiązania
2x1 + x2 + x3 = 5
x1 + 2x2 - x3 = 4
x1 +x2 + 2x3 = 5
2x1 + x2 + x3 = 5
x1 + x2 + 2x3 = 6
2x1 +2x2 + x3 = 6
Wyszukiwarka
Podobne podstrony:
Drugi wykład 14?z tłaCzwarty wykład 14?z tłaCzwarty wykład 14?z tłaTrzeci wykład 14?z tłaKonstrukcje zespolone pierwszy wykładrownania rozniczkowe rzedu pierwszego wyklad 5zapytania ap (pierwszy wykład)Czwarty wykład? 2014?z tłaCzwarty wykład? 2014?z tłaR Ingarden Wstęp do fenomenologii Husserla wyklad pierwszy03 Wykład 03 Upadek pierwszych ludzi i karawykład pierwszy 18 wrzesień 2010Szósty wykład 14 bez tłaZadania do wykładu pierwszego 18 wrzesień 2010Wyklad 2?kultet?rmatozy tla autoimmunologicznegowięcej podobnych podstron