Jakie są objawy złego warunkowania przy stosowaniu metod bezpośrednich?

Załóżmy, że mamy system liniowy i nie wiemy nic o jego warunkowaniu i nie mamy wstępnych informacji o rozwiązaniu. Ślepo stosujemy eliminację Gaussa i uzyskujemy rozwiązanie $x$ . Czy można ustalić, czy to rozwiązanie jest godne zaufania (tj. Czy system jest dobrze uwarunkowany) bez dokładnej wstępnej analizy matrycy ? Czy wielkość czopów dostarcza wiarygodnych informacji?

I ogólnie, jakie są główne wytyczne dotyczące wykrywania złych warunków „w locie”?

linear-solver condition-number conditioning

— faleichik
źródło

Odpowiedzi:

Kiedy matryca jest źle uwarunkowana ? Zależy to od dokładności poszukiwanego rozwiązania, tak samo jak „piękno jest w oku patrzącego” ...

Czy twoje pytanie powinno być lepiej sformułowane, ponieważ istnieją tanie i solidne estymatory liczbowe stanu oparte na faktoryzacji ? $LU$

Zakładając, że interesuje Cię prawdziwy ogólny (gęsty, niesymetryczny) problem arytmetyki podwójnej precyzji, sugerowałbym skorzystanie z solvera eksperckiego LAPACK DGESVX, który zapewnia oszacowanie warunków w postaci jego wzajemności, . Jako bonus masz również inne zalety, takie jak wyrównywanie / równoważenie równań, iteracyjne udoskonalanie, granice błędów do przodu i do tyłu. Nawiasem mówiąc, patologiczne złe warunkowanie ( ) jest sygnalizowane jako błąd przez . $\text{RCOND}\approx 1/\kappa(A)$ $\kappa(A) > 1/\epsilon$ INFO>0

Mówiąc bardziej szczegółowo, LAPACK szacuje liczbę warunków w 1-normie (lub normie, jeśli rozwiązujesz ) za pomocą DGECON . Podstawowy algorytm opisano w trawniku 36: „Solidne rozwiązania trójkątne do zastosowania w ocenie stanu” . $\infty$ $A^T x = b$

Muszę wyznać, że nie jestem ekspertem w tej dziedzinie, ale moja filozofia jest następująca: „jeśli wystarczy dla LAPACK, to dla mnie”.

— Stefano M.
źródło

Rozwiązanie źle uwarunkowanego układu równań z macierzą normy 1 losowa prawa strona normy 1 będzie z dużym prawdopodobieństwem normą rzędu liczby warunków. W ten sposób obliczenie kilku takich rozwiązań powie ci, co się dzieje.

— Arnold Neumaier
źródło

To właśnie robi DGECON, z dodatkową finezją iteracyjnego udoskonalania kierunku wyszukiwania w celu zmaksymalizowania wyniku oraz za pomocą niestandardowego trójkątnego solvera (nie BLAS), aby nie wypaczać rzeczy przez błędy aproksymacji. Koszt obliczeniowy DGECON jest zatem porównywalny z twoim prostym testem. +1 za zapamiętanie prostego znaczenia norm macierzowych i liczby warunków. Ciekawe powinno być sprawdzenie, czy DGECON jest naprawdę bardziej odporny na proste losowe sprawdzanie.

— Stefano M

Biorąc pod uwagę, że liczba warunków rozwiązania

pokrywa się z liczbą warunków obliczenia

czy wystarczy pomnożyć skalowaną macierz przez te losowe wektory zamiast rzeczywistego rozwiązania

A x = b

$Ax=b$

A x

$Ax$

A x = b

$Ax=b$

— faleichik

@faleichik Na pewno nie: sztuczka polega na takim skalowaniu

, aby

. Oczywiście, będąc algebrą liniową, nie musisz tak naprawdę skalować

ale tylko

... jednak musisz najpierw obliczyć

. Twój odwrotny argument musiałby najpierw obliczyć

A

$A$

‖ A ‖ = 1

$\| A \| = 1$

κ (A) = ‖ A ‖ \cdot ‖ A^{- 1} ‖ = ‖ A^{- 1} ‖

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

A

$A$

A x

$Ax$

‖ A ‖

$\| A \|$

‖ A^{- 1} ‖

$\| A^{-1} \|$ co staramy się ocenić.

— Stefano M

Jest prawie niemożliwe, aby stwierdzić, czy twój system jest źle uwarunkowany na podstawie tylko jednego wyniku. O ile nie masz pewności co do zachowania twojego systemu (tj. Wiesz, jakie powinno być rozwiązanie), niewiele możesz powiedzieć z jednego rozwiązania.

Mimo to, można uzyskać więcej informacji, jeśli rozwiązać więcej niż jeden system z tego samego . Załóżmy, że masz system w postaci . Dla konkretnego A, którego nie masz wcześniejszej wiedzy na temat jego warunkowania, możesz wykonać następujący test: $A$ $Ax=b$

Rozwiąż dla określonego wektora prawej strony . $Ax=b$ $b$
Przesuń wektor prawej strony o gdzie jest bardzo mały w porównaniu do . $b_{new}=b+\mathbf{\varepsilon}$ $||\mathbf{\epsilon}||$ $||b||$
Rozwiąż . $Ax_{new}=b_{new}$
Jeśli twój system jest dobrze uwarunkowany, nowe rozwiązanie powinno być dość zbliżone do starego (tj. powinno być małe). Jeśli zaobserwujesz dramatyczną zmianę w nowym rozwiązaniu (tj. jest duży), oznacza to, że twój system jest prawdopodobnie źle uwarunkowany. $||x-x_{new}||$ $||x-x_{new}||$

Konieczne może być rozwiązanie kilku układów liniowych za pomocą różnych wektorów po prawej stronie, aby lepiej określić, czy układ jest źle uwarunkowany. Oczywiście proces ten jest nieco kosztowny ( operacji dla pierwszego rozwiązania i operacji dla każdego kolejnego rozwiązania, przy założeniu, że Twój bezpośredni solver zapisuje jego czynniki). Jeśli matryca A jest dość mała, nie stanowi to problemu. Jeśli jest duży, możesz tego nie chcieć. Zamiast tego lepiej jest obliczyć numer warunku $\Theta(n^3)$ $\Theta(n^2)$ w dogodnej normie. $||A||\cdot||A^{-1}||$

— Paweł
źródło

Θ (k n^{3})

$\Theta(kn^3)$

A

$A$

A

$A$

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

@JackPoulson: Masz absolutną rację ... Wydaje mi się, że całkowicie się od tego rozdzieliłem. Bez obaw :) Zaktualizuję moją odpowiedź

— Paweł

| | A x - b | |

$||Ax - b ||$ scales as

| | A | | \cdot | | x | |

$||A||\cdot||x||$ a nearly singular

A

$A$ might give a meaningful residual even if its solution is very bad.

— Reid.Atcheson

@Reid.Atcheson: Not really. The approximate solution to an ill conditioned system can still produce a small residual. This does not really doesn't give you any indication as to how far away it is from the true solution.

— Paul

May be it is more wise to explicitly state

‖ ε ‖

$\|\varepsilon\|$ very small with respect to

‖ b ‖

$\|b\|$ . Everything is relative in this area... Most readers will know, but someone could be mislead in dangerous waters.

— Stefano M