Dlaczego metoda Newtona nie jest zbieżna?

22

Używam nieliniowego pakietu solvera PETSc SNES do rozwiązania układu równań nieliniowych uzyskanych przez dyskretyzację równania różniczkowego cząstkowego. Jak mogę ustalić, dlaczego solver nie jest zbieżny i co mogę zrobić, aby pomyślnie rozwiązać moje równania?

Jed Brown
źródło
8
Jak w przypadku każdej metody iteracyjnej, najważniejsze jest, aby uzyskać dobre ziarno, aby uruchomić metodę Newtona-Raphsona. Zły punkt początkowy często powoduje chaos.
JM
6
Myślę, że „często powoduje chaos” jest niepoprawne. Nawiązując do Blum, Cucker, Shub i Smale, Newton ma atrakcyjne baseny oddzielone granicami, co może skutkować chaotyczną iteracją. Zatem tego rodzaju zachowanie jest bardzo mało prawdopodobne w porównaniu do konwergencji. Jeśli algorytm szuka tylko prawdziwych rozwiązań, często się nie zbiegnie, ale nie będzie chaotyczny.
Matt Knepley,
5
Miałem na myśli „chaos” w nietechnicznym sensie, @Matt; na przykład dywergencja do nieskończoności lub zachowanie cykliczne. Może „katastrofa” byłaby lepszym wyborem słów?
JM

Odpowiedzi:

43

Metoda Newtona może nie zbiegać się z wielu powodów, oto niektóre z najczęstszych.

  • Jakobian jest niepoprawny (lub poprawny w kolejności, ale nie równolegle).
  • Układ liniowy nie został rozwiązany lub nie został rozwiązany wystarczająco dokładnie.
  • System jakobowski ma osobliwość, której nie rozwiązuje solver liniowy.
  • Wystąpił błąd w procedurze oceny funkcji.
  • Funkcja nie jest ciągła lub nie ma ciągłych pierwszych pochodnych (np. Zmiana fazy lub ograniczniki TVD).
  • Równania mogą nie mieć rozwiązania (np. Cykl graniczny zamiast stanu ustalonego) lub może istnieć „wzgórze” między początkowym odgadnięciem a stanem ustalonym (np. Reagenty muszą zapalić się i spalić przed osiągnięciem stanu ustalonego, ale ustalone- stan resztkowy będzie większy podczas spalania).

Oto kilka sposobów na debugowanie braku konwergencji Newtona.

  • Uruchom z opcjami -snes_monitor -ksp_monitor_true_residual -snes_converged_reason -ksp_converged_reason. Jeśli rozwiązanie liniowe nie jest zbieżne, sprawdź, czy jakobian jest poprawny, a następnie zobacz to pytanie . Jeśli wstępnie kondycjonowana reszta zbiegnie się, ale prawdziwa reszta nie, zbieżność może być pojedyncza. Jeśli rozwiązanie liniowe dobrze zbiegnie się, ale wyszukiwanie linii nie powiedzie się, jakobian może być niepoprawny.
  • Uruchom z, -pc_type lu or -pc_type svdaby sprawdzić, czy problem jest złym rozwiązaniem liniowym
  • Biegnij z -mat_viewlub -mat_view_drawzobacz, czy jakobian wygląda rozsądnie
  • Biegnij z, -snes_type test -snes_test_displayaby sprawdzić, czy używany przez Ciebie jakobian jest niewłaściwy. Porównaj dane wyjściowe po dodaniu, -mat_fd_type dsaby zobaczyć, czy wynik jest wrażliwy na wybór parametru różnicowania.
  • Biegnij z, -snes_mf_operator -pc_type luaby sprawdzić, czy używany przez Ciebie jakobian jest niewłaściwy. Jeśli problem jest zbyt duży do bezpośredniego rozwiązania, spróbuj -snes_mf_operator -pc_type ksp -ksp_ksp_rtol 1e-12. Porównaj dane wyjściowe po dodaniu, -mat_mffd_type dsaby zobaczyć, czy wynik jest wrażliwy na wybór parametru różnicowania.
  • Uruchom na jednym procesorze, aby sprawdzić, czy problem występuje tylko równolegle.
  • Uruchom z, -snes_ls_monitoraby sprawdzić, czy wyszukiwanie linii nie powiedzie się (zwykle jest to oznaka złego jakobianu).
  • Uruchom z, -infoaby uzyskać bardziej szczegółowe informacje na temat procesu rozwiązania.

Oto kilka sposobów, aby pomóc procesowi Newtona, jeśli wszystko powyżej się sprawdzi

  • Uruchom sekwencję siatki ( -snes_grid_sequencejest to wszystko, czego potrzebujesz, jeśli pracujesz z a DM), aby wygenerować lepsze początkowe domysły na drobniejszych siatkach
  • Uruchamianie z poczwórną precyzją ( ./configure --with-precision=__float128 --download-f2cblaslapackz PETSc 3.2 i nowszymi, wymaga kompilatorów GNU w wersji 4.6 lub nowszej)
  • Zmień jednostki (niedimensalizacja), skalowanie warunków brzegowych lub sformułowanie, aby jakobian był lepiej uwarunkowany.
  • Zmiękcz funkcje w funkcji, które nie mają ciągłych pierwszych pochodnych (często występują, gdy ifw ocenie resztkowej występują stwierdzenia, np. Zmiana fazy lub ograniczenia TVD). Użyj rozwiązania nierówności wariacyjnych ( SNESVINEWTONRSLS ), jeśli nieciągłości mają fundamentalne znaczenie.
  • Wypróbuj metodę regionu zaufania ( -ts_type trmoże być konieczne dostosowanie parametrów).
  • Uruchom z pewnym parametrem kontynuacji od punktu, w którym znasz rozwiązanie, zobacz TSPSEUDO, aby rozwiązać problemy ze stanem ustalonym. Istnieją pakiety solvera homotopii, takie jak PHCpack, które mogą zapewnić ci wszystkie możliwe rozwiązania (i powiedzieć, że wszystkie je znalazły), ale nie są one skalowalne i nie mogą rozwiązać niczego oprócz drobnych problemów.
Jed Brown
źródło