1. Uwarunkowanie zadania a stabilność algorytmu numerycznego.
Własność samego zadania w oderwaniu od metody określająca jaki wpływ na wynik mają odchylenia (zaburzenia) danych wejściowych.
Dane rozwiązanie układu równań liniowych w postaci macierzowej x =
A-1b, gdzie
Jeżeli do macierzy A dodamy pewną macierz zaburzeń
rozwiązanie układu w postaci x = (A+ E)-1 b jest wektorem.
Można łatwo sprawdzić, że dla dowolnej macierzy trójkątnej zadanie odwracania macierzy jest dobrze uwarunkowane numerycznie.
Stabilność algorytmu jest własnością metody rozwiązywania problemu określa, czy błędy reprezentacji mają skłonność do kumulowania się. Mówimy, że algorytm jest niestabilny.
Następujący algorytm
x = (y/b + z/b) b2, b 6= 0,
jest niestabilny numerycznie, podczas gdy poprawiony algorytm
x = (y + z) b, b 6= 0,
jest stabilnym algorytmem nawet dla wartości b bliskich zeru.
2. Sprowadzanie wyznacznika do postaci trójkątnej.
Wyznacznik nie zmienia swojej wartości, jeżeli elementy wiersza (albo kolumny) pomnożymy przez dowolną liczbę i dodamy do elementów innego wiersza (albo konsekwentnie kolumny).
Stąd:
1. wyznacznik o zerowym wierszu lub kolumnie ma wartość 0,
2. wyznacznik o dwóch identycznych wierszach lub kolumnach ma wartość 0,
3. wyznacznik o dwóch wierszach (lub kolumnach) proporcjonalnych ma wartość 0.
Wyznacznik, który pod swoją główną przekątna (diagonalną) ma wartości zerowe jest wyznacznikiem trójkątnym górnym. Rozwiniecie takiego wyznacznika względem ostatniego wiersza dowodzi, że
3. Odwracanie macierzy.
A|I ˜ A1|B1 ˜ A2|B2 ˜ . . . ˜ I|A-1
Operacje elementarne muszą być dokonywane konsekwentnie tylko na wierszach złączonych macierzy albo tylko na kolumnach.
4. Rozwiązywanie układów równań liniowych dla diagonalnej i trójkątnej macierzy głównej.
Trójkątna górna macierz główna - metoda postępowania odwrotnego
Z ostatniego równania wyznaczamy xn, następnie z przedostatniego xn-1 ...
Trójkątna dolna macierz główna - metoda postępowania w przód
5. Metoda eliminacji Gaussa.
Macierz główna musi być tylko nieosobliwą.
1. Etap eliminacji zmiennych
Odejmujemy od i-tego równania (wiersza macierzy dołączonej) (i = 2, 3, . . . , n) pierwszy wiersz pomnożony przez a otrzymujemy układ postaci A(2)x =b(2). Wyeliminowaliśmy w ten sposób współczynniki leżące poniżej diagonali dla pierwszej niewiadomej x1. Podobnie eliminujemy współczynniki
dla x2, . . . , xn-1.
2. Etap postępowania odwrotnego polega na zastosowaniu metody specyficznej dla trójkątnej macierzy głównej.
Całkowity koszt obliczeniowy:
• 1/3 n3 + n2 – 1/3 n mnożeń,
• 1/3 n3 + 1/2 n2 – 5/6 n sumowań.
Wymagania pamięciowe:
• jeśli nie zachowujemy pierwotnych postaci macierzy A i wektora b, to wymagana liczba komórek pamięci wynosi n2 + n,
• w przeciwnym wypadku 2n2 + 2n.
6. Metoda dekomozycji Crouta.*
Polegają na przedstawieniu macierzy głównej w postaci iloczynu macierzy trójkątnych, np. dolnej i górnej:
Teoria: (o rozkładzie) Każdą macierz nieosobliwą A o niezerowych elementach diagonali można przedstawić w postaci iloczynu macierzy trójkątnej dolnej z niezerowymi elementami na diagonali i macierzy trójkątnej górnej z jedynkami na diagonali.
A = LU.
Zadanie rozwiązania układu równań sprowadza się wówczas do rozwiązywania układu:
a po podstawieniu do sekwencyjnego rozwiązania dwóch trójkątnych układów równań
Ly = b, Ux = y,
przy czym dla układu z trójkątna dolną macierzą główną stosujemy metodę postępowania w przód, natomiast dla układu z macierzą trójkątną górną stosujemy metodę postępowania wstecznego. Metodę dekompozycji macierzy głównej można używać do równoczesnego rozwiązywania kilku układów o tej samej macierzy głównej identycznie jak w metodzie eliminacji Gaussa.
7. Metody dedykowane dla układów z macierzą symetryczną.*
Jeżeli po dekompozycji macierzy A macierz trójkątna dolna posiada jedynki na diagonali, to
A = LIU = LIDUI .
Jeśli zaś macierz A jest macierzą symetryczną, to
LIDUI = A = AT= LTIDUTI; UI = LTI
Zatem dla macierzy symetrycznej istnieje jednoznaczny rozkład A = LIDLTI
Poprzez podstawienia układ równań Ax = b ≡ LIDLTI x = b zastępujemy sekwencją trzech równań: LIz= b; Dy= z; LTIx= y.
Całkowity koszt obliczeniowy (ok. 2 razy mniejszy niz. w eliminacji Gaussa):
• 1/6 n3 + n2 – 7/6 n (+n2) mnożeń,
• 1/6 n3 – 1/6 n (+n2 – n) sumowań.
8. Wskaźnik uwarunkowania macierzy.
Dla danego układu równań liniowych: Ax = b, zakłócamy wektor wyrazów wolnych b i badamy zakłócenie wektora x, itd....
W ogólności dodając zaburzenia do macierzy i wektora wyrazów wolnych uzyskamy zaburzony wektor rozwiązania (A + δA) (x+δx) = b + δb.
• δA = 0 i δb 6≠0
A(x + δx) = b + δb; δx = A-1δb
δx zależy nie tylko od wielkości zaburzenia δb ale również od uwarunkowania zadania. Możemy bowiem zapisać
||δx||p ≤||A-1||qp ||δk||q
(ponieważ ||AB||pq ≤||A||rq ||B||pr).
||A-1||qp - miara wpływu zaburzenia wektora wyrazów wolnych na wektor rozwiązania
k wymaga znajomości dokładnej wartości rozwiązania układu x. Podczas gdy K jest wskaźnikiem uwarunkowania układu równań Ax = b niezależnym od x oraz b.
9. Iteracyjne poprawianie rozwiązania.*
Następująca metoda powoduje zmniejszanie błędu rozwiązania, przy obranej mierze ||r(t)||∞=||b-Ax(t)||∞
10. Iteracja Gaussa-Siedla i Jacobiego.*
WJ= U+ L
x(k+1) = Ux(k) + Lx(k)+z, k = 1, . . .
*Metoda automatycznego przestawiania wierszy macierzy A:
1. spośród kolumn, w których na diagonali znajduje się element zerowy, wybieramy tę, w której jest największa liczba zer
2. w kolumnie tej wybieramy element o maksymalnym module i tak przestawiamy wiersze, by wybrany element znalazł się na diagonali; wiersz ten ustalamy i pomijamy go w dalszym badaniu wartości elementów
3. spośród pozostałych kolumn, w których na diagonali znajduje się element zerowy, wybieramy tę, w której jest największa liczba zer...
4. dokonując kolejnych przestawień wierszy doprowadzamy ostatecznie wyjściową macierz do takiej postaci macierzy w której na diagonali są elementy niezerowe
W= U+ L
x(k+1) = Ux(k) + Lx(k+1)+z, k = 1, . . .
*Aby móc stosować metodę Gaussa-Seidla, należy przyjąć taką kolejność równań Ax = b, by elementy na diagonali były niezerowe.
11. Metoda Kryłowa wyznaczania wartości własnych i jej wady dla zastosowań numerycznych.
det (A-λI) = 0
Wartości własne są zależne od współczynników wielomianu charakterystycznego W(x) w większym stopniu, niż od elementów macierzy A.
12. Metoda Jacobiego z naciskiem na wyznaczanie wartości własnych.
Budowanie ciągu macierzy podobnych A1 = A,A2, . . . ,Ar
Ak+1 = (Tkpq)TAkTkpq
• Tkpq : akpq = maxl≠m aklm
• θ : ak+1pq = 0, tj.
a’pq =1/2(app-aqq)sin2θ+apq cos 2θ = 0
skąd
13. Przykładowa metoda iteracyjna wyznaczania wartości własnych.*
Przyjmujemy przybliżenie pewnego wektora V0 ≠ 0. Wektor ten traktujemy jako kombinacje liniową niezależnych wektorów własnych.
V0 = c1x1 + c2x2 + . . . + cnxn
Jeżeli wektory xi stanowią bazę liniowo niezależnych wektorów w Rn, to każdy wektor z tej przestrzeni jest kombinacją liniową wektorów bazowych.
AV0 = c1Ax1 + c2Ax2 + . . . + cnAxn
Axi = λixi; i = 1, . . . , n
pio1281trek