Zgodnie z odpowiedzią tutaj duża liczba warunków (dla liniowego rozwiązywania układu) zmniejsza gwarantowaną liczbę poprawnych cyfr w rozwiązaniu zmiennoprzecinkowym. Matryce różnicowania wyższego rzędu w metodach pseudospektralnych są zazwyczaj bardzo źle uwarunkowane. Dlaczego zatem wciąż są to bardzo dokładne metody?
Rozumiem, że niska precyzja pochodząca ze źle uwarunkowanych matryc jest jedynie wartością gwarantowaną , ale wciąż zastanawiam się, dlaczego źle uwarunkowane matryce są dokładnie rozwiązywane metodami bezpośrednimi w praktyce - np. LCOL
Kolumny tabeli 3.1 na stronie 11 Wang i wsp., DOBRZE STANOWANA METODA KOLOKACJI Z WYKORZYSTANIEM MATERIAŁU INTEGRACJI PSEUDOSPEKTRALNEJ , SIAM J. Sci. Comput., 36 (3) .
spectral-method
precision
condition-number
Zoltán Csáti
źródło
źródło
Odpowiedzi:
Dodano po mojej pierwszej odpowiedzi:
Wydaje mi się teraz, że autor cytowanej pracy podaje numery warunków (pozornie 2-normowe numery warunków, ale być może numery warunków nieskończoności) w tabeli, jednocześnie podając maksymalne błędy bezwzględne zamiast normalnych błędów względnych lub maksymalnych błędów względnych elementarnych ( są to różne miary.) Zauważ, że maksymalny błąd względny elementu nie jest tym samym, co błąd względny normy nieskończoności. Ponadto błędy w tabeli odnoszą się raczej do dokładnego rozwiązania pierwotnego problemu wartości granicy równania różniczkowego, a nie dyskretnego liniowego układu równań. Tak więc informacje zawarte w artykule naprawdę nie są odpowiednie do użycia z błędem związanym z numerem warunku.
Jednak w mojej replikacji obliczeń widzę sytuacje, w których błąd względnej normy nieskończoności (lub błąd względny dwu-normalny) jest znacznie mniejszy niż wartość graniczna ustawiona przez numer warunku nieskończoności (odpowiednio numer warunku 2-normowego). Czasami po prostu masz szczęście.
Użyłem pakietu DMSUITE MATLAB i rozwiązałem przykładowy problem z tego artykułu, stosując metodę pseudospektralną z wielomianami Czebyszewa. Moje liczby warunków i maksymalne błędy bezwzględne były podobne do podanych w pracy.
Widziałem także błędy względne normy, które były nieco lepsze niż można by się spodziewać na podstawie liczby warunków. Na przykład na przykładowym problemie z , używając , otrzymujęN = 1024ϵ=0.01 N=1024
cond (A, 2) = 7,9e + 8
cond (A, inf) = 7,8e + 8
norma (u-uexact, 2) / norma (uexact, 2) = 3,1e-12
norm (u-uact, inf) / norma (uexact, inf) = 2,7e-12
Wydaje się, że rozwiązanie jest dobre na około 11-12 cyfr, a numer warunku jest rzędu 1e8.
Jednak sytuacja z błędami elementarnymi jest bardziej interesująca.
max (abs (u-uact)) = 2,7e-12
To nadal wygląda dobrze.
max (abs ((u-uact) ./ uexact) = 6,1e + 9
Wow - w co najmniej jednym elemencie rozwiązania występuje bardzo duży błąd względny.
Co się stało? Dokładne rozwiązanie tego równania ma małe elementy (np. 1,9e-22), podczas gdy przybliżone rozwiązanie osiąga znacznie większą wartość 9e-14. Jest to ukryte przez pomiar błędu względnego normy (niezależnie od tego, czy jest to norma 2, czy norma nieskończoności) i staje się widoczny tylko wtedy, gdy spojrzysz na błędy względne elementarne i weźmiesz maksimum.
Moja oryginalna odpowiedź poniżej wyjaśnia, dlaczego można uzyskać błąd względny normy w rozwiązaniu, który jest mniejszy niż granica podana przez numer warunku.
Jak zauważyłeś w pytaniu, liczba warunków macierzy niepodzielnej daje najgorszy możliwy błąd względny związany z rozwiązaniem zaburzonego układu równań. Oznacza to, że jeśli rozwiążemy A ( x + Δ x ) = b + Δ b dokładnie i rozwiążemy A x = b dokładnie, toκ(A) A(x+Δx)=b+Δb Ax=b
Numery stanów można obliczyć w odniesieniu do różnych norm, ale często stosuje się dwuznakowy numer warunku, a jest to numer warunku użyty w dokumencie, do którego się odwołujesz.
Najgorszy przypadek występuje wtedy, gdy błąd jest lewa pojedynczej wektor odpowiada najmniejszej liczbie pojedynczej wartości . Najlepszy przypadek występuje wtedy, gdy jest lewy pojedynczej wektora odpowiada wielkości pojedynczej wartości . Gdy jest losowa, musisz spojrzeć na rzuty na wszystkie lewe wektory w liczbie pojedynczej i odpowiadające im wartości w liczbie pojedynczej. W zależności od spektrum , sprawy mogą pójść bardzo źle lub bardzo dobrze. A A hemibursztynianu b A A hemibursztynianu b hemibursztynianu b A AΔb A A Δb A A Δb Δb A A
Rozważ dwie macierze , obie o 2-normowym stanie warunku . Pierwsza macierz ma liczby pojedyncze , , , . Druga macierz ma pojedyncze wartości , , , , . 1,0 × 10 10 1 1 x 10 - 10 ... 1 x 10 - 10 1 1 ... 1 1 x 10 - 10A 1.0×1010 1 1×10−10 … 1×10−10 1 1 … 1 1×10−10
W pierwszym przypadku jest mało prawdopodobne, aby przypadkowe zaburzenie było w kierunku pierwszego lewego pojedynczego wektora, a bardziej prawdopodobne, aby znajdowało się w pobliżu jednego z pojedynczych wektorów o wartości pojedynczej . Zatem względna zmiana w rozwiązaniu będzie prawdopodobnie bardzo duża. W drugim przypadku prawie każde zaburzenie będzie zbliżone do pojedynczego wektora o pojedynczej wartości , a względna zmiana w roztworze będzie niewielka.1×10−10 1
PS (dodane później po powrocie z zajęć jogi ...)
Wzór na rozwiązanie toAΔx=Δb
Według twierdzenia Pitagorasa
Jeśli zatrzymamy , wtedy ta suma jest zmaksymalizowana, gdy i zminimalizowana, gdy .∥Δb∥2=1 Δb=Un Δb=U1
W rozważanej tutaj sytuacji jest wynikiem losowych błędów zaokrąglania, więc wartości powinny być w przybliżeniu tej samej wielkości. Warunki z mniejszymi wartościami przyczynią się dużo do błędu, podczas gdy warunki z większymi wartościami nie przyczynią się wiele. W zależności od spektrum może to być znacznie mniejsze niż w najgorszym przypadku.Δb UTiΔb σi σi
źródło
?getrs
tl; dr Zgłosili się liczbę warunek, niekoniecznie właściwą liczbę Warunkiem matrycy, ponieważ istnieje różnica.
Jest to specyficzne dla macierzy i wektora po prawej stronie. Jeśli spojrzysz na dokumentację
*getrs
, to zobaczysz , że granica błędu przekazywania to Tutaj nie jest całkiem zwykłym numerem warunku , ale raczej (Wewnątrz normy są to bezwzględne wartości składowe.) Zobacz na przykład iteracyjne udoskonalenie układów liniowych i LAPACK firmy Higham lub Dokładność i stabilność algorytmów numerycznych Highama (7.2).Dla twojego przykładu wziąłem pseudospektralny operator różnicowy dla podobnego problemu z , i faktycznie istnieje duża różnica międzyi , obliczyłem i , co wystarcza do wyjaśnienia obserwacji, że dzieje się to dla wszystkich prawych stron, ponieważ rzędy wielkości z grubsza odpowiadają temu, co jest patrz Tabela 3.1 (lepsze błędy o 3-4 zamówienia). To nie działa, gdy próbuję to samo tylko na losowej źle uwarunkowanym matrycy, więc to musi być właściwością .n=128 ∥|A−1||A|∥ κ∞(A) 7×103 2.6×107 A
Wyraźnym przykładem, dla którego dwie liczby nie pasują do siebie, którą wziąłem od Highama (7.17, s. 124), z powodu Kahana, jest Innym przykładem, który znalazłem, jest zwykła macierz Vandermonde z losowym . Przeszedłem i niektóre inne źle uwarunkowane matryce również dają tego typu wynik, jak i .
[1:10]
MatrixDepot.jl
triw
moler
Zasadniczo chodzi o to, że analizując stabilność rozwiązywania układów liniowych w odniesieniu do zaburzeń, najpierw musisz określić, które zaburzenia rozważasz. Podczas rozwiązywania układów liniowych za pomocą LAPACK, to ograniczenie błędu uwzględnia perturbacje składowe w , ale brak perturbacji w . To różni się od zwykłego, która uwzględnia zaburzenia normalne zarówno w jak i .A b κ(A)=∥A−1∥∥A∥ A b
Zastanów się (jako kontrprzykład) również, co by się stało, gdybyś nie rozróżniał. Wiemy, że stosując iteracyjne udoskonalanie z podwójną precyzją (patrz link powyżej) możemy uzyskać najlepszy możliwy błąd względny w przód dla tych macierzy z . Więc jeśli weźmiemy pod uwagę pomysł, że układów liniowych nie da się rozwiązać z dokładnością lepszą niż , to jak udałoby się dopracować rozwiązania?O(u) κ(A)≪1/u κ(A)u
PS Ważne jest, żeE A b b
?getrs
obliczone rozwiązanie jest prawdziwym rozwiązaniem(A + E)x = b
z perturbacją w , ale bez perturbacji w . Sytuacja wyglądałaby inaczej, gdyby perturbacje były dozwolone w .Edytuj Aby pokazać temu działającemu bardziej bezpośrednio, w kodzie, że nie jest to przypadek ani szczęście, ale raczej (nietypowa) konsekwencja dwóch liczb warunków bardzo różniących się dla niektórych określonych macierzy, np.
Edycja 2 Oto kolejny przykład tego samego zjawiska, w którym różne liczby warunków nieoczekiwanie różnią się znacznie. Tym razem Tutaj jest macierzą Vandermonde 10 × 10 na , a gdy jest wybierane losowo, jest zauważalnie mniejsze niż , a najgorszy przypadek jest podany przez dla niektórych .
Średnia wielkość liter (prawie 9 rzędów lepszych błędów):
Najgorszy przypadek ( ):a=1,…,12
Edycja 3 Kolejnym przykładem jest macierz Forsythe, która jest zaburzonym blokiem Jordana o dowolnym rozmiarze postaci Ma to , , więc , ale , więc . I jak można zweryfikować ręcznie, rozwiązywanie układów równań liniowych, takich jak jest niezwykle dokładne, pomimo potencjalnie nieograniczonego . Więc ta matryca przyniesie nieoczekiwanie precyzyjne rozwiązania.
Edycja 4 macierzy Kahana jest również taka, z :cond(A)≪κ(A)
źródło