Rozwiazanie ukladu rownan:
1.000000E+00 2.000000E+00 3.000000E+00
PROGRAM 2.3
Rozwiazywanie ukladu rownan liniowych.
Metoda relaksacji.
Liczba rownan ukladu - n = 3
Parametr relaksacji - om = 1.400
Zadana liczba iteracji - iter = 50
Zadana dokladnosc obliczen - eps = 1.000000E-06
Uklad sprowadzono do postaci normalnej
Macierz wspolczynnikow:
wiersz nr 1
2.000000E+00 1.000000E+00 -1.000000E+00
wiersz nr 2
1.000000E+00 3.000000E+00 -1.000000E+00
wiersz nr 3
1.000000E+00 -1.000000E+00 2.000000E+00
Wektor prawych stron:
1.000000E+00 4.000000E+00 5.000000E+00
Liczba wykonanych iteracji: 21
Rozwiazanie ukladu rownan:
9.999999E-01 2.000000E+00 3.000000E+00
2.7. Ekstremalne wartości własne
Działanie macierzy kwadratowej
na wektor X
(2.131)
możemy traktować jako operację liniową przejawiającą się w zmianie długości i kierunku wektora X. Jeśli przekształcenie to transformuje wektor X na siebie samego (tak, żeby wektor był równoległy do wektora X )
(2.132)
to liczbę nazywamy wartością własną macierzy A , a wektor X - wektorem własnym. Działanie macierzy A na wektor własny X możemy więc zastąpić pomnożeniem tego wektora przez liczbę, co umożliwia jakościowe uproszczenie rozwiązywania wielu zagadnień matematycznych i fizycznych.
Wartości własne macierzy A są pierwiastkami wielomianu charakterystycznego (2.13) tej macierzy
(2.133)
W obliczeniach numerycznych rzadko jednak wyznaczamy pierwiastki tego wielomianu, gdyż często zadanie to jest źle uwarunkowane - podczas gdy dobrze jest uwarunkowane zadanie pierwotne, ze względu na macierz A.
Dlatego też na ogół macierz A przekształcamy bez rozwijania jej wyznacznika charakterystycznego - do bardziej dogodnych postaci, umożliwiających obliczanie wartości własnych na podstawie różnych twierdzeń algebry liniowej [1 - 3, 6, 9].
Przy rozwiązywaniu wielu zadań wystarczająca jest znajomość wartości własnych: maksymalnej i minimalnej co do modułu np. alternatywna definicja wskaźnika uwarunkowania macierzy A (2.43): [6, 7], a najczęściej tylko maksymalnej np. (2.14) lub (2.130). Ograniczymy się więc do przedstawienia kilku prostych algorytmów obliczania ekstremalnych co do modułu wartości własnych macierzy o elementach rzeczywistych, omawianych m.in. w pracach [2, 8].
Mnożąc lewostronnie zależność dla k-tej wartości własnej i k-tego wektora własnego
(2.134)
przez macierz A otrzymamy
i po m-krotnym powtórzeniu tej operacji mamy
(2.135)
Podobnie mnożąc lewostronnie (2.134) przez dostajemy
i w ogólnym przypadku słuszna jest zależność
(2.136)
Po wykorzystaniu zależności (2.135) i (2.136) z twierdzenia, że suma wartości własnych macierzy A jest równa jej śladowi
(2.137)
wynika wniosek, że
(2.138)
dla dowolnej, całkowitej liczby m.
W przypadku, gdy maksymalna co do modułu wartość własna jest pierwiastkiem rzeczywistym i pojedynczym równania charakterystycznego (2.133)
(2.139)
na mocy (2.138) uzyskujemy związek
(2.140)
z którego, gdy m rośnie nieograniczenie mamy
(2.141)
Również w przypadku, gdy maksymalna co do modułu wartość własna jest rzeczywistym pierwiastkiem q-krotnym równania charakterystycznego (2.133)
(2.142)
jej wartość wyraża się wzorem (2.140), gdyż we wzorze (2.140) zarówno w liczniku, jak i w mianowniku będzie występowała jednakowa liczba jedynek
Po obliczeniu ze wzoru (2.141) nie wiadomo zatem, czy jest to pierwiastek pojedynczy czy też pierwiastek wielokrotny. Krotność pierwiastka rzeczywistego
o maksymalnej co do modułu wartości własnej możemy jednak łatwo obliczyć z zależności (2.138)
(2.143)
dla dostatecznie dużych m.
Wprowadzając we wzorze (2.138) wykładnik całkowity ujemny możemy w ana-logiczny sposób wyznaczyć minimalną co do modułu wartość własną macierzy A.
(2.144)
oraz jej krotność
(2.145)
odwracając uprzednio macierz A.
Maksymalną co do modułu wartość własną będącą pojedynczym pierwiastkiem zespolonym równania charakterystycznego (2.133)
(2.146)
można również obliczyć opierając się na własności (2.138).
Zapisując i w postaci wykładniczej
otrzymujemy
i następnie uzyskujemy zależność
z której dla dostatecznie dużych m mamy
(2.147)
Podstawiając uzyskane wyrażenie (2.147) do zależności
ostatecznie otrzymujemy
(2.148)
Do sprawdzenia prawidłowości wyznaczonych ekstremalnych wartości własnych i lokalizacji następnych pierwiastków równania charakterystycznego (2.133) można - oprócz (2.137) - wykorzystywać inne twierdzenia o wartościach własnych:
1. Jeżeli macierz A jest macierzą symetryczną o elementach rzeczywistych, to jej wartości własne i wektory własne są rzeczywiste.
2. Twierdzenie Perrona. Jeśli macierz A jest macierzą o elementach rzeczywistych dodatnich, to jej największa co do modułu wartość własna jest dodatnia i jest pojedynczym pierwiastkiem równania charakterystycznego, a odpowiadający jej wektor własny ma składowe dodatnie.
3. Twierdzenie Gerszgorina. Wszystkie wartości własne macierzy A leżą w obszarze, będącym sumą teoriomnogościową kół
o środkach oraz promieniach
Twierdzenie to, dla macierzy 4 stopnia o elementach rzeczywistych ilustruje poniższy rysunek 2.2.
Rys. 2.2
Znając wartość własną i odpowiadający jej wektor własny (obliczony np. przy przyjęciu dodatkowego warunku dotyczącego długości tego wektora) można również wyznaczyć drugą wartość własną i następne wartości własne metodą redukcji, korzystając z możliwości rozkładu dowolnego wektora względem różnych między sobą wektorów własnych [2, 13].
Znajomość wektorów własnych jest szczególnie istotna dla macierzy A symetrycznych o elementach rzeczywistych, gdyż np. dla macierzy kwadratowej, której kolumny są wektorami własnymi
można udowodnić zależność [6, 7]
oraz wykazać ortogonalność (2.30) macierzy S.
Obliczanie ekstremalnych co do modułu wartości własnych za pomocą wzorów (2.141), (2.143) ÷ (2.145) oraz (2.148) odbywa się w programie 2.4, którego tabulogram jest następujący:
{Program 2.4}
uses Crt;
const nmax = 20;
type
Tabl1 = array [1..nmax,1..nmax] of Real;
Tabl2 = array [1..nmax,1..2*nmax] of Real;
var
i,j,k,n,m,q,war: Integer;
bl,det,lam,lam1,eps,r,r1,s,Spm,Spm1: Real;
rep: Boolean;
A,Am,Am1: Tabl1;
B: Tabl2;
plik: Text;
label kon,omin,powt;
{Procedure ElimGaussa(n,m: Integer; var A: Tabl2; var det: Real);}
begin
Assign(plik,'Pr_2_4.dan');
Reset(plik);
Readln(plik,n,eps);
for i:=1 to n do
for j:=1 to n do
Read(plik,A[i,j]);
Close(plik);
ClrScr;
Writeln('Wybor alternatywy obliczen:');
Writeln(' - 1: obliczanie wartosci wlasnej o module max');
Writeln(' i jej krotnosci');
Writeln(' - 2: obliczanie ekstremalnych wartosci wlasnych');
Writeln(' i ich krotnosci');
Writeln(' - 3: obliczanie maksymalnego modulu zespolonej');
Writeln(' wartosci wlasnej');
Write('Wariant nr: '); Readln(war);
Assign(plik,'Pr_2_4.wyn');
Rewrite(plik);
Writeln(plik,'PROGRAM 2.4');
if war=1 then begin
Writeln(plik,'Obliczanie wartosci wlasnej o module max');
Writeln(plik,'i jej krotnosci.');
end;
if war=2 then begin
Writeln(plik,'Obliczanie ekstremalnych wartosci wlasnych');
Writeln(plik,'i ich krotnosci.');
end;
if war=3 then begin
Writeln(plik,'Obliczanie maksymalnego modulu zespolonej');
Writeln(plik,'wartosci wlasnej.');
end;
Writeln(plik);
Writeln(plik,'Stopien macierzy - n = ',n:2);
Writeln(plik,'Dokladnosc obliczen - eps = ',eps:11);
Writeln(plik);
Writeln(plik,'Macierz wspolczynnikow:');
for i:=1 to n do begin
Writeln(plik,' wiersz nr ',i:2);
k:=0; Write(plik,' ');
for j:=1 to n do begin
k:=k+1;
if k=5 then begin
k:=0;
Writeln(plik);
Write(plik,' ');
end;
Write(plik,' ',A[i,j]:13);
end;
Writeln(plik);
end;
Writeln(plik);
rep:=False;
powt:
m:=2; Spm:=0;
for i:=1 to n do
Spm:=Spm+A[i,i];
for i:=1 to n do
for j:=1 to n do begin
s:=0;
for k:=1 to n do
s:=s+A[i,k]*A[k,j];
Am[i,j]:=s;
end;
Spm1:=0;
for i:=1 to n do
Spm1:=Spm1+Am[i,i];
if not rep then lam:=Spm1/Spm else lam:=Spm/Spm1;
if war=3 then begin
r:=Exp(0.5/m*Ln(0.5*Abs(Spm*Spm-Spm1)));
goto omin;
end;
Spm:=Spm1;
repeat
for i:=1 to n do
for j:=1 to n do begin
s:=0;
for k:=1 to n do
s:=s+A[i,k]*Am[k,j];
Am1[i,j]:=s;
end;
Spm1:=0;
for i:=1 to n do
Spm1:=Spm1+Am1[i,i];
if not rep then lam1:=Spm1/Spm else lam1:=Spm/Spm1;
bl:=Abs(lam1-lam);
for i:=1 to n do
for j:=1 to n do
Am[i,j]:=Am1[i,j];
Spm:=Spm1; lam:=lam1;
m:=m+1;
until bl < eps;
s:=1;
for i:=1 to m do
if not rep then s:=s*lam else s:=s*(1/lam);
q:=Round(Spm/s);
if not rep then begin
Write(plik,'Wartosc wlasna o module max: ');
Writeln(plik,lam:16);
Write(plik,'Krotnosc max wartosci wlasnej - q: ');
Writeln(plik,q:2);
Write(plik,'Liczba potegowan macierzy zadanej - m: ');
Writeln(plik,m:2);
Writeln(plik);
end else begin
Write(plik,'Wartosc wlasna o module min: ');
Writeln(plik,lam:16);
Write(plik,'Krotnosc min wartosci wlasnej - q: ');
Writeln(plik,q:2);
Write(plik,'Liczba potegowan macierzy odwrotnej - m: ');
Writeln(plik,m:2);
Writeln(plik);
end;
if (war=1) or rep then goto kon;
for i:=1 to n do
for j:=1 to n do begin
B[i,j]:=A[i,j];
if i=j then B[i,n+j]:=1
else B[i,n+j]:=0;
end;
ElimGaussa(n,n,B,det);
Writeln(plik,'Macierz odwrotna:');
for i:=1 to n do begin
Writeln(plik,' wiersz nr ',i:2);
k:=0; Write(plik,' ');
for j:=1 to n do begin
k:=k+1;
if k=5 then begin
k:=0;
Writeln(plik);
Write(plik,' ');
end;
Write(plik,' ',B[i,n+j]:13);
end;
Writeln(plik);
end;
Writeln(plik);
for i:=1 to n do
for j:=1 to n do
A[i,j]:=B[i,n+j];
if not rep then begin
rep:=True;
goto powt;
end;
omin:
m:=3;
repeat
for i:=1 to n do
for j:=1 to n do begin
s:=0;
for k:=1 to n do
s:=s+A[i,k]*Am[k,j];
B[i,j]:=s;
end;
Spm:=0;
for i:=1 to n do
Spm:=Spm+B[i,i];
for i:=1 to n do
for j:=1 to n do begin
s:=0;
for k:=1 to n do
s:=s+B[i,k]*B[k,j];
Am1[i,j]:=s;
end;
Spm1:=0;
for i:=1 to n do
Spm1:=Spm1+Am1[i,i];
r1:=Exp(0.5/m*Ln(0.5*Abs(Spm*Spm-Spm1)));
bl:=Abs(r1-r);
for i:=1 to n do
for j:=1 to n do
Am[i,j]:=B[i,j];
m:=m+1; r:=r1;
until bl < eps;
Write(plik,'Max modul zespolonej wartosci wlasnej: ');
Writeln(plik,r:16);
Write(plik,'Liczba potegowan macierzy zadanej - m: ');
Writeln(plik,m:2);
Writeln(plik);
kon:
Close(plik);
end.
Wczytywane przez program 2.4 dane z pliku o nazwie pr_2_4.dan zawierają: stopień macierzy n, dokładność obliczania granicy ciągów (2.141), (2.144) lub (2.148) oraz zapisane wierszami współczynniki macierzy A. Wybór alternatywy obliczeń jest dokonywany z klawiatury poprzez przyjęcie odpowiedniej wartości zmiennej sterującej war ( war = 1,2,3), zgodnie z opisem ukazującym się na ekranie monitora.
Za pomocą programu 2.4 obliczono ekstremalne wartości własne następujących macierzy:
Przykład 1
.
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 3
Dokladnosc obliczen - eps = 1.0000E-06
Macierz wspolczynnikow:
wiersz nr 1
2.000000E+00 -2.000000E+00 3.000000E+00
wiersz nr 2
1.000000E+00 1.000000E+00 1.000000E+00
wiersz nr 3
1.000000E+00 3.000000E+00 -1.000000E+00
Wartosc wlasna o module max: 3.000000301E+00
Krotnosc max wartosci wlasnej - q: 1
Liczba potegowan macierzy zadanej - m: 42
Macierz odwrotna:
wiersz nr 1
6.666667E-01 -1.166667E+00 8.333333E-01
wiersz nr 2
-3.333333E-01 8.333333E-01 -1.666667E-01
wiersz nr 3
-3.333333E-01 1.333333E+00 -6.666667E-01
Wartosc wlasna o module min: 9.999998212E-01
Krotnosc min wartosci wlasnej - q: 1
Liczba potegowan macierzy odwrotnej - m: 24
Przykład 2
.
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 4
Dokladnosc obliczen - eps = 1.0000E-10
Macierz wspolczynnikow:
wiersz nr 1
1.000000E+00 2.000000E+00 3.000000E+00 4.000000E+00
wiersz nr 2
2.000000E+00 1.000000E+00 2.000000E+00 3.000000E+00
wiersz nr 3
3.000000E+00 2.000000E+00 1.000000E+00 2.000000E+00
wiersz nr 4
4.000000E+00 3.000000E+00 2.000000E+00 1.000000E+00
Wartosc wlasna o module max: 9.099019514E+00
Krotnosc max wartosci wlasnej - q: 1
Liczba potegowan macierzy zadanej - m: 29
Macierz odwrotna:
wiersz nr 1
-4.000000E-01 5.000000E-01 0.000000E+00 1.000000E-01
wiersz nr 2
5.000000E-01 -1.000000E+00 5.000000E-01 0.000000E+00
wiersz nr 3
0.000000E+00 5.000000E-01 -1.000000E+00 5.000000E-01
wiersz nr 4
1.000000E-01 0.000000E+00 5.000000E-01 -4.000000E-01
Wartosc wlasna o module min: -5.857864377E-01
Krotnosc min wartosci wlasnej - q: 1
Liczba potegowan macierzy odwrotnej - m: 36
Przykład 3
.
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 4
Dokladnosc obliczen - eps = 1.0000E-03
Macierz wspolczynnikow:
wiersz nr 1
1.000000E+00 3.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
2.000000E+00 5.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 2.000000E+00 -3.000000E+00
wiersz nr 4
0.000000E+00 0.000000E+00 -6.000000E+00 2.000000E+00
Wartosc wlasna o module max: 6.204897657E+00
Krotnosc max wartosci wlasnej - q: 2
Liczba potegowan macierzy zadanej - m: 11
Macierz odwrotna:
wiersz nr 1
-5.000000E+00 3.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
2.000000E+00 -1.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 -1.428571E-01 -2.142857E-01
wiersz nr 4
0.000000E+00 0.000000E+00 -4.285714E-01 -1.428571E-01
Wartosc wlasna o module min: -1.623287267E-01
Krotnosc min wartosci wlasnej - q: 1
Liczba potegowan macierzy odwrotnej - m: 4
W tym przykładzie wartości własne i są bliskie sobie, co spowodowało wyznaczenie jednej podwójnej wartości własnej o maksymalnym module - równej
O tym, że nie jest to wartość własna zadanej macierzy A możemy zorientować się z przebiegu obliczeń i bardzo wolnej zbieżności ciągu (2.141).
Przykład 4
.
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 4
Dokladnosc obliczen - eps = 1.0000E-06
Macierz wspolczynnikow:
wiersz nr 1
1.000000E+00 3.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
2.000000E+00 5.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 1.000000E+00 -2.000000E+00
wiersz nr 4
0.000000E+00 0.000000E+00 3.000000E+00 1.000000E+00
Wartosc wlasna o module max: 6.162278865E+00
Krotnosc max wartosci wlasnej - q: 1
Liczba potegowan macierzy zadanej - m: 20
Macierz odwrotna:
wiersz nr 1
-5.000000E+00 3.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
2.000000E+00 -1.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 1.428571E-01 2.857143E-01
wiersz nr 4
0.000000E+00 0.000000E+00 -4.285714E-01 1.428571E-01
Wartosc wlasna o module min: -1.622773833E-01
Krotnosc min wartosci wlasnej - q: 1
Liczba potegowan macierzy odwrotnej - m: 6
Przykład 5
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 4
Dokladnosc obliczen - eps = 1.0000E-04
Macierz wspolczynnikow:
wiersz nr 1
1.000000E+00 -2.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
3.000000E+00 1.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 2.000000E+00 -2.000000E+00
wiersz nr 4
0.000000E+00 0.000000E+00 5.000000E+00 2.000000E+00
Max modul zespolonej wartosci wlasnej: 3.741195271E+00
Liczba potegowan macierzy zadanej - m: 20
Przykład 6
.
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 4
Dokladnosc obliczen - eps = 1.0000E-04
Macierz wspolczynnikow:
wiersz nr 1
1.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
0.000000E+00 1.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 2.000000E+00 -2.000000E+00
wiersz nr 4
0.000000E+00 0.000000E+00 5.000000E+00 2.000000E+00
Max modul zespolonej wartosci wlasnej: 3.741652529E+00
Liczba potegowan macierzy zadanej - m: 9
Przykład 7
.
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 4
Dokladnosc obliczen - eps = 1.0000E-04
Macierz wspolczynnikow:
wiersz nr 1
5.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
0.000000E+00 5.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 1.000000E+00 -3.000000E+00
wiersz nr 4
0.000000E+00 0.000000E+00 2.000000E+00 -5.000000E+00
Wartosc wlasna o module max: 4.999963760E+00
Krotnosc max wartosci wlasnej - q: 2
Liczba potegowan macierzy zadanej - m: 41
Macierz odwrotna:
wiersz nr 1
2.000000E-01 0.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
0.000000E+00 2.000000E-01 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 -5.000000E+00 3.000000E+00
wiersz nr 4
0.000000E+00 0.000000E+00 -2.000000E+00 1.000000E+00
Wartosc wlasna o module min: -2.679604579E-01
Krotnosc min wartosci wlasnej - q: 1
Liczba potegowan macierzy odwrotnej - m: 5
Przykład 8
.
Wielomian charakterystyczny
Wartości własne:
Stopien macierzy - n = 4
Dokladnosc obliczen - eps = 1.0000E-06
Macierz wspolczynnikow:
wiersz nr 1
1.000000E+00 3.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 2
2.000000E+00 5.000000E+00 0.000000E+00 0.000000E+00
wiersz nr 3
0.000000E+00 0.000000E+00 1.000000E+00 3.000000E+00
wiersz nr 4
0.000000E+00 0.000000E+00 2.000000E+00 5.000000E+00
116 2. Układy równań liniowych
2.7. Ekstremalne wartości własne 117
Wyszukiwarka