Wo verwendet man das Newtonverfahren?
Hallo, wie oben schon steht ist meine Frage die folgt: Wo genau, also nicht weshalb sondern wo im Alltag z.B. wird das Newtonverfahren benutzt? Bisher habe ich irgendwo entnehmen können, dass Computern dieses Verfahren einprogrammiert wird, da sie mit der normalen Nullsetzung nicht arbeiten können. Ist das richtig und wo noch wird dieses Verfahren angewandt?
Danke, mfG
3 Antworten
bei zahlreichen numerischen verfahren zur optimierung oder zur simulation wird das newton-verfahren als hilfsmittel verwendet.
beispiele:
notation: x ist eine funktion, die von t abhängt. d.h.: x(t) ist x ausgewertet an der stelle t, wie zB f(x) ist f ausgewertet an der stelle x, falls f die funktion ist und x die variable von der f abhängig ist.
gewöhnliche differentialgleichungen vom typ d/dt x(t) = f(x(t),t), zB d/dt x(t) =x(t) + t (dann ist f(x(t),t)=x(t) + t) kann man auch anders schreiben:
x(t)=x(0)+ integral von 0 bis t über f(x(s),s) ds.
numerisch approximiert man nun das integral (weil man im allgemeinen nicht exakt integrieren kann). man verwendet da sozusagen die streifenmethode aus der schule, mit der normalerweise die integrale eingeführt werden. also man nähert das integral durch säulen an. man kennt f(x(s),s) nicht vollständig, aber man kenn f(x(0),0), weil man das vorschreiben kann, sonst gibt es mehrere lösungen. das nennt man dann einen anfangswert und das problem heißt anfangswert-problem. d.h.: näherungsweise gilt dann:
x(t)=x(0)+ integral von 0 bis t über f(x(0),0) ds = x(0) + (t-0) * f(x(0),0). das kann man explizit ausrechnen. im obigen beispiel erhält man x(t) = (ungefähr) x(0) + t * x(0). das benötigt nun noch nicht das newtonverfahren, aber man kann auch folgende schätzung nehmen:
der folgende ansatz ist etwas un-intuitiv, aber geht analog:
x(0) = (ungefähr) x(0) + t * f(x(t),t) = x(0) + t * (x(t) + t). das sieht schon sehr anders aus. statt s=0 zu setzen im integral (= säule mit höhe von f(x(0),0)) setze ich s auf das ende des integrationsbereiches. also auf t. damit habe ich aber den unbekannten wert x(t) verwendet, obwohl ich nur x(0) kenne. nun entscheide ich mich zuerst für welches t ich eigentlich meine näherung bestimmen möchte... (t war ja noch nicht festgelegt. üblicherweise wählt man t klein, da je größer t desto schlechter die näherung. man wiederholt dann mit dem näherungswert für kleine t denselben ansatz nochmal um eine weitere näherung für spätere t zu bekommen). für ein festes t können wir dann nach x(t) auflösen. in diesem fall geht das noch recht einfach, aber die terme können kompliziert werden, außerdem rechnet der computer anders als wir menschen. das führe ich nicht näher aus. man kann eine fixpunktiteration durchführen (für t klein genug funktioniert das), d.h.: man rechnet immer wieder aus:x(0) + t * (y + t) und setzt das ergebnis davon für y ein, wenn man es nochmal ausrechnet. dazu muss man natürlich zu beginn ein willkürliches y als startwert wählen. das newton-verfahren ist aber besser !! deshalb nimmt man wenn möglich das newton-verfahren. (das "wenn möglich" führe ich auch nicht weiter aus)
da ich schon viel mehr geschrieben habe, als ich vorhatte, mach ich das optimierungsbeispiel ganz schnell!
ein konvexes optimierungsproblem mit nebenbedingungen kann folgende gestalt haben: f(x) = x^2 unter nebenbedingung x>=1 (sehr einfaches beispiel). es ist das minimum gesucht. das liegt offensichtlich bei x=1 und f(1)=1. es liegt auf dem "rand" der menge an punkten, die die nebenbedingung erfüllen (solche punkte nennt man "zulässig"). am rand von mengen kann man nicht ableiten! (führe ich nicht weiter aus) daher kann man nicht die ableitung von f gleich 0 setzen! f ' (x) = 2x und das ist nur dann 0, falls x=0 ist.trotzdem haben wir unser minimum ja bei x=1.
die sogenannten KKT bedingungen lauten dann:
2x -s = 0, x>=1, s>=0, s * (1-x) = 0
punkte s,x, die das gleichugssystem lösen, sind optimal. also aus letzterem folgt s=0 ODER x=1. (das ist ja schon unsere lösung), für s=0 ist auch zwingendermaßen x=0 (folgt aus ersterem), was ein widerspruch zu x>=1 ist. also ist unsere lösung: x=1 und das passende s dazu ist s=2. (unwichtig)
das war eine nicht-lineare gleichung. das ist sehr viel komplizierter als lineare gleichungssysteme: in der schule mit linearen gleichungssystemen weiß man: hat man 2 unbekannte, so braucht man für eine eindeutige lösung 2 gleichungen. wenn die gleichungen ungünstig gewählt sind, so kann auch trotzdem keine lösung rauskommen. ich nehme dabei an, dass beide gleichungen nicht durch äquivalenzumformungen ineinander überführbar sind. hier hatte man aber 2 gleichungen und sogar 2 ungleichungen und bekommt trotzdem eine lösung. diese ist auch eindeutig, aber es kann im allgemeinen auch unendlich viele lösungen geben oder auch wiederum gar keine, obwohl die gleichungen nicht ineinander überführbar sind.
deshalb löst man sowas dann zB mit den newton-verfahren. dies ist in dem fall sogar noch komplizierter, da man 2 unbekannte hat. aber man kann das newton-verfahren auch für mehrere unbekannte aufstellen.
die angeführten beispiele sind absolut einfachste einführende grundlagen-beispiele, welche in der industrie/wirtschaft längst nicht konkurrenzfähig mit anderen noch komplizierteren numerischen verfahren.
ich nehme an, dass du die nullstellen berechnen willst... was genau soll ich erklären?
ich erklär mal kurz das verfahren. wenn du nur die berechnung sehen willst, kannst du gleich weiter nach unten gucken.
es gibt die sogenannte taylor-entwicklung, aus der folgt, dass f(x) (falls es ausreichend oft ableitbar ist) ungefähr f(x0)+(x-x0) * f ' (x0) ist, dabei ist x0 ein fest gewählter punkt. veranschaulicht hat man dann folgedes. man geht zum punkt (x0,f(x0)) vom graphen der funktion und geht dann die tangente in diesem punkt entlang um näherungsweise den verlauf von f nachzumachen. das ist natürlich nur für die "nähe" von x0 angemessen.
löst man dann auf: f(x)=0 entspricht ungefähr f(x0)+(x-x0) f ' (x0) = 0 und formt um, so erhält man:
x = x0 - f(x0) / f ' (x0)
nun ist x0 beliebig. und nachdem man x ausgerechnet hat, rechnet man dasselbe nochmal, aber mit neuem x0. x0 hat dabei den wert des vorherigen ergebnisses. das nennt man fixpunkt iteration, da auf diese weise ein punkt gesucht wird, sodass y = y - f(y)/ f ' (y). das lässt sich so anschaulich machen: man ersetzt ja jedes mal x0 mit dem alten wert von x. d.h.: sowohl x0 als auch x ändern sich und nehmen dieselben werte an, aber zeitversetzt. (nacheinander). im "unendlichen" nehmen dann beide denselben wert an, weil sich x oder x0 irgendwann nicht mehr ändern, sonst würde die fixpunktiteration nicht funktionieren, also keine lösung herausbekommen. (das kann durchaus passierem, wenn man pech hat). diesen wert, den x und x0 annehmen nenn ich y.
nach umformen gilt:f(y)/f ' (y) = 0 und das ist äquivalent zu f(y) = 0. damit ist y unsere gesuchte nullstelle.
man hätte als iteration auch folgendes machen können: x=x0-f(x0). falls diese iteration funktioniert, dann gilt y = y - f(y) und dann folgt f(y) = 0. diese iteration funktioniert aber meistens nicht und ist selbst wenn sie funktioniert ungenauer, weil man nicht die ableitung der funktion verwendet. die steigung einer funktion kann aber eine wichtige information sein. (also gleich wieder vergessen wie die gleichung war)
angewandt auf deine gleichung:
ich nehme mal x0 = 1 und natürlich das newton-verfahren.
f ' (x) = 4 x^3 - 9 x^2 + 4 x
x=1 - (-5)/(-1) = -4... nehme nun x0=-4
x=-4 - 475 / (-416) = 5.1418269230......
x = 5.1418269230... - 339.0401368/326.3882315 = ungefähr 4. ich runde an der stelle recht arg, damit mal wieder schönere zahlen rauskommen.
x= 4 - 91/128 = ungefähr 3.3
x= 3.3 - 27.5611/58.938 = 2.8
das wird immer so weiter gehen bis man bei 2.518... ankommt.
die frage die sich stellt... wie kommt man zur nullstelle -0.937...?
nun da kommt man wahrscheinlich nur dann hin, wenn man bereits nah an der -0.937... dran ist. das newton-verfahren ist kein allheil-mittel. das verfahren kann schief gehen. es kann entweder nie fertig werden also keine lösung liefern, oder man dividiert durch 0, sodass die iteration abbricht (wenn f ' (x) = 0 ist, das ist ja im nenner). und es ist unvorhersehbar, welche nullstelle man damit findet, es sei denn man fängt "nah genug" neben der nullstelle an.
dazu bietet es sich dann an mehreren werten für x die funktion auszuwerten.
zB.:
f(-2) = 43
f(-1) = 1
f(0) = -5
f(1) = -5
f(2) = -5
f(3) = 13
damit wissen wir zumindest, dass zwischen 2 und 3 und zwischen -1 und 0 eine nullstelle liegt, weil man da von "+" zu "-" wechselt oder umgekehrt. es kann aber noch mehr nullstellen geben!! zB könnte zwischen 1 und 2 auch eine nullstelle sein, falls die funktion schnell genug ins positive und wieder zurück ins negative verläuft, bevor man bei der 2 angekommen ist.
man kann somit sinnvolle startwerte finden, aber vorsicht: das ist keine garantie, dass man auch bei der erwarteten nullstelle landet.
wenn du etwas rumprobieren möchtest, dann kannst du dir ganz einfach im internet newton-rechner angucken und startwerte raten, um nullstellen zu finden.
gib mal bei http://www.gjlay.de/helferlein/newton.html deinen term als pow(x,4)-3pow(x,3)+2pow(x,2)-5 ein und variiere den startwert (x0). die restlichen parameter kannst du ignorieren.
für x0=0 kommt ein fehler, weil du dann versehentlich durch 0 teilst im verlauf der berechnungen.
für werte x0 nahe an der 0 braucht das verfahren verdammt lange (musst dass N erhöhren).
für x0 = 1.5 erhalte ich die "linke" nullstelle, obwohl ich damit näher dran bin als mit 0.5. bei x0=0.5 erhalte ich aber die "rechte" nullstelle, obwohl ich weiter davon weg bin.
verstehen kannst du diese phänomene, wenn du dir immer die tangenten anguckst zu den startwerten x0. anschaulich bestimmst du die nullstelle der tangente, welche eine näherung an f(x) darstellt. d.h.: du gehst vom punkten (x0,f(x0)) des graphen die tangente entlang bis zum punkt, an dem sie die x-achse schneidet. das ist das ergebnis für x und damit auch dein neuer startwert x0 für den nöchsten rechenschritt. nun kannst du dir vielleicht selber die phänomene erklären.
Hey entschuldige, dass ich so spät schreibe. Also ich hab mal die Funktion in einen Graphengenerator eingegeben und konnte dem entnehmen dass sich die NST aufjedenfall zwischen -1 und 0 befindet. dementsprchend habe ich x0=-1 als startwert genommen und kam dann nach einigen iterationsschritten auf die -0,937 :) Ich habe das Verfahren also schon ganz gut verstanden^^.
Danke nochmals für die Mühe!
Genau dafür! :)
Oft werden mit solchen Funktionen irgendwelche Sachverhalte beschrieben. Also wie was wann am besten, schlechtesten etc wirkt. Und um solche Dinge ermitteln zu können, kann es sein, dass man die Nullstellen braucht. Und bei komplexen Funktionen kann man hier das Newtonvverfahren anwenden :)
In Computern, wenn die Nullstellen von komplexeren Funktionen gesucht werden. Du hast dir die Antwort schon selbst gegeben
Echt vielen Dank für die Mühe hast mir sehr weitergeholfen^^. Allerdings hast Du leider nur einfache Gleichungen als Beispiele angelegt. Du scheinst das ja so einfach zu können. Kannst Du mir bei der Funktion: f(x)=x^4-3x^3+2x^2-5 weiterhelfen? Es ist immer so ein Unterscheid wenn da aufeinmal eine etwas komplexere Gleichung vorliegt.. Wenn möglich, könntest Du noch etwas die Schritte erläutern? :/ Wäre Dir echt sehr Dankbar..
mfG