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 w odpowiedzi.

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ędnego $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 {\|A^{-1}e\|/\|A^{-1}b\|}{\|e\|/\|b\|}}.$

Można to przekształcić do:

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

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ę wartości bezwzględnych wierszy):

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

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)=\|A^{-1}\|\cdot \|A\|=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} )=35\ 988,$

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
• regularyzacja Tichonowa

Linki zewnętrzne

• Zagadnienie uwarunkowania macierzy na Holistic Numerical Methods Institute