BenBE: Mathematisch gesehen ist natürlich eine exakte Formel genauer als jegliche Iterationsformel. Das ist definitiv so.
Jedoch (und dieser Fall ist für die Numerik relevant) ist eine komplizierte exakte Formel bei einer numerischen Rechnung mit endlicher Genauigkeit fast immer schlechter als eine einfachere Rekursionsformel. Bei der Rekursionsformel kann ich bis zur Maschinengenauigkeit genau rechnen, nämlich ganz einfach, in dem ich einfach so lange iteriere, bis die Maschinengenauigkeit erreicht ist. In der Praxis macht man einfach so lange, bis sich die Zahl nicht mehr ändert.
Bei einer fertigen Formel jedoch muss man aufpassen: Da rechnet man ja nur ein mal, und eventuelle Rundungsfehler in der letzten Nachkommastelle schaukeln sich eventuell auf. Diese können nicht mehr korrigiert werden. Wenn die Rechnung abgeschlossen ist, muss man hoffen, dass man nahe am exakten Wert ist. Bei der Iteration ist das nicht so. Dort kann ich die Genauigkeit selbst bestimmen.
Beispiel:
Polynom 4. Grades: (x-100)*(x-101)*(x-102)*(x-103)
Nullstellen sind also: 100, 101, 102, 103
Koeffizienten lauten: a=1, b=-406, c=61811, d=-4182206, e=106110600
Durch Einsetzen in eine Fertig-Formel erhält man die Nullstellen:
106.962775739360 - 3.033763478306i
104.634140557553 + 5.287819491106i
98.365859442441 - 5.287819491129i
96.037224260647 + 3.033763478329i
Durch Iteration hingegen erhält man:
102.999999958598
102.000000121276
100.999999881611
100.000000038515
Die iterative Lösung wurde mithilfe von Matrix Rechnung und dem QR-Algorithmus bestimmt. Mit dem modifizierten QD-Algorithmus wäre die Rechnung wahrscheinlich bis auf die letzte Stelle genau, jedoch ginge die Rechnung auch ein wenig länger.
Auf jeden Fall sieht man, dass die Lösungsformel sehr ungenau ist. Das Resultat ist praktisch unbrauchbar.
Konvergenz: Die Genauigkeit muss nicht immer proportional zur Anzahl Iterationsschritte sein. Newton konvergiert z.B. von zweiter Ordnung. Das heisst praktisch(/unwissenschaftlich) gesprochen: Die Lösung hat nach jedem Schritt doppelt so viele korrekte Nachkommastellen. Zuerst 1 Stelle, dann 2, dann 4, 8. Man sieht: Nach 5-6 Schritten hat man bereits 16 korrekte Nachkommastellen.
Es gibt auch Verfahren, die sogar von dritter Ordnung konvergieren. Zum Beispiel folgende Funktion, die sqrt(a^2+b^2) berechnet (und zwar ohne jemals die Wurzel zu ziehen. Ein Überlauf, wie bei der Rechnung sqr(a)+sqr(b) auftreten kann, passiert nie):
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| function Pythagoras(a, b: Extended): Extended; var q, p, r, s: Extended; I: Integer; begin if abs(a)>abs(b) then begin p := a; q := b; end else begin p := b; q := a; end; for I := 1 to 3 do begin r := sqr(q/p); s := r/(4+r); p := p + 2*s*p; q := s*q; end; Result := p; end; |
Da wegen kubischer Konvergenz (fast) nie mehr als 3 Schritte nötig sind, hab ich das bereits so drin. Die Funktion ist ca. 5x (oder mehr) langsamer als ein "sqrt(sqr(a)+sqr(b))", das ist aber klar, weil die exakte Formel sehr kurz ist.