Pierwszy wyklad 2014 bez tła


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ś
ę ś

3
ę ś
ę
U = 0 1 ś 3 1
L = 1 0
ę ś
ę
Q = 1 ś

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ła
Czwarty wykład 14?z tła
Czwarty wykład 14?z tła
Trzeci wykład 14?z tła
Konstrukcje zespolone pierwszy wykład
rownania rozniczkowe rzedu pierwszego wyklad 5
zapytania ap (pierwszy wykład)
Czwarty wykład? 2014?z tła
Czwarty wykład? 2014?z tła
R Ingarden Wstęp do fenomenologii Husserla wyklad pierwszy
03 Wykład 03 Upadek pierwszych ludzi i kara
wykład pierwszy 18 wrzesień 2010
Szósty wykład 14 bez tła
Zadania do wykładu pierwszego 18 wrzesień 2010
Wyklad 2?kultet?rmatozy tla autoimmunologicznego

więcej podobnych podstron