.0.4/251

(10.116)

i = 2, ..., xV—1, . «₂ = b_tlci

= 2, ...» A/ >    =/₁/c₁

.2 Tak więc algorytm ten składa się z dw^fó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, c_v, ó.-, 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.

orytm korzystający z FFT    10.4.3

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).