Kurs:Numerik I/Nullstellenverfahren

Nullstellenbestimmung reeller Funktionen einer Veränderlichen

Häufig sucht man in Anwendungen für eine gegebene stetige Funktion $f\in 𝒞([a,b],ℝ)$ eine Nullstelle (auch Wurzel genannt), d. h. einen Punkt $x^{*}\in (a,b)$ mit $f(x^{*})=0$.

Diffentialrechnung - Extremalpunkte

Weiß man zusätzlich, dass die Funktion 2x stetig differierbar $g\in {𝒞}^2([a,b],ℝ)$ ist, benötigt man für die Bestimmung der Extremalpunkte einer Funktion $g$ die Nullstellen der 1. Ableitung und man setzt dazu $f:=g^{\prime }$ und wendet auf $f$ das Nullstellenverfahren an. Mit der 2. Ableitung entscheidet man, ob ein Minimum oder Maximum vorliegt.

Wurzeln mit Nullstellenverfahren bestimmen

Wenn die Wurzel $\sqrt{c}$ für $c>0$ näherungsweise bestimmen möchte, sucht man z.B. für nach der Nullstelle der Funktion $f(x):=x^2-c$

• in dem Intervall $[a,b]:=[1,c]$ für $c\ge 1$ und
• in dem Intervall $[a,b]:=[0,1]$ für $0<c<1$.

Fixpunkte

Ein Fixpunkt $x\in [a,b]$ einer Funktion $g:[a,b]\to ℝ$ ist ein Punkt mit der Eigenschaft $g(x)=x$, also dem Schnittpunkt des Graphen von $g$ mit der Winkelhalbierenden. Auch diese Problem kann man in ein Problem der Nullstellensuche überführen, indem man $f:[a,b]\to ℝ$ über $f(x):=g(x)-x$ definiert. Ein Fixpunkt von $g$ ist damit eine Nullstelle von $f$.

Aufgaben

• Analysieren die folgenden Nullstellenverfahren und berechnen Sie die Wurzel von 5 näherungsweise mit Tabellenkalkulation (LibreOffice).
• Definieren Sie eine Funktion $f:[a,b]\to ℝ$ mit der man die 3. Wurzel aus $c\in ℝ$ bestimmen kann.
• Geben Sie eine Funktion $f:[a,b]\to ℝ$ mit dem Intervall $[a,b]\subset ℝ$ an, wobei man mit Nullstellenverfahren die Stellen $x\in [a,b]$ näherungsweise bestimme kann, für die $sin(x)=cos(x)$ gilt.

Startintervall für Nullstellenverfahren

Ist eine Funktion $f:[a,b]\to ℝ$ gehen, so ist es im allgemeinen nicht notwendigerweise der Fall, dass $f(a)\cdot f(b)<0$ gilt und damit eine Vorzeichenwechsel bei den Intervallrenzen vorliegt. In einem solchen Fall kann ggf. auf ein Teilintervall $[\alpha ,\beta ]$ in $[a,b]$ übergehen, für das $f(\alpha )\cdot f(\beta )<0$.

Teilintervall mit Vorzeichenwechsel

Um eine möglichst gute Startnäherung für jede solche Nullstelle zu erhalten, sucht man dann Teilintervalle $[\alpha ,\beta ]$ in $[a,b]$, in dem ein Vorzeichenwechsel $f(\alpha )\cdot f(\beta )<0$ vorliegt und möglichst nur eine Nullstelle $x^{*}\in [\alpha ,\beta ]$ liegt.

Zerlegung des Intervalls in Teilintervalle

Dazu berechnet man im Allgemeinen Funktionswerte $f({\xi }_i)$ mit

${\xi }_i:=a+ih(i=0,\dots ,n),h:=\frac{b-a}{m}$

für ein gegebenes, genügend großes $m\in \mathbb{N}$. Dadurch zerlegt man das Ausgangsintervall $[a,b]$ in $m$ Teilintervalle und identifiziert die Teilintervalle in denen ein Vorzeichenwechsel vorliegt.

Funktionswerte an Gitterpunkten

Die Menge aller ${\xi }_i$ bezeichnet man auch als ein Gitter in $[a,b]$, die ${\xi }_i$ selbst als Gitterpunkte und den Prozess der Auswahl von endlich vielen Punkten aus $[a,b]$ als Diskretisierung des Intervalls.

Zwischenwertsatz - Analysis

Sind $f({\xi }_i)\ne 0$ und $f({\xi }_{i+1})\ne 0$ (anderenfalls hätte man eine Nullstelle von $f$ gefunden) und ist

$f({\xi }_i)\cdot f({\xi }_{i+1})<0(i=0,\dots ,n-1),$

so muss $f$ nach dem Zwischenwertsatz im Intervall $[{\xi }_i,{\xi }_{i+1}]$ eine (einfache) Nullstelle besitzen und können wir $\alpha :={\xi }_i$ und $\beta :={\xi }_{i+1}$ setzen.

Anwendung unterschiedlicher Nullstellenverfahren

Es werden im Folgenden eine Reihe von Verfahren behandelt, die, ausgehend von einem solchen Intervall mit Vorzeichenwechsel, unter geeigneten Bedingungen eine genäherte Nullstelle von $f$ liefern. Dabei geht man davon aus, dass eine Funktion zumindest stetig ist, denn $f\in 𝒞([a,b],ℝ)$ liefert dem Zwischenwertsatz die Existenz einer Nullstelle $x^{*}\in (a,b)$ mit $f(x^{*})=0$. Für das Newtonverfahren benötigt man noch die zusätzliche Eigenschaft der Differenzierbarkeit, weil die Ableitung $f^{\prime }(x_n)$ für die Interation von $x_n$ zu $x_{n+1}$ benötigt wird.

Bemerkung

Im Folgenden wird vorausgesetzt, dass $f(a)\cdot f(b)<0$ für $f:[a,b]\to ℝ$ erfüllt ist.

Das Bisektionsverfahren

Das erste Verfahren, das wir vorstellen wollen, ist das Intervallschachtelungs- oder auch Bisektionsverfahren. Bei diesem wird, beginnend mit dem Intervall $[a_0,b_0]\subseteq [a,b]$, eine Folge von Intervallen $[a_k,b_k]$ erzeugt, so dass $f(a_k)f(b_k)<0$ und damit $x^{*}\in (a,b)$ gilt. Dieses Verfahren verwendet in jeder Iteration als einzige Information nur die Vorzeichen der Funktionswerte an den Randpunkten des aktuellen Intervalls, so dass keine schnelle Konvergenzgeschwindigkeit zu erwarten ist.

Animation - Bisektionsverfahren

Algorithmus - Bisektionsverfahren

(0) Gib $a_0,b_0\in [a,b]$ mit $f(a_0)\cdot f(b_0)<0$ und $\epsilon >0$. Setze $k=0$.

(1) Berechne $x_{k+1}:=\frac{1}{2}(a_k+b_k)$ und $f(x_{k+1})$.

(2) Falls $|f(x_{k+1})|\le \epsilon$, stop!

(3) Falls $f(a_k)f(x_{k+1})<0$, setze $a_{k+1}:=a_k,b_{k+1}:=x_{k+1}$.

Falls $f(a_k)\cdot f(x_{k+1})>0$, setze $a_{k+1}:=x_{k+1},b_{k+1}:=b_k$.

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

Intervallbreite im Bisektionsverfahren

Offenbar gilt für die Länge der bei der Bisektionsmethode erzeugten Intervalle $[a_k,b_k]$

$|b_k-a_k|=\frac{1}{2}|b_{k-1}-a_{k-1}|=\frac{1}{2^k}|b_0-a_0|,k=0,1,\dots .$

Wenn Algorithmus in Schritt (2) nicht abgebrochen wird, folgt damit

$\underset{k\to \mathrm{\infty }}{\lim }|b_k-a_k|=0.$

Einschachtelung der Nullstelle

Wegen $a_{k+1}\le x^{*}\le b_{k+1}$ sowie $x_{k+1}=a_{k+1}$ oder $x_{k+1}=b_{k+1}$ hat man weiter mit der Abschätzung der Intervallbreite

$|x_{k+1}-x^{*}|\le |b_{k+1}-a_{k+1}|\le \frac{1}{2^{k+1}}|b_0-a_0|,k=0,1,\dots$

und demnach

$\underset{k\to \mathrm{\infty }}{\lim }{x}_k=\underset{k\to \mathrm{\infty }}{\lim }{a}_k=\underset{k\to \mathrm{\infty }}{\lim }{b}_k=x^{*}.$

Bemerkung - Abbruchkriterium Bisektionsverfahren

Die Abbruchbedingung (2) $|f(x_{k+1})|\le \epsilon$ schließt u.a. den Fall mit ein, dass $f(x_{k+1})=0$ gilt, also bei der Intervallmitte bereits die gesuchte Nullstelle gefunden wurde.

Abbruchkriterium

Da $f(x^{*})=0$ und $f$ stetig ist, ist daher das Abbruchkriterium $|f(x_{k+1})|\le \epsilon$ in Schritt (2) von Algorithmus nach endlich vielen Schritten erfüllt. Statt dieses Abbruchkriteriums, das beispielsweise im Fall

$0\le f(x)\ll 1,x\in [a,b]$

ungünstig ist, könnte man alternativ oder zusätzlich auch die Abfrage $|b_k-a_k|\le \vartheta$ mit einer kleinen Konstante $\vartheta >0$ als Abbruchkriterium verwenden.

Beispiel - Genauigkeit Bisektionsverfahren

Ist $b_0-a_0=1$, so folgt aus (5.6)

$|x_1-x^{*}|\le \frac{1}{2}=0.5,$

$|x_5-x^{*}|\le \frac{1}{2^5}\approx 0.031,$

$|x_{20}-x^{*}|\le \frac{1}{2^{20}}\approx 0.00000095.$

Bemerkung - Konvergenzgeschwindigkeit und Stabilität

Das Bisektionsverfahren ist ein sicheres und numerisch stabiles Verfahren, aber mit langsamer Konvergenz. Es konvergiert i. a. nicht einmal linear. Für die Fehler zweier aufeinander folgender Iterierter $x_{k+1}$ und $x_k$ kann sogar gelten:

$|x_{k+1}-x^{*}|>|x_k-x^{*}|.$

Beispiel für Fehlervergrößerung in einem Iterationsschritt

Für die Funktion $f(x):=x+0.1$ kann man die Nullstelle $x^{*}=-0.1$ in $[-1,1]$ direkt angeben. Im Beispiel wird diese mit Bisektionsverfahren berechnet. Ferner ist $f$ stetig und erfüllt $f(-1)<0$ und $f(1)>0$ die Voraussetzung für die Anwendung des Bisektionsverfahrens:

$[a_0,b_0]:=[-1,1],x_1:=0,f(x_1)=0.1>0,$

$[a_1,b_1]:=[-1,0],x_2:=-0.5,f(x_2)=-0.4<0$

und demzufolge wird der Fehler von $x_1$ zu $x_2$ größer:

$|x_1-x^{*}|=0.1<|x_2-x^{*}|=0.3.$

Die Regula falsi

Bei der Regula Falsi verwendet man im $k$-ten Schritt die Sekante, welche die Punkte $(a_k,f(a_k))$ und $(b_k,f(b_k))$ verbindet. Diese Gerade kann durch Graph einer Funktion $g_k(x)=c_k\cdot x+d_k$ dargestellt werden

$g_k(x)=\underset{=:c_k}{\underbrace{\frac{f(b_k)-f(a_k)}{b_k-a_k}}}(x-a_k)+f(a_k)d_k:=f(a_k)-c\cdot a_k$

Schnittpunkt mit der x-Achse

Der Graph der $k$-ten Sekante $g_k$ schneidet die $x$-Achse in dem folgenden Punkt:

$x_{k+1}:=a_k-f(a_k)\frac{b_k-a_k}{f(b_k)-f(a_k)}.$

Der Punkt $x_{k+1}$ wird nun als neue Näherung für $x^{*}$ genommen. Ansonsten verfährt man wie bei der Bisektion.

Aufgabe

Zeigen Sie, dass der Punkt $x_{k+1}:=a_k-f(a_k)\frac{b_k-a_k}{f(b_k)-f(a_k)}$ ein Nullstelle der Funktion $g_k:[a_k,b_k]\to ℝ$ ist.

Animation - Regular Falsi

Algorithmus (Regula Falsi)

Man startet mit einer stetigen Funktion $f:[a_0,b_0]\to ℝ$, die auf dem Intervall $[a_0,b_0]$ einen Vorzeichenwechsel bei den Funktionswerten besitzt (d.h. $f(a_0)\cdot f(b_0)<0$). Dann berechnet in jedem Iterationsschritt jeweils den Schnittpunkt der Sekante durch die Punkte $(a_k,f(a_k))$ und $(b_k,f(b_k))$. Die Schnittpunkt teilt das Intervall $[a_k,b_k]$ in zwei Teilintervalle. Wenn $f(x_{k+1})=0$ gilt, hat man eine Nullstelle gefunden. Falls das $f(x_{k+1})=0$, betrachtet man das Teilintervall $[a_{k+1},b_{k+1}]$ in dem dann ein Vorzeichnenwechsel vorliegt.

Algorithmus - Regula Falsi

(0) Gib $a_0,b_0\in [a,b]$ mit $f(a_0)\cdot f(b_0)<0$ und $\epsilon >0$. Setze $k=0$.

(1) Berechne $x_{k+1}:=a_k-f(a_k)\frac{b_k-a_k}{f(b_k)-f(a_k)}$ sowie $f(x_{k+1})$.

(2) Falls $|f(x_{k+1})|\le \epsilon$, stop!

(3) Falls $f(a_k)f(x_{k+1})<0$, setze $a_{k+1}:=a_k,b_{k+1}:=x_{k+1}$.

Falls $f(a_k)f(x_{k+1})>0$, setze $a_{k+1}:=x_{k+1},b_{k+1}:=b_k$.

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

Bemerkung - Abbruchkriterium Regula Falsi

Die Abbruchbedingung (2) $|f(x_{k+1})|\le \epsilon$ schließt wieder den Fall mit ein, dass $f(x_{k+1})=0$ gilt, also die Sekante durch die Punkte ${(}_k,f{(}_k))$ die x-Achse bereits in der gesuchten Nullstelle schneidet.

Fehlerabschätzung - Regula Falsi

Für die Regula Falsi ist keine aussagekräftige Fehlerabschätzung erhältlich. Aber sie konvergiert unter gewissen Voraussetzungen mindestens linear (siehe z. B. Stoer). Man beachte, dass wegen $f(a_k)\cdot f(b_k)<0$ keine Auslöschung bei der Berechnung von $x_{k+1}$ eintritt, so dass das Verfahren überdies numerisch stabil ist. Die erzeugten Näherungen $x_k$ liegen alle im Ausgangsintervall $[a_0,b_0]$ und können alle auf einer Seite der gesuchten Nullstelle liegen.

Sekantenverfahren

Beim Sekantenverfahren wählt man, ähnlich wie bei der Regula Falsi, die Nullstelle einer Sekante als neue Iterierte, wobei jeweils die Sekante von den beiden letzten Iterationspunkten $(x_{k-1},f(x_{k-1}))$ und $(x_k,f(x_k))$ des Graphen von $f$ verbunden werden. Der nächste Stelle $x_{k+1}$ der Iteration wieder der Schnittpunkt der Sekante $g_k$ mit der $x$-Achse, wenn dieser existiert.

Unterschiede - Regula Falsi und Sekantenverfahren

• Bei Regula Falsi wird die Sekante zwischen den Punkten $(a_k,f(a_k))$ und $(b_k,f(b_k))$ gebildet.
• Beim Sekantenverfahren wird die Sekante zwischen den beiden letzten Iterationspunkten $(x_{k-1},f(x_{k-1}))$ und $(x_k,f(x_k))$ des Graphen von $f$ gebildet.

Konsequenzen der Unterschiede - Regula Falsi und Sekantenverfahren

• Bei Regula Falsi wird die Sekante in einem Teilintervall $[a_k,b_k]$ zwischen den Punkten $(a_k,f(a_k))$ und $(b_k,f(b_k))$ gebildet, in dem ein Vorzeichenwechsel $f(a_k)\cdot f(b_k)<0$. Damit liegt die nachfolgende Iterationstelle $x_{k+1}$ in dem Teilintervall $[a_k,b_k]$.
• Beim Sekantenverfahren kann es möglich sein, dass die Sekantensteigung zwischen den beiden letzten Iterationspunkten $(x_{k-1},f(x_{k-1}))$ und $(x_k,f(x_k))$ so gering ist, dass der Schnittpunkt mit der $x$-Achse außerhalb des Definitionsbereiches $[a,b]$ liegt.
• Im ungünstigen Fall, dass $f(x_{k-1})=f(x_k)$ gilt, hat die Sekante sogar überhaupt keinen Schnittpunkt mit der $x$-Achse und das Verfahren bricht ab.

Wahl der Startwerte - Sekantenverfahren

Im Allgemeinen kann man zwei Startstellen $x_{-1},x_0\in [a,b]$ wählen, die die Eigenschaft haben sollten, dass die zugehörige Sekante $g_0$ eine Schnittpunkt mit der $x$-Achse in $[a,b]$ besitzt. Dabei muss nicht notwendig $f(x_{-1})\cdot f(x_0)<0$ gelten. Wenn allerdings die Voraussetzung $f(a)\cdot f(b)<0$ erfüllt ist, so kann man analog zu Regula Falsi $x_{-1}:=a$ und $x_0:=b$ wählen. In weiteren Iterationsschritten werden sich dann aber die Sekanten von Regula Falsi und dem Sekantenverfahren unterscheiden.

Berechnung der Nullstelle der Sekanten

Die Nullstelle der Sekante beim Sekantenverfahren ist offenbar durch

$x_{k+1}:=x_k-f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$

gegeben.

Animation (Sekantenverfahren)

Algorithmus - Sekantenverfahren

(0) Gib $x_{-1},x_0\in [a,b]$ und $\epsilon >0$. Berechne $f(x_{-1})$ sowie $f(x_0)$ und setze $k=0$.

(1) Berechne

$x_{k+1}:=x_k-f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$

sowie $f(x_{k+1})$.

(2) Falls $|f(x_{k+1})|\le \epsilon$, stop!

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

Bemerkung - Korrektur der Iterierten

Man beachte hier beim Sekantenverfahren in Schritt (1), dass man die Iterierte im $(k+1)$-ten Schritt eines Verfahrens meist als Korrektur der Iterierten im $k$-ten Schritt schreibt, also in der Form $x_{k+1}:=x_k+h_k$ mit einem $h_k\in ℝ$ mit:

$h_k:=-f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$

Bei Konvergenz des Verfahrens gegen $x^{*}\ne 0$ muss man $|h_k|\ll |x_k|$ zumindest für größere $k$ voraussetzen, dass also die Iterationsstellen genügend nahe bei der gesuchten Nullstelle $x^{*}\ne 0$ liegen.

Konvergenz vom Sekantenverfahren

Während bei dem Bisektionsverfahren und der Regula Falsi die Konvergenz durch den Vorzeichenwechsel in dem jeweils betrachtet nächsten Teilintervall $[a_k,b_k]$ mit $x_{k+1}\in [a_k,b_k]$ und den sich immer weiter halbierende Intervallen sofort einleuchtet, ist das beim Sekantenverfahren nicht klar.

Monotonie

Bei Regula Falsi wird die Sekante bzgl. der Intervallgrenzen von $[a_k,b_k]$ gebildet, was zu einer monoton steigenden Folge $(a_k{)}_{k\in {\mathbb{N}}_0}$ und einer monoton fallenden Folge $(b_k{)}_{k\in {\mathbb{N}}_0}$ führt, die beide gegen die Nullstelle konvergieren $x^{*}$. Beim Sekantenverfahren weist die Folge der Iterationsstellen $(x_k{)}_{k\in {\mathbb{N}}_0}$ in der Regel kein Monotonieverhalten auf (weder steigend noch fallend)

Intervalle aus Interationstellen

Auch der Fall

• $x_{k+1}\in [x_{k-1},x_k]$ bei $x_{k-1}\le x_k$ bzw.
• $x_{k+1}\in [x_k,x_{k-1}]$ bei $x_k\le x_{k-1}$

muss im Allgemeinen beim Sekantenverfahren nicht gelten, so dass das Verfahren im Allgemeinen nur lokal konvergiert. Genauer kann man den folgenden Satz beweisen (vgl. Isaacson and Keller):

Unterschied zwischen Sekantenverfahren und Regula Falsi

Bei der Anwendung des Sekantenverfahrens wird die Sekanten immer bzgl. der beiden vorhergehenden Iterationsstellen $x_{k-1}$ und $x_k$ gebildet und damit die nächste Iterationsstelle $x_{k+1}$ berechnet, während bei der Regula Falsi die Sekante bzgl. der linken und rechten Intervallgrenze $a_k$ bzw. $b_k$ gebildet wird, in dem ein Vorzeichenwechsel der stetigen Funktion zu finden ist.

Konsequenz der Unterschiede zwischen Sekantenverfahren und Regula Falsi

Als Konsequenz der der Unterschiede zwischen Sekantenverfahren und Regula Falsi ergibt sich daher,

• dass bei der Regula Falsi der nächste Iterationspunkt $x_{k+1}$ immer im Intervall $[a_n,b_n]$ liegen muss,
• dass bei dem Sekantenverfahren der Schnittpunkt der Sekante mit der $x$-Achse nicht notwendigerweise zwischen $x_n$ und $x_{n-1}$ liegen muss.

Ferner ergeben sich auch Unterschiede in der Konvergenzgeschwindigkeit.

Satz - Konvergenz Sekantenverfahren

Sei $f\in {𝒞}^2([a,b],ℝ)$, und es existiere ein $x^{*}\in [a,b]$ mit $f(x^{*})=0$ und $f^{\prime }(x^{*})\ne 0$. Sind die Anfangsnäherungen $x_{-1}$ und $x_0$ hinreichend nahe bei $x^{*}$ gewählt, so konvergiert nach Streichung des Abbruchkriterium in Schritt (2) durch das Sekantenverfahren erzeugte Folge $(x_k)$ superlinear gegen $x^{*}$ von der Ordnung $p:=(1+\sqrt{5})/2=1.618\dots$.

Bemerkung - Konvergenz Sekantenverfahren

Das Sekantenverfahren konvergiert also im Allgemeinen schneller als das Bisektionsverfahren und die Regula Falsi. Anders als diese, neigt es aber zu instabilem Verhalten, da der Fall $sgn(f(x_k))=sgn(f(x_{k-1}))$ und damit Auslöschung bei der Berechnung von $x_{k+1}$ eintreten kann.

Die schnelle Konvergenz des Sekantenverfahrens soll an einem Beispiel demonstriert werden.

Beispiel - Berechnung Wurzel 2 mit Sekantenverfahren

Es soll $\sqrt{2}$ berechnet werden. Dies kann man tun, indem man die positive Nullstelle der Funktion $f(x):=x^2-2$. Mit dem Startintervall $[a,b]:=[-2,0]$ sucht man die Nullstelle $x^{*}=-\sqrt{2}$ und z.B. mit dem Startintervall $[a,b]:=[0,5]$ bestimmt man näherungsweise die Nullstelle $x^{*}=\sqrt{2}$. In dem folgenden Beispiel setzen wir $[a,b]:=[0,5]$.

Näherungsweise Angabe der Nullstelle

Der gesuchte Wert lautet auf 12 Stellen hinter dem Dezimalpunkt genau

$\sqrt{2}=1.414213562373\dots .$

Vereinfachung der Interationsvorschrift

Die Iterationsvorschrift des Sekantenverfahrens lässt sich hier durch Anwendung der 3. Binomischen Formel im Quotienten wie folgt vereinfachen:

$x_{k+1}:=x_k-\underset{=f(x)}{\underbrace{(x_k^2-2)}}\cdot \frac{x_k-x_{k-1}}{x_k^2-x_{k-1}^2}=x_k-\frac{x_k^2-2}{x_k+x_{k-1}}.$

Startstellen des Sekantenverfahrens

Die Startstellen sollte nahe bei der gesuchten Nullstelle liegen und verwendet daher als Startstellen $x_{-1}:=1.3$ und $x_0:=1.5$

Interationsschritt 1

Man errechnet mit $x_{-1}:=1.3$ und $x_0:=1.5$ für $k:=0$

$x_1:=1.5-\frac{(1.5{)}^2-2}{1.5+1.3}=1.41071428571.$

mit $x_0:=1.5$ und $x_1:=1.41071428571$ für $k:=1$

Interationsschritt 2

$x_2:=1.41071428571-\frac{(1.41071428571{)}^2-2}{1.41071428571+1.5}$

usw.

Iteriertenfolge

Insgesamt erhält man die Iteriertenfolge

• $x_1=\underset{\_}{1.41}071428571,$
• $x_2=\underset{\_}{1.414}11042945,$
• $x_3=\underset{\_}{1.414213}69013,$
• $x_4=\underset{\_}{1.41421356237},\dots ,$

wobei die richtigen Ziffern jeweils unterstrichen sind.

Bemerkung - Berechnungsaufwand

Hätte man mit der ursprünglichen Formel gearbeitet, wie man das meist in der Praxis zu tun hat, so hätte man 2 Funktionsauswertungen von $f$ zur Berechnung von $x_1$ und jeweils eine für die von $x_2$ bis $x_4$, d. h. insgesamt 5 Funktionsauswertungen zur Berechnung von $x_4$ benötigt.

Funktionsauswertungen sind in vielen Situationen ein gutes praktisches Vergleichskriterium für unterschiedliche Algorithmen zur Lösung eines Problems, da diese häufig die numerisch teuersten Teilaufgaben bei der Problemlösung darstellen.

Newton-Verfahren für Nullstellen

Es sei nun $f\in {𝒞}^1[a,b]$ und die Existenz eines $x^{*}\in (a,b)$ mit $f(x^{*})=0$ vorausgesetzt. Beim Newton-Verfahren benötigt man nur eine Startnäherung $x_0\in (a,b)$ für $x^{*}$. Ist $x_k$ die Näherung für $x^{*}$ zu Beginn der $k$-ten Iteration, so wählt man bei diesem Verfahren die Nullstelle $x_{k+1}$ der Tangente im Punkt $(x_k,f(x_k))$ an den Graphen von $f$ als nächste Näherung.

Gleichung der Tangente

Die Funktion $g_k:[a,b]\to ℝ$, dessen Graph die Tangente in $x_k\in [a,b]$ beschreibt, wird wie folgt definiert:

$g(x):=f(x_k)+f^{\prime }(x_k)\cdot (x-x_k)$

gegeben, so dass man $g(x)=0$ für folgendes $x_{k+1}$ erfüllt ist:

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

erhält.

Aufgaben

• Erläutern Sie an einem Schaubild/Zeichnung die Herleitung des Funktionsterms von $g(x)$!
• Erläutern Sie an einem eigenzeichnet Steigungsdreieck in einer Skizze die geometrische Herleitung des Terms $x_{k+1}:=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$!

Bemerkung - Eigenschaft der Ableitung an der gesuchten Nullstelle

Wenn wir beispielsweise $f^{\prime }(x^{*})\ne 0$ voraussetzen ($x^{*}$ ist dann eine einfache Nullstelle), können wir dabei zumindest für solche $x_k$, die nahe bei $x^{*}$ liegen, $f^{\prime }(x_k)\ne 0$ annehmen. Wenn die Ableitung stetig ist, gibt es eine Umgebung $(x^{*}-\epsilon ,x^{*}+\epsilon )$, in der $f^{\prime }$ nur positiv (streng monoton steigend) oder nur negativ ist (streng monoton fallend).

Abgebraische und geometrische Konsequenzen von f'(x)=0

• (Algebra) Wenn man sich die Iterationsvorschrift vom Newtonverfahren ansieht, führt $f^{\prime }(x_k)=0$ im Nenner zu einem undefinierten Iterationsschritt für die Definition von $x_{k+1}$.
• (Geometrie) Im Fall $f(x_k)\ne 0$ und $f^{\prime }(x_k)=0$ hätte die Tangente als Parallele zur $x$-Achse auch keine Nullstelle, wobei das Newton-Verfahren keine nächste Iterationsstelle liefert.

Animation der Iteration

Algorithmus - Newton-Verfahren

(0) Wähle ein $\epsilon >0$ und $x_0\in (a,b)$, berechne $f(x_0)$ und setze $k:=0$.

(1) Berechne $f^{\prime }(x_k)$,

(5.9) $x_{k+1}:=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$

und $f(x_{k+1})$.

(2) Falls $|f(x_{k+1})|\le \epsilon$, stop!

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

Beispiel - Newton-Verfahren zur Berechnung der Wurzel 2

Man betrachtet nun eine Funktion $f:[1,2]\to ℝ$ mit dem Funktionsterm $f(x):=x^2-2$ und damit ist $f^{\prime }(x)=2x$. Gesucht ist die positive Nullstelle $\sqrt{2}\approx 1.414213562373$ von $f$.

Berechnung der Iterationsvorschrift

Die Iterationsvorschrift des Newton-Verfahrens lässt sich hier schreiben als

$x_{k+1}:=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}=x_k-\frac{x_k^2-2}{2x_k}=\frac{1}{2}{x}_k+\frac{1}{x_k}.$

Startwert der Iteration

Beginnend mit $x_0:=1.5\in [1,2]$ und $k:=0$ berechnet man die Iterierten

• $x_1=\underset{\_}{1.41}6,$
• $x_2=\underset{\_}{1.41421}568627,$
• $x_3=\underset{\_}{1.4142135623}8,\dots .$

Bemerkung - Notation

Die unterstrichen Ziffern nach dem Iterationsschritt bezeichnen, wie viele Stelle bereits mit der gesuchten Nullstelle von $f(x):=x^2-2$ übereinstimmen

Berechnungsaufwand

Bei direkter Verwendung von der allgemeinen Iterationsvorschrift

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$

muss man für jeden Iterationsschritt neben Division und Subtraktion einmal $f$ und einmal $f^{\prime }$ auswerten. Das wären für die Berechnung von $x_3$ jeweils 3 Funktionsauswertungen von $f$ und $f^{\prime }$, also insgesamt 6 Funktionsauswertungen erforderlich gewesen. Das Newtonverfahren ist also in diesem Fall ein sehr schnelles Verfahren.

Vergleich mit Sekantenverfahren im Beispiel

Bei diesem Beispiel $f(x):=x^2-2$ und der Wahl von Startwerten (!) erreicht das Sekantenverfahren aber mit etwas weniger Aufwand sogar etwas höhere Genauigkeit.

Konvergenz des Newton-Verfahrens

Wir wollen uns nun mit der Konvergenz des Newton-Verfahrens beschäftigen. Dazu holen wir etwas weiter aus. Für eine gegebene Funktion $g:{ℝ}^n\to {ℝ}^n$ nennen wir einen Punkt $x^{*}\in {ℝ}^n$ mit

$g(x^{*})=x^{*}$

einen Fixpunkt von $g$. Weiter sprechen wir bei der Iterationsvorschrift

$x^{k+1}:=g(x^k),k=0,1,2,\dots$

von der Fixpunktiteration mit der Verfahrensfunktion $g$. Ist $g$ stetig und konvergiert die Iteriertenfolge, so muss ihr Grenzwert offenbar notwendig ein Fixpunkt von $g$ sein. Man beachte in diesem Zusammenhang, dass $x^{*}$ genau dann Fixpunkt von $g$ ist, wenn $x^{*}$ Nullstelle z. B. der Funktion $f(x):=g(x)-x$ ist, dass also die Probleme der Bestimmung einer Nullstelle und der eines Fixpunktes einer Funktion äquivalent sind.

Bemerkung

Wir beweisen nun folgenden allgemeinen Satz über die lokale Konvergenz der Fixpunktiteration, wobei

${𝒰}_{\delta }(x^{*}):=\{x\in ℝ:|x-x^{*}|<\delta \}$

eine offene $\delta$-Umgebung des Punktes $x^{*}\in ℝ$ bezeichne.

Konvergenzsatz - Fixpunktiteration

Sei $g:ℝ\to ℝ$ gegeben und $x^{*}\in ℝ$ Fixpunkt von $g$. Weiter sei $g$ in $x^{*}$ $p$-mal differenzierbar mit einem $p\in \mathbb{N}$, und es gelte entweder

• $g^{(k)}(x^{*})=0,k=1,\dots ,p-1,$ für $p\ge 2$ oder
• $0<|g^{\prime }(x^{*})|<1,$ für $p=1.$

Dann existiert ein $\delta >0$, so dass die durch $x_{k+1}:=g(x_k),k\in {\mathbb{N}}_0$ erzeugte Iteriertenfolge $(x_k)$ für jeden Startpunkt $x_0\in {𝒰}_{\delta }(x^{*})$ gegen $x^{*}$ konvergiert und zwar mindestens von der Ordnung $p$. Im Fall $g^{(p)}(x^{*})\ne 0$ ist die Konvergenzordnung genau $p$.

Beweis - Konvergenzsatz - Fixpunktiteration

Taylorentwicklung von $g$ um $x^{*}$ liefert für beide Fälle in (5.10)

$g(x)=\sum _{i=0}^p\frac{g^{(i)}(x^{*})}{i!}(x-x^{*}{)}^i+o(|x-x^{*}{|}^p)$

$=\underset{=x^{*}}{\underbrace{g(x^{*})}}+\frac{g^{(p)}(x^{*})}{p!}(x-x^{*}{)}^p+o(|x-x^{*}{|}^p)$ für $x\to x^{*}$

Somit hat man

(5.11) $|\frac{g(x)-x^{*}}{(x-x^{*}{)}^p}-\frac{g^{(p)}(x^{*})}{p!}|\to 0(x\to x^{*}),$

so dass zu einem gegebenen $\epsilon >0$ ein $\delta >0$ existiert und

$|g(x)-x^{*}|\le (\epsilon +\frac{|g^{(p)}(x^{*})|}{p!})|x-x^{*}{|}^p$

(5.12) $=[C|x-x^{*}{|}^{p-1}]|x-x^{*}|=\tilde{C}(x)|x-x^{*}|,x\in {𝒰}_{\delta }(x^{*})$

mit $C:=\epsilon +|g^{(p)}(x^{*})|/p!$ und $\tilde{C}(x):=C|x-x^{*}{|}^{p-1}$ gilt. Im Fall $p=1$ sei dabei $\epsilon$ so klein gewählt, dass

$\tilde{C}:=\tilde{C}(x)\equiv C=\epsilon +|g^{\prime }(x^{*})|<1$

ist, was aufgrund der Voraussetzung $|g^{\prime }(x^{*})|<1$ möglich ist. Für $p>1$ ist es offenbar möglich, $\delta$ so klein zu wählen, dass $\tilde{C}(x)\le 0.5=:\tilde{C}<1$ für alle $x\in {𝒰}_{\delta }(x^{*})$ folgt.

Die Ungleichung (5.12) impliziert nun für $|x-x^{*}|\le \delta$ auch $|g(x)-x^{*}|\le \delta$ und damit im Fall $x_0\in {𝒰}_{\delta }(x^{*})$ auch $x_k\in {𝒰}_{\delta }(x^{*})$ für alle $k\in \mathbb{N}$, so dass man

$|x_{k+1}-x^{*}|\le C|x_k-x^{*}{|}^p\le \tilde{C}|x_k-x^{*}|\le {\tilde{C}}^{k+1}|x_0-x^{*}|,k\in {\mathbb{N}}_0$

hat und daraus wegen $\tilde{C}<1$ die Konvergenz $\underset{k\to \mathrm{\infty }}{\lim }{x}_k=x^{*}$ von mindestens der Ordnung $p$ schließen kann. Ist die Zusatzbedingung $g^{(p)}(x^{*})\ne 0$ erfüllt und wird oben $\epsilon$ so gewählt, dass $0<\epsilon <|g^{(p)}(x^{*})|/p!$ gilt, so gilt wegen (5.11)

(5.13) $|g(x)-x^{*}|\ge (\frac{|g^{(p)}(x^{*})|}{p!}-\epsilon )|x-x^{*}{|}^p=:\hat{C}|x-x^{*}{|}^p,x\in {𝒰}_{\delta }(x^{*})$

Daraus folgt die genaue Konvergenzordnung $p$ in diesem Fall, denn wäre diese mindestens $p+1$, so folgte mit (5.13) für ein $\bar{C}$ und ein $k_0\in \mathbb{N}$

$\hat{C}|x_k-x^{*}{|}^p\le |x_{k+1}-x^{*}|\le \bar{C}|x_k-x^{*}{|}^{p+1},k\ge k_0$

und damit im Widerspruch zu Konvergenz von $(x_k)$ gegen $x^{*}$

$0<\frac{\hat{C}}{\bar{C}}\le |x_k-x^{*}|,k\ge k_0.$

q.e.d.

In dem folgenden Satz wird nun unter verschiedenen Voraussetzungen eine jeweilige Konvergenzordnung des Newton-Verfahrens angegeben.

Konvergenzsatz - Newton-Verfahren

Es sei $f:ℝ\to ℝ$ gegeben und es existiere $x^{*}\in ℝ$ mit $f(x^{*})=0$. Mit einem $\eta >0$ sei weiter für Aussage (i) $f\in {𝒞}^3({𝒰}_{\eta }(x^{*}))$ und für Aussage (ii) $f\in C^2({𝒰}_{\eta }(x^{*}))$. Dann gilt nach Streichung von Schritt (2) für die durch das Newton-Verfahren (Algorithmus 8) erzeugte Folge $(x_k)$:

• (i) Ist $f^{\prime }(x^{*})\ne 0$, dann existiert ein $\delta \in (0,\eta ]$, so dass $(x_k)$ für jeden Startpunkt $x_0\in {𝒰}_{\delta }(x^{*})$ gegen $x^{*}$ konvergiert und zwar mindestens quadratisch. Im Fall $f^{″}(x^{*})=0$ konvergiert $(x_k)$ sogar von einer Ordnung $p\ge 3$.
• (ii) Ist $x^{*}$ andererseits eine $m$-fache Nullstelle von $f$ mit einem $m\ge 2$, d. h., ist

$f(x)=(x-x^{*}{)}^{m}z(x),z(x^{*})\ne 0$

und ist weiter $z$ in $x^{*}$ zweimal differenzierbar, so ist die Iterationsfunktion

(5.14) $g(x):=\{\begin{array}{cc}x-\frac{f(x)}{f^{\prime }(x)},& fallsx\ne x^{*},\\ x^{*},& fallsx=x^{*}\end{array}$

des Newton-Verfahrens differenzierbar in $x^{*}$ mit (5.15) $g^{\prime }(x^{*})=1-\frac{1}{m}$ und existiert ein $\delta \in (0,\eta ]$, so dass $(x_k)$ für jeden Startpunkt $x_0\in {𝒰}_{\delta }(x^{*})$ (genau) linear gegen $x^{*}$ konvergiert.

Beweis.

Die Behauptung folgt mit Satz 5.9, wenn man diesen auf $g$ in (5.14) anwendet sowie mit den folgenden Darstellungen. Im Fall (i) zeigt man zunächst die Stetigkeit von $g,g^{\prime }$ und $g^{″}$ in $x^{*}$. Man ermittelt dann

$g^{\prime }=1-\frac{(f^{\prime }{)}^2-f{f}^{″}}{(f^{\prime }{)}^2}=\frac{f{f}^{″}}{(f^{\prime }{)}^2},g^{″}=\frac{(f^{\prime }{)}^3{f}^{″}+f(f^{\prime }{)}^2(f^{‴})-2f{f}^{\prime }(f^{″}{)}^2}{(f^{\prime }{)}^4},$

so dass also

$g(x^{*})=x^{*},g^{\prime }(x^{*})=0,g^{″}(x^{*})=\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}$

gilt. Damit folgt die Behauptung.

Im Fall (ii) erhält man

$f^{\prime }(x)=m(x-x^{*}{)}^{m-1}z(x)+(x-x^{*}{)}^m{z}^{\prime }(x)$

und somit

(5.16) $\frac{f(x)}{f^{\prime }(x)}=\frac{(x-x^{*})z(x)}{mz(x)+(x-x^{*})z^{\prime }(x)}.$

Wegen $z(x^{*})\ne 0$ folgt damit $\underset{x\to x^{*}}{\lim }f(x)/f^{\prime }(x)=0$ und ist demzufolge $g$ aus (5.14) stetig in $x^{*}$. Weiter hat man mit (5.16) wegen $f(x^{*})=0$

$g^{\prime }(x^{*})=\underset{h\to 0}{\lim }\frac{g(x^{*}+h)-g(x^{*})}{h}=\underset{h\to 0}{\lim }\frac{x^{*}+h-\frac{f(x^{*}+h)}{f^{\prime }(x^{*}+h)}-x^{*}}{h}=1-\underset{h\to 0}{\lim }\frac{f(x^{*}+h)}{h{f}^{\prime }(x^{*}+h)}$

$=1-\underset{h\to 0}{\lim }\frac{hz(x^{*}+h)}{h[mz(x^{*}+h)+h{z}^{\prime }(x^{*}+h)]}=1-\frac{1}{m}.$

Also ist $0<g^{\prime }(x^{*})<1$ und damit insbesondere auch $g^{\prime }(x^{*})\ne 0$.

q.e.d.

Man beachte, dass das Newton-Verfahren pro Iteration zwei Funktionsauswertungen benötigt, während das Sekanten-Verfahren nur eine verlangt. Im Fall, dass der Grenzwert eine einfache Nullstelle ist, konvergiert letzteres Verfahren unter geeigneten Voraussetzungen aber nur superlinear, während das Newton-Verfahren dann mindestens quadratisch konvergiert. Es stellt sich also die Frage, welches der Verfahren in der Praxis effizienter ist. Bemerkenswert ist es daher, dass man zeigen kann, dass das Sekantenverfahren, wenn man zwei Iterationen zu einer zusammenfasst und es damit etwa gleichen Aufwand pro Iteration wie das Newton-Verfahren bekommt, eine Konvergenzrate von mindestens $p:=2.618$ hat, und es folglich lokal schneller als das Newton-Verfahren konvergiert. Allerdings neigt das Sekanten-Verfahren, anders als das Newton-Verfahren, aufgrund von Auslöschungen zu instabilem Verhalten.

Siehe auch

• Konvergenzraten
• Zwischenwertsatz

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Nullstellenverfahren
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.