MN 07 Uklady Row Lin 2, metody numeryczne


MN07

Uwarunkowanie układu równań liniowych

Zajmiemy się wrażliwością układu równań na zaburzenia danych: prawej strony i współczynników macierzy układu. Czułość danego układu równań na zaburzenia da się precyzyjnie scharakteryzować, a cecha ta nie tylko będzie miała wpływ na jakość rozwiązań możliwych do uzyskania w arytmetyce skończonej precyzji, ale także na efektywność metod iteracyjnych rozwiązywania układów równań liniowych, w których są tysięcy (lub więcej) niewiadomych.

Przykład: Uwarunkowanie układu dwóch równań liniowych

Rozwiązanie układu dwóch równań liniowych można przedstawić w formie graficznej: jest to punkt przecięcia się dwóch prostych wyznaczonych przez dane współczynniki i wyrazy prawej strony.

Rozważmy pewien nieosobliwy układ dwóch równań liniowych. Ma on dokładnie jedno rozwiązanie, na rysunku oznaczone kolorem czerwonym. Co się stanie, gdy trochę zaburzymy prawą stronę takiego układu?

Wykresy zaburzonych prostych mogą zająć jedną z zaznaczonych łososiowym kolorem pozycji.

Obszar, gdzie mogą znaleźć się rozwiązania zaburzonego układu, zaznaczyliśmy na czerwono. Jest on, kolokwialnie rzecz ujmując, z grubsza tak wielki jak wielkie były zaburzenia, co zgodne jest z typową intuicją "człowieka z zewnątrz".

Jednak bywają równania, wrażliwe jak mimoza na nawet delikatne zaburzenia danych. Takie równanie właśnie widzimy na rysunku: jego cechą szczególną jest to, że tym razem proste, choć wciąż przecinają się dokładnie w jednym punkcie, są prawie równoległe.

Bierzemy zaburzenia takie same, jak poprzednio. Wykresy zaburzonych prostych mogą zająć jedną z zaznaczonych łososiowym kolorem pozycji.

Tym razem obszar niepewności, gdzie mogą być rozwiązania naszego zaburzonego układu, jest gigantyczny.

A więc równania liniowe mogą, choć nie muszą, być bardzo podatne na zaburzenia danych. Gdy zamiast prawej strony, zaburzymy wyrazy macierzy układu, może nawet okazać się, że dostaniemy układ równań sprzecznych .

Aby przedstawić ogólną teorię zaburzeń dla układów równań liniowych, musimy mieć narzędzia do pomiaru błędu rozwiązań, a także zaburzeń danych zadania: czyli macierzy i wektora prawej strony. Temu będą służyć normy.

Normy wektorowe i macierzowe

Aby badać odległość między rozwiązaniem dokładnym układu równań a jego wartością przybliżoną uzyskaną np. algorytmem eliminacji Gaussa, będziemy posługiwać się normami wektorów 0x01 graphic
i macierzy 0x01 graphic
. Najczęściej używanymi normami wektorowymi będą normy 0x01 graphic
-te,

0x01 graphic

oraz

0x01 graphic

W szczególności, norma 0x01 graphic
jest dobrze nam znaną normą euklidesową wektora.

Kula jednostkowa w normie 0x01 graphic
w 0x01 graphic

Kula jednostkowa w normie 0x01 graphic
w 0x01 graphic

Kula jednostkowa w normie 0x01 graphic
w 0x01 graphic

Normą macierzową jest norma Frobeniusa

0x01 graphic

a także normy indukowane przez normy wektorowe (np. przez normy 0x01 graphic
-te)

0x01 graphic

Jeśli norma macierzowa jest indukowana przez normę wektorową, to dla dowolnego wektora mamy

0x01 graphic

Przypomnijmy, że w przestrzeniach liniowych skończenie wymiarowych (a więc także w 0x01 graphic
i w przestrzeni macierzy wymiaru 0x01 graphic
) każde dwie normy są równoważne. To znaczy, że jeśli mamy dwie normy 0x01 graphic
i 0x01 graphic
w przestrzeni skończenie wymiarowej 0x01 graphic
, to istnieją stałe 0x01 graphic
takie, że

0x01 graphic

W szczególności dla 0x01 graphic
mamy

0x01 graphic

a dla 0x01 graphic
mamy

0x01 graphic

gdzie 0x01 graphic
.

Dla macierzy 0x01 graphic
mamy

0x01 graphic

oraz

0x01 graphic

Dowód tego faktu zostawiamy jako ćwiczenie.

Uwarunkowanie układu równań liniowych

Wyprowadzimy teraz wynik świadczący o tym, jak zaburzenie względne danych przenosi się na błąd względny wyniku rozwiązania 0x01 graphic
układu równań liniowych 0x01 graphic
.

Lemat Neumanna o otwartości zbioru macierzy odwracalnych

Jeśli 0x01 graphic
jest macierzą taką, że 0x01 graphic
, to macierz 0x01 graphic
jest nieosobliwa oraz

0x01 graphic

Dowód. Rzeczywiście, gdyby 0x01 graphic
była osobliwa, to istniałby niezerowy wektor 0x01 graphic
taki, że 0x01 graphic
, co implikuje 0x01 graphic
i w konsekwencji 0x01 graphic
. Aby pokazać oszacowanie normy macierzy 0x01 graphic
zauważmy, że

0x01 graphic

skąd już wynika dowodzona nierówność.

Twierdzenie O uwarunkowaniu układu równań

Niech 0x01 graphic
i 0x01 graphic
będą zaburzeniami odpowiednio macierzy 0x01 graphic
i wektora 0x01 graphic
na poziomie względnym 0x01 graphic
, tzn.

0x01 graphic

Jeśli

0x01 graphic

to układ zaburzony 0x01 graphic
ma jednoznaczne rozwiązanie 0x01 graphic
spełniające

0x01 graphic

gdzie definiujemy współczynnik uwarunkowania układu

0x01 graphic

Zauważmy najpierw, że zachodzi

Dowód. Po podstawieniu 0x01 graphic
mamy teraz

0x01 graphic

co wobec równości 0x01 graphic
daje, że macierz 0x01 graphic
jest nieosobliwa i układ zaburzony ma jednoznaczne rozwiązanie 0x01 graphic
. Przedstawmy to rozwiązanie w postaci 0x01 graphic
. Rozpisując układ zaburzony i wykorzystując równość 0x01 graphic
otrzymujemy, że 0x01 graphic
, czyli

0x01 graphic

a stąd

0x01 graphic

co kończy dowód.

Gdy więc np. 0x01 graphic
, oszacowanie błędu rozwiązania układu zaburzonego możemy zastąpić czytelniejszym (choć mniej precyzyjnym)

0x01 graphic

Octave i MATLAB mają wbudowane funkcje wyznaczające normy wektorów i macierzy

N = 3;

x = [1:N]'

A = pascal(N)

norm(A,1)

norm(x,2)

norm(A,Inf)

a także funkcje wyznaczające uwarunkowanie macierzy, przy czym Octave liczy tylko uwarunkowanie w normie 0x01 graphic
:

cond(A)

W LAPACKu służy do tego funkcja DGECON. Zadanie wyznaczania uwarunkowania macierzy jest zadaniem bardzo intensywnym numerycznie. Problem, czy da się je wyznaczyć z dobrą dokładnością kosztem niższym niż wyznaczenie macierzy odwrotnej i jej normy, jest wciąż otwarty.

W praktyce obliczeniowej trafiają się zarówno układy dobrze uwarunkowane, jak i macierze, których uwarunkowanie może być patologicznie duże (np. takie macierze są chlebem powszednim osób rozwiązujących równania różniczkowe).

Przykład: Macierz Hilberta

Przykładem macierzy o uwarunkowaniu wyjątkowo szybko rosnącym z wymiarem jest m.in. macierz Hilberta 0x01 graphic
, gdzie

0x01 graphic

Macierz Hilberta wymiaru 25. Kolor odpowiada rzędowi wielkości elementu macierzy, dokładniej, 0x01 graphic
. Jak widzisz, większość elementów tej macierzy jest równa prawie zero, a więc w konsekwencji kolumny macierzy są prawie liniowo zależne.

Taką macierz możemy wygenerować w Octave komendą hilb(N). Jest to bardzo specyficzna macierz, co m.in. przejawia się tym, że uwarunkowanie macierzy Hilberta rośnie eksponencjalnie z 0x01 graphic
, 0x01 graphic
:

<realnowiki><realnowiki>octave:2> cond(hilb(5))

ans = 4.7661e+05

octave:3> cond(hilb(10))

ans = 1.6025e+13

octave:4> cond(hilb(15))

ans = 3.7689e+17

octave:5> cond(hilb(20))

ans = 7.1209e+19

</realnowiki></realnowiki>

Numeryczna poprawność eliminacji Gaussa

Przedstawimy bez dowodu klasyczne twierdzenie o "praktycznej numerycznej poprawności" eliminacji Gaussa z wyborem w kolumnie.

Twierdzenie Wilkinsona. Algorytm eliminacji Gaussa z wyborem elementu głównego w kolumnie, zrealizowany w arytmetyce 0x01 graphic
, wyznacza 0x01 graphic
taki, że 0x01 graphic
jest dokładnym rozwiązaniem zadania zaburzonego

0x01 graphic

przy czym

0x01 graphic

dla pewnej niedużej stałej 0x01 graphic
. Wskaźnik wzrostu 0x01 graphic
definiujemy tutaj jako

0x01 graphic

gdzie 0x01 graphic
i 0x01 graphic
są numerycznie wyznaczonymi czynnikami rozkładu PA0x01 graphic
LU.

Jak widzimy, kluczowe dla numerycznej poprawności jest oszacowanie wskaźnika wzrostu 0x01 graphic
. Okazuje się, co wiedział już Wilkinson, że

0x01 graphic

Konkluzja jest więc taka, że algorytm eliminacji Gaussa z wyborem w kolumnie jest praktycznie numerycznie poprawny. Z drugiej strony, dla bardzo dużych 0x01 graphic
i niezbyt dobrze uwarunkowanych macierzy, może okazać się, że arytmetyka pojedynczej precyzji może okazać się niewystarczająca dla uzyskania godnego wyniku.

Algorytm eliminacji Gaussa z pełnym wyborem elementu głównego jest numerycznie poprawny, ze wskaźnikiem wzrostu 0x01 graphic
, a w praktyce grubo poniżej 0x01 graphic
.

Literatura



Wyszukiwarka

Podobne podstrony:
MN 05 Uklady Row Lin 1, metody numeryczne
MN 08 Uklady Row Lin 3, metody numeryczne
MN 02 Row Nielin, metody numeryczne
R4 Niel Row Alg(1), metody numeryczne
R8 Row Roz, metody numeryczne
Metody numeryczne PDF, MN mnk2 07
MN energetyka zadania od wykładowcy 09-05-14, STARE, Metody Numeryczne, Część wykładowa Sem IV
Metody numeryczne PDF, MN macierze 01 1
Metody numeryczne PDF, MN raphson 11
Cichy B Metody numeryczne, mn 06
Cichy B Metody numeryczne, mn 08
Metody numeryczne PDF, MN mnk1 06
Metody numeryczne PDF, MN inter 05

więcej podobnych podstron