Nichtlineare Gleichungssysteme, Nullstellen

Allgemeine Problemstellung

Gegeben sei eine Funktion

$$f:\R^n\to \R^n$$

Es ist nun eine Stelle $\xi\in \R^n$ gesucht, so dass

$$f(\xi)=0:=(0,0,\hdots,0)^T\in\R^n$$ (1)

ist. Eine solche Stelle $\xi$ heißt Nullstelle der Funktion $f$ .

Problem (1) ist äquivalent zu

$$f_i(\xi_1,\hdots,\xi_n)=0 i=1,\hdots,n f_i:\R^n\to \R$$ (2)

Das System (2) nennt man ein nichtlineares Gleichungssystem.
Ist dagegen zusätzlich noch ein Vektor $z\in \R^n$ gegeben, und möchte man dann das allgemeine Problem lösen, ein $\xi\in \R^n$ zu bestimmen, so dass

$$f(\xi)=z$$

so kann man $g(x)=f(x)-z$ setzen. Dann gilt

$$f(\xi)=z \Longleftrightarrow g(\xi)=0$$

Es reicht also, ohne Einschränkung, Nullstellen einer Funktion bestimmen zu können. Wie bestimmt man aber nun ein solches $\xi$ ?

Einteilung der Verfahren

Schon von Polynomen mit einem Grad größer als 4 lassen sich die Nullstellen im Allgemeinen nicht mehr exakt bestimmen. Man versucht also nun eine Näherung $\tilde x$ der tatsächlichen Nullstelle $\xi$ zu berechnen. Allen Verfahren ist somit gemein, dass sie sich, ausgehend von einem oder mehreren Startwerten, (hoffentlich) immer mehr einer Lösung von (1) annähern. Man kann die Verfahren jedoch nach folgenden Kriterien unterscheiden:

• Dimension des Systems:
  Im Falle $n=1$ hat man mit dem Zwischenwertsatz ein wichtiges Hilfsmittel zur Verfügung, dass einem unter gewissen Voraussetzungen die Existenz einer Nullstelle garantiert. Dies lässt sich in einigen Verfahren ausnutzen.
  Im Falle $n\geq 2$ ist die Situation im Allgemeinen nicht mehr so einfach.
• Anzahl der Startwerte:
  Die Verfahren berechnen stets aus zurückliegenden Näherungen der Nullstelle eine weitere, von der man hofft dass sie näher an $\xi$ liegt als die vorherigen. Die Verfahren haben also die Form
  $$x_{i}=\Phi(x_{i-1},\hdots,x_{i-k})$$
  Dabei nennt man $\Phi$ die Iterationsfunktion, und diese greift auf genau $k$ vorherige Werte zurück.
  Das bedeutet aber dass man zunächst Werte $x_0,\hdots,x_{k-1}$ vorgeben muss, damit das Verfahren anlaufen kann.
• Verwendung der Ableitung:
  Bei einigen Verfahren hängt die Iterationsfunktion nur von der Funktion $f$ selbst ab, und nicht etwa noch von $f'$ $(n=1)$ oder $Df$ $(n\geq 2)$ . Dies ist von Vorteil, weil oft nicht einmal die Ableitung bekannt ist, oder es sehr aufwändig ist, diese zu berechnen. Dagegen können Informationen über die Ableitung der Funktion benutzt werden, um die Nullstellen mit unter sehr viel effektiver anzunähern.

Die Verfahren im R¹

Fixpunktiteration

Das Verfahren der Fixpunktiteration wird benutzt um eine Lösung der skalaren Gleichung $g(x)=x$ zu finden. Will man dagegen die Nullstelle einer Funktion $f$ finden, so definiert man $g(x)=f(x)+x$ und die Nullstelle von $f$ ist Fixpunkt von $g$ .

Das Verfahren besteht darin, einen Wert in $g$ einzusetzen, und dies mit dem Ergebnis zu wiederholen, usw.... Formal ergibt sich der Algorithmus

1. INIT: Gegeben sei $x_0$
2. $0\to k$
3. $g(x_k)\to x_{k+1}$
4. FALLS $\vert g(x_k)-x_{k+1}\vert<\textrm{tol}$
   $~~~~~$ RETURN $x_{k+1}$
5. $k+1\to k$
6. WEITER bei 3.

Der Banachsche Fixpunktsatz gibt an unter welchen Bedingungen das Verfahren konvergiert:
Sei $g:A\to A$ eine kontrahierende Abbildung, d.h.

$$\vert\vert g(x)-g(y)\vert\vert\leq L\vert\vert x-y\vert\vert$$

mit einem $L<1$ , auf einer abgeschlossenen Teilmenge $A$ eines Banach-Raumes. Dann konvergiert das Verfahren für alle Startwerte $x_0\in A$ gegen den eindeutig bestimmten Fixpunkt $\xi$ von $g(x)=x$ .

Das Bisektions- oder Intervallhalbierungsverfahren

Das Bisektionsverfahren wird verwandt um Nullstellen einer skalaren Funktion $f:\R\to \R$ zu bestimmen. Vorgegeben werden müssen zwei Stellen $x_0$ und $x_1$ , so dass $f(x_0)f(x_1)<0$ (d.h. die beiden Funktionswerte von $f$ haben unterschiedliches Vorzeichen). Also liegt zwischen $x_0$ und $x_1$ mindestens eine Nullstelle. Als neue Näherung wird dann die Mitte des Intervalls $[x_0,x_1]$ verwandt:

$$x_2:=\frac{x_0+x_1}{2}$$

Je nachdem welches Vorzeichen nun $f(x_2)$ hat, wird das Verfahren nun erneut entweder auf das linke oder im auf das rechte Teilintervall angewandt. Abgebrochen wird, falls das Intervall in dem die Nullstelle sicher liegt hinreichend klein geworden ist.

1. INIT: Gegeben ist ein Intervall $[a, b]$ mit $f(a)f(b)<0$
2. $(a+b)/2\to m$
3. FALLS $f(m)=0$
   $~~~~~$ RETURN $m$
4. FALLS $\vert a-b\vert<\textrm{tol}$
   $~~~~~$ RETURN $m$
5. FALLS $f(a)f(m)<0$
   $~~~~~$ DANN WEITER bei 1. mit $[a,m]$
   $~~~~~$ SONST WEITER bei 1. mit $[m,b]$

Das Verfahren konvergiert unter den gegebenen Voraussetzungen immer gegen eine Nullstelle $\xi$ .

Regula Falsi

Achtung: Hier gilt Regula Falsi $\neq$ Sekantenverfahren, an anderen Stellen könnten abweichende Bezeichnungen verwandt werden!
Regula Falsi wird verwandt um Nullstellen einer skalaren Funktion $f:\R\to \R$ zu bestimmen. Das Verfahren ist identisch zum Bisektionsverfahren, nur wird nicht einfach die Mitte des Intervalls verwandt, sondern es wird die Nullstelle der interpolierenden Geraden durch $\left(x_{k}/f(x_{k})\right)$ und $\left(x_{k+1}/f(x_{k+1})\right)$ verwandt:

$$0=f(a) + (x - a)\frac{f(b) - f(a)}{b - a}$$

$$\Rightarrow x=\frac{b f(a)-a f(b)}{f(a)-f(b)}$$

1. INIT: Gegeben ist ein Intervall $[a, b]$ mit $f(a)f(b)<0$
2. $(b f(a)-a f(b))/(f(a)-f(b))\to m$
3. FALLS $f(m)=0$
   $~~~~~$ RETURN $m$
4. FALLS $\vert a-b\vert<\textrm{tol}$
   $~~~~~$ RETURN $m$
5. FALLS $f(a)f(m)<0$
   $~~~~~$ DANN WEITER bei 1. mit $[a,m]$
   $~~~~~$ SONST WEITER bei 1. mit $[m,b]$

Das Verfahren konvergiert unter den gegebenen Voraussetzungen immer gegen eine Nullstelle $\xi$ .

Sekantenverfahren

Achtung: Hier gilt Regula Falsi $\neq$ Sekantenverfahren, an anderen Stellen könnten abweichende Bezeichnungen verwandt werden!
Das Sekantenverfahren wird verwandt um Nullstellen einer skalaren Funktion $f:\R\to \R$ zu bestimmen. Verzichtet man in der Regula Falsi auf die Forderung von verschiedenen Vorzeichen an den Enden des jeweiligen Intervalls, erhält man das Sekantenverfahren:

1. INIT: Gegeben sind $x_0, x_1$ mit $x_0\neq x_1$
2. $0\to k$
3. $(x_{k+1} f(x_{k})-x_{k} f(x_{k+1}))/(f(x_{k})-f(x_{k+1}))\to x_{k+2}$
4. FALLS $f(x_{k+2})=0$
   $~~~~~$ RETURN $x_{k+2}$
5. FALLS $\vert x_{k+2}-x_{k+1}\vert<\textrm{tol}$
   $~~~~~$ RETURN $x_{k+2}$
6. $k+1\to k$
7. WEITER bei 3.

Das Verfahren ist nicht stabil, falls in Schritt 3. $f(x_k)\approx f(x_{k+1})$ gilt, und daher ist die Konvergenz nicht immer garantiert, es besitzt aber lokal in einer hinreichend kleinen Umgebung der Nullstelle die Konvergenzordnung $\phi=\frac{1}{2}(1+\sqrt{5})\approx 1.618$ .

Newton Verfahren

Das Newton-Verfahren wird verwandt um Nullstellen einer skalaren Funktion $f:\R\to \R$ zu bestimmen. Dabei muss $f$ mindestens einmal stetig differenzierbar sein.
Das Newton-Verfahren kann als Verbesserung der Sekantenmethode angesehen werden, nur wird dabei die Sekante durch eine Tangente ersetzt. Aus der Tangentengleichung

$$y=f(a)+(x-a)f'(a)$$

ergibt sich aus $y=0$ die Vorschrift:

$$\displaystyle x=a-\frac{f(a)}{f'(a)}$$

Dies führt zu folgendem Verfahren:

1. INIT: Gegeben sei $x_0$
2. $0\to k$
3. $$x_{k}-\frac{f(x_k)}{f'(x_k)}\to x_{k+1}$$
4. FALLS $f(x_{k+1})=0$
   $~~~~~$ RETURN $x_{k+1}$
5. FALLS $\vert x_{k+1}-x_{k}\vert<\textrm{tol}$
   $~~~~~$ RETURN $x_{k+1}$
6. $k+1\to k$
7. WEITER bei 3.

In Schritt 3. kann eine Division durch 0 auftreten, falls $f$ an der Stelle $x_k$ eine waagerechte Tangente besitzt. Das Verfahren bricht dann erfolglos ab.
Das Newton Verfahren ist für eine einfache Nullstelle, und falls $f$ dreimal stetig differenzierbar ist, in einer hinreichend kleinen Umgebung der Nullstelle mindestens quadratisch konvergent.

Vereinfachtes Newton Verfahren

Um nicht in jedem Schritt $f'$ auswerten zu müssen (teuer), kann man den Wert von $f'(x_0)$ in den folgenden Iterationen weiterbenutzen, wenn man annimmt dass dieser eine gute Näherung der folgenden $f'(x_k), k\geq 1$ darstellt. Dies führt zu folgendem Verfahren:

1. INIT: Gegeben sei $x_0$
2. $0\to k$
3. $$x_{k}-\frac{f(x_k)}{f'(x_0)}\to x_{k+1}$$
4. FALLS $f(x_{k+1})=0$
   $~~~~~$ RETURN $x_{k+1}$
5. FALLS $\vert x_{k+1}-x_{k}\vert<\textrm{tol}$
   $~~~~~$ RETURN $x_{k+1}$
6. $k+1\to k$
7. WEITER bei 3.

Das vereinfachte Newton Verfahren konvergiert allerdings nur noch linear.

Das mehrdimensionale Newton-Verfahren

Das mehrdimensionale Newton-Verfahren wird benutzt um Nullstellen $\bar{x}$ von Funktionen $f \in C({\mathbb{R}}^n,{\mathbb{R}}^n)$ zu bestimmen. Hierbei muss $\mathcal{D}f$ invertierbar sein.
Es ist die folgende Gleichung zu lösen:

$$x_{n+1} = x_n - \mathcal{D}f (x_n)^{-1} f(x_n).$$

Man erhält das lineare Gleichungssystem

$$\mathcal{D}f(x_n) d_n = f(x_n).$$

Dieses wird numerisch gelöst. Dann ergibt sich $x_{n+1}$ aus

$$x_{n+1}= d_n + x_n.$$

Verfahren von Muller

Eine weitere Verallgemeinerung des Sekantenverfahrens stellt das Verfahren von Muller dar. Dabei wird nicht durch 2 Punkte eine Sekante gelegt, sondern durch 3 Punkte eine interpolierende Parabel. Das führt zu folgendem Algorithmus:

1. INIT: Gegeben sind $x_0, x_1, x_2$ paarweise verschieden
2. $0\to k$
3. Bestimme eine Parabel $P$ durch die Punkte $\left(x_{k}/f(x_{k})\right)$ , $\left(x_{k+1}/f(x_{k+1})\right)$ und $\left(x_{k+2}/f(x_{k+2})\right)$ .
4. FALLS $P$ keine reelle Nullstelle besitzt
   $~~~~~$ RETURN "`Fehler"'
5. Die Nullstelle die am dichtesten bei $x_{k+2}$ liegt $\to$ $x_{k+3}$ .
6. FALLS $f(x_{k+3})=0$
   $~~~~~$ RETURN $x_{k+3}$
7. FALLS $\vert x_{k+3}-x_{k+2}\vert<\textrm{tol}$
   $~~~~~$ RETURN $x_{k+3}$
8. $k+1\to k$
9. WEITER bei 3.