Warum konvergiert Newtons Methode nicht?

22

Ich verwende das nichtlineare Lösungspaket SNES von PETSc , um ein System nichtlinearer Gleichungen zu lösen, das durch Diskretisieren einer partiellen Differentialgleichung erhalten wird. Wie kann ich feststellen, warum der Löser nicht konvergiert, und was kann ich tun, um meine Gleichungen erfolgreich zu lösen?

petsc pde implicit-methods Jed Brown
quelle
8
Wie bei jeder iterativen Methode ist es von größter Bedeutung, einen guten Startwert für die Newton-Raphson-Methode zu finden. Ein schlechter Startpunkt führt oft zu Chaos.
JM
6
Ich denke, dass "oft zu Chaos führt" falsch ist. In Bezug auf Blum, Cucker, Shub und Smale weist Newton attraktive Becken auf, die durch Grenzen getrennt sind, was zu einer chaotischen Iteration führen kann. Daher ist ein solches Verhalten im Vergleich zur Konvergenz sehr unwahrscheinlich. Wenn der Algorithmus nur nach echten Lösungen sucht, wird er häufig nicht konvergieren, aber nicht chaotisch.
Matt Knepley
5
Ich meinte "Chaos" im nichttechnischen Sinne, @Matt; Zum Beispiel Divergenz gegen Unendlich oder zyklisches Verhalten. Vielleicht wäre "Katastrophe" eine bessere Wortwahl gewesen?
JM

Antworten:

42

Newtons Methode kann aus vielen Gründen nicht konvergieren, hier sind einige der häufigsten.

  • Der Jakobianer ist falsch (oder richtig in der Reihenfolge, aber nicht parallel).
  • Das lineare System wird nicht oder nicht genau genug gelöst.
  • Das jakobianische System hat eine Singularität, die der lineare Löser nicht handhabt.
  • Es gibt einen Fehler in der Funktionsbewertungsroutine.
  • Die Funktion ist nicht kontinuierlich oder hat keine kontinuierlichen ersten Ableitungen (z. B. Phasenwechsel oder TVD-Begrenzer).
  • Die Gleichungen haben möglicherweise keine Lösung (z. B. Grenzzyklus anstelle eines stationären Zustands) oder es besteht ein "Hügel" zwischen der anfänglichen Schätzung und dem stationären Zustand (z. B. müssen die Reaktanten sich entzünden und brennen, bevor sie einen stationären Zustand erreichen, aber der stationäre Zustand Zustand Rest wird während der Verbrennung größer sein).

Hier sind einige Möglichkeiten, um die fehlende Konvergenz von Newton zu beheben.

  • Führen Sie mit den Optionen -snes_monitor -ksp_monitor_true_residual -snes_converged_reason -ksp_converged_reason. Wenn die lineare Lösung nicht konvergiert, prüfen Sie, ob der Jacobi korrekt ist, und sehen Sie sich diese Frage an . Wenn das vorkonditionierte Residuum konvergiert, das wahre Residuum jedoch nicht, kann der Vorkonditionierer singulär sein. Wenn die lineare Lösung gut konvergiert, die Zeilensuche jedoch fehlschlägt, ist der Jacobi möglicherweise falsch.
  • Führen Sie mit aus, -pc_type lu or -pc_type svdum festzustellen, ob das Problem ein schlechter linearer Löser ist
  • Laufen Sie mit -mat_viewoder, um -mat_view_drawzu sehen, ob der Jacobianer vernünftig aussieht
  • Renne mit, um -snes_type test -snes_test_displayzu sehen, ob der Jacobianer, den du benutzt, falsch ist. Vergleichen Sie die Ausgabe beim Hinzufügen, -mat_fd_type dsum festzustellen, ob das Ergebnis von der Wahl des Differenzierungsparameters abhängt.
  • Renne mit, um -snes_mf_operator -pc_type luzu sehen, ob der Jacobianer, den du benutzt, falsch ist. Wenn das Problem für eine direkte Lösung zu groß ist, versuchen Sie es -snes_mf_operator -pc_type ksp -ksp_ksp_rtol 1e-12. Vergleichen Sie die Ausgabe beim Hinzufügen, -mat_mffd_type dsum festzustellen, ob das Ergebnis von der Wahl des Differenzierungsparameters abhängt.
  • Führen Sie einen Prozessor aus, um festzustellen, ob das Problem nur parallel auftritt.
  • Führen Sie mit aus, -snes_ls_monitorum festzustellen, ob die Zeilensuche fehlschlägt (dies ist normalerweise ein Zeichen für einen schlechten Jakobianer).
  • Führen Sie mit aus -info, um detailliertere Informationen zum Lösungsprozess zu erhalten.

Hier sind einige Möglichkeiten, um den Newton-Prozess zu unterstützen, wenn alle oben genannten Punkte ausgecheckt sind

  • Führen Sie die Rastersequenzierung aus (dies -snes_grid_sequenceist alles, was Sie für die Arbeit mit a benötigen DM), um eine bessere erste Schätzung Ihres feineren Netzes zu erzielen
  • ./configure --with-precision=__float128 --download-f2cblaslapackAusführung mit Quad-Genauigkeit (ab PETSc 3.2 werden GNU-Compiler der Version 4.6 oder höher benötigt)
  • Ändern Sie die Einheiten (Nichtdimensionierung), die Skalierung der Randbedingungen oder die Formulierung, damit der Jacobi besser konditioniert wird.
  • Mollify-Merkmale in der Funktion, die keine stetigen ersten Ableitungen haben (tritt häufig auf, wenn ifAussagen in der Restauswertung vorliegen , z. B. Phasenwechsel oder TVD-Limiter). Verwenden Sie einen Variations-Ungleichungslöser ( SNESVINEWTONRSLS ), wenn die Diskontinuitäten von grundlegender Bedeutung sind.
  • Versuchen Sie es mit einer Vertrauensbereichsmethode ( -ts_type trmöglicherweise müssen Parameter angepasst werden).
  • Führen Sie mit einigen Fortsetzungsparametern ab einem Punkt aus, an dem Sie die Lösung kennen. Informationen zum Lösen von stationären Problemen finden Sie in TSPSEUDO . Es gibt Homotopy-Solver-Pakete wie PHCpack, mit denen Sie alle möglichen Lösungen finden (und Ihnen mitteilen können, dass sie alle gefunden haben). Diese sind jedoch nicht skalierbar und können nur kleine Probleme lösen.
Jed Brown
quelle