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