Wskaźnik uwarunkowania

Ten artykuł od 2023-06 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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.

Zasugerowano, aby ta sekcja została przeniesiona do artykułu Wskaźnik uwarunkowania macierzy. (dyskusja)

Wskaźnik uwarunkowania macierzy ${\displaystyle A}$ w równaniu ${\displaystyle 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 ${\displaystyle x}$ do błędu względnego ${\displaystyle b.}$

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

${\displaystyle {\frac {\|A^{-1}e\|/\|A^{-1}b\|}{\|e\|/\|b\|}}.}$

Można to przekształcić do:

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

Maksymalna wartość (dla niezerowych ${\displaystyle b}$ i ${\displaystyle 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):

${\displaystyle \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.

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 ${\displaystyle \mathbf {A} {:}}$

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

${\displaystyle \mathbf {A^{-1}} ={\begin{bmatrix}-2&1\\1{,}5&-0{,}5\end{bmatrix}}.}$

Stosując tak zdefiniowaną normę: ${\displaystyle \|A\|=max_{1<i<n}\sum _{j=1}^{n}|a_{ij}|}$ możemy obliczyć wskaźnik uwarunkowania ${\displaystyle \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 ${\displaystyle \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:

${\displaystyle 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 ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} .}$ Jeśli do naszych obliczeń wybierzemy macierz o wysokim wskaźniku uwarunkowania, np.:

${\displaystyle \mathbf {A} ={\begin{bmatrix}1&2\\2&3{,}999\end{bmatrix}};\mathbf {b} ={\begin{bmatrix}4\\7{,}999\end{bmatrix}};}$ ${\displaystyle 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 ${\displaystyle \mathbf {x} ={\begin{bmatrix}2\\1\end{bmatrix}}.}$ Jeśli zmodyfikujemy następująco wektor ${\displaystyle \mathbf {b} ={\begin{bmatrix}4\\8\end{bmatrix}},}$ to otrzymamy rozwiązanie ${\displaystyle \mathbf {x} ={\begin{bmatrix}4\\0\end{bmatrix}}.}$

W przypadku macierzy dobrze uwarunkowanej np.:

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

rozwiązanie wynosi ${\displaystyle \mathbf {x} ={\begin{bmatrix}3{,}998\\0{,}001\end{bmatrix}}.}$

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

• efekt motyla
• regularyzacja Tichonowa

• Zagadnienie uwarunkowania macierzy na Holistic Numerical Methods Institute