Nun zur Konvergenz des Newton-Verfahrens. Ich zeige hier die Konvergenz unter ganz bestimmten Voraussetzungen. Man kann die Konvergenz auch für viel schwächere Voraussetzungen, also im viel allgemeineren Fall, zeigen. Allerdings muss man dann um einiges mehr Arbeit hinein stecken in den

Beweis. Also sei f nun zweimal differenzierbar und wir nehmen an, dass wir auch wirklich eine Nullstelle a haben. Dann nehmen wir um a ein Intervall, so eine r Umgebung, das heißt das sieht so aus, das Intervall von a minus r bis a

plus r und zwar so, dass ich auf diesem Intervall die ersten Ableitungen von der Null weg beschränken kann. Das heißt, es gibt so eine Konstante m1, die echt größer ist als Null, so dass alle Beträge der ersten Ableitungen

größer oder gleich m1 sind für x aus dem Intervall. Und dann nehme ich mir weiter noch eine Schranke m2 der zweiten Ableitungen, das heißt Betrag f2 von x ist kleiner gleich m2 für alle x aus diesem Intervall.

Hier hat sich noch ein Epsilon eingeschlichen, entschuldigen Sie, das kann ein R sein. So, das sind unsere Voraussetzungen und wählen wir dann unseren Startwert x1 der Newton-Folge, so dass er zum einen in diesem Intervall liegt, dass zum anderen aber auch noch der Abstand von diesem Startwert

zu a schon kleiner ist als 2m1 durch m2. Ja, das kann, wenn 2m1 durch m2 kleiner ist als R, eine wirkliche Einschränkung an unserem Startwert sein. So, aber wenn wir das haben, dann konvergiert das Newton-Verfahren

quadratisch. Und was heißt das? Das heißt, dass ich das n-plus-erste Folgeglied beziehungsweise seinen Abstand zur Nullstelle immer abschätzen kann durch den Abstand des n-plus-ersten Folgegliedes zur Nullstelle zum Quadrat

mal dieser Konstante m2 durch 2m1. Gut, zum Beweis schauen wir uns mal an, was wir eigentlich wissen. Nun, wir müssen eine Abschätzung für diesen Abstand

des n-plus-ersten Folgegliedes zur Nullstelle herstellen. Da setzen wir erst mal ein, wie wir das n-plus-erste Folgeglied erhalten, nämlich durch die Newton-Iteration. Das heißt, das ist xn minus f von xn durch f' von xn minus a. Und da bringe ich mal alles auf einen

Bruchstrich, f' von xn will ich da raushaben. So, dann habe ich hier einen großen Betragsstrich. Dann habe ich hier erst mal oben ein minus f von xn

und dann habe ich noch ein minus f' von xn mal a minus xn.

Also, diese beiden Zahlen, die muss ich mit f' von xn erweitern. Das erklärt diesen Faktor und die Vorzeichen, die stimmen auch. Gut, so und jetzt schauen wir uns mal an, was hier steht. Erst mal schreibe ich die

erste Ableitung im Nenner ab. So, bis auf das Minus. Ich kann mir eigentlich das Minus auch sparen. Ich betrachte es ja nur betragsmäßig. Was steht denn da? Da steht gerade die Gleichung der Tangente an die

Funktionsgrafen im Punkt xn und zwar ausgewertet im Punkt a. So und das

heißt, ja ich habe hier hinten, ich schreibe es nochmal ab, minus f von xn minus f' von xn mal a minus xn. So, da kann ich ja jetzt locker mal noch f von a dazu addieren, weil ich weiß, a ist eine Nullstelle von f, also ist es

Null und ich mache keinerlei Fehler. Jetzt steht hier f von a minus die Tangente in xn ausgewertet im Punkt a. Ja, das erkennen wir, das ist das Restglied, das ersten Tellerpolynom von f, erstes Tellerpolynom und zwar an

der Entwicklungsstelle xn und das werte ich aus in a. Und ja, was weiß ich

jetzt? Jetzt weiß ich ja, für das Restglied existiert eine Zahl xi zwischen a und xn derart, dass ich das Restglied schreiben kann als f. Das ist

das erste, also brauche ich f2 von xi halbe mal a minus xn zum Quadrat. Gut, das heißt, hier habe ich die Formel für das Restglied reingesteckt und

damit kann ich nun hier oben weiter schreiben. Das ist also betragsmäßig gleich die zweite Ableitung an der Stelle xi durch zwei mal die erste Ableitung an der Stelle xn mal, ja hier kann ich auch xn minus a zum

Quadrat schreiben, betragsmäßig. So, und jetzt kann ich hier wiederum meine Schranken, die ich nach Voraussetzung gegeben habe, einsetzen. Das heißt, ich

weiß f2 Strich, das ist auf dem gesamten Intervall kleiner oder gleich betragsmäßig. Ja, und dieses xi, das liegt zwischen a und xn, also auf alle Fälle auch in diesem Intervall. Und im Nenner habe ich f Strich von xn

betragsmäßig. Nun, das kann ich nach unten abschätzen durch m1 und damit kann ich jetzt, weil es im Nenner steht, kann ich auch den ganzen Bruch abschätzen und dann habe ich hier eben noch mal ein xn minus a zum Quadrat.

Also schreiben wir es ruhig noch mal hin. Wir haben gerade gezeigt xn plus 1 minus a ist kleiner gleich xn minus a zum Quadrat mal m2 durch 2 m1 und

ist nun, ja, ziehe meine Konstante, die ich kriege, indem ich den Abstand vom ersten Glied zur Nullstelle nehme, mal m2 durch 2 m1. Ist das kleiner als 1?

Ja, das habe ich gerade so gewählt. Deswegen ist diese Voraussetzung hier ja, dass das hier wirklich kleiner als 1 ist. Dann folgt also, wenn ich diese Abschätzung benutze, dass x2 minus a kleiner gleich c mal x1 minus a ist

beziehungsweise induktiv sehe ich, dass ich xn minus a abschätzen kann durch c

hoch 2 n minus 1 minus 1 mal x1 minus a. So und jetzt habe ich c das heißt das hier geht gegen Null und demnach muss auch xn minus a gegen

Null gehen und demnach weiß ich diese Folge konvergiert. Zu dem gerade bewiesenen sind noch einige Bemerkungen angebracht. Also zum einen habe ich ja im Beweis dieses Startintervall symmetrisch um die Nullstelle

gewählt. Ich habe das gemacht, damit ich mir sicher sein konnte, dass ich alle Folgeglieder wirklich auch in diesem Intervall drin liegen habe. Aber praktisch ist das unmöglich. Also ich kann keinen Startintervall wählen,

das symmetrisch um die Nullstelle liegt, bevor ich die Nullstelle nicht kenne. Und da ich die, der ja durchs Newtonverfahren bestimmen will, kann ich das nicht. Aber es reicht eigentlich auch zu fordern, dass das Startintervall, das Startbereich so was erfüllt, wie das mit x auch x minus f von x durch f Strich von x in dem Intervall enthalten sind. Dann hatte ich ja auch

als Voraussetzung gefordert, dass die ersten Ableitungen von Null weg beschränkt sind im Startintervall. Und es ist eine ganz schön harte Forderung, die manchmal gar nicht so einfach zu erfüllen ist. Aber in der Praxis, also wenn man das Newtonverfahren irgendwo implementiert,

dann kümmert einen das gar nicht. Also man wählt fast beliebig ein x1, schaut vielleicht noch das f Strich an diesem Startwert x1, ungleich Null ist. Aber ansonsten ist es so gut wie beliebig und schaut einfach mal, was passiert im Newtonverfahren. Sieht man nicht, dass

sich sehr schnell eine Konvergenz abzeichnet, dann bricht man ab und wählt ein neues x1. Denn man weiß, diese quadratische Konvergenz, die ist so schnell. Ich sehe auch schnell, dass da was passiert. Gut, ja, es kann natürlich auch sein, und das kann man erst mal nicht

beeinflussen, dass man halt in A nicht nur eine Nullstelle, sondern einen kritischen Punkt hat. Das heißt, dass auch die Ableitung von F eine Nullstelle in A hat. Da konvergiert das Newtonverfahren nicht mehr so gut. Also das kriegt da wirklich rein, was halt da anliegt, dass die Steigungen von den Tagenten dann auch um A rum

sehr gering sind. Aber man weiß, sich zu helfen. Ich hatte ja schon gesagt, dass es auch genutzt werden kann, um kritische Punkte zu finden. Nämlich, wenn man statt F mit F Strich arbeitet. Also man arbeitet mit F Strich statt mit F. So bestimmt das, was da steht.

Und zuletzt noch, was heißt eigentlich quadratische Konvergenz? Ja, das heißt, dass sich in jedem Schritt die Anzahl der

Nachkommastellen, die schon korrekt sind, verdottet. Also wenn wir wissen, dass x n minus a sagen wir mal schon kleiner oder gleich 10 hoch minus k ist, dass da also k Nachkommastellen sozusagen stimmen, dann ist ja x n minus a zum

Quadrat kleiner gleich 10 hoch minus 2 k. Das heißt, abgesehen von der Konstante, die wir davor drin haben, verdoppeln sich die Nachkommastellen. Und wir hatten ja schon durch das Intervallschachtelungsverfahren ein

Verfahren zur Nullstellenbestimmung kennengelernt und hatten damals gesagt, ja, das konvergiert exponentiell. Und das möchte ich Ihnen jetzt erklären, warum diese quadratische Konvergenz trotzdem besser ist. Wir müssen nämlich sagen, was exponentiell ist dabei. Also bei der

Intervallschachtelung, da halbiert man, ja, das war das Intervall-Halbierungsverfahren, da halbiert man in jedem Schritt die Intervall und damit kommt man eben, ja, um die Hälfte näher an die Nullstelle

heran. So das heißt, wir haben hier ein, das ist ein halb hoch n mal den Abstand vom Startwert zur Nullstelle. So und diese Konstante hier, die ist

schön kleiner als eins und diese Konstante hier, das ist exponentieller Abfall. Aber im Newton-Verfahren, da steht ja xn plus 1 minus a, das ist jetzt

kleiner gleich, ich schreibe hier mal ein großes c dafür hin für diese Konstante, die aus den Abschätzungen gebildet wird, mal xn minus a zum Quadrat. So und wenn ich das hier weiterführe, da kriege ich raus, dass das c hoch n mal, nee, hoch 2n, mal xn minus a hoch 2n ist. So und da sehen Sie, ich

habe hier einen linearen Term, ja, ich habe also, abgesehen von der konstantischen linearen Sache, wenn es quadratisch ist, dann ist es dann nach

n Schritten schon eine Potenz 2 hoch n, die ich dadurch gewinne und das ist um einiges stärker. Zum Abschluss noch eine schöne Anwendung und zwar die Ernährung ente Wurzeln. Wir können aus einer positiven prioren Zahl b die

ente Wurzel ziehen, das heißt wir nehmen an, dass n größer oder gleich 2 ist. So und der Satz sagt eben, es gibt diese rekursive Folge xm, Startwert 1

und xm plus 1 ist gegeben als 1 minus 1 durch n mal xm plus b durch n mal xm hoch n minus 1. So das ist nicht viel anderes, nein, es ist das Newtonverfahren, das da drin steckt, bevor wir uns das angucken. Nur noch zwei kurze

Bemerkungen. Zum einen sehen wir, wenn b hier eine rationale Zahl ist und x1 ist 1, dann sind alle diese Bildungen, die ich hier mache, wieder rational. Das heißt, versuche ich die Ente Wurzel aus einer rationalen Zahl zu ziehen, dann kriege ich hier auch eine Ernährung durch rationale Zahlen.

Und meine zweite Bemerkung ist die, vielleicht kennen sie dieses Verfahren schon im Spezialfall n gleich 2, also für Quadratwurzel. Da ist es nämlich gleich dem Herunverfahren und da ist die Rekursion, wenn wir hier endlich zwei

einsetzen, sehen wir das, das ist ein halb mal xm plus b durch xm. So und jetzt noch zum Beiß. Das ist wie gesagt das Newtonverfahren, das heißt, wir brauchen eine Funktion, für die wir Nullstelle finden können. Ja, das ist natürlich, wenn wir die

Nullstelle mit Newtonverfahren. So, das heißt, wir brauchen als erstes mal die Ableitung von f, das ist n mal xn minus 1 und dann kriegen wir also die

Newtonrequersion als xm plus 1 gleich xm minus f von xm, also xm hoch n minus b

durch f Strich von xm, das ist n mal xm hoch n minus 1. So, und das können wir noch ein bisschen anders schreiben. Das heißt, xm plus 1 ist, ja, ich bringe das

erst mal auf einen Buchstrich und dann kann ich wieder kürzen und ich nehme hier einfach die ersten beiden zu manten. Dann kriege ich einmal ein 1 mal xm und davon muss ich wieder ein Minus 1 durch n noch nehmen für den zweiten Term. So und

dann habe ich noch den letzten Term, das ist b durch n mal xm hoch n minus 1. Das ist die Iteration, die da angegeben ist. Ja, streng genommen müssten wir jetzt

noch die Voraussetzungen aus unserem Satz prüfen, damit wir uns auch sicher sein können, dass das konvergiert, aber das nur als Beispiel, das ist ein wirklich fest etabliertes Verfahren, wenn man schnell eine Intervurzel bestimmen will. Wir müssen es jetzt nicht im Detail noch wirklich tief begründen.