Newtonverfahren und Regula Falsi

Neue Frage »

Bjoern1982 Auf diesen Beitrag antworten »
Newtonverfahren und Regula Falsi
Hallo zusammen Wink

Ich bin auf der Suche nach einer Begründung dafür, warum das Newtonverfahren zum einen schneller konvergiert als das Regula-Falsi-Verfahren und zudem auch noch exakter sein soll.

Darüberhinaus soll das Regula-Falsi-Verfahren auch unter bestimmten Voraussetzungen (Funktion f stetig im Intervall [a,b] mit f(a)*f(b)<0) zu einer SICHEREN Konvergenz im Gegensatz zum Newtonverfahren führen, was mir auch noch nicht ganz einleuchtend ist...
Ok es hat wohl mit der Sekante zu tun, welche eine mögliche Divergenz verhindert aber ich kann diesen Gedanken noch nicht ganz zu Ende spinnen.

Der Unterschied zwischen quadratischer und linearer Konvergenz in diesem Zusammenhang ist mir schon klar aber ich würde das gern noch detaillierter wissen, was jetzt genau ausschlaggebend für die quadratische Konvergenz ist.

Bin auch für weitere Vor- und Nachteile offen Augenzwinkern

Wäre super wenn mir das jemand mit eigene Worten erklären könnte smile


Vielen Dank für eure Mühe.

Gruß Björn
Dual Space Auf diesen Beitrag antworten »
RE: Newtonverfahren und Regula Falsi
Ich *verschieb* mal in die Numerik.
tigerbine Auf diesen Beitrag antworten »
RE: Newtonverfahren und Regula Falsi
Hallo Bjoern,

also wenn die beiden Verfahren hinsichtlich der Konvergenz und deren Geschwindigkeit vergleich willst, musst Du genau sagen um welche Art der Nullstelle es sich handelt und welche eigenschaften die Funktion hat.

Beispiel:

f 2mal steitg diff'bar, einfach Nullstelle -> Es gibt eine Umgebung der das NVF konvergiert (mit quadratischer Konvergenz). Jedoch ist der zu führende Beweis nicht konstruktiv, d.h. man erhält keine Anhaltspunkte über den zu wählenden Startpunkt. Den Beweis hierzu habe ich auch schon mal im Numerik Forum gemacht.

Bei der regula falsi - Kombination aus Bisektion und Sekantenverfahren

Mit f stetig und f(a)*f(b) <0 drückt man aus, das die Funktion in dem Intervall aufgrund des Mittelwertsatzes mind. eine Nullstelle hat. Was versteht Du dort an der sicheren Konvergenz nicht?

Gruß



Mit der Behauptung "exakter" tue ich mit etwas schwer. Was meinst Du damit?
Bjoern1982 Auf diesen Beitrag antworten »

Hallo tigerbine

Vielen Dank dafür, dass du mir hilfst smile

Ich helfe jemandem bei seiner Facharbeit und es geht zur Zeit um die Vor- und Nachteile der beiden Verfahren.

Das ist auch für einen Grundkurs, deshalb muss man wohl auch nicht so detailliert durch Laufzeitabschätzungen arbeiten.

Festhalten kann man wohl, dass quadratische Konvergenz beim Newtonverfahren nur bei einfacher Nullstelle und einem Startwert, der möglichst in der Nähe der Nullstelle ist, vorliegen kann.

Kann es somit auch Funktionen geben, deren Nullstellen man effektiver mit Regula Falsi annähern kann ?

Zitat:
Mit f stetig und f(a)*f(b) <0 drückt man aus, das die Funktion in dem Intervall aufgrund des Mittelwertsatzes mind. eine Nullstelle hat. Was versteht Du dort an der sicheren Konvergenz nicht?


Beim Newtonverfahren kann es ja passieren, dass in bestimmten Fällen (zwei Nullstellen, die nahe beieinander liegen, ungünstiger Startwert) keine Konvergenz eintritt wohingegen mit dem Regula Falsi Verfahren eine sichere Konvergenz unter den beiden oben genannten Voraussetzungen gewährleistet ist, egal ob die Startwerte weit von der Nullstelle weg liegen oder nicht...
Oder ist mit sicherer Konvergenz nur gemeint dass durch die ZWEI Startwerte schon ein konkretes Intervall festgelegt wird, indem die Nullstelle gesucht wird wohingegen dies beim Newtonverfahren durch den einen Startwert nicht schon derart eingegrenzt ist... verwirrt

Mir ist also noch nicht ganz klar warum es mit Regula Falsi keine Probleme geben kann.

Zitat:
Mit der Behauptung "exakter" tue ich mit etwas schwer. Was meinst Du damit?


Das hatte ich ein paar Male in anderen Facharbeiten gelesen.
Z.B. hier auf Folie 13 unten

----> http://www.gunis.de/Facharbeit-Dominik.pdf

Gruß Björn
tigerbine Auf diesen Beitrag antworten »

Hallo Bjoern,

ich schaue da gerne nochmal drüber und versuche es auf Schulniveau zu erklären. Aber nicht mehr heute Abend.

Gruß,
tigerbine

P.S.: Wann ist Abgabe?
Bjoern1982 Auf diesen Beitrag antworten »

In einer Woche.

Danke für deine Mühe Wink

Gute Nacht
 
 
tigerbine Auf diesen Beitrag antworten »

Hier mal 2 Wiki-Links zum Thema, weil ich keine Lust habe es alles selbst zu schreiben. Die regula Falsi kombiniert das Bisektions- und das Sekantenverfahren.

Bisektion

Sollten wir zu einer stetigen Funktion f ein Intervall [a,b] finden, mit f(a)f(b)<0, dann hat die Funktion dort mindestent eine einfache Nullstelle. (Folgt aus dem VZW und dem Zwischenwertsatz stetiger Funktionen). Dabei verwendet man zur Bestimmung dieser Nullstelle ein Intervallschachtlungsverfahren. Hier wird das Intervall eben immer halbiert, und somit beliebig klein, daher die sichere Konvergenz.

Die Idee bei der Regula falsi ist die Frage, ob man den Intervallteilungspunkt, bei Bisektion die Intervallmitte, nicht auch noch geschickter wählen kann. Deswegen wird hier das Sekantenverfahren mit einbezogen. Dadurch wird eine schnellere Konvergenz erreicht.

Sekantenverfahren

Mit dem Newton-Verfahren erhält man nun ein i.a. schneller konvergierendes Verfahren, jedoch kann man nicht so leicht vorhersagen, ob es zu einem verwendeten Startpunkt auch konvergiert. Es kann passieren, dass man sich auf der Stelle dreht, oder sich sogar von der Nullstelle entfernt, oder eine Definitionslücke( Steigung = 0) erwischt. Beispiele solltet ihr im Netz finden.

Die Beweise sagen nur, dass es um eine einfache Nullstelle unter best.weiteren Voraussetzungen einen Bereich (Intervall) gibt, so dass das NewtonVerfahren für jeden Startwert mit einer bestimmten Geschwindigkeit konvergiert.

Interssant wäre es hier den Bogen zum Fixpunktsatz von Banach zu schlagen. Da sich dessen Bedingungen unabhängig vom Fixpunkt formulieren. Und man wie bei Regula falsi die Funktion f im Intervall [a,b] untersuchen kann.
Bjoern1982 Auf diesen Beitrag antworten »

Danke schonmal soweit smile

Ist es eine notwenige Voraussetzung des Newtonverfahrens, dass die Nullstelle selbst keine Extremstelle sein darf ?
Denn eigentlich gilt ja nur f ' (xn) ungleich null aber dieses xn ist ja nur in den seltensten Fällen auch gleichzeitig die Nullstelle selbst...

Oder muss man das so sehen, dass man auch die konkrete Nullstelle einer Funktion als Extremstelle ausschliessen muss, da sonst eine Konvergenz nicht garantiert ist ?

Gruß Björn
tigerbine Auf diesen Beitrag antworten »

Wenn Die Nullstelle eine Extremstelle ist, dann ist sie nicht einfach Augenzwinkern

Meine Bemerkung bezog sich auf die Startstelle x0 (und nat. die Iterierten xn)
Bjoern1982 Auf diesen Beitrag antworten »

Ok, hab ich verstanden Augenzwinkern

Noch eine Frage:

Ab wann spricht man von günstigen Starwerten, also wenn man mit dem Bisketionsverfahren "schönere" Startwerte berechnen will, ab wann kann man da von hinreichend nützlichen Starwerten bezüglich einer erfolgreichen Konvergenz sprechen ?

Gruß Björn
tigerbine Auf diesen Beitrag antworten »

So ganz verstehe ich gerade die FRage nicht. Willst du jetzt mit Bisektion Startwerte für Newton bestimmen?

In diesem Thread steht der Beweis für die Konvergenz des Newtonverfahrens. Dazu mussen wir die Extremstellen der ersten und zweiten Ableitung bestimmen, um das Konvergenzintervall bestimmen zu können. Was aber im allgemeinen nicht so einfach sein dürfte. Augenzwinkern (brauchen wir ja auch da Nullstellen Augenzwinkern )

Der Nachteil bei Newton ist eben i.A. dass Du nicht weißt, ob Du schon dich genug dran bist. Du könntest mit Bisektion sicher das Intervall immer verkleinern, aber wann Du dich genug dran bist, weißt Du "nie" so ganz sicher Augenzwinkern
Bjoern1982 Auf diesen Beitrag antworten »

Hmm, ich dachte nur dass es besser ist z.B. beim Newtonverfahren einen Startwert zu haben, der in der Nähe der Nullstelle liegt, da ich eben oft gelesen habe, dass ein "ungünstiger" Startwert dazu führen kann, dass entweder keine Konvergenz eintritt oder man sich einer anderen Nullstelle nähert oder aber sich immer im Kreis dreht...

Deswegen die Vorarbeit mit der Bisektion...

Gruß Björn
tigerbine Auf diesen Beitrag antworten »

Das ist sicherlich richtig gedacht, aber leider weißt Du oft nicht, ob Du schon nahe genug dran bist. aber man kann so eine eingrenzung vorschalten.
Bjoern1982 Auf diesen Beitrag antworten »

Und nochmal muss ich dich stören Augenzwinkern

Ich habe desöfteren gelesen, dass es beim Newtonverfahren bei einer ungünstigen Wahl des Startwerts passieren kann, dass man sich am Ende einer ganz anderen Nullstelle nähert als man wollte...

Kann bzw darf das denn überhaupt passieren ohne dass man die Voraussetzung f'(xn) ungleich null verletzt, denn wenn es in einem Intervall schon zwei Nullstellen gibt muss hier ja zwangsweise eine Extremstelle vorliegen an der eben f'(xn)=0 gilt ?

Gruß Björn
tigerbine Auf diesen Beitrag antworten »

Ja dass kann passieren.

nicht-konvergenz

Ich hab vielleicht auch noch ein Beispiel in meinen Unterlagen, muss ich aber erst suchen Wink
tigerbine Auf diesen Beitrag antworten »

Wegen *Spambefall* geschlossen. PN an mich zum öffnen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »