Autor Beitrag
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: So 19.06.05 13:15 
Eine Iterative Lösung ist nach meinen Erfahrungen nur so genau, wie der Datentyp, den man dafür verwendet proportional zur Anzahl der Iterationsschritte.

Eine konkretes Lösungsverfahren anhand einer Formel ist somit in 99% der Fälle für Gleichungen 3. und 4. Grades wesentlich genauer als jeglliche Iteration.

Außerdem kann man, wie Du bereits sagtest, die Gleichungen stark vereinfachen ... --> Beschleunigung dieser.

JMHO.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
harryp
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 52
Erhaltene Danke: 9

Win 8.1
Delphi 7, XE8
BeitragVerfasst: So 19.06.05 13:29 
Mal ne Zwischenfrage : was haltet ihr für die Nullstellenberechnung einfach mal vom Sekantenverfahren oder vom Newton-Verfahren.

--> Mittels der Funktion und ihrer Ableitung sich der Nullstelle immer mehr annähern ?
Geht eigentlich recht gut und für alle Funktion (die in dem Bereich definiert sind) (also nicht nur ganzrat. Funktionen, sondern auch trigonometrische, Exponentialfkt usw...).
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: So 19.06.05 13:46 
\Sekantenverfahren sind beides mögliche Wege das Problem zu lösen, bieten aber gerade bei Funktionen höheren Grades mitunter hohe Iterationsschritte, bzw. müssen speziell gehandhabt werden, wenn eine Funktion einen Minimumpunkt\Maximumpunkt hat, der nicht von Nullstellen umgeben ist.

BTW: Newton bzw. Regula Falsi liefern absolut nette Singularitäten, wenn F'(x) beim Startwert oder irgendeinem Zwischenwert 0 ist. Außerdem empfehle ich mal zu versuchen mit Regula Falsi die Nullstelle einer Exponential-Funktion zu suchen ;-)

Mit Lösungsformeln erhält man ohne langwierige Iterationen gleich dire korrekten Werte.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
harryp
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 52
Erhaltene Danke: 9

Win 8.1
Delphi 7, XE8
BeitragVerfasst: So 19.06.05 17:04 
ok, für einige Funktionen mag Regula Falsi / Newton nicht so geeignet zu sein.
Aber im Allgemeinen geht das doch recht gut, gerade wenn man sinnvolle Startwerte wählt (Kann ja überprüfen ob f'(x)=0 oder nicht)

edit: Also zumindest mein Infolehrer (auch mal mein Mathelehrer gewesen) hat mir jedenfalls von diesen Lösungsformeln ab 3. Grad abgeraten
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: So 19.06.05 20:54 
user profile iconBenBE: 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):

ausblenden 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.
iX0r
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 34

Ubuntu
D6, Lazarus
BeitragVerfasst: Fr 01.07.05 06:19 
ich weise darauf hin, dass eine QR zerlegung nur bei postiv definiten matrizen möglich ist (denn eine qr zerlegung ist gleichzeitig ein test auf postive definitheit einer matrix). wenn dies nicht der fall ist, empfiehlt sich die lösung des problems mittels eine orthogonalen transformation, wie es zum beispiel das householder verfahren macht.
praktisch daran ist, dass sich die kondition des problems nicht verschlechtert (die euklidische norm bleibt unter orthognaltransformationen invariant).
zum konkreten problem:
polynome bis grad 3 können ohne iteration gelöst werden (lösungsformel).
für probleme höherer ordnung empfiehlt sich:
- newton (im idelfall quadratische konvegenz)
- regula false (in der erweiterten form afair konvergenzordnung von (1+sqrt(5)*2)
- wenn diese beiden gar nicht funktionieren, kann man es immer noch mit fixpunktiteration versuchen, die hinreichende bedingung dazu ist allerdings dass die funktion in der umgebung deiner nullstelle L-stetig ist.

also insgesamt kein wirklcih triviales probelm, aber im bereich der polynome noch alles gefahrlos möglich!
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Fr 01.07.05 10:21 
user profile iconiX0r:
Bevor du dich mit Fachwörtern rumschmeisst:

- Du verwechselst die QR-Zerlegung mit der Cholesky-Zerlegung. Deine "orthogonalen transformation" ist die QR-Zerleung. Q=Orthogonalmatrix, R=Rechte obere Dreiecksmatrix.
- QR Zerlegung geht für jede Matrix mit vollem Rang (Beweis: Q kann aus Gram-Schmidt Verfahren berechnet werden). (iirc geht's aber auch für singuläre Matrizen)
- QR-Zerlegung kann man auch mit der Householder-Transformation berechnen (bis auf Vorzeichen identische Lösung wie mit Gram-Schmidt)
- (Geschlossene) Lösungsformeln gibt es sogar bis Polyn. 4. Grades. Wieso die aber numerisch schlecht sind, hab ich auch schon erklärt (siehe oben)
- Newton ist nicht geeignet für mehrfache Nullstellen. Mit quadratischer Konvergenz kann man sonst eigentlich immer rechnen.

:arrow: Zuverlässige Lösung: Companion-Matrix + Eigenwertsolver via QR (bzw. mit dem hochpräzisen modifizierten QD).