Hallo, das Thema von heute ist das Newton-Verfahren. Das ist streng genommen kein Optimierungsverfahren,

sondern ein Nullstellen-Algorithmus. Aber die Ideen von diesem Verfahren sind ähnlich wie

die, die man bei approximativen Optimierungsverfahren sieht. Und außerdem kann man es auch dazu nutzen,

um zum Beispiel Nullstellen von Gradienten zu finden, was ja wichtig ist, um kritische

Stellen zu finden von extremalen Problemen. Also wie schon gesagt, es geht es hier darum,

dass man Nullstellen von nicht-legalen Gleichungen sucht. Jetzt hier in dem Fall ihre x plus

x gleich 0. Also da gibt es einfach keine klaren Kandidaten für was diese Nullstelle

ist. Es muss auf jeden Fall irgendeine negative Zahl sein, also minus eins funktioniert schon

mal nicht, 0 ist auch zu groß und es gibt eine Zahl, die eine Nullstelle liefert. Also

wie sieht diese Funktion aus? Ungefähr so. Und es gibt hier irgendwo eine Nullstelle,

aber der numerische Wert für diese Nullstelle ist alles andere als trivial. Also er ist trivial

in dem Sinne, dass man weiß, es gibt eine Nullstelle, aber das ist nicht immer minus

eins oder minus eins aufgrund von zwei oder sonst irgendwas leichtes, was man hinschreiben

könnte. Und die Menge der nicht-linearen Gleichungen, zu denen man keine analytischen

Nullstellen finden kann, die ist deutlich größer als die, für die es Lösungsformen

gibt. Also es gibt Lösungsformen für lineare oder quadratische Polynome. Also wir wissen

a x² plus bx plus c gleich 0, das ist sehr einfach zu lösen. Da gibt es die quadratische

Lösungsformel oder auch für a x plus b gleich 0 natürlich. Es gibt auch noch für Polynome

von Grad 3 und 4 Formeln, die sich aber kein Mensch merken kann normalerweise und die auch

ein bisschen kundiziert abends zu werden sind und deswegen benutzt eigentlich keiner so

wirklich. Aber wenn man schon Polynome von Grad 5 oder größer anschaut, dann kann man

sogar beweisen, dass es keine Lösungsformel geben kann. Jetzt wie macht man das dann zum

Beispiel hier in diesem Fall, dass man Nullstellen findet. Und das erste was wir uns anschauen

werden ist das Bisektionsverfahren. Jetzt machen wir doch mal irgendeine Funktion, sieht vielleicht

so aus. Und wir starten damit, dass wir einen Punkt a nehmen, wo f von a größer als Null

ist und einen Punkt b, wo f von b kleiner als Null ist. Das ist normalerweise nicht so

schwierig zu finden, also irgendwie findet man schon Punkte mit verschiedenen Vorzeichen.

Und wenn wir eine stetige Funktion gegeben haben und wir gehen jetzt offen aus, dass

die Funktion f, die wir haben, stetig ist, dann wissen wir nach dem Zwischenmerz, dass

es irgendwo eine Nullstelle geben muss, die wir extern nehmen. Die ist irgendwo größer

als a und kleiner als b in diesem Intervall dazwischen. Und was man jetzt macht ist, man

nimmt jetzt mal den Mittelwertpunkt zwischen a und b, also a plus b halbe und dann guckt

man, ob der Wert positiv oder negativ ist, in dem Fall ist er positiv und dann weiß

man, dass zwischen a plus b halbe und b eine Nullstelle sein muss. Jetzt nimmt man wieder

den Mittelpunkt, das ist dann a plus b halbe plus b halbe. Das kann man natürlich vereinfachen,

aber das ist erstmal einfach nur a plus b halbe plus b halbe. Hier merkt man, aha wir

sind hier negativ, dann geht man wieder auf die Mitte, jetzt wird es schon langsam interessant,

also es könnte jetzt tatsächlich genau die Nullstelle sein, aber typischweise ist es

natürlich ein bisschen links davon oder rechts davon. Und so kessel man dann hier so nach

und nach das hier so ein und dann weiß man irgendwann, aha zum Beispiel hier in diesem

Intervall hier, da muss eine Nullstelle irgendwo drin liegen. Und weil das Intervall jedesmal

halbiert wird, schrumpft auch das Intervall jedesmal mit dem Faktor 2 zusammen, das heißt

wir wissen nach 1000 Schritten ist die Länge des Intervalls auf 1024 der ursprüngliche,

Entschuldigung nicht 1000 Intervalls, nach 10 Intervalls ist die Länge des Intervalls

auf 1024 zusammen geschrumpft. Okay, können wir also machen. Wir machen mal ein Beispiel

dazu. Wir nehmen mal die Funktion x squared minus fünf, sieht die aus, das ist hier so

eine Parabelfunktion und wir schauen die nur an im Bereich von zwei bis drei, da liegt

eine Nullstelle drin, die nennen wir typischerweise Wurzel fünf, also wir kennen die Zahl Wurzel

fünf, wir können mit der gut umgehen, wir tun es trotzdem mal so, als wüssten wir

nicht von der Existenz von Wurzeln und benutzen unser Wissen mit der Zahl Wurzel fünf, um