Whittaker-Iteration. |
| 06.07.2004, 14:42 | dein-zahnarzt | Auf diesen Beitrag antworten » |
| Whittaker-Iteration. Ich bastle gerne und an 'Sachen aus Mathe für's Auge'. Sprich raytracing, tolle 3d Gebilde aus einfachen Linien usw. Naja, Winamp AVS, wem das was sagt. Dabei bin ich auf eine Methode zur Annäherung der Nullstellen einer beliebigen Funktion gestoßen. Sie nennt sich Whittaker-Iteration. Eigentlich ist sie unvorstellbar einfach zu benutzen. Man subtrahiert, im Prinzip, immer wieder einen Teil des Argument vom vorigen Funktionswert. Etwa so: x(n+1) = x(n) - f(x(n)) * a Wobei 'a' frei wählbar ist und über den Erfolg der Iteration entscheidet. Ich verwende sie um komplexe Objekte die sich nicht durch einfach Polynome darstellen lassen zu raytracen. Zwar weiß ich wie ich sie dort verwende, aber ich würde gerne auch eine mathematisch korrekte Ausführung davon zustande kriegen. Falls ich das mal vernünftig erklären muss. |
||
| 07.07.2004, 21:48 | Shopgirl | Auf diesen Beitrag antworten » |
| RE: Whittaker-Iteration. Hallo dein-zahnarzt, du suchst also nach Nullstellen einer Funktion f. Ist das eine Funktion von R nach R? Das nehme ich für diesen Beitrag einmal an. Setzen wir phi(x) := x - f(x)*a. Dann iterierst du also x(n+1) = phi(x(n)). Vielleicht findest du ein gutes Numerik-Buch oder -Skript, in dem das ausführlich beschrieben wird. Meine Erklärung ist nämlich ziemlich theoretisch. Um zum Beispiel mit dem Banachschen Fixpunktsatz nachzuweisen, dass diese Iteration konvergiert, brauchst du ein Intervall [A,B], in dem phi eine so genannte Kontraktion ist. Das heißt, es gilt: 1. phi(x) in [A,B] für alle x aus [A,B], und 2. |phi'(x)| < L < 1 für alle x aus [A,B], mit einem von x unabhängigen Wert 0 < L < 1. Wenn phi eine Kontraktion auf [A,B] ist, dann hat phi genau einen Fixpunkt in dem Intervall, und mit jedem Startwert aus dem Intervall konvergiert die Iteration gegen den Fixpunkt. Das Problem dabei ist, den Wert a und das Intervall [A,B] so zu bestimmen, dass phi eine Kontraktion ist. Es gibt noch ein theoretisches Resultat, was den Fixpunktsatz verwendet: Wenn f stetig differenzierbar ist, bei x0 eine Nullstelle hat und in einer Umgebung von x0 monoton wachsend ist (bei fallendem f betrachte -f), dann gilt: Für jedes (hinreichend kleine) e>0 ist f' in dem Intervall [x0-e, x0+e] nichtnegativ und beschränkt, es gibt also eine zahl M(e)>0 mit 0 <= f'(x) <= M(e) für alle x aus [x0-e, x0+e]. Setzen wir a := 1/(2*M(e)), dann ist 0 <= 1 - f'(x)*a = phi'(x) <= 1/2 für alle x aus [x0-e,x0+e]. Für x aus [x0-e, x0+e] gilt , also ist |f(x)|/(2M) <= e/2. Weiterhin haben wir phi(x) = x - f(x)/(2M) = x0 + (x-x0) - f(x)/(2M). Ist x >= x0, dann ist 0 <= x-x0 <= e und 0 <= f(x)/(2M) <= e/2 (wegen der Monotonie von f), also ist x0 <= phi(x) <= x0+e. Ist x < x0, dann ist -e <= x-x0 < 0 und -e/2 <= f(x)/(2M) <= 0 (wieder wegen der Monotonie von f), also ist x0-e <= phi(x) <= x0. Damit ist phi eine Kontraktion, und die Iteration konvergiert im Intervall [x0-e, x0+e] gegen x0. Um das praktisch nutzen zu können, musst du eine Startnäherung für x0 kennen (mit Abschätzung, wie genau die Näherung ist, um einen Wert für e zu haben), und die Ableitung von f kennen, um deren Maximum zu bestimmen. |
||
| 08.07.2004, 13:22 | SirJective | Auf diesen Beitrag antworten » |
Shopgirl, deine Berechnungen sehen richtig aus. Damit beschaeftige ich mich gerade in meiner Numerik I-Vorlesung. Ich bin "nur" ein Uebungsleiter, und hab von dem Verfahren selbst noch nichts mitbekommen (war in der Uebung noch nicht dran). Das Skript ist hier: http://www.mathematik.uni-muenchen.de/~l...04/num/skr.html Der Teil, der sich mit Nullstellensuche beschaeftigt, ist im Kapitel 8 der Abschnitt 8.5. Beachte aber, dass das Skript noch in Arbeit ist, und nicht notwendig fehlerfrei ist. Gruss, SirJective |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
