Wykład drugi
1
Metody iteracyjne
przybliżonego rozwiązywania
układów równań liniowych
2
EiT, sem. 2, 2014/2015
Metody iteracji prostej:
A x + b = 0
- metoda Jacobiego,
- metoda Gaussa-Seidla
x(k+1) = f (x(k )) k = 0,1,2,....
1. Wzór rekurencyjny -
x(o)
2. Warunki początkowe -
x(k+1) - x(k ) < e
3. Warunki zakończenia obliczeń -
x(k+1) = x*
4. Rozwiązanie -
5. Warunki zbieżności algorytmu
3
Metody iteracji prostej
Dane jest równanie liniowe
(1)
A x = b , x Rn
A macierz nieosobliwa n x n wymiarowa,
b wektor wyrazów wolnych
Równanie (1) przekształcamy do postaci:
(2)
x = G x + c
G macierz n x n wymiarowa, c wyrazy wolne
x(0) Rn,
(3)
x(k+1) = G x(k ) + c , dla k = 0,1,2,Lż
4
x(0) Rn,
(3)
x(k+1) = G x(k ) + c , dla k = 0,1, 2,Lż
{x(k+1)} k = 0,1,2,...
Ciąg zdefiniowany formułą rekurencyjną algorytmu iteracji prostej
Jeżeli ciąg {x(k+1)} k = 0,1,2,...
jest zbieżny, to jego granicą jest wektor będący
rozwiązaniem równania (2)
x(k+1) = x*
5
Metoda Jacobiego
x = G x + c
A x = b , x Rn
x(0) Rn,
x(k+1) = G x(k ) + c , dla k = 0,1,2,Lż
a11 a12 L a1n x1 b1
ł ł ł
ęa21 a22 L a2n ś ęx2 ś ęb2 ś
=
ę ś ę ś ę ś
M M M M M
ęaM
an2 L ann ś ęxn ś ębn ś
n1
6
A x = b
x = G x + c
1 b1
x1 = (- a12 x2 - a13 x3 -K- a1n xn )+
a11 a11
1 b2
x2 = (- a21 x1 - a23 x3 -K- a2n xn )+
(4)
ż
a22 a22
......................................................
1 bn
xn = (- an1 x1 - an2 x2 -K- an,n-1 xn-1)+
ann ann
a12 a13 a1n
ł
0 - - L -
ę
a11 a11 a11 ś
ę ś
a23 a2n ś
ę- a21
0 - L -
ę
a22 a22 a22 ś (5)
ę
G =
a31 a32 a3n ś
ę ś
- - 0 L -
a33 a33 a33
ę ś
ę ś
M M M O M
ę ś
an1 an2 an3
ę- ann - ann - ann L 0 ś
7
Formuła rekurencyjna algorytmu w metodzie Jacobiego
xi,(0) R, dla i = 1,2,L,n,
1 b1
x1,(k+1) = (- a12 x2,(k ) - a13 x3,(k ) -K- a1n xn,(k ))+
a11 a11
1 b2
x2,(k +1) = (- a21 x1,(k ) - a23 x3,(k ) -K- a2n xn,(k ))+
k = 0,1,2,L
a22 a22
ż
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
1 bn
xn,(k+1) = (- an1 x1,(k ) - an2 x2,(k ) -K- an,n-1 xn-1,(k ))+
ann ann
b1
c1 =
a11
b2
c2 =
macierz G
a22
bn
cn =
ann
8
Zaczynamy obliczenia od przyjęcia, że
x(0) = c
Kończymy obliczenia, gdy
x(k+1) - x(k ) < e
Rozwiązanie
x(k +1) = x*
9
START
DANE: G, c, x(0),
k = 0
obliczenia
x(k+1)
TAK
SPRAWDZENIE
x(k+1) - x(k ) < e
NIE
x(k+1) = x*
k = k + 1
10
STOP
Czy warto zaczynać obliczenia ????
Trzeba sprawdzić warunki zbieżności !!!!
11
g11 g12 g1n
ł
ęg
g22 g2n ś
21
ę ś
G =
ę ś
ę ś
gn2 gnn
n1
g
Warunki zbieżności
n
gij < 1 j = 1,2,...,n
i=1
n
gij < 1 i = 1,2,...,n
j=1
12
Wyszukiwarka
Podobne podstrony:
Pierwszy wyklad 14?z tłaCzwarty wykład 14?z tłaCzwarty wykład 14?z tłaTrzeci wykład 14?z tłaCzwarty wykład? 2014?z tłaCzwarty wykład? 2014?z tławykład drugi 25 wrzesień 2010R Ingarden Wstęp do fenomenologii Husserla wyklad drugiSzósty wykład 14 bez tłaWykład drugiWyklad 2?kultet?rmatozy tla autoimmunologicznegoSieci komputerowe wyklady dr FurtakWykład 05 Opadanie i fluidyzacjaWYKŁAD 1 Wprowadzenie do biotechnologii farmaceutycznejwięcej podobnych podstron