Układy równań liniowych z macierzami pasmowymi - omówienie

Nasza ocena:

3
Pobrań: 133
Wyświetleń: 637
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Układy równań liniowych z macierzami pasmowymi - omówienie - strona 1 Układy równań liniowych z macierzami pasmowymi - omówienie - strona 2 Układy równań liniowych z macierzami pasmowymi - omówienie - strona 3

Fragment notatki:

WYKŁAD 6
UKŁADY RÓWNAŃ LINIOWYCH Z MACIERZAMI PASMOWYMI
Jeśli macierz A układu równań
AX = B
jest trójdiagonalna
b 1

a 2



A=







c1
b2
c2
.
.
.
.
.
.
.
.
.
an−1
bn−1
0
0
an






,



cn−1 

bn 

(1)
to układ równań:
b1 x1 + c1 x2 = d 1 , 

a2 x1 + b2 x2 + c2 x3 = d 2 , 

an −1 xn − 2 + bn −1 xn −1 + cn −1 xn = d n −1 , 
an xn −1 + bn xn = d n 

(2)
mo na rozwiązać nadzwyczaj szybko, wykonując małą liczbę działań arytmetycznych. Wykorzystując
zasadę eliminacji zmiennych wyznaczamy niewiadomą x1 z pierwszego równania, z równania drugiego
wyznaczamy niewiadomą x2 , którą podstawiamy do równania trzeciego itd.
Rezultatem takiego postępowania jest algorytm, zwany metodą faktoryzacji (przeganiania,
ros. pieriegonka), polegający na obliczeniu najpierw wielkości pomocniczych:
qk = −
uk =
ck
,
pk
1
( d k − a k u k −1 ) (u 0 = 0)
pk
( k = 1, 2, ..., n),











(3)
gdzie
pk = ak qk −1 + bk (q0 = 0) ,
a następnie niewiadomych:
xn = u n ,
xk = qk xn+1 + u k
(k = n − 1, ..., 1) .







(4)
Metoda faktoryzacji jest niezawodna, jeśli macierz A jest diagonalnie dominująca tzn. gdy
b1 ≥ c1
,
bk ≥ a k + ck ( k = 2, 3, ..., n − 1),
bn ≥ an .
Równie skuteczną metodą rozwiązywania układów równań z trójdiagonalnymi macierzami
współczynników jest metoda, zwana algorytmem Thomasa [11], oparta na rozkładzie macierzy (1)
na iloczyn LU. Po wyznaczeniu elementów macierzy L i U:
β 1
a β
2
 2
L=
.




.
a n −1 β n −1
an
c

1 1
 β

1



1


;U = 




βn 




c2
β2





,
. .
cn − 1 

1
β n −1 
1 

(5)
gdzie:
β1 = b1 ,
β k = bk − a k
c k −1
β k −1
(k = 2, 3, ..., n)









(6)
i obliczeniu wielkości pomocniczych:
γ1 =
γk =











d1
,
β1
1
(d k − ak γ k −1 )
βk
(k = 2, 3, ..., n)
(7)
dostajemy:
xn = γ n ,
xk = γ k −
ck
xk +1
βk
(k = n − 1, n − 2, ..., 1) .









(8)
Układy równań z trójpasmowymi macierzami współczynników i niezerowymi elementami naro nymi
b 1

a 2









c
 n
c1
b2
c2
.
.
.
.
.
.
.
.
.
an−1
bn−1
0
0
an
występują przy rozwiązywaniu zagadnień okresowych.
a1   x1   d1 
 


  x2   d 2 


 


 


 
  ...  =  ... 
 



 


 

cn−1   xn−1  d n−1 
 


bn   xn   d n 


 
(9)
Rozkładając macierz A na podmacierze
a1
A′
A=
(10)
cn−1
cn
an
bn
układ (9) zastępujemy dwoma układami równowa nymi:
 a1 
 
 0 
 
A ′ X ′ +  ...  xn = D ′,
 
 0 
 
c 
 n−1 
[c , 0, ..., 0, a ] X ′ + b x
n
n
n n
= dn ,













gdzie:
 x1 


 x2 
,
X′ = 
 ... 


 xn−1 


 d1 


 d2 
.
D′ = 
 ... 


d n−1 


(11)
Podstawiając
X ′ = X (1) + xn X ( 2 )
(12)
do pierwszego układu (11) uzyskujemy układy równań z trójdiagonalnymi macierzami współczynników
dla wektorów X (1) i X ( 2) :
A ′ X ( 2)
 a1 
 
 0 
  ... zobacz całą notatkę



Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz