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)