Ein neues Iterationsverfahren |
14.03.2006, 15:10 | Linker | Auf diesen Beitrag antworten » | ||
Ein neues Iterationsverfahren ich habe ein neues Iterationsverfahren zum Berechnen von Nullstellen herausgefunden. Man kann damit sich nach und nach einer Nullstelle von ganzrationalen Funktionen nähern (funktioniert wie das Newton-Verfahren) , die Formel dafür ist zwar komplexer, aber man nähert sich damit schneller einer Nullstelle. So sieht sie aus: Man kann es probieren an Nach Bilden der ersten beiden Ableitungen kann man einen beliebigen Wert x0 nehmen und in die Formel einsetzen. Das solange wiederholen, bis auf dem Taschenrechner nach Einsetzen in die Formel dasselbe Er- gebnis steht (dann ist es eine Nullstelle). |
||||
14.03.2006, 15:25 | therisen | Auf diesen Beitrag antworten » | ||
Hallo Linker, um deine Freude mal etwas zu mildern: Dein Verfahren, sofern es allgemein funktioniert (Beweis?), setzt die Existenz der 2. Ableitung voraus, wohingegen man beim Newton-Verfahren nur die 1. Ableitung benötigt. Und hier ein Auszug aus Wikipedia:
Und vielleicht auch mal hier: http://de.wikipedia.org/wiki/Newton_Iter...sche_Konvergenz Gruß, therisen |
||||
14.03.2006, 15:39 | Linker | Auf diesen Beitrag antworten » | ||
Dieses Verfahren kann nur benutzt werden, wenn die Funktion mindestens eine Funktion 2.Grades ist (weil da eine 2.Ableitung existiert). Außerdem noch eine kleine Verbesserung in der Formel: Bei soll eigentlich stehen: |
||||
14.03.2006, 15:47 | AD | Auf diesen Beitrag antworten » | ||
@Linker Ich nehme an, du hast die Idee vom Newtonverfahren lokale Approximation durch lineare Funktion mit Taylorpolynom 1.Ordnung, dann Schnittpunkt dieser Funktion mit x-Achse dahingehend erweitert: lokale Approximation durch quadratische Funktion mit Taylorpolynom 2.Ordnung, dann Schnittpunkt dieser Funktion mit x-Achse Dann hast du aber unter der Wurzel einen Faktor vergessen: Was numerische Gründe betrifft, muss ich allerdings therisen zustimmen: Die Stabilitätsprobleme des Newtonverfahrens treten hier noch in potenzierter Form auf. EDIT: Oh, hast den Fehler selbst gemerkt - da habe ich wohl zu lange an meinem Beitrag geschrieben. |
||||
14.03.2006, 22:46 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Zur Info für dich: Die Funktion f(x)=3x+2 ist beliebig oft differenzierbar! |
||||
14.03.2006, 23:24 | pimaniac | Auf diesen Beitrag antworten » | ||
Auch wenn natürlich viele von uns schon irgendwo mal Numerische Mathematik gelesen haben, können wir nicht davon ausgehen dass das auch für Linker gilt.... Falls er noch in der Schule ist find ichs trotzdem interessant was er so rumgebastelt hat, also mach ma ihn jetzt nicht allzu fertig... auch ein Gauss hat klein begonnen :-) |
||||
Anzeige | ||||
|
||||
15.03.2006, 00:25 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Wer macht ihn denn hier fertig? |
||||
21.03.2006, 19:08 | Linker | Auf diesen Beitrag antworten » | ||
Veröffentlichung Hallo, ein Mathelehrer hat mal meine Iterationsformel gesehen und ihm kam diese noch nicht bekannt vor. Ich habe es mit einer Gleichung x^3+4x^2-8 versucht und man brauchte etwa 3 Durchläufe mit der Formel, um eine genaue Nullstelle zu bekommen. Und vielleicht hilft die Formel dabei, (versteckte) komplexe Nullstellen zu finden, wenn in der Wurzel der Formel eine negative Zahl steht; das kann das Newton-Verfahren nicht! Diese Formel kann probeweise veröffentlicht werden. |
||||
21.03.2006, 19:34 | AD | Auf diesen Beitrag antworten » | ||
RE: Veröffentlichung
Da irrst du dich: Das kann das Newton-Verfahren auch, nur musst du da eben mit einem krummen "echt" komplexen Startwert beginnen! |
||||
22.03.2006, 16:32 | Linker | Auf diesen Beitrag antworten » | ||
RE: Veröffentlichung Man könnte mit dieser Formel 2 Nullstellen gleichzeitig berechnen. Das kann vielleicht helfen bei der Gleichung x^4+3x^3-7=0. Wenn man mit einen anderen Verfahren nur eine Nullstelle berechnet und dann eine Polynomdivision macht, kommt eine Gleichung 3.Grades mit irrationalen Zahlen und es wird schwer, eine weitere Lösung zu finden. Mit diesem Iterationsverfahren kommt es danach zur "doppelten Polynomdivision" zu einer Gleichung 2.Grades, die sich mit der pq-Formel berechnen lässt. Es könnte sein, dass es dieses Verfahren noch nicht gibt, also kann ich diese Formel veröffentlichen. |
||||
22.03.2006, 16:36 | AD | Auf diesen Beitrag antworten » | ||
RE: Veröffentlichung
Begründung? |
||||
22.03.2006, 16:42 | Linker | Auf diesen Beitrag antworten » | ||
RE: Veröffentlichung In der Formel befindet sich doch eine Wurzel. Wie du weißt, kann eine Wurzel sowohl einen positiven als auch einen negativen Wert besitzen, z.B. Da die Formal auch zwei verschiedene Werte für x0 ausgeben kann, ist es möglich, 2 Nullstellen anzupeilen. |
||||
22.03.2006, 16:52 | AD | Auf diesen Beitrag antworten » | ||
RE: Veröffentlichung Bevor du hier weiter spekulierst, mache ich dir mal ein paar Vorschläge, wie du das ganze seriös vergleichen kannst: Kennst du die Begriffe Konvergenzgeschwindigkeit / Konvergenzordnung ? Wenn nicht, dann solltest du dich damit befassen, und mal die Konvergenzordnung für dein Verfahren bestimmen und z.B. mit der des Newton-Verfahrens vergleichen. Da wird dein Verfahren ganz gut abschneiden. Dann muss man allerdings abwägen, ob dass den Aufwand lohnt, da man wegen des höheren Rechenaufwands bei deinem Verfahren in der gleichen Zeit weniger Schritte ausführen kann, als beim Newton-Verfahren. Und außerdem die Problematik der Startwertbestimmung, die hier noch viel schlimmer und instabiler als beim Newton-Verfahren ist - aber das hatten wir ja schon angesprochen. EDIT:
Na und? Da wird an einer Stelle im Verlauf der Rekursion diese in zwei Zweige aufgesplittet. Inwiefern bedeutet das eine gleichzeitige Bestimmung zweier Nullstellen??? Bedeutet es nicht, denn wenn du beide Zweige dann verfolgst, machst du zwei Rekursionen zum Finden von zwei Nullstellen. Da sehe ich keine Einsparung. |
||||
22.03.2006, 17:53 | Linker | Auf diesen Beitrag antworten » | ||
RE: Veröffentlichung Ein Nachteiln an dieser Formel ist, dass sie länger ist als das Newton-Verfahren. Doch man benötigt weniger Iterationsschritte zum Berechnen der Nullstelle. |
||||
22.03.2006, 18:06 | Tobias | Auf diesen Beitrag antworten » | ||
Jede Fixpunktiteration (wobei hier genau deine Formel ist) konvergiert (mindestens) quadratisch, falls mit Fixpunkt der Iteration. Newton konvergiert lokal quadratisch (falls die Nullstelle in der Umgebung einfach ist). Bei deiner Funktion konnte ich jedoch nur lineare Konvergenz ausmachen. Für mich wird nämlich nicht 0. (Kann aber auch sein, dass ich mich verrechnet habe.) Das würde aber bedeuten, dass deine Iteration asymptotisch sogar schlechter ist als Newton. Daher würde mich interessieren: Wie hast du die Formel denn hergeleitet? |
||||
22.03.2006, 18:24 | Linker | Auf diesen Beitrag antworten » | ||
Iterationsformel Ich habe die Iterationsformel mithilfe eines quadratischen Taylor- polynoms hergeleitet. Die Taylor-Entwicklung an einer beliebigen Stelle x0 kann folgendes Näherungspolynom liefern: Und wenn man nun nach x umstellt, erhält man meine Iterationsformel. |
||||
22.03.2006, 18:38 | AD | Auf diesen Beitrag antworten » | ||
Wissen wir doch (siehe mein Beitrag vom 14.03.2006 15:47). Ich hab nochmal über den Bären nachgedacht, den du uns mit den "zwei gleichzeitig auffindbaren Nullstellen" aufbinden wolltest: Das stimmt natürlich nicht. Es muss schon eine sehr speziell gewählte Funktion sein, dass du mit deiner Folge von Taylorparabeln (so kann man ja deine Iteration grafisch deuten), deren einer Schnittpunkt gegen eine Funktionsnullstelle konvergiert, auch gleichzeitig mit der anderen Schnittunktfolge gegen eine weitere Nullstelle konvergierst! Auszuschließen ist das nicht, aber wie gesagt, das klappt nur im Ausnahmefall. Und überhaupt: Genauer müsste dein Verfahren so lauten: Der andere Zweig ist nicht zu gebrauchen, denn der führt von der Lösung weg!!! EDIT: Hab mal die Formeln unter der Wurzel noch etwas freundlicher geschrieben... |
||||
22.03.2006, 18:46 | Tobias | Auf diesen Beitrag antworten » | ||
Ja, mit der Formel von Arthur haben wir nun auch eine kubische Konvergenzrate . |
||||
23.03.2006, 11:45 | mathemaduenn | Auf diesen Beitrag antworten » | ||
Hallo Arthur_Dent, Deine erste Formel hat allerdings ein kleines Auslöschungsproblem. Ich würde also noch die Erweiterung mit dem was in der unteren Klammer steht vorschlagen. Die ursprüngliche Formel ist nat. auch nicht besser aber das dürfte die Verbesserung der Konvergenzgeschwindigkeit wieder auffressen. viele Grüße mathemaduenn |
||||
23.03.2006, 11:56 | AD | Auf diesen Beitrag antworten » | ||
Ja klar ist da ein Auslöschungsproblem, und zwar umso schlimmer, je näher man der Nullstelle kommt. Das ist bei der ursprünglichen Formel von Linker aber auch nicht anders - eine weitere, diesmal klar numerische Schwachstelle des Verfahrens. Es hat schon seine guten Gründe, warum es (bisher?) keine praktische Verwendung findet. |
||||
23.03.2006, 12:13 | mathemaduenn | Auf diesen Beitrag antworten » | ||
Aber lösbar Hallo Arthur, Man kann das Auslöschungsproblem aber auflösen indem man den hinteren Summanden mit erweitert. Das Ergebnis ist auch interessant Das erinnert doch irgendwie ans Newtonverfahren. viele Grüße mathemaduenn |
||||
23.03.2006, 12:28 | AD | Auf diesen Beitrag antworten » | ||
RE: Aber lösbar
Wie sollte es auch anders sein, ist ja eng verwandt. |
||||
23.03.2006, 16:13 | mathemaduenn | Auf diesen Beitrag antworten » | ||
Hallo nochmal,
Bei einem Verfahren der Ordnung 2 würde sich die Anzahl der gültigen Nachkommastellen verdoppeln(analog Ordnung 3 - verdreifachen) Startet man mit einer gültigen Nachkommastelle ergeben sich also in Folge: 1,2,4,8 gültige Stellen bw. 1,3,9 gültige Stellen Wenn man also 8 Stellen Genauigkeit als nonplusultra ansieht, wäre das vorgeschlagene Verfahren 1 Schritt schneller. Damit der höhere Rechenaufwand gerechtfertigt ist müßte man also schon sehr viele gültige Stellen fordern. - Vielleicht ein zukünftiges Problem :-) viele Grüße mathemaduenn |
||||
23.03.2006, 18:39 | Ben Sisko | Auf diesen Beitrag antworten » | ||
[OffTopic] Hallo mathemaduenn schön, dich mal wieder hier zu sehen. War hoffentlich keine Eintagsfliege Gruß vom Ben [/OffTopic] |
||||
23.03.2006, 19:32 | AD | Auf diesen Beitrag antworten » | ||
@mathemaduenn Ist schon klar, aber der Vorteil ist zunichte, falls ein Iterationsschritt hier um den Faktor länger dauert als beim klassischen Newtonverfahren - etwa, weil die zweite Ableitung so aufwändig in der Berechnung ist. Sowas muss man natürlich auch bedenken. |
||||
23.03.2006, 21:06 | mathemaduenn | Auf diesen Beitrag antworten » | ||
Hallo Arthur, Die Anzahl der gültigen Stellen steigt doch exponentiell mit den Iterationschritten während der Rechenaufwand nur linear steigt. Das sollte doch eigentlich eine Überschneidung geben oder? für irgendein n Wenn ich jetzt Tomaten auf den Augen habe kannst Du Sie vllt. entfernen? [OT] Hallo Ben Danke für die nette Begrüßung. Obwohl ich nat. auch öfters hier nach dem Rechten sehe;-) werd' ich sicher ab und zu vorbeischaun. viele Grüße Christian [/OT] |
||||
23.03.2006, 21:12 | AD | Auf diesen Beitrag antworten » | ||
Aber gern: Wenn ich z.B. mit dem Newtonverfahren doppelt so schnell bin, also in der gleichen Zeit (ja, unsere physikalische Zeit) doppelt so viele Schritte wie beim Linker-Verfahren ( ) durchführen kann, dann gilt: Linker-Verfahren: Schritte, macht Dezimalstellen Newton-Verfahren: Schritte (!!!), macht Dezimalstellen Jetzt klar? |
||||
23.03.2006, 23:28 | mathemaduenn | Auf diesen Beitrag antworten » | ||
Hallo Arthur, Klar. Wenn Du jetzt gefragt hättest ob's wehtut hätte ich ja sagen müssen. Aber zum Glück hast Du ja nicht gefragt;-) viele Grüße mathemaduenn |
||||
24.03.2006, 02:02 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Ah, wir haben dich also an die "Konkurrenz" verloren Schade, schade. |
||||
26.04.2006, 16:01 | mathemaduenn | Auf diesen Beitrag antworten » | ||
Aufwand der Berechnng Hallo zusammen, Da ich de Woche drübergestolpert bin rolle ich nochmal auf. Damit die von Arthur genannte Grenze nicht überschritten wird müsste die Berechnung von f(x),f'(x) eher schwer und die von f''(x) eher einfach sein. Was praktisch nat. eher selten sein dürfte. Ein 1D Bsp. wäre die Nst. von zu bestimmen. Der Hauptaufwand liegt in der Berechnung von . Das wäre aber für beide Verfahren nur einmal nötig. Da's mit dem Computer egal wäre(ob nun 10 oder 20µs) nehme man sich einen Taschenrechner ohne implementierte Exponentialfunktion, dann wäre wohl das Verfahren 3. Ordnung zu bevorzugen. Das ist aber alles nicht neu (vgl. "Numerische Lösung nichtlinearer Gleichungen" von Hubert Schwetlick Seite 164 Stichwort Euler-Chebychev-Verfahren-ein ähnliches Verfahren 3.Ordnung und wie die Bezeichnung vermuten lässt sicher schon etwas älter) viele Grüße mathemaduenn |
||||
27.04.2006, 01:16 | Noone | Auf diesen Beitrag antworten » | ||
Hö?Kann mir das vielleicht jemand erklären? |
||||
27.04.2006, 02:03 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Die 2. Ableitung ist die Nullfunktion und auch die ist wieder differenzierbar. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|