Wskaźnik uwarunkowania

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Wskaźnik uwarunkowania określa w jakim stopniu błąd reprezentacji numerycznej danych wejściowych danego problemu wpływa na błąd wyniku. Wskaźnik uwarunkowania definiuje się jako maksymalny stosunek błędu względnego rozwiązania do błędu względnego danych. Problem o niskim wskaźniku uwarunkowania nazywamy dobrze uwarunkowanym zaś problemy o wysokim wskaźniku uwarunkowania – źle uwarunkowanymi. Zagadnienia o zbyt dużym wskaźniku uwarunkowania nie nadają się do numerycznego rozwiązywania ponieważ, już sam błąd wynikający z numerycznej reprezentacji liczb wprowadza nieproporcjonalnie duży błąd.

Wskaźnik uwarunkowania jest cechą problemu i jest niezależny od numerycznych właściwości konkretnych algorytmów. W odróżnieniu od błędu zaokrągleń wprowadzonego przez algorytm, wskaźnik uwarunkowania stanowi informację o błędzie przeniesionym z danych.

Wskaźnik uwarunkowania macierzy[edytuj | edytuj kod]

Wskaźnik uwarunkowania macierzy A w równaniu Ax = b jest charakterystyczną własnością macierzy informującą o tym jakie wzmocnienie będzie miała zmiana normy macierzy A na normę rozwiązania x.

Wskaźnik uwarunkowania macierzy definiuje się bardziej precyzyjnie jako maksymalny stosunek błędu względnego wektora rozwiązania x do błędu względego b

Załóżmy, że e jest błędem b. Stąd błąd w rozwiązaniu A^{-1} b wynosi A^{-1} e. Stąd stosunek relatywnego błędu rozwiązania do relatywnego błędu w b wynosi:


\frac{\Vert A^{-1} e\Vert / \Vert A^{-1} b\Vert}{\Vert e\Vert / \Vert b\Vert}.

Można to przekształcić do:

(\Vert A^{-1} e\Vert / \Vert e\Vert) \cdot (\Vert b\Vert / \Vert A^{-1} b\Vert).

Maksymalna wartość (dla niezerowych b i e) będzie iloczynem dwóch norm (definiowanych w różny sposób, np. często jako normę traktuje się maksymalną sumę warości bezwzględnych wierszy):

\kappa (A) = \Vert A^{-1}\Vert \cdot \Vert A\Vert.

Definicja ta jest taka sama dla każdej zwartej normy. Liczba ta pojawia się tak często w algebrze liniowej, że nadano jej nazwę wskaźnika uwarunkowania macierzy

Zastosowania[edytuj | edytuj kod]

Wskaźnik uwarunkowania macierzy pozwala na oszacowanie, z jaką (maksymalnie) dokładnością (do ilu miejsc po przecinku) możemy podać wynik. Dokładność jest zależna od iloczynu epsilonu maszynowego i wskaźnika uwarunkowania. Załóżmy dla przykładu, że mamy macierz \mathbf{A}:

\mathbf{A} = \begin{bmatrix}
1 & 2 \\
3 & 4  \end{bmatrix}


  \mathbf{A^{-1}} = \begin{bmatrix}
-2 & 1 \\
1.5 & -0.5  \end{bmatrix} .

Stosując tak zdefiniowaną normę: \|A\|= max_{1<i<n} \sum_{j=1}^n |a_{ij}| możemy obliczyć wskaźnik uwarunkowania \kappa (A) = \Vert A^{-1}\Vert \cdot \Vert A\Vert =21.

Załóżmy dodatkowo, że mamy do czynienia z maszyną, która przechowuje liczby rzeczywiste używając 24 bitowej mantysy, wtedy epsilon maszynowy wynosi \varepsilon_{masz} = 2^{1-24} = 0.119209\cdot 10^{-6}. Po pomnożeniu tych wartości możemy oszacować do ilu miejsc po przecinku otrzymany wynik będzie istotny na podstawie poniższej równości: 5 \cdot 10^{-m} = 0.25 \cdot 10^{-7}. Obliczając m, możemy wnioskować, że w tym przypadku dokładność wyniesie 6 miejsc po przecinku.
Jako inny przykład rozpatrzmy prosty układ równań typu \mathbf{A}\mathbf{x}=\mathbf{b}. Jeśli do naszych obliczeń wybierzemy macierz o wysokim wskaźniku uwarunkowania, np.:

\mathbf{A} = \begin{bmatrix}
1 & 2 \\
2 & 3.999  \end{bmatrix} ; \mathbf{b} = \begin{bmatrix} 4  \\ 7.999 \end{bmatrix}  ; cond(\mathbf{A})=35988,

to otrzymane rozwiązanie jest niestabilne. Oznacza to, że mała zmiana wartości współczynników może znacząco wpłynąć na wynik. W podanym wyżej przypadku rozwiązanie wynosi \mathbf{x} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}. Jeśli zmodyfikujemy następująco wektor \mathbf{b} = \begin{bmatrix} 4 \\ 8 \end{bmatrix}, to otrzymamy rozwiązanie \mathbf{x} = \begin{bmatrix} 4 \\ 0 \end{bmatrix}.
W przypadku macierzy dobrze uwarunkowanej np.:

\mathbf{A} = \begin{bmatrix}
1 & 2 \\
2 & 3  \end{bmatrix} ; \mathbf{b} = \begin{bmatrix} 4  \\ 7.999 \end{bmatrix}  ; cond(\mathbf{A}) = 25,

rozwiązanie wynosi \mathbf{x} = \begin{bmatrix} 3.998 \\ 0.001 \end{bmatrix}. Jeśli zmodyfikujemy następująco wektor \mathbf{b} = \begin{bmatrix} 4 \\8 \end{bmatrix}, to otrzymamy rozwiązanie \mathbf{x} = \begin{bmatrix} 4 \\ 0 \end{bmatrix}, które jest zbliżone do poprzedniego.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]