5
40
41
(1.53)
(1.54)
Ulepszenie metody Gaussa nazywane metoda eliminacji z wyborem elementu dominującego polega na odpowiednim wyborze elementów eliminujących, tzn. elementów cn, przez które dzielimy kolejne równania. Optymalny wybór tych elementów znacznie poprawia dokładność otrzymanych rezultatów obliczeń. Najlepszy z tego punktu widzenia jest wybór największego co do wartości bezwzględnej elementu macierzy A i takie przestawienie wierszy oraz kolumn w tej macierzy, aby maksymalny element był elementem cu. Spośród pozostałych elementów macierzy powtórnie wybieramy maksymalny co do wartości bezwzględnej element i tak zamieniamy wiersze oraz kolumny macierzy, by element ten zajął miejsce cM (oczywiście, nie „ruszamy” elementu cu). Kontynuując to postępowanie,otrzymamy na głównej przekątnej maksymalne elementy tej macierzy, które tworzą ciąg nierosnący.
Optymalny algorytm metody eliminacji Gaussa nie będzie tutaj przedstawiony. Jego opracowanie wymaga tylko rozbudowania wersji podstawowej o fragmenty, które zostały wyżej szczegółowo omówione. Metoda eliminacji z wyborem elementu dominującego jest jednym z podstawowych algorytmów w pakietach programów narzędziowych dotyczących metod numerycznych.
W grupie algorytmów dokładnych rozwiązywania liniowych układów równań dość popularne są tzw. metody dekompozycyjne [7], które - ogólnie rzecz biorąc — polegają na przedstawieniu macierzy A w postaci iloczynu dwóch innych macierzy. Najczęściej są to macierze trójkątne, np. dolna L (lower) i górna U (upper) - A=LU. Zadanie sprowadza się wówczas do rozwiązywania dwóch trójkątnych układów równań. Szczegóły dotyczące metod dekompozycyjnych i kilku innych metod dokładnych przedstawiono między innymi w [5, 7],
1.3. Metody iteracyjne [3, 5, 7, 9]
Proces iteracyjnego obliczania wartości X polega - ogólnie rzecz biorąc - na przyjęciu pewnej wartości początkowej X° (przybliżenie początkowe), a następnie wykonaniu określonych operacji arytmetycznych dających w wyniku wartość X1 (pierwsze przybliżenie), W drugim kroku zmienna X* przejmuje rolę przybliżenia zerowego i obliczamy X2, wykorzystując tę samą sekwencję działań arytmetycznych. Powyższą operację powtarzamy wielokrotnie. Jeżeli ciąg przybliżeń {X"} zmierza do X, to proces iteracyjny nazywa sit zbieżny i tylko wtedy metoda iteracji jest efektywna. Algorytmy iteracyjne są często stosowane jako sposób realizacji obliczeń numerycznych, przy czym ich popularność w praktyce inżynierskiej wiąże się ze stosunkowo łatwym dostępem do szybkołiczącycli komputerów o wystarczająco dużej pamięci operacyjnej.
Metody iteracyjnego rozwiązywania układów równań liniowych można stosować dla układów typu
|
xl |
W11 |
wl2 . |
■ wm |
*1 | ||||
|
*2 |
= |
W21 |
w22 . |
■ W2» |
• |
*2 |
*2 | |
|
Wnl |
wm ■ |
■ |
.*» . |
.Zn. |
lub w postaci macierzowej
X = W X + z .
Przejście od typowej dla układów równań postaci AX=B do postaci (1.54) nie jest trudne.
«r Przykład 1.11
Układ równań
2*i + *2 + *3 = 4
*! + X2 - *3 = 1 *1 + 2*2 +*3=4
sprowadzić do postaci (1.54).
Powyższe zadanie można wykonać natychmiastowo, obliczając z kolejnych równań niewiadome *i, *2, *3
*! = - 0,5*2 - 0,5*3 + ^
*2 = -*, + *3 + 1
*3 = -*, - 2*2 + 4 ,
czyli
|
*1 |
0 -0,5 -0,5 |
X1 |
' 2 | |||
|
*2 |
= |
-1 0 1 |
• |
X2 |
+ |
1 |
|
3. |
-1-2 0 |
X3 . |
4 |
Takie podejście może zakończyć się sukcesem jedynie przy obliczeniach wykonywanych ręcznie dla układów równań o małej liczbie niewiadomych, natomiast w realizacji
komputerowej stosuje się specjalny algorytm przekształcania układu AX=B do postaci (1.54).
W pierwszej kolejności macierz A rozkładamy na dwie macierze D i R, przy czym macierz D zawiera tylko główną przekątną macierzy A, natomiast macierz R pozostałe elementy
|
’ 2 |
1 |
1 |
' 2 |
0 |
0 |
0 |
1 |
1 | ||
|
1 |
1 |
-1 |
= |
0 |
1 |
0 |
+ |
1 |
0 |
-1 |
|
1 |
2 |
1 . |
0 |
0 |
1 |
1 |
2 |
0 |
Pierwsza z macierzy po prawej stronie to macierz D, a druga R. Na tym etapie realizacji obliczeń równanie A X=B sprowadziło się do postaci
D X + R X = B ,
skąd
D X = -R X + B .
Wyszukiwarka