254 (51)

METODY NUMERYCZNE...

każdego ustalonego i, i — 1. ...,JV — 1, wynosi rzędu M \og_zM działań (przyjmujemy, że M - 2", /j-naturalne). Stąd całkowity koszt wyznaczenia rozwiązania zadania (10.118) przedstawionym algorytmem jest rzędu NM log₂A/ działań (przy N = M mamy 4A4'²log₂Af). Koszt ten jest bliski optymalnemu, bowiem zadanie zawiera (A— 1) (M — 1) niewiadomych. Wymagana pamięć jest rzędu liczby niewiadomych.

Algorytm ten jest numerycznie poprawny (por. z artykułem [73]).

Przedstawiony algorytm może być stosowany do rozwiązywania pewnych zadań ogólniejszych niż (10.118), np. równania Helmholtza o stałych współczynnikach. pewnych zagadnień o zmiennych współczynnikach itd. Wykorzystanie algorytmu FFT do zadań powstałych w metodzie siatek omówione jest dość obszernie w książce [95], którą polecamy Czytelnikom.

Zakres stosowalności przedstawionego algorytmu w metodach elementu skończonego jest ograniczony do pewnych szczególnych wariantów tej metody (por. z poz. [2]).

Dodajmy na zakończenie, że obecnie znamy kilka algorytmów rozwiązywania zadania (10.118) kosztem takim samym jak powyższy a nawet trochę mniejszym (różnica w stałych). Należy tu wymienić przede wszystkim tzw. algorytm cyklicznej redukcji i algorytmy powstałe z połączenia tego algorytmu z FFT (por. z poz. [71] i [109]). Algorytm optymalny co do kosztu, ale logicznie złożony przedstawiony jest w pracy [3]).

Algorytm z macierzą pojemnościową    10.

W tym punkcie zajmiemy się algorytmem rozwiązywania zadań w pewnych obszarachnieprostokątnych. Algorytm ten będzie bazowa! na algorytmie zp. 10.4.3. Przedstawimy go najpierw dla dowolnego układu

Ay= b    (10.121)

z macierzą nieosobliwą -4 wymiaru m x m.

Niech K będzie zbiorem w początkowych, liczb naturalnych. S zaś - jego p--cleinentowym podzbiorem, S <= K = (1, 2, ..., m}. Niech B oznacza macierz nieosobliwą również wymiaru m x n>, różniącą się od macierz)' A o p wierszy, tj.

j-ty wiersz A jest równy j-temu wierszowi ił dla je (AT\5)

Rozwiązania układu (10.121) poszukujemy w postaci

y = >+ X ^x>9' • ^<xi^ęR>

IcS

gdzie y jest rozwiązaniem układu By = b

Wektor b ma współrzędne b_} równe bj dla je (JC\&), zaś dla j e S mogą one być dowolno, np. równe zeru. Pozostaje określić zależności, z których wyznaczymy