POLITECHNIKA LUBELSKA WYDZIAŁ ELEKTRYCZNY
KATEDRA INFORMATYKI
METODY NUMERYCZNE
Temat : Rozwiązać układ liniowy A x = b dla macierzy symetrycznej
dodatnio określonej.
Opracował:
Artur Chmarzyński
Grupa E.D. 7.5
Lublin styczeń 1996
Treść zadania.
a) Pokazać, że macierz synetryczna:
jest dodatnio określona,
b) Wyznaczyć macierz trójkątną R taką, że A = RT R,
c) Napisać program rozwiązujący układ liniowy A x = b ( dla macierzy symertycznej dodatnio określonej ), tak aby zminimalizować zajęte miejsce w pamięci.
Macierze symetryczne dodatnio określone
Niech A=( aji ) będzie macierzą symetryczną; jest więc aij=aji(1i,jn). Udowodnimy, że jeśli eliminację Gaussa wykonuje się bez przestawiania wierszy i kolumn, to
a(k)ij=a(k)ji (ki,jn),
tzn. przekształcane elementy tworzą macierze symetryczne stopnia n+1-k dla k=2,3,...,n. Zdanie jest prawdziwe dla k=1 zgodnie z:
(i=k+1, k+2 , ... , n ; j=k+1 , k+2 , ... , n+1)
w k-tym kroku elementy przekształca się w/g wzoru:
.
Jeśli zatem tożsamość a(k)ij=a(k)ji (ki,jn) zachodzi dla pewnego k, to:
i indukcja dowodzi słuszność twierdzenia.
Widzimy więc, że jeśli eliminację Gaussa stosuje się do macierzy symetrycznej bez przestawiania wierszy i kolumn, to wystarczy obliczać elementy leżące w A(k) na głównej przekątnej i nad nią. W symetrycznej eliminacji Gaussa przekształcamy te elementy w/g wzoru:
(i=k+1, k+2 , ... , n ; j=k+1 , k+2 , ... , n+1)
a dla k=1,2, ... , n-1 zgodnie ze wzorami :
(i=k+1 , k+2 , ... , n ; j=i , i+1, ... , n).
Dzięki temu liczba operacji zmniejsza się w przybliżeniu dwukrotnie do i tak samo maleje wykorzystanie pamięci.
Kryterium Sylwestra
Macierz A stopnia n jest dodatnio określona wtedy i tylko wtedy, gdy:
, (k=1,2, ... ,n)
gdzie Ak jest macierzą k*k utworzoną z przecięcia k początkowych wierszy i kolumn macierzy A.
Z wzoru:
, (k=1,2,... ,n)
wynika, że to kryterium jest równoważne nierównościom (k=1,2, ... ,n). Jeśli zatem wykonujemy eliminację Gaussa nie przestawiając wierszy ani kolumn, to wszystkie elementy główne są dodatnie wtedy i tylko wtedy, gdy macierz A jest dodatnio określona. Zauważamy, że wobec powyższego kryterium zredukowane macierze są też dodatnio określone.
Ad a) Dana macierz:
Z symetrycznej wersji:
(i=k+1 , k+2 , ... , n ; j=i , i+1, ... , n)
eliminacji Gaussa otrzymujemy kolejno następujące zredukowane macierze (wystarcza tylko przekształcać ich części górne trójkątne):
Elementy główne: 10;0,1;2;0,5 są dodatnie więc macierz A jest dodatnio określona.
Twierdzenie o rozkładzie trójkątnym dla macierzy symetrycznej dodatnio określonej.
Niech A będzie macierzą symertyczną dodatnio określoną. Istnieje wtedy jedyna macierz trójkątna górna R o dodatnich elementach na głónej przekątnej i taka, że
Z twierdzenia o rozkładzie LU wynika, że A=LU, gdzie u11=a11>0 i
(k=2,3, ... ,n).
Wprowadziwszy macierz przekątniową
możemy napisać rozkład
, gdzie ,
a macierze L i U są trójkątne, mają jedynki na głównej przekątnej i są jednoznacznie określone. Z symetrii A wynika, że
, czyli .
Przyjmijmy teraz , gdzie macierz przekątniowa ma dodatnie elementy . Otrzymujemy wtedy
Podkreślamy, że w symetrycznej eliminacji Gaussa nie trzeba pamiętać mnożników. Układ w tym przypadku rozkłada się na dwa układy trójkątne
i (unikamy w ten sposób pierwiastkowania).
Ad b)
Mamy , gdzie wobec symetrycznej eliminacji Gaussa otrzymujemy macierz trójkątną górną R o dodatnich elementach na głównej przekątnej taką, że A=RTR
;
c) Do rozwiązania równania liniowego Ax = b (dla macierzy symetrycznej dodatnio określonej) wykorzystałem procedury zamieszczone w opracowaniu:
„Numerical Procedures in Turbo Pascal for Your PC”
Andrzej Marciniak , Dorota Gregulec , Jan Kaczmarek
Wydawnictwo Nakom Poznań 1992.
Przykładowe obliczenia z programu :
Dana macierz:
Kolejne elementy macierzy b :
Przykład 1. Przykład 2.
b[1]=1 b[1]=-0.001
b[2]=1 b[2]=35
b[3]=1 b[3]=0.07
b[4]=1 b[4]=9
Rozwiązanie układu równań :
Prykład 1. Przykład 2.
x[1]=-12.0000 x[1]=-1488.3250
x[2]=20.0000 x[2]=2468.8510
x[3]=-5.0000 x[3]=-621.6600
x[4]=3.0000 x[4]=367.7960
Wyszukiwarka