Wskaźnik uwarunkowania

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

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

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ż

• Efekt motyla (fizyka)

Linki zewnętrzne

• Zagadnienie uwarunkowania macierzy na Holistic Numerical Methods Institute