w11, pk niestac 2st IIsem, MZT, wykłady
[ Pobierz całość w formacie PDF ]
Rozwi ą zanie układów równa ń liniowych algebraicznych z macierzami rzadkimi symetrycznymi metodami iteracyjnymi Û Metody iteracyjne doprowadzaj ą do rozwi ą zania przybli ż onego z podan ą dokładno ś ci ą za pewn ą ilo ść iteracji – ilo ść operacji nie pozostaje przewidywan ą z góry. Û Główn ą cech ą metod iteracyjnych jest zbie ż no ść . Je ś li dla zagadnienia podanego proces iteracyjny si ę zbiega za nie wielk ą ilo ść iteracji (zwykłe ilo ść iteracji odnosz ą do rozmiary zadania), mówimy ż e zbie ż no ść jest szybk ą . W przeciwnym przypadku – woln ą . Cz ę sto wyst ę puje sytuacje, gdy w ogóle nie da si ę osi ą gn ąć podanej dokładno ś ci rozwi ą zania – mówimy o braku zbie ż no ś ci. Obliczenia wysokiej wydajności w11 1 Û Porównywanie metod iteracyjnych i bezpo ś rednich Obliczenia wysokiej wydajności w11 2 Û Oszacowanie ilo ś ci operacji zmiennoprzecinkowych dla metod bezpo ś rednich w najlepszym przypadku wynosi C N 2 , gdzie N – ilo ść równa ń , C – stała, która zale ż y głównie od tego, o ile renumerator jest w stanie zmniejszy ć ilo ść zapełnie ń . Û Oszacowanie ilo ś ci operacji zmiennoprzecinkowych dla metod iteracyjnych wynosi rz ę du C 1 N, gdzie C 1 zale ż y od zdolno ś ci prekonditioningu polepszy ć uwarunkowanie układu równa ń . Prekonditioning – to specjalnie skonstruowany operator, przeznaczony do przyspieszenia zbie ż no ś ci. Û Z tego wynika, ż e dla ka ż dego problemu istnieje taki rozmiar zadania N i Û Z tego wynika, ż e dla ka ż dego problemu istnieje taki rozmiar zadania N A i taki punkt A, zaczynaj ą c od którego przy zwi ę kszeni N iteracyjna metoda staje skuteczn ą od bezpo ś redniej (je ś li bardziej ta metoda iteracyjna demonstruje stabiln ą zbie ż no ść dla podanej klasy zagadnie ń ). Obliczenia wysokiej wydajności w11 3 Zalety (+) i wady (-) metod bezpoŚrednich i iteracyjnych Cech ę Bezpo ś rednia Iteracyjna Czujno ść do złego uwarunkowania Nie wielka + Wielka - Zale ż no ść czasu rozwi ą zania od ilo ś ci Nie wielka + Quasiliniowa rozwi ą zania od ilo ś ci prawych stron - Zdolno ść do wykrycia niestabilno ś ci geometrycznej + - Zale ż no ść czasu rozwi ą zywania od rozmiaru zagadnienia Kwadratowa Quasiliniowa - + Obliczenia wysokiej wydajności w11 4 Û Iteracyjne metody maj ą tylko jedn ą zalet ę w porównywaniu do metod bezpo ś rednich – quasiliniowy wzrost ilo ś ci operacji zmiennoprzecinkowych przy wzro ś cie rozmiaru zagadnienia. I to jest główn ą przyczyn ą , ż e tyle uwagi pozostaje przydzielono rozwini ę ciu metod iteracyjnych. Û Zbie ż no ść metod iteracyjnych zale ż y od współczynnika uwarunkowania macierzy układu równa ń . To jest najwa ż niejsza charakterystyka macierzy. Normy wektora i normy macierzy Û Istniej ą ró ż ne normy wektora i normy macierzy symetrycznej rzeczywistej, Û Istniej ą ró ż ne normy wektora i normy macierzy symetrycznej rzeczywistej, przecie ż nas b ę dzie interesowała norma 2: A ³ 0 and A = 0 A = 0 c × A = c × A A = max L = R ( A ) T x = x x i 2 i A + B £ A + B 2 Av = L × v A × B £ A × B i i i Û Rozwa ż amy macierzy rzeczywiste symetryczne. Normu 2 macierzy nazywaj ą jeszcze norm ą spektraln ą – jest zwi ą zana ta norma z najwi ę ksz ą warto ś ci ą własn ą . Obliczenia wysokiej wydajności w11 5 [ Pobierz całość w formacie PDF ] |