Pourquoi la méthode de Newton ne converge-t-elle pas?

22

J'utilise le package de résolution non linéaire SNES de PETSc pour résoudre un système d'équations non linéaires obtenues en discrétisant une équation différentielle partielle. Comment puis-je déterminer pourquoi le solveur ne converge pas et que puis-je faire pour résoudre avec succès mes équations?

Jed Brown
la source
8
Comme pour toute méthode itérative, il est primordial de trouver une bonne graine pour démarrer la méthode Newton-Raphson. Un mauvais point de départ entraîne souvent le chaos.
JM
6
Je pense que "entraîne souvent le chaos" est incorrect. Se référant à Blum, Cucker, Shub et Smale, Newton a des bassins attrayants séparés par des limites qui peuvent entraîner une itération chaotique. Ce type de comportement est donc très peu probable par rapport à la convergence. Si l'algorithme ne cherche que des solutions réelles, il ne parviendra pas à converger souvent, mais ne deviendra pas chaotique.
Matt Knepley du
5
Je voulais dire "chaos" dans le sens non technique, @Matt; par exemple, divergence à l'infini ou comportement cyclique. Peut-être que «catastrophe» aurait été un meilleur choix de mots?
JM

Réponses:

43

La méthode de Newton peut ne pas converger pour de nombreuses raisons, voici quelques-unes des plus courantes.

  • Le jacobien est faux (ou correct en séquence mais pas en parallèle).
  • Le système linéaire n'est pas résolu ou n'est pas résolu avec suffisamment de précision.
  • Le système jacobien a une singularité que le solveur linéaire ne gère pas.
  • Il y a un bogue dans la routine d'évaluation des fonctions.
  • La fonction n'est pas continue ou n'a pas de dérivées premières continues (par exemple, changement de phase ou limiteurs TVD).
  • Les équations peuvent ne pas avoir de solution (par exemple, cycle limite au lieu d'un état stationnaire) ou il peut y avoir une "colline" entre la supposition initiale et l'état stationnaire (par exemple, les réactifs doivent s'enflammer et brûler avant d'atteindre un état stationnaire, mais l'état résiduel sera plus important pendant la combustion).

Voici quelques façons d'aider à déboguer le manque de convergence de Newton.

  • Exécutez avec les options -snes_monitor -ksp_monitor_true_residual -snes_converged_reason -ksp_converged_reason. Si la résolution linéaire ne converge pas, vérifiez si le jacobien est correct, puis voyez cette question . Si le résidu préconditionné converge, mais pas le vrai résidu, le préconditionneur peut être singulier. Si la résolution linéaire converge bien, mais la recherche de ligne échoue, le jacobien peut être incorrect.
  • Exécutez avec -pc_type lu or -pc_type svdpour voir si le problème est un mauvais solveur linéaire
  • Courez avec -mat_viewou -mat_view_drawpour voir si le jacobien semble raisonnable
  • Courez avec -snes_type test -snes_test_displaypour voir si le jacobien que vous utilisez est faux. Comparez la sortie lorsque vous ajoutez -mat_fd_type dspour voir si le résultat est sensible au choix du paramètre de différenciation.
  • Courez avec -snes_mf_operator -pc_type lupour voir si le jacobien que vous utilisez est faux. Si le problème est trop important pour être résolu directement, essayez -snes_mf_operator -pc_type ksp -ksp_ksp_rtol 1e-12. Comparez la sortie lorsque vous ajoutez -mat_mffd_type dspour voir si le résultat est sensible au choix du paramètre de différenciation.
  • Exécutez sur un processeur pour voir si le problème n'est que parallèle.
  • Exécutez avec -snes_ls_monitorpour voir si la recherche de ligne échoue (c'est généralement le signe d'un mauvais jacobien).
  • Exécutez avec -infopour obtenir des informations plus détaillées sur le processus de solution.

Voici quelques façons d'aider le processus de Newton si tout ce qui précède est vérifié

  • Exécutez avec un séquencement de grille ( -snes_grid_sequencec'est tout ce dont vous avez besoin si vous travaillez avec a DM) pour générer une meilleure estimation initiale de votre maillage plus fin
  • Exécuter avec une précision quadruple ( ./configure --with-precision=__float128 --download-f2cblaslapackavec PETSc 3.2 et versions ultérieures, nécessite des compilateurs GNU version 4.6 ou ultérieure)
  • Modifiez les unités (non dimensionnalisation), la mise à l'échelle des conditions aux limites ou la formulation afin que le jacobien soit mieux conditionné.
  • Mollify les fonctionnalités de la fonction qui n'ont pas de dérivées premières continues (se produit souvent quand il y a des ifinstructions dans l'évaluation résiduelle, par exemple un changement de phase ou des limiteurs TVD). Utilisez un solveur variationnel d'inégalité ( SNESVINEWTONRSLS ) si les discontinuités sont d'une importance fondamentale.
  • Essayez une méthode de région de confiance ( -ts_type tr, il faudra peut-être ajuster les paramètres).
  • Exécutez avec un paramètre de continuation à partir d'un point où vous connaissez la solution, voir TSPSEUDO pour résoudre les problèmes de régime permanent. Il existe des packages de solveurs homotopy comme PHCpack qui peuvent vous offrir toutes les solutions possibles (et vous dire qu'il les a toutes trouvées), mais ceux-ci ne sont pas évolutifs et ne peuvent résoudre que de petits problèmes.
Jed Brown
la source