Ein neues Iterationsverfahren

14.03.2006, 15:10

Linker

Auf diesen Beitrag antworten »

Ein neues Iterationsverfahren

Hallo,

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:

$\begin{eqnarray*} x = x_{0} - \frac{f'(x_{0})}{f''(x_{0})} + \sqrt{(\frac{f'(x_{0})}{f''(x_{0})})^{2} - \frac{f(x_{0})}{f''(x_{0})}} \end{eqnarray*}$

Man kann es probieren an

$\begin{eqnarray*} f(x) = x^{3}+ 2 x^{2} - 19 x + 6 \end{eqnarray*}$

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:

Zitat:

Das größte Problem bei der Anwendung des Newton-Verfahrens liegt darin, dass man die erste Ableitung der Funktion benötigt. Die Berechnung dieser ist meist aufwändig und in vielen Anwendungen ist eine Funktion auch nicht explizit, sondern beispielsweise nur durch ein Computerprogramm gegeben (siehe auch Automatisches Differenzieren). Im eindimensionalen ist dann die Regula Falsi vorzuziehen, bei der die Sekante und nicht die Tangente benutzt wird. Im Mehrdimensionalen muss man andere Alternativen suchen. Hier ist das Problem auch dramatischer, da die Ableitung eine Matrix mit n^2 Einträgen ist, der Aufwand der Berechnung steigt also quadratisch mit der Dimension.

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

$\begin{eqnarray*} \frac{f(x_{0})}{f''(x_{0})} \end{eqnarray*}$

soll eigentlich stehen:

$\begin{eqnarray*} \frac{2f(x_{0})}{f''(x_{0})} \end{eqnarray*}$

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:

$\begin{eqnarray*} x = x_{0} - \frac{f'(x_{0})}{f''(x_{0})} + \sqrt{(\frac{f'(x_{0})}{f''(x_{0})})^{2} - \frac{2f(x_{0})}{f''(x_{0})}} \end{eqnarray*}$

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. Augenzwinkern

Augenzwinkern

14.03.2006, 22:46

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von Linker
Dieses Verfahren kann nur benutzt werden, wenn die Funktion mindestens eine Funktion 2.Grades ist (weil da eine 2.Ableitung existiert).

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? verwirrt

verwirrt

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

Zitat:

Original von Linker
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!

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

Zitat:

Original von Linker
Man könnte mit dieser Formel 2 Nullstellen gleichzeitig berechnen.

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.

$\begin{eqnarray*} \sqrt{9} = 3 \end{eqnarray*}$
$\begin{eqnarray*} \sqrt{9} = -3 \end{eqnarray*}$

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:

Zitat:

Original von Linker
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.

$\begin{eqnarray*} \sqrt{9} = 3 \end{eqnarray*}$
$\begin{eqnarray*} \sqrt{9} = -3 \end{eqnarray*}$

Da die Formal auch zwei verschiedene Werte für x0 ausgeben kann, ist es möglich, 2 Nullstellen anzupeilen.

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. unglücklich

unglücklich

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 $\begin{eqnarray*} x_{n+1} = \Phi(x_n) \end{eqnarray*}$ (wobei $\begin{eqnarray*} \Phi(x_n) \end{eqnarray*}$ hier genau deine Formel ist) konvergiert (mindestens) quadratisch, falls $\begin{eqnarray*} \Phi'(x^\ast) = 0 \end{eqnarray*}$ mit $\begin{eqnarray*} x^\ast \end{eqnarray*}$ 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 $\begin{eqnarray*} \Phi'(x^\ast) \end{eqnarray*}$ 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:

$\begin{eqnarray*} T(x) = f(x_{0}) + f'(x_{0})(x - x_{0}) + \frac{f''(x_{0})}{2}(x - x_{0})^2 \end{eqnarray*}$

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:

$\begin{eqnarray*} x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)} \left[ 1- \sqrt{1-\frac{2f(x_n)f''(x_n)}{(f'(x_n))^2}} \right] \end{eqnarray*}$

Der andere Zweig

$\begin{eqnarray*} x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)} \left[ 1+ \sqrt{1-\frac{2f(x_n)f''(x_n)}{(f'(x_n))^2}} \right] \end{eqnarray*}$

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 $\begin{eqnarray*} O(\|x^\ast - x_k\|^3) \end{eqnarray*}$ .

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
$\begin{eqnarray*} \frac{1+ \sqrt{1-\frac{2f(x_n)f''(x_n)}{(f'(x_n))^2}}}{1+ \sqrt{1-\frac{2f(x_n)f''(x_n)}{(f'(x_n))^2}}} \end{eqnarray*}$
erweitert.
Das Ergebnis ist auch interessant
$\begin{eqnarray*} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \left[ \frac{2}{1+ \sqrt{1-\frac{2f(x_n)f''(x_n)}{(f'(x_n))^2}}}\right] \end{eqnarray*}$
Das erinnert doch irgendwie ans Newtonverfahren.
viele Grüße
mathemaduenn

23.03.2006, 12:28

AD

Auf diesen Beitrag antworten »

RE: Aber lösbar

Zitat:

Original von mathemaduenn
Das erinnert doch irgendwie ans Newtonverfahren.

Wie sollte es auch anders sein, ist ja eng verwandt. Augenzwinkern

Augenzwinkern

23.03.2006, 16:13

mathemaduenn

Auf diesen Beitrag antworten »

Hallo nochmal,

Zitat:

Original von Arthur Dent
Es hat schon seine guten Gründe, warum es (bisher?) keine praktische Verwendung findet.

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 Wink

Wink

schön, dich mal wieder hier zu sehen.
War hoffentlich keine Eintagsfliege Big Laugh

Big Laugh

Augenzwinkern

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 $\begin{eqnarray*} \log_2 3 \end{eqnarray*}$ 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. Augenzwinkern

Augenzwinkern

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?
$\begin{eqnarray*} \frac{3^n}{an}>\frac{2^n}{bn} \end{eqnarray*}$ für irgendein n
Wenn ich jetzt Tomaten auf den Augen habe kannst Du Sie vllt. entfernen?

[OT]
Hallo Ben Wink

Wink

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 »

Zitat:

Original von mathemaduenn
Wenn ich jetzt Tomaten auf den Augen habe kannst Du Sie vllt. entfernen?

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 ( Augenzwinkern

Augenzwinkern

) durchführen kann, dann gilt:

Linker-Verfahren: $\begin{eqnarray*} n \end{eqnarray*}$ Schritte, macht $\begin{eqnarray*} 3^n \end{eqnarray*}$ Dezimalstellen

Newton-Verfahren: $\begin{eqnarray*} 2n \end{eqnarray*}$ Schritte (!!!), macht $\begin{eqnarray*} 2^{2n}=4^n \end{eqnarray*}$ 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 »

Zitat:

Original von mathemaduenn
[OT]
Hallo Ben Wink

Wink

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]

Ah, wir haben dich also an die "Konkurrenz" verloren Augenzwinkern

Augenzwinkern

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 $\begin{eqnarray*} x+e^x \end{eqnarray*}$ zu bestimmen. Der Hauptaufwand liegt in der Berechnung von $\begin{eqnarray*} e^x \end{eqnarray*}$ . 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 »

Zitat:

Original von Ben Sisko
Zur Info für dich: Die Funktion f(x)=3x+2 ist beliebig oft differenzierbar!

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.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »