Berechnung nichtlinearer Gleichgewichtslösungen

Newton Verfahren - Basisversion

Gesucht

$x_{s}$ mit $0=f\left(x_{s}\right)$

Start

$\left(k=0\right)$ Wahr eines Startvektors $x^{\left(0\right)}$

• z.B. aus Kentnissen über das dem Modell zugrundelegene physikalische Modell
• Ausprobieren
• Herantasten von der bekannten Lösung eines einfacheren Problems (Fortsetzungsmethode)

Iterationsschritt

$\left(k\rightarrow k+1\right)$

• Berechnung von $f\left(x^{\left(k\right)}\right)$
• Berechnung der Jakobimatrix $\frac{\partial f}{\partial x}\left(x^{\left(k\right)}\right)$
  • siehe Abschnitt sub:Jacobi-Matrix
  • oder Jakobimatrix durch konstante Matrix, z.B. $\frac{\partial f}{\partial x}\left(x^{\left(0\right)}\right)$ bzw. deren Approximation ersetzen
    • Verfahren nicht mehr quadratisch, höchstens linear konvergent
    • Wenn konvergent, dann heufig schneller als ``normales'' Newtonverfahren
• Berechnung der Korrektur (Suchrichtung) $\Delta x^{\left(k\right)}$ durch lösen des linearen Gleichungssystems
  $$\frac{\partial f}{\partial x}\left(x^{\left(k\right)}\right)\cdot\Delta x^{\left(k\right)}=-f\left(x^{\left(k\right)}\right)$$

• Berechnung der neuen Näherung $x^{\left(k+1\right)}=x^{\left(k\right)}+\Delta x^{\left(k\right)}$

Terminierungstest

Falls ``nahe genug'' an der Lösung oder ``kein Fortschritt'' Stop, ansonsten $k$ um 1 erhöhen und nächsten Iterationsschritt.

• ``Nahe genug'' an der Lösung
  • keine nennenswerte Änderung in $x^{\left(k+1\right)}$
    $$\left\Vert \Delta x^{\left(k\right)}\right\Vert \le\varepsilon_{1}\cdot\left(1+\left\Vert x^{\left(k\right)}\right\Vert \right)$$

  • Funktionswerte klein genug
    $$\left\Vert f\left(x^{\left(k+1\right)}\right)\right\Vert \le\varepsilon_{2}$$

• ``kein Fortschritt'' mehr
  • keine nennenswerte Abnahme mehr
    $$\left\Vert f\left(x^{\left(k+1\right)}\right)\right\Vert \ge\left\Vert f\left(x^{\left(k\right)}\right)\right\Vert -\varepsilon_{3}$$

  • zu viele Iterationsschritte
    $$k+1\ge k_{max}$$

• Für $\varepsilon_{j},j=1,2,3$ geeignete Toleranzen z.B. $\varepsilon_{j}=10^{-4},\ldots,10^{-8}$

Problembereiche

Einzugsbereich bei mehreren Lösungen

• Es können einige Nullstellen durch andere in Ihrere Umgebung versteck sein, so dass sie nur gefunden werden wenn der Startwert in einem (kleinen) Bereich liegt.

Divergenz und Singularitäten

• Singularitäten in der Nähe von Nullstellen können diese ``Verstecken''

hoch Nichtlineare Probleme

• Divergenz obwohl Startwert ``nahe'' an Nullstelle

Abhilfe

durch ``kleineren'' Schritt zur Berechnung von $x^{\left(k+1\right)}$

$$x^{\left(k+1\right)}=x^{\left(k\right)}+\alpha^{\left(k\right)}\cdot\Delta x^{\left(k\right)}$$

• mit $0<\alpha_{min}\le\alpha^{\left(k\right)}\le1$
• Bestimmung der Schrittweite durch Näherungsweise Minimierung von
  

  $$\varphi\left(\alpha\right) = \left\Vert f\left(x^{\left(k\right)}+\alpha\cdot\Delta x^{\left(k\right)}\right)\right\Vert _{2}^{2}$$

  $$= \sum_{i=1}^{n}\left(f_{i}\left(x^{\left(k\right)}+\alpha\cdot\Delta x^{\left(k\right)}\right)\right)^{2}$$

  
  

• Fausregel: $\alpha$ nur so ``klein wie nötig'' und ``so groß wie möglich'', denn nur für $\alpha\approx1$ quadratische Konvergenz