258 (48)

METODY NUMERYCZNE... io./25S

W pierwszym etapie wyznaczamy wartości funkcji gf' ale tylko w punktach sąsiednich punktów' P„. Są one potrzebne do obliczenia współczynników macierzy C. Wartości te możemy wyznaczyć algorytmem z p. 10.4.3 kosztem rzędu ;VA/’ log₂A/ działań. Obliczenie macierzy C (drugi etap) wymaga rzędu M~ działań, koszt rozwiązania układu z tą macierzą wyniosi zaś A/³ działań (algorytmem eliminacji Gaussa). Etap trzeci i piąty' wymagają rzędu MN log₂Af działań. Koszt całkowity jest więc rzędu {MN log,A/ + A/²) M działań arytmetycznych.

Widać zatem, że przedstawiony algorytm opłaca się stosować w przypadku gdy M jest dużo mniejsze od N, np. wówczas, gdy obszar typu L dzieli się na prostokąty o bokach istotnie różnej długości. Tanio rozwiązuje się tym algorytmem również zadania rozpatrywane w' obszarach takich jak na rys. 10.21.

W przedstawionym algorytmie układ z macierzą C często rozwiązujemy metodami iteracyjnymi. Pozwala to nieraz istotnie zmniejszyć koszt realizacji algorytmu i liczbę potrzebnych miejsc pamięci maszyny. Na przykład w wyżej rozpatrywanym algorytmie można zredukować liczbę działań i obciążenia pamięci do rzędu MN log_z\f (macierz C jest symetryczna i dodatnio określona). Czytelników zainteresowanych tą tematyką odsyłamy do prac [13], [87], 199]. W pracy [86] jest zawarta implementacja metody.

Algorytm Georgea    10.4.5

Algorytmy przedstawione w' poprzednich punktach zależały istotnie od postaci zadania oraz od kształtu obszaru, w którym to zadanie jest rozpatrywane. W tym punkcie zajmiemy się algorytmem niezależnym od tych własności zadania. Jest nim algorytm George'a (ang. nested dissection, [35]). Stosujemy go do rozwiązywania układów z macierzą symetryczną i dodatnio określoną otrzymywanych w metodach siatek i pewnych wariantach MES. Aigortm ten jest modyfikacją algorytmu ChoIesky’cgo-Banachicwic/.a. Polega on na takim uporządkowaniu niewiadomych (permutacje macierzy rozrzedzonej A = PAP¹), aby w rozkładzie PAP¹ - LDlJ zminimalizować liczbę niezerowych elementów macierzy L.

Algorytm George’a przedstawimy na przykładzie układu równań, który powstaje przy rozwiązywaniu zadania modelowego MES z aproksymacją dwu-liniową na elementach prostokątnych (zob. p. 10.3.4).

Zadanie wyjściowe w sformułowaniu wariacyjnym ma postać:

wyznaczyć u e H:_} (Q). takie że

a (u, v) s I Vu Vixl£2 = / (c) = J /ud £2 , ve H^l0(Cl)    (10.126)

ó    ó

Dla uproszczenia rozważań przyjmujemy, że Q jest prostokątem, £2 = (0, /,)x x(0, U).

Obszar £2 dzielimy na prostokąty e._} siatką O*:

C2_fc = {x = (i/t_Ł, jit₂) , l — 0,...» m_Ł + l; j =* 0. i, ...» m₂ — 1;

(ffl,rl) h_% ~    , -s = 1,2}