1. Uwarunkowanie zadania a stabilność algorytmu numerycznego.

Uwarunkowanie zadania 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 numerycznego

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.

Diagonalna macierz główna

Trójkątna górna macierz główna - metoda postępowania odwrotnego

Z ostatniego równania wyznaczamy x_n, następnie z przedostatniego x_n-1 ...

Trójkątna dolna macierz główna - metoda postępowania w przód

Z ostatniego równania wyznaczamy x_n, następnie z przedostatniego x_n-1 ...

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⁽²⁾x =b⁽²⁾. Wyeliminowaliśmy w ten sposób współczynniki leżące poniżej diagonali dla pierwszej niewiadomej x₁. Podobnie eliminujemy współczynniki

dla x₂, . . . , x_n-1.

2. Etap postępowania odwrotnego polega na zastosowaniu metody specyficznej dla trójkątnej macierzy głównej.

Całkowity koszt obliczeniowy:

• 1/3 n³ + n² - 1/3 n mnożeń,

• 1/3 n³ + 1/2 n² - 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 n² + n,

• w przeciwnym wypadku 2n² + 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:

Ax = b, LUx = b

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 = L_IU = L_IDU_I .

Jeśli zaś macierz A jest macierzą symetryczną, to

L_IDU_I = A = A^T= L^T_IDU^T_I; U_I = L^T_I

Zatem dla macierzy symetrycznej istnieje jednoznaczny rozkład A = L_IDL^T_I

Poprzez podstawienia układ równań Ax = b ≡ L_IDL^T_I x = b zastępujemy sekwencją trzech równań: L_Iz= b; Dy= z; L^T_Ix= y.

Całkowity koszt obliczeniowy (ok. 2 razy mniejszy niz. w eliminacji Gaussa):

• 1/6 n³ + n² - 7/6 n (+n²) mnożeń,

• 1/6 n³ - 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.*

Metoda Jacobiego

W_J= 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

Metoda Gaussa-Seidla

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 A₁ = A,A₂, . . . ,A_r

A_k+1 = (T^k_pq)^TA^kT^k_pq

• T^k_pq : a^k_pq = max_l≠m a^k_lm

• θ : a^k+1_pq = 0, tj.

a'_pq =1/2(a_pp-a_qq)sin2θ+a_pq cos 2θ = 0

skąd

13. Przykładowa metoda iteracyjna wyznaczania wartości własnych.*

Przyjmujemy przybliżenie pewnego wektora V⁰ ≠ 0. Wektor ten traktujemy jako kombinacje liniową niezależnych wektorów własnych.

V⁰ = c₁x₁ + c₂x₂ + . . . + c_nx_n

Jeżeli wektory x_i stanowią bazę liniowo niezależnych wektorów w R_n, to każdy wektor z tej przestrzeni jest kombinacją liniową wektorów bazowych.

AV⁰ = c₁Ax₁ + c₂Ax₂ + . . . + c_nAx_n

Ax_i = λ_ix_i; i = 1, . . . , n

---