.0.4/251
ODY ROZWIĄZYWANIA WirLKJCII UKŁADÓW LINIOWYCH...
osując eliminację Gaussa dochodzimy do następujących wzorów (szczególny —rpadck wzorów' z p. 6.6.2):
(10.116)
\>iV = fis I-1
i = 2, ..., xV—1, . «2 = btlci
= 2, ...» A/ > =/1/c1
.2 Tak więc algorytm ten składa się z dwfóch etapów. W pierwszym obliczamy współ
czynniki i w drugim zaś — rozwiązania y\. Należy wyjaśnić przy jakich założeniach o współczynnikach rozpatrywany układ jest nieosobliwy i kiedy algorytm ten jest numerycznie poprawmy. Warunki dostateczne są zawarte w następującym lemacie.
Lemat 10.10
Jeśli współczynniki Cj, cv, ó.-, i = 2. .... N— ł są różne od zera oraz
(10.117)
przy czym co najmniej w jednej z nierówności w (10.117) zachodzi ostra nierówność, to układ (10.115) ma jednoznaczne rozwiązanie i algorytm (10.116) jest
numerycznie poprawny.
Dowód tezy pierwszej można znaleźć np. w książce [95], drugiej zaś — v-’ artykule [48].
Analizując algorytm (10.116) widzimy, że koszt jego wynosi rzędu A działań arytmetycznych i wymaga tyle samo miejsc pamięci. Co do rzędu liczby działań * obciążenia pamięci algorytm ten jest optymalny (por. p. 1.?). Przedstawiony algorytm jest szczególnym przypadkiem algorytmu dla macierzy wstęgowej opisanego w artykule w [126]. Tam też podane są procedury rozwiązywania takich układów.
amy teraz szybki algorytm rozwiązywania zadań różnicowych aproksymują-t równanie Poissona w prostokącie z warunkami Dirichlcta (dla ustalenia gi będziemy zakładać, że są one jednorodne). Algorytm ter. jest połączeniem rytmów' rozwiązywania układów z macierzą irójdiagonaimi (zob. p. 10.4.2) bkich przekształceń Fouriera (FFT). (zob. p. 2.6.2).