MN07
Uwarunkowanie układu równań liniowych
<<< Powrót do strony głównej przedmiotu Metody numeryczne
Zajmiemy się wrażliwością układu równań na zaburzenia danych: prawej strony i współczynników macierzy układu. Jak zobaczymy na poniższym przykładzie, bywają równania, które są mało podatne na zaburzenia danych (a więc: dobrze uwarunkowane) oraz równania, które są szalenie wrażliwe na zaburzenia, a więc źle uwarunkowane. Jak wkrótce się przekonamy, 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ęce (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.
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 (czy możesz podać przykład?)
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
i macierzy . Najczęściej używanymi normami wektorowymi będą normy -te,oraz
W szczególności, norma
jest dobrze nam znaną normą euklidesową wektora.Normą macierzową jest norma Frobeniusa
a także normy indukowane przez normy wektorowe (np. przez normy
-te)Jeśli norma macierzowa jest indukowana przez normę wektorową, to dla dowolnego wektora mamy
Przypomnijmy, że w przestrzeniach liniowych skończenie wymiarowych (a więc także w
i w przestrzeni macierzy wymiaru ) każde dwie normy są równoważne. To znaczy, że jeśli mamy dwie normy i w przestrzeni skończenie wymiarowej , to istnieją stałe takie, żeW szczególności dla
mamya dla
mamygdzie
.Dla macierzy
mamyoraz
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
układu równań liniowych .Twierdzenie O uwarunkowaniu układu równań
Niech
i będą zaburzeniami odpowiednio macierzy i wektora na poziomie względnym , tzn.Jeśli
to układ zaburzony
ma jednoznaczne rozwiązanie spełniającegdzie definiujemy współczynnik uwarunkowania układu
Zauważmy najpierw, że zachodzi
Lemat Neumanna o otwartości zbioru macierzy odwracalnych
Jeśli
jest macierzą taką, że , to macierz jest nieosobliwa orazDowód
Rzeczywiście, gdyby
była osobliwa, to istniałby niezerowy wektor taki, że , co implikuje i w konsekwencji . Aby pokazać oszacowanie normy macierzy zauważmy, żeskąd już wynika dowodzona nierówność.

Dowód twierdzenia o uwarunkowaniu
Po podstawieniu
mamy terazco wobec równości
daje, że macierz jest nieosobliwa i układ zaburzony ma jednoznaczne rozwiązanie . Przedstawmy to rozwiązanie w postaci . Rozpisując układ zaburzony i wykorzystując równość otrzymujemy, że , czylia stąd
co kończy dowód.

Gdy więc np. oszacowanie błędu rozwiązania układu zaburzonego możemy zastąpić czytelniejszym (choć mniej precyzyjnym)
,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
: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
, gdzieTaką 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 , :
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
,wyznacza
taki, że jest dokładnym rozwiązaniem zadania zaburzonegoprzy czym
dla pewnej niedużej stałej
. Wskaźnik wzrostu definiujemy tutaj jako
gdzie i są numerycznie wyznaczonymi czynnikami rozkładu PA LU.
Jak widzimy, kluczowe dla numerycznej poprawności jest oszacowanie wskaźnika wzrostu
. Okazuje się, co wiedział już Wilkinson, że- w ogólnym przypadku, zachodzi oszacowanie , które jest osiągane dla macierzy
- dla macierzy trójdiagonalnych lub diagonalnie dominujących, lub dla macierzy symetrycznych dodatnio określonych, ;
- w średnim przypadku, obserwuje się , to znaczy macierze spotykane w praktyce obliczeniowej mają mały wskaźnik wzrostu.
Konkluzja jest więc taka, że algorytm eliminacji Gaussa z wyborem w kolumnie jest praktycznie numerycznie poprawny. Z drugiej strony, dla bardzo dużych
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
, a w praktyce grubo poniżej .Literatura
W celu dogłębnego zapoznania się z omawianym na wykładzie materiałem, przeczytaj rozdział 4.4 i, nieobowiązkowo, 4.5 w
- D. Kincaid, W. Cheney Analiza numeryczna, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 83-204-3078-X.
Bardzo dużo informacji na temat omawianych zagadnień znajduje się w monografiach
- A.Kiełbasiński, H. Schwetlick, Numeryczna algebra liniowa, Wydawnictwa Naukowo-Techniczne, Warszawa, 1992,
- N. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, 2002.