R3_Ukl_Row_Lin.doc

(646 KB) Pobierz

Rozwiązywanie numeryczne układów równań liniowych

Droga jasności mroczną się wpierw zdaje.

Postęp zaś cofaniem wydać się może.

Lao-cy

Bardzo ważną klasą intensywnych obliczeniowo zadań jest rozwiązywanie układów równań liniowych

gdzie jest nieosobliwą macierzą , a jest dany wektor.

Szacuje się, że około 75 procent czasu obliczeniowego superkomputerów jest wykorzystywanych właśnie na rozwiązywanie takich zadań.

Czasem takie zadania obliczeniowe wymagają wykonania wielkiej liczby obliczeń zmiennoprzecinkowych, przy czym wiele znanych, matematycznie równoważnych metod rozwiązywania, ma diametralnie różne własności numeryczne.

Dowolny układ równań liniowych.

Obecnie rozważamy układ równań liniowych złożony z równań o niewiadomych

Oznaczymy macierz rozszerzoną

Twierdzenie. Każdą macierz za pomocą przekształceń elementarnych na wierszach i kolumnach można sprowadzić do postaci normalnej

Dowód. Ponieważ nie wszystkie są zerami, więc można tak przestawić wierszy i kolumny, żeby . Po pomnożeniu pierwszego wiersza przez otrzymamy wiersz, w którym . Mnożąc wtedy pierwszy wiersz przez i dodając do i-tego wiersza () otrzymujemy w pierwszej kolumnie poniżej wyrazu same zera.

Przy tych operacjach wyrazy macierzy na ogół ulegli zmianie i dla tego oznaczymy je przez . Wówczas mamy

Zwróćmy uwagę, że jeśli wszystkie wyrazy poniżej pierwszego wiersza są zerami, to macierz już jest macierzą postaci . Natomiast, gdy tak nie jest, to nie zmieniając położenia pierwszego wiersza i pierwszej kolumny przestawimy tak wiersze i kolumny macierzy , aby i powtarzamy cykl czynności opisanych powyżej – w rezultacie czego uzyskamy w drugiej kolumnie (z wyjątkiem wyrazu same zera

Powtarzając czynności dochodzimy do postaci macierzy .

Z postaci macierzy wynika, że jeśli , to nie ma wierszy wypełnionych samymi zerami. Jeśli , to r-ta kolumna jest przedostatnią kolumną.

Macierzy odpowiada następna postać układu równań liniowych

Wnioski:

— układ sprzeczny;

— układ rozwiązalny oraz przy jest oznaczony, a kiedy jest nieoznaczony.

Twierdzenie. Układ równań liniowych jest rozwiązalny wtedy i tylko wtedy, gdy

przy czym, gdy

to układ ma dokładnie jedno rozwiązanie, gdy zaś

to układ ma nieskończenie wiele rozwiązań zależnych od parametrów.

Zaznaczmy, że , a tym samym na podstawie twierdzenia wtedy i tylko wtedy, gdy .

Metody dokładne (sformułowanie zagadnienia). Dany jest układ równań liniowych z niewiadomymi

Układ ten można w skrócie zapisać w postaci równania macierzowego

gdzie

jest macierzą współczynników układu równań,

— kolumna niewiadomych i wyrazów wolnych tego układu.

Gdy macierz jest nieosobliwa, tzn. , wówczas układ ma dokładnie jedno rozwiązanie. Wyróżnimy dwie metody dokładne.

Pierwsza z nich opiera się na wykorzystaniu macierzy odwrotnej. Mnożąc lewostronnie obie strony równania macierzowego przez macierz odwrotną otrzymamy rozwiązanie układu równań liniowych w postaci macierzowej

Druga metoda wykorzystuje właściwości wyznaczników. Rozwiązanie układu równań liniowych przy użyciu wyznaczników dają następujące wzory Cramera

, ,

gdzie

jest wyznacznikiem, który powstaje z wyznacznika

przez zamianę jego i-tej kolumny () kolumną wyrazów wolnych rozważanego układu.

Opisane metody ścisłe jest bardzo czasochłonne i są wykorzystane za zwyczaj tylko w rozważaniach teoretycznych.

Uwarunkowanie układu dwóch 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.

Definicja. Układ równań liniowych nazywa się złe uwarunkowanym, jeśli małe zmiany współczynników prowadzą do dużych zmian rozwiązania ().

Przykład. Rozważmy dwa mało różniący się układy równań liniowych

oraz

Dokładne rozwiązanie pierwszego układu , , wówczas dla drugiego układu mamy , .

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.

(plik: MN_07_Uklady_Row_Lin_2)

Proste układy równań.

Układy z macierzą trójkątną.

Rozważmy układ z macierzą trójkątną . Będą nas szczególnie interesować macierze trójkątne górne , dla których , gdy , oraz macierze trójkątne dolne z jedynkami na przekątnej , tzn. () i , mianowicie

i .

Układ z nieosobliwą macierzą trójkątną górną

gdzie , , można rozwiązać stosując algorytm:

Algorytm Podstawienie w tył

$\displaystyle x_N^*\, =\, c_N / u_{N,N}$ ;

for (i = N-1; i >= 1; i--)

$\displaystyle x_i^*\,:=\,\left( c_i\,-\, \sum_{j=i+1}^N u_{i,j}x_j^*\right)/u_{i,i}$ ;

Algorytm ten jest wykonalny, ponieważ nieosobliwość macierzy implikuje, że .

Podobnie, układ rozwiązujemy algorytmem:

Algorytm Podstawienie w przód

$\displaystyle x_1 = c_1$ ;

for (i=2; i <= N; i++)

$\displaystyle x_i = c_i\,-\,\sum_{j=1}^{i-1} l_{i,j} x_j^*$ ;

Oba algorytmy wymagają rzędu mnożeń lub dzieleń i dodawań lub odejmowań, a więc łącznie działań arytmetycznych.

Układy z macierzą ortogonalną

Równie prosto można rozwiązać układ równań

gdy jest macierzą ortogonalną, to znaczy . Z ortogonalności wynika wprost, że

i w konsekwencji można wyznaczyć kosztem takim, jak koszt mnożenia macierzy przez wektor, czyli operacji.

Podobnie, gdy jest unitarna, to znaczy (przypomnijmy: oznacza macierz sprzężoną do , tzn. taką, że ), rozwiązaniem układu równań jest

Metoda eliminacji Gaussa (Carl Friedrich Gauss).

Dla dalszych rozważań wykorzystamy inną notację współczynników układu równań i jego wyrazów wolnych, nadając im na początek górny wskaźnik (1), mianowicie

Oprócz tego, że , załóżmy również, że . Jeśli , to można tak przestawiać kolumny lub wierszy w układzie, żeby uzyskać w lewym górnym rogu niezerowy element.