Kurs:Numerik I/5 Numerische Lösung nichtlinearer Gleichungssysteme

5.4 Das Newton-Verfahren im ${ℝ}^n$

4.1 Grundlagen

Es sei $D\subseteq {ℝ}^n$ eine offene Menge und $F:D\subseteq {ℝ}^n\to {ℝ}^n$ eine Funktion mit

$F(x):=(F_1(x),\dots ,F_n(x){)}^T,x\in D$

und stetigen partiellen Ableitungen $(\partial F_i/\partial x_j)(x)$ $(i,j=1,\dots ,n)$, es sei also $F\in C^1(D,{ℝ}^n)$. Die zu $F$ gehörige Jacobi-Matrix bezeichnen wir mit

${𝒥}_F(x):={(\frac{\partial F_i}{\partial x_j}(x))}_{i,j=1,\dots ,n}\in {ℝ}^{n\times n}.$

Mit $\Vert \cdot \Vert$ ist im ganzen Abschnitt 5.4 wieder die Euklidische Norm auf dem ${ℝ}^n$ bzw. die durch sie induzierte Spektralnorm gemeint.

Schließlich werden wir von dem folgenden Lemma Gebrauch machen.

Lemma 5.17

Sei $v:[a,b]\to {ℝ}^n$ eine stetige vektorwertige Funktion, sei $v(t):=(v_1(t),\dots ,v_n(t){)}^T$ für $t\in [a,b]$ und sei $u:=\underset{a}{\overset{b}{\int }}v(t)dt$ der Vektor mit den Komponenten $u_i:=\underset{a}{\overset{b}{\int }}{v}_i(t)dt$. Dann gilt:

$\Vert \underset{a}{\overset{b}{\int }}v(t)dt\Vert \le \underset{a}{\overset{b}{\int }}\Vert v(t)\Vert dt$

Beweis.

Es sei $K:=\Vert u\Vert$. Dann kann man unter Verwendung des Standardskalarprodukts

$⟨x,y⟩:=\sum _{i=1}^n{x}_i{y}_i,x,y\in {ℝ}^n$

auf dem ${ℝ}^n$ und der Cauchy-Schwarz-Ungleichung abschätzen:

$K^2=⟨u,u⟩=⟨\underset{a}{\overset{b}{\int }}v(t)dt,u⟩=\sum _{i=1}^n{u}_i\underset{a}{\overset{b}{\int }}{v}_i(t)dt=\underset{a}{\overset{b}{\int }}\sum _{i=1}^n{u}_i{v}_i(t)dt=\underset{a}{\overset{b}{\int }}⟨u,v(t)⟩dt\le \underset{a}{\overset{b}{\int }}\Vert u\Vert \Vert v(t)\Vert dt$

$=K\underset{a}{\overset{b}{\int }}\Vert v(t)\Vert dt.$

q.e.d.

5.4.2 Das Verfahren

Es sei wieder $D\subseteq {ℝ}^n$ eine offene Menge und es sei $F\in C^1(D,{ℝ}^n)$ mit

$F(x)=(F_1(x),\dots ,F_n(x){)}^T,x\in D$

und Jacobi- bzw. Funktionalmatrix ${𝒥}_F(x)$ gegeben. Es soll nun das Newton-Verfahren zur Bestimmung einer Lösung $x^{*}\in D$ des Gleichungssystems

$F(x)=0\iff F_i(x_1,\dots ,xn)=0(i=1,\dots ,n)$

vorgestellt und seine Konvergenz untersucht werden. Für $n=1$ hatten wir dies bereits in Abschnitt 5.2.4 getan.

Die Iterationsvorschrift des Newton-Verfahrens lautete im Fall $n=1$

$x_{k+1}:=x_k-[f^{\prime }(x_k){]}^{-1}f(x_k),$

wobei sich $x_{k+1}$ als Nullstelle einer linearen Approximation von $f$, der Tangente bei $x_k$ an $f$, ergab. Ähnlich kann man für eine Funktion $F\in C^1(D,{ℝ}^n)$ mit beliebigem $n\in \mathbb{N}$ das Newton-Verfahren dadurch motivieren, dass man $x^{k+1}$ als Nullstelle der linearen Approximation von $F$ bei $x^k$

$F_k(x):=F(x^k)+{𝒥}_F(x^k)(x-x^k)$

wählt. Dieses Vorgehen führt zu der allgemeinen Iterationsvorschrift

(5.23) $x^{k+1}:=x^k-{[{𝒥}_F(x^k)]}^{-1}F(x^k),k\in {\mathbb{N}}_0$

des Newton-Verfahrens. Wir gehen hier implizit davon aus, dass die Jacobi-Matrix ${𝒥}_F(x^k)$ des Systems für jedes $k\in {\mathbb{N}}_0$ nichtsingulär ist. Da man, wenn immer möglich, die Berechnung der Inversen einer Matrix vermeiden sollte, geht man praktisch bei der Berechnung von $x^{k+1}$ von der zu (5.23) äquivalenten Gleichung

${𝒥}_F(x^k)(\underset{=:h^k}{\underbrace{x^{k+1}-x^k}})=-F(x^k)$

aus und bestimmt man die eindeutige Lösung $h^k$ des linearen Gleichungssystems

${𝒥}_F(x^k)h=-F(x^k).$

Anschließend setzt man

$x^{k+1}:=x^k+h^k.$

Das Newton-Verfahren lautet somit wie folgt:

Algorithmus 9 (Newton-Verfahren)

(0) Wähle $x^0\in D$ und ein $\epsilon >0$. Berechne $F(x^0)$ und setze $k:=0$.

(1) Berechne ${𝒥}_F(x^k)$ und bestimme die eindeutige Lösung $h^k\in {ℝ}^n$ von

(5.24) ${𝒥}_F(x^k)h=-F(x^k).$

(2) Setze $x^{k+1}:=x^k+h^k$ und berechne $F(x^{k+1})$.

(3) Falls ${\Vert F(x^{k+1})\Vert }_2\le \epsilon$, stop!

(4) Setze $k:=k+1$ und gehe nach (1).

Der folgende Satz besagt, dass das Newton-Verfahren unter geeigneten Voraussetzungen durchführbar, d. h. für alle $k$ insbesondere $x^k\in D$ und ${𝒥}_F(x^k)$ nichtsingulär ist und dass es superlinear bzw. quadratisch konvergiert.

Satz 5.18

Es sei $D\subset {ℝ}^n$ offen und $F\in C^1(D,{ℝ}^n)$. Ferner existiere ein $x^{*}\in D$, für welches $F(x^{*})=0$ und ${𝒥}_F(x^{*})$ nichtsingulär sei. Dann gibt es eine Umgebung ${𝒰}_{\delta }(x^{*})$ von $x^{*}$ für ein $\delta >0$, so dass das Newton-Verfahren, Algorithmus 9, für jeden Startpunkt $x^0\in {𝒰}_{\delta }(x^{*})$ durchführbar ist und die durch ihn ohne das Abbruchkriterium (3) erzeugte Iteriertenfolge $(x^k)$ superlinear gegen $x^{*}$ konvergiert. Gilt mit einem $L>0$

(5.25) $\Vert {𝒥}_F(x)-{𝒥}_F(x^{*})\Vert \le L\Vert x-x^{*}\Vert ,x\in {𝒰}_{\delta }(x^{*}),$

so konvergiert $(x^k)$ gegen $x^{*}$ sogar quadratisch.

Beweis.

Wegen der Stetigkeit von ${𝒥}_F(x)$ auf $D$ können wir zunächst $\eta >0$ so klein wählen, dass gilt:

$\Vert {𝒥}_F(x)-{𝒥}_F(x^{*})\Vert \le \frac{1}{2\Vert [{𝒥}_F(x^{*}){]}^{-1}\Vert },x\in {𝒰}_{\eta }(x^{*}).$

Für $x\in {𝒰}_{\eta }(x^{*})$ ergibt sich damit und mit $\beta :=\Vert [{𝒥}_F(x^{*}){]}^{-1}\Vert$ gemäß Korollar 2.21 die Invertierbarkeit der Matrix

${𝒥}_F(x)={𝒥}_F(x^{*})+[{𝒥}_F(x)-{𝒥}_F(x^{*})]$

sowie die Abschätzung

(5.26) $\Vert [{𝒥}_F(x){]}^{-1}\Vert \le \frac{\Vert [{𝒥}_F(x^{*}){]}^{-1}\Vert }{1-\Vert [{𝒥}_F(x^{*}){]}^{-1}\Vert \Vert {𝒥}_F(x)-{𝒥}_F(x^{*})\Vert }\le 2\beta .$

Sei nun

$𝒩(x):=x-[{𝒥}_F(x){]}^{-1}F(x),x\in {𝒰}_{\eta }(x^{*})$

die Iterationsfunktion des lokalen Newton-Verfahrens, die nach dem Gezeigten auf ${𝒰}_{\eta }(x^{*})$ wohldefiniert ist. Mit $F(x^{*})=0$ und den Identitäten

$\underset{0}{\overset{1}{\int }}{𝒥}_F(x^{*}+s(x-x^{*}))(x-x^{*})ds=F(x^{*}+s(x-x^{*})){|}_0^1=F(x)-F(x^{*})=F(x)$

schließen wir als nächstes

$𝒩(x)-x^{*}=x-x^{*}-[{𝒥}_F(x){]}^{-1}[F(x)-F(x^{*})]$

$=x-x^{*}-[{𝒥}_F(x){]}^{-1}\{{𝒥}_F(x^{*})(x-x^{*})+\underset{0}{\overset{1}{\int }}[{𝒥}_F(x^{*}+s(x-x^{*}))-{𝒥}_F(x^{*})](x-x^{*})ds\}$

$=-[{𝒥}_F(x){]}^{-1}[{𝒥}_F(x^{*})-{𝒥}_F(x)](x-x^{*})-[{𝒥}_F(x){]}^{-1}\underset{0}{\overset{1}{\int }}[{𝒥}_F(x^{*}+s(x-x^{*}))-{𝒥}_F(x^{*})](x-x^{*})ds.$

Für

(5.27) $\epsilon (x):=2\beta \{\Vert {𝒥}_F(x^{*})-{𝒥}_F(x)\Vert +\underset{0}{\overset{1}{\int }}\Vert {𝒥}_F(x^{*}+s(x-x^{*}))-{𝒥}_F(x^{*})\Vert ds\}$

leiten wir daraus unter Anwendung von Lemma 5.17 mit (5.26) die folgende Abschätzung ab:

(5.28) $\Vert 𝒩(x)-x^{*}\Vert \le \epsilon (x)\Vert x-x^{*}\Vert .$

Wegen der Stetigkeit von ${𝒥}_F(x)$ auf ${𝒰}_{\eta }(x^{*})$ existiert ein $\delta \in (0,\eta ]$, so dass $\epsilon (x)\le 1/2$ auf ${𝒰}_{\delta }(x^{*})$ ist und damit gilt:

$\Vert 𝒩(x)-x^{*}\Vert \le \frac{1}{2}\Vert x-x^{*}\Vert ,x\in {𝒰}_{\delta }(x^{*}).$

Beginnend mit $x^0\in {𝒰}_{\delta }(x^{*})$, liegt folglich mit $x^k\in {𝒰}_{\delta }(x^{*})$ auch $x^{k+1}:=𝒩(x^k)$ in ${𝒰}_{\delta }(x^{*})$ und konvergiert die Folge $(x^k)$ linear gegen $x^{*}$. Die Konvergenz von $(x^k)$ impliziert weiter die Konvergenz $\epsilon (x^k)\to 0$ $(k\to \mathrm{\infty })$. Da gemäß (5.28)

(5.29) $\Vert x^{k+1}-x^{*}\Vert \le \epsilon (x^k)\Vert x^k-x^{*}\Vert$

für alle k gilt, folgt schließlich die superlineare Konvergenz von $(x^k)$.

Gilt nun (5.25) auf ${𝒰}_{\delta }(x^{*})$, dann liegt für jedes $k$ mit $x^{*}$ und $x^k$ auch $x^{*}+s(x^k-x^{*})$ für alle $s\in [0,1]$ in ${𝒰}_{\delta }(x^{*})$ und folgt somit

$\Vert {𝒥}_F(x^{*}+s(x^k-x^{*}))-{𝒥}_F(x^{*})\Vert \le L\Vert x^k-x^{*}\Vert .$

Aus (5.27) gewinnt man damit für alle $k$ die Abschätzung

$\epsilon (x^k)\le 2\beta \{L+\frac{1}{2}L\}\Vert x^k-x^{*}\Vert =3\beta L\Vert x^k-x^{*}\Vert$

Letzteres zeigt zusammen mit (5.29) die quadratische Konvergenz der Folge $(x^k)$.

q.e.d.

Beispiel 5.19

Gesucht sei die Lösung $x^{*}:=(x_1^{*},x_2^{*}{)}^T$ der beiden Gleichungen

(5.30) $\begin{array}{c}{F}_1(x_1,x_2):=x_1^2+x_2^2+0.6x_2-0.16=0,\\ F_2(x_1,x_2):=x_1^2-x_2^2+x_1-1.6x_2-0.14=0,\end{array}$

für die $x_1^{*},x_2^{*}>0$ gilt, wobei wir hier keine Abbruchschranke $\epsilon >0$ angeben. Die Jacobi-Matrix von $F$ lautet

${𝒥}_F(x)=\left(\begin{array}{cc}2x_1& 2x_2+0.6\\ 2x_1+1& -2x_2-1.6\end{array}\right).$

Für $(x_1^0,x_2^0{)}^T:=(0.6,0.25{)}^T$ erhält man somit das lineare Gleichungssystem (5.24)

$\left(\begin{array}{cc}1.2& 1.1\\ 2.2& -2.1\end{array}\right)\left(\begin{array}{c}{h}_1\\ h_2\end{array}\right)=-\left(\begin{array}{c}0.4125\\ 0.3575\end{array}\right).$

Dieses besitzt die Lösung

$\left(\begin{array}{c}{h}_1^0\\ h_2^0\end{array}\right)=\left(\begin{array}{c}-0.254960\\ -0.096862\end{array}\right),$

so dass sich

$\left(\begin{array}{c}{x}_1^1\\ x_2^1\end{array}\right)=\left(\begin{array}{c}0.60\\ 0.25\end{array}\right)+\left(\begin{array}{c}-0.254960\\ -0.096862\end{array}\right)=\left(\begin{array}{c}0.345040\\ 0.153138\end{array}\right)$

ergibt mit dem Defekt

$\sqrt{[F_1(x_1^1,x_2^1){]}^2+[F_2(x_1^1,x_2^1){]}^2}=0.0928827.$

Mit $(x_1^1,x_2^1{)}^T$ verfährt man nun analog usw. Für die ersten vier Iterationen ergibt sich insgesamt die folgende Tabelle:

$\begin{array}{cccccc}k& x_1^k& x_2^k& \Vert F(x^k)\Vert & h_1^k& h_2^k\\ 0& 0.600000+0& 0.250000+0& 0.545859+0& -0.254960+0& -0.096862+0\\ 1& 0.345040+0& 0.153138+0& 0.928827-1& -0.675094-1& -0.306747-1\\ 2& 0.277531+0& 0.122463+0& 0.658124-2& -0.564594-2& -0.279860-2\\ 3& 0.271885+0& 0.119664+0& 0.464212-4& -0.406023-4& -0.210055-4\\ 4& 0.271845+0& 0.119643+0& 0.241346-8& & \end{array}$

Das Newton-Verfahren, Algorithmus 9, ist invariant gegenüber affin-linearen Transformationen (Übung!). Dies bedeutet, wenn $A\in {ℝ}^{n\times n}$ eine beliebige reguläre Matrix und $c\in {ℝ}^n$ irgendein Vektor: Ist $\{x^k\}$ die durch das lokale Newton-Verfahren für den Startpunkt $x^0$ erzeugte Iteriertenfolge zur Bestimmung einer Lösung des Gleichungssystems $F(x)=0$, so erzeugt das Verfahren bei Anwendung auf das System

$G(z):=F(Az+c)=0$

für den Startpunkt $z^0:=A^{-1}(x^0-c)$ die Iteriertenfolge $\{z^k\}$ mit

$z^k=A^{-1}(x^k-c)\iff x^k=A{z}^k+c.$

Verfahren, die invariant gegenüber affin-linearen Transformationen sind, gelten gegenüber Verfahren, die diese Eigenschaft nicht besitzen, insofern als robuster, als ihre Konvergenzgeschwindigkeit weit weniger von den gerade vorliegenden speziellen Daten abhängt. Anders als z. B. bei dem CG-Verfahren zur Lösung linearer Gleichungssysteme mit symmetrischer, positiv definiter Matrix (s. Kanzow) ändert sich beim lokalen Newton-Verfahren insbesondere durch eine (affin-)lineare Transformation der Variablen die Konvergenzgeschwindigkeit des Verfahrens nicht. Denn ist $\epsilon >0$ eine vorgegebene Abbruchschranke, so gilt aufgrund der oben beschriebenen Invarianz gegenüber affin-linearen Transformationen und der sich daraus ergebenden Identitäten

$\Vert G(z^k)\Vert =\Vert F(A{z}^k+c)\Vert =\Vert F(x^k)\Vert$

die Äquivalenz

$\Vert F(x^k)\Vert \le \epsilon \iff \Vert G(z^k)\Vert \le \epsilon .$

Bei Verfahren, die wie die CG-Verfahren nicht invariant gegenüber affin-linearen Transformationen sind, kann man zwar möglicherweise die Konvergenzgeschwindigkeit durch eine geeignete Wahl der Matrix $A$ erheblich beschleunigen, ist es aber häufig nicht vorhersehbar, ob das Verfahren für die aktuellen Daten langsam konvergiert, oder ist es nicht klar, ob gegebenenfalls eine geeignete Transformation zur Konvergenzbeschleunigung gefunden werden kann. Mit

$p^k:={[{𝒥}_F(x^k)]}^{-1}F(x^k)$

lautet die Iterationsvorschrift des Newton-Verfahrens

$x^{k+1}:=x^k+p^k,k=0,1,\dots .$

Die Richtung $p^k$ bezeichnet man dabei auch als Newton-Richtung in $x^k$.

Es gibt eine große Zahl von Varianten des Newton-Verfahrens, die zum Ziel haben, den Konvergenzbereich des Verfahrens zu vergrößern und/oder seinen numerischen Aufwand zu reduzieren. So kann man das Newton-Verfahren in gewisser Weise globalisieren, indem man eine geeignete Schrittweite $t_k>0$ einführt und

$x^{k+1}:=x^k+t_k{p}^k,k=0,1,\dots$

definiert. Dabei wählt man $t_k$ beispielsweise als (Näherungs-)Lösung des Problems

(5.31) $\underset{t\ge 0}{\min }{\Vert F(x^k+t{p}^k)\Vert }_2,$

da ja ${\Vert F(x^{k+1})\Vert }_2$ möglichst klein werden sollte. Von dem so modifizierten sog. gedämpften Newton-Verfahren kann man unter relativ schwachen Voraussetzungen für jeden Startpunkt $x^0$ einer geeigneten, hinreichend großen Menge Konvergenz zeigen. (Man hat sich dabei zu überlegen, dass ein solches $t_k$ existiert und eine positive Zahl ist. Da eine Lösung des globalen Optimierungsproblems (5.31) im Allgemeinen nicht realistisch ist, wählt man die Schrittweite $t_k$ häufig aber auf eine andere Weise; siehe z. B. Stoer, wo für eine solche andere Schrittweitenwahl auch ein Konvergenzsatz zu finden ist.)

Eine weitere praktisch relevante Modifikation des Newton-Verfahrens besteht darin, die numerisch aufwendig zu berechnende Jacobi-Matrix ${𝒥}_F(x^k)$ im Verfahren durch eine geeignete Näherung $H_k\in {ℝ}^{n\times n}$ zu ersetzen, wobei $H_k$ alleine aus den Daten $x^k,x^{k-1},F(x^k)$ und $F(x^{k-1})$ numerisch relativ günstig berechnet werden kann und somit insbesondere keine partiellen Ableitungen benötigt werden. Wir kennen ein solches Vorgehen schon vom Sekantenverfahren her, bei dem der Faktor

$\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})},$

der eine Näherung für $1/f^{\prime }(x_k)$ darstellt, in der Iterationsvorschrift vorkommt. Verfahren dieses Typs werden als Sekanten- oder Quasi-Newton-Verfahren bezeichnet. Das bekannteste ist das Broyden-Verfahren.

Quasi-Newton-Verfahren haben vor allem im Zusammenhang mit der Bestimmung von Extremalpunkten von $F$ und damit der Lösung des Systems $\mathrm{\nabla }F(x)=0$ große Bedeutung, da man ja bei Anwendung des Newton-Verfahrens in einem solchen Fall in jeder Iteration die Hesse-Matrix ${\mathrm{\nabla }}^{2}F(x^k)$ für $F$, also etwa $n^2/2$ partielle Ableitungen zweiter Ordnung zu berechnen hat. Von solchen Quasi-Newton-Verfahren gibt es eine Reihe von Varianten, die sich durch die Wahl der $H_k$ unterscheiden, wobei man im Fall der Lösung von Optimierungsaufgaben zusätzlich bestrebt ist, die positive oder negative (Semi-)Definitheit der Hesse-Matrix in einer Umgebung des Extremalpunktes auch für die $H_k$ zu erreichen. Die verbreitetste Methode ist das BFGS-Verfahren, das nach seinen Erfindern Broyden, Fletcher, Goldfarb und Shanno benannt wurde, die das Verfahren 1970 unabhängig voneinander vorschlugen. Es hat sich herausgestellt, dass dieses unter allen Quasi-Newton-Verfahren das wohl unempfindlichste gegenüber der Schrittweitenwahl ist. (Es gibt Alternativen zu der numerisch teuren Berechnung der Minimumschrittweite in (5.31).)

Von Quasi-Newton-Verfahren kann man keine quadratische Konvergenz erwarten, da sie ja weniger Information der Funktion als das Newton-Verfahren verwenden. Unter geeigneten Voraussetzungen lässt sich aber für sie im Allgemeinen superlineare Konvergenz nachweisen. Die schlechtere Konvergenzrate gegenüber dem Newton-Verfahren wird jedoch durch den pro Iteration erforderlichen, geringeren numerischen Aufwand kompensiert.

Allgemein kann man sagen, dass das Newton-Verfahren wohl das erfolgreichste und verbreitetste Verfahren der Mathematik ist. Es wurde im Hinblick auf die Lösung zahlloser Probleme, auch solcher in unendlich-dimensionalen Räumen, verallgemeinert und modifiziert.