konvergenz newtonververfahren

Neue Frage »

munzlmunz Auf diesen Beitrag antworten »
konvergenz newtonververfahren
Meine Frage:
hallo leute,
ich bin schüler aus dem lk mathemathik 13. stufe und schreibe facharbeit über das newtonverfahren.
mit dem konverganzbeweis habe ich so einige probleme, also meine lehrerin meint ich kann schon einen beweis zitieren aber ich muss ihn dann eben verstehen... leider will mir das so gar nicht gelingen, deshalb wollte ich fragen ob mir jemand die einzelnen schritte grob erklären könnte, so dass man es als schüler auch einigermaßen verstehtsmile
im vorab schon dankesmile

Meine Ideen:
habe mir den beweis bei wikipedia angeschaut, denke aber der erste schritt müsste für mich unnötig sein, weil ich eh nur polynome behandlen muss, es erscheint mir sinnlos ein polynom durch ein polynom zu aproximieren. stimmt das? und wie würde der beweis dann aussehen?
tigerbine Auf diesen Beitrag antworten »
RE: konvergenz newtonververfahren
Zitat:
habe mir den beweis bei wikipedia angeschaut, denke aber der erste schritt müsste für mich unnötig sein, weil ich eh nur polynome behandlen muss, es erscheint mir sinnlos ein polynom durch ein polynom zu aproximieren. stimmt das? und wie würde der beweis dann aussehen?


Dann hast du das Newton-Verfahren "gar" nicht verstanden. Man nimmt es auch um Nullstellen von Polynomen zu berechnen. Haben die Grad größer 5, so gibt es gar keine Lösungsformeln mehr (bei Grad 2 kennst du ja die Mitternachtsformel).

Welches spezielle Polynom nimmt man nun bei Newton?
[WS] Eindimensionale Nullstellenprobleme 1 - versch. Verfahren
 
 
lgrizu Auf diesen Beitrag antworten »
RE: konvergenz newtonververfahren
die frage ist, was du möchtest, meinst du das newton-interpolationsverfahren oder meinst du tatsächlich das newton iterationsverfahren?

@bienchen
wollte mich nicht einmischen, aber das klingt für mich vielleicht nach interpolation...
tigerbine Auf diesen Beitrag antworten »
RE: konvergenz newtonververfahren
Hallöchen Feuerwehrmann Wink

So selektiv kann man lesen, wenn man selbst gerade im Newtonverfahren (für Nullstellenprobleme) steckt. Aber die kluge Hausfrau sorgt vor:
[WS] Polynominterpolation - Theorie
lgrizu Auf diesen Beitrag antworten »
RE: konvergenz newtonververfahren
guten morgen erst mal,

Zitat:
Original von tigerbine
Hallöchen Feuerwehrmann Wink

So selektiv kann man lesen, wenn man selbst gerade im Newtonverfahren (für Nullstellenprobleme) steckt. Aber die kluge Hausfrau sorgt vor:
[WS] Polynominterpolation - Theorie


kommt vor... Augenzwinkern

nun ist es an munzelmunz, sich klar auszudrücken.


@munzelmunz
wenn du noch hilfe benötigst, einfach melden, falls du etwas in dem workshop nicht verstehst, fragen fragen, eine beweismethode für die newtoninterpolation kann man auch etwas "einfacher" führen, indem man den beweis für lagrange mit hilfe des kronecker-deltas über die konstruktion der polynome führt und dann zeigt, dass lagrange und newton identisch sind.

das newton iterationsverfahren kann direkt aus dem taylorschen satz gefolgert werden.
munzlmunz Auf diesen Beitrag antworten »

hmm also mir ging es eig nur um den beweis, dass das newtonverfahren (bei mir nur zur nullstellenberechnung von polynomen) bei geeignetem startwert quadratisch konvergiert...
so und bei dem beweis auf wikipedia wird allgemein für irgendeine funktion der beweis gemacht, deshalb wird f(x) durch ein taylorpolynom angenähert.
ich bräuchte den beweis aber nur für polynome, deshalb wollte ich wissen ob ich mir die darstellung durch ein taylorpolynom nicht sparen könnte.

Außerdem habe ich bei der festlegung von m1 und M2 und der abschätzung schwierigkeiten, weil ich so etwas noch nie gesehen habe...
also ich verstehe nicht warum genau die genannte abschätzung folgt
(ich würde das ja gern hier zitieren, hab aber keinen plan wie das gehtunglücklich das wäre der link zur seite: http://de.wikipedia.org/wiki/Newtonverfa...sche_Konvergenz )
tigerbine Auf diesen Beitrag antworten »

Ok, dann wissen wir welches Verfahren du meinst.

Ist dir nun klar, was das Verfahren eigentlich macht und warum deine Frage mit den Polynomen i.A. "falsch" ist?

Zitat:
hmm also mir ging es eig nur um den beweis, dass das newtonverfahren (bei mir nur zur nullstellenberechnung von polynomen) bei geeignetem startwert quadratisch konvergiert...


Du hast Humor Big Laugh
munzlmunz Auf diesen Beitrag antworten »
....
jup das is mir (denke ich) alles schon klar, hab ja auch schon den ersten teil meiner facharbeit abgegeben(also alles über das newtonverfahren bei polynomen) und es gab eben nur noch die diskussion über den konvergenzbeweis... meine mathelehrerin war der meinung so wie er ist kann ich den beweis von wikipedia nicht stehen lassen und ich weiß eben nicht, wie ich es anstellen soll ihn zu verbessern, wenn ich ihn noch nicht mal so richtig verstanden habeunglücklich
lgrizu Auf diesen Beitrag antworten »
Re: ....
was weißt du denn über das taylorpolynom, einfach nen beweis von wiki übernehmen würde ich als lehrer auch nicht zulassen.

das taylorpolynom konvergiert im entwicklungspunkt (sicherlich konvergiert es auch in einer bestimmten umgebung um den entwicklungspunkt, ist aber erst mal nicht sooo wichtig, jedenfalls nicht für das, was wir vorhaben).

bei wiki steht nun: "so ist die taylorformel zweiten grades...", was dann folgt ist aber die taylorformel 1. grades und ein restglied.


mach dich mal ein bisschen über taylopolynome schlau.


du kannst dir auch die tangent an der stelle x_0 einer funktion f(x) anschauen:

,

berechne nun die nullstelle von p(x).
tigerbine Auf diesen Beitrag antworten »
RE: konvergenz newtonververfahren
Zitat:
Original von tigerbine
Zitat:
habe mir den beweis bei wikipedia angeschaut, denke aber der erste schritt müsste für mich unnötig sein, weil ich eh nur polynome behandlen muss, es erscheint mir sinnlos ein polynom durch ein polynom zu aproximieren. stimmt das? und wie würde der beweis dann aussehen?


Dann hast du das Newton-Verfahren "gar" nicht verstanden. Man nimmt es auch um Nullstellen von Polynomen zu berechnen. Haben die Grad größer 5, so gibt es gar keine Lösungsformeln mehr (bei Grad 2 kennst du ja die Mitternachtsformel).


Du gehst überhaupt nicht auf Rückfragen ein. Warum soll ich mir die Mühe machen, hier was hinzuschreiben, wenn dann nur so Sätze kommen wie

Zitat:
jup das is mir (denke ich) alles schon klar,


Für alles weitere: Du verlinkst nichts, sprcihst nur wage davpn, worum es geht und teilst uns auch nicht mit, was du für Vorwissen hast. Ich habe hier im Forum im [WS] bereits Beispiele für Beweise zur Konvergenz geschrieben und sie dir auch verlinkt.

Man kann nun überlegen, wo sich Vereinfachungen ergeben können, da deine Funktionen Polynome sind und man so mehr Informationen über das Restglied hat. Ferner ist die Rückmeldung "So nicht" von deiner Lehrerin etwas wenig Input für uns. Augenzwinkern
munzlmunz Auf diesen Beitrag antworten »
RE: konvergenz newtonververfahren
Zitat:
Du gehst überhaupt nicht auf Rückfragen ein.


tut mir leid, dass ich mich so ungenau ausgedrückt habe. ich dachte als du geschrieben hast ich hätte das newtonverfahren nicht verstanden, hättest du mich falsch verstenden. meine antwort darauf war, dass ich mich genauer erklärt habe:
Zitat:
hmm also mir ging es eig nur um den beweis, dass das newtonverfahren (bei mir nur zur nullstellenberechnung von polynomen) bei geeignetem startwert quadratisch konvergiert...


mein vorwissen besteht darin, dass ich bereits folgendes erstellt habe:
(mein genaues facharbeitsthema um missverständnisse vorzubeugen ist übrigens
"Berechnung reeller NS von Polynomen durch Näherungsverfahren)

1.vorstellen des newtonverfahrens(vorgehensweise + beispiele)
2.herleitung der formel
3.probleme beim newtonverfahren

den konvergenzbeweis habe ich vorerst von wikipedia übernommen.

da wikipedia am anfang die taylorformel verwendet
Zitat:
Sei f eine zweimal stetig differenzierbare reelle Funktion und a eine Nullstelle von f, in welcher die Ableitung keine Nullstelle hat. Das bedeutet, dass der Graph der Funktion transversal, d. h. nicht-berührend, die x-Achse schneidet. Sei x ein Punkt nahe bei a. Dann kann die Taylor-Formel zweiten Grades (mit Restglied)

war ich gerade dabei mir hierrüber einiges anzuschauen. wie das aber so ist, wenn man gerade am arbeiten ist, habe ich mich gefragt ob es sich überhaupt lohnt, da ich ja wie gesagt nur polynome und nicht x-beliebige funktionen behandle. mittlerweile ist mir klar, dass ich mir die annäherung durch ein taylorpolynom wohl nicht werde sparen können...

es war dumm von mir einfach so wage ins blaue hinein zu fragen, aber leider gibt es bei mir so viele fragezeichen, dass ich gar nicht weiß wo ich anfangen soll zu fragenunglücklich

meine erste frage wäre also warum nehme ich ausgerechnet die taylorformel 2ten ( oder 1ten, also laut feuerwehrmann) grades mit restglied?
lgrizu Auf diesen Beitrag antworten »
Re: ....
fang doch mal hiermit an:

Zitat:
Original von lgrizu

du kannst dir auch die tangent an der stelle x_0 einer funktion f(x) anschauen:

,

berechne nun die nullstelle von p(x).


..vielleicht wird dann einiges klarer....
munzlmunz Auf diesen Beitrag antworten »
Re: ....
okey, habe das jetzt gemacht.

x=x0-f(x0)/f'(x0)

also das ergebnis ist jetzt die formel für das newtonverfahren. und p(x) ist das taylorpolynom 1. grades ohne restglied? d.h. ich kann das newtonverfahren aus der taylorformel ableiten?
aber was heißt das jetzt für meinen konvergenzbeweis? i-wie steh ich grad aufm schlauch
lgrizu Auf diesen Beitrag antworten »
Re: ....
nein, p(x) ist die tangente am graphen f(x).

jetzt haben wir das newtonverfahren hergeleitet.

die idee ist es, die nullstellen über die nullstellen der tangenten anzunähern.

du bist reichlich ungeduldig, ich denke dir fehlt im verständnis mehr, als der beweis, aber wenn du unbedingt einen haben willst:





mit taylor:

.

wobei .

sei nun , also eine nullstelle von f(x), dann folgt:



nun ist und setzen wir den "rest", also so ist qed.

ich weiß nur nicht, ob dir das jetzt sooo viel bringt....

ich denke, dass dein problem schon mit taylor beginnt und du dich fragen solltest, "warum folgt aus das folgende..?"

Zitat:
Original von munzlmunz


meine erste frage wäre also warum nehme ich ausgerechnet die taylorformel 2ten ( oder 1ten, also laut feuerwehrmann) grades mit restglied?


die frage ist gut, und ich habe die antwort schon gegeben: weil das taylorpolynom im entwicklungspunkt gegen die funktion konvergiert.
also nehme ich die gesuchte nullstelle der funktion als entwicklungspunkt, ich weiß, dass taylor dann gegen die nullstelle konvergiert, und bilde das taylorpolynom in der nullstelle.

1. grades+restgleid reicht aus, zum einen wissen wir nicht, wie oft die funktion differenzierbar ist, zweimal mindestens, sonst gäbe es kein nullstellenproblem.

zum zweiten wenden wir ein verfahren iterativ an, und da reicht es, sich schritt für schritt anzunähern.
tigerbine Auf diesen Beitrag antworten »
Re: ....
Ich will nur kurz Stellung auf die "Polynomsache" beziehen. Wenn du dir die Bilder angeschaut hast, funktioniert das Newton verfahren recht einfach. Anstatt der Nullstelle einer (mind. differenzierbaren) Funktion, berechnet es die Nullstelle einer Tangente [Polynom Grad 1] an die Funktion. Außer den Spezialfall, dass die Funktion selbst schon polynomial vom Grad 1 ist, ist es also sehr wohl ein Unterschied.

Der Tangente, können wir auch den Namen "Taylorpolynom vom Grad 1" und entsprechendem Entwicklungspunkt geben. Das hat dann auch den Vorteil, dass wir gleich eine Fehlerformel an der Hand haben. Da hat lgrizu ja schon was zu hingeschrieben.
munzlmunz Auf diesen Beitrag antworten »
Re: ....
okey, also schon mal vielen dank... werde jetzt also versuchen mir all das zu verinnerlichen.

hmm mir ist gerade noch die frage eingefallen, ob es den satz gibt , dass ein polynom vom grad i höchstens i nullstellen hat?
tigerbine Auf diesen Beitrag antworten »
Re: ....
Hauptsatz der Algebra.
baphomet Auf diesen Beitrag antworten »
Re: ....
Ja der Fundamentalsatz der Algebra sagt das mit der Anzahl der Nullstellen aus.
lgrizu Auf diesen Beitrag antworten »
Re: ....
@baphomet:

warum schreibst du bienchens antwort einfach noch einmal hier hin?
traust du ihr nicht zu, das sie weiß, wovon sie spricht?
...ich finde es ziemlich daneben, eine bereits richtige antwort einfach nochmal stumpf zu wiederholen und ich habe schon mehrere antworten dieser art von dir gelesen, halt dich doch einfach mal zurück....

@munzlmunz:

hast du denn jetzt verstanden, warum man taylor benutzt?
ich habe auch noch die frage, wie du das newtonverfahren in deiner HA hergeleitet hast.

wenn ansonsten noch fragen sind, einfach melden....
munzlmunz Auf diesen Beitrag antworten »
Re: ....
also ich habe das auch über die tangentengleichung gemacht:

Zitat:
Rechnerische Herleitung der Formeln:

Die allgemeine Tangentengleichung sieht so aus:

T(x) = m * x + t

m = f’(x0)

Zusätzlich ist Punkt P (x0| f(x0)) Element der Tangente, womit sich t ausrechnen lässt:

t = f(x0)-f’(x0) * x0



Die Tangentengleichung hätte also dann folgende Form:

y = f’(x0) * x + f(x0)-f’(x0) * x0

Um die Nullstelle der Tangente zu berechnen wird y = 0 gesetzt.

0 = f’(x0) * x1 + f(x0)-f’(x0) * x0

-f(x0) = f’(x0) * (x1 – x0)

x1 = x0 – f(x0)/f’(x0)

Analog hierzu kann man jetzt die nächsten Näherungen berechnen:
Man bekommt also wenn man rechts für x0 x1 einsetzt links x2, usw. Für n Näherungen bekommt man also:

xn+1= xn -f(xn)/f'(xn)
munzlmunz Auf diesen Beitrag antworten »

hallo leute, habe jetzt 2 fragen:

zum beweis von feuerwehrmann
warum folgt aus der letzten folgerung am ende des beweises die konvergenz?

und warum verdoppeln sich jetzt die gültigen dezimalen in jedem schritt?
munzlmunz Auf diesen Beitrag antworten »

habt ihr nicht mal nen tipp?
lgrizu Auf diesen Beitrag antworten »

die Konvergenz folgt für .

also


Zitat:
Original von munzlmunz


und warum verdoppeln sich jetzt die gültigen dezimalen in jedem schritt?


Hier weiß ich nicht, was du genau sagen bzw. fragen möchtest.

Meinst du, warum das Verfahren quadratisch Konvergiert?

...das kann man an dem Restglied sehen.
munzlmunz Auf diesen Beitrag antworten »

naja man findet bei der recherche oft den hinweis darauf, dass man, wenn man den Startwert nah genug an der Nullstelle setzt, das Verfahren pro näherungsschritt die gültigen dezimalen verdoppelt, also z.B wäre der erste wert 1,4... der danach1,423...und der danach 1,4235466... also die ... stehen für i-welche anderen dezimalen.
munzlmunz Auf diesen Beitrag antworten »
taylorformel
also ich bin immer noch leicht verwirrt, dass der beitrag in wikipedia sagt es handelt sich um die taylorformel 2. grades + restglied, ihr aber schreibt, es sei die formel 1. grades + restglied...
der beweis von tigerbiene im workshop zum newtonverfahren spricht uach von der formel 2. grades +restglied:/

was ist denn jetzt die richtige bezeichnung?
tigerbine Auf diesen Beitrag antworten »
RE: taylorformel
Ich habe nur eine Stelle gefunden, wo ich vom 2-ten TP sprach. Zählweisen=0,1. Habe das in ersten Grad umbenannt.
munzlmunz Auf diesen Beitrag antworten »
RE: taylorformel
ok dankeschönsmile
Neue Frage »
Antworten »



Verwandte Themen

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