Wichtig: Damit alle benötigten Pakete richtig eingebunden werden, führen Sie die nächste Zelle einmal aus, sobald Sie das Notebook neu öffnen.
# some setup
%matplotlib inline
import numpy as np
import numpy.linalg as linalg
import matplotlib.pyplot as plt
Schreiben Sie ein Programm zur iterativen Lösung nichtlinearer Gleichungssysteme $f(x) = 0$ mit Hilfe des Newton-Verfahrens, wobei $f: R^n \to R^n$ stetig differenzierbar ist.
Der Aufruf des Programms soll mit \begin{equation} \texttt{[x,X] = newton}(\texttt{f, df, x0, tol, kmax}); \end{equation} erfolgen mit den Eingabeparametern \begin{align} \texttt{f, df} \qquad &\text{Funktion } y = f(x), \text{ bzw. Jacobimatrix } J = f'(x) \text{ der Funktion }f \\ \texttt{x0} \qquad &\text{Startvektor } x^{(0)} \text{ der Iteration} \\ \texttt{tol} \qquad &\text{Fehlertoleranz} \\ \texttt{kmax} \qquad &\text{maximale Anzahl der Iterationen} \end{align} und Ausgabeparameter \begin{align} \texttt{[x, X]} \qquad &\text{Approximation der Nullstelle } x^*, f(x^*) = 0, \\ &\text{und Folge der Iterierten } x^{(0)}, x^{(1)}, \ldots \text{ in den Spalten der Matrix } X. \end{align}
Dabei soll die Iteration abgebrochen werden, falls die maximale Iterationszahl $\texttt{kmax}$ überschritten wurde oder \begin{equation} | f(x^{(k)} ) |_2 + | x^{(k-1)} - x^{(k)}|_2 < \texttt{tol} \end{equation} gilt.
Schreiben Sie ein modifiziertes Newton-Verfahren, in dem in jedem Schritt die Jacobimatrix des Startwertes $Df(x^{(0)})$ benutzt wird. Erweitern Sie das Verfahren, indem die Jacobimatrix jeden $l$-ten Schritt neu berechnet wird, für z.B. $l =10, 20, 50, 100$.
$\textit{Hinweis:}$ Zur Lösung des linearen Gleichungssystems in jedem Schritt können Sie die $\texttt{solve}$-Funktion der $\texttt{linalg}$-Bibliothek benutzen.
a) Finden Sie mit Hilfe des Programms eine Nullstelle zu \begin{equation} x_1 + e^{-x_1} + x_2^3 = 0\, , \quad x_1^2 + 2x_1x_2 - x_2^2 + \tan(x_1) = 0\, , \quad x_1,x_2 \in R\, . \end{equation} Wählen Sie $\epsilon = 10^{-8}$, $kmax = 100$ und probieren Sie unterschiedliche Startwerte $x^{(0)}$ aus, z.B. $x^{(0)} = (-1,-1)$.
b) Gegeben sei das nichtlineare Gleichungssystem \begin{align} 3x_2 = 0\, , \quad x_1^2 + \frac{2x_2}{x_2 + 5} = 0\, , \quad x_1,x_2 \in R\, , \end{align} dessen eindeutig bestimmte Lösung $(x_1,x_2) = (0,0)$ ist. Führen Sie das Newtonverfahren mit Startwert $x^{(0)} = (1,0)$ aus (z.B. mit Fehlertoleranz $\epsilon = 10^{-8}$, $kmax = 50$).
c) Fertigen Sie semilogarithmische plots an, um die Konvergenzraten der unterschiedlichen Verfahren angewandt auf die Funktionen in a) und b) zu visualisieren. Warum sieht man in b) nur lineare Konvergenz des (unmodifizierten) Newton-Verfahrens?
# Fuegen Sie hier Ihre Loesung ein!