Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Kubische Gleichung: numerische Näherung schneller als Cardanische Formeln?
Thema eröffnet 2021-10-13 17:46 von MontyPythagoras
Seite 4   [1 2 3 4]   4 Seiten
Autor
Kein bestimmter Bereich Kubische Gleichung: numerische Näherung schneller als Cardanische Formeln?
AlphaSigma
Senior Letzter Besuch: im letzten Monat
Dabei seit: 23.11.2012
Mitteilungen: 360
  Beitrag No.120, eingetragen 2021-12-11

Hallo hyperG, \quoteon(2021-12-11 12:31 - hyperG in Beitrag No. 118) Wie schlecht dieser Algorithmus beim Polynom Grad 6 ist, zeigt ein Vergleich mit einem online php-Interpreter , der alles in weniger als 1 s auf 64 Stellen genau rechnet: \sourceon Beispiel 18 https://www.lamprechts.de/gerd/php/gleichung-6-grades.php Beispiel 18 0=x^6-4172632616·x^5+6344404029307640093·x^4-3603965158510003887102910160·x^3-526071972220794201468221896772894941·x^2+1349630312122629736867982208623247714325561336·x-391364266793116131369995542312354122742202695217334593 .. x1=858599509 ... \sourceoff \sourceon durand_kerner_roots.c 1. Lauf:Iterations: 841687 ... 858599509.0014115571975708008+1.99e-023j ... absolute average change: 7.512e-007 2. Lauf: Iterations: 3967976 858599509.0014125108718872070-3.42e-024j absolute average change: 7.512e-007 \sourceoff Es stimmen oft nur die ersten 5 Dezimalstellen, d.h.: - statt über 60 Dezimalstellen oft gerade mal 6 richtige - statt unter 1 s mit durand_kerner_roots 27 ... 124 s \quoteoff Durand-Kerner findet doch 11 Dezimalstellen. Im 1. Lauf macht er jedoch weiter und wird wieder schlechter. 11 Stellen bei Rechnung mit 19 Stellen sind für ein Polynom vom Grad 6 doch auch nicht so schlecht, abgesehen von der Rechenzeit. In durand_kerner_root.c ist das Konvergenzkriterium auf 1.0e-10 eingestellt. \sourceon C #define ACCURACY 1e-10 /**< maximum accuracy limit */ \sourceoff


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1681
  Beitrag No.121, eingetragen 2021-12-11

Bei der Eingabe war auch noch ein Fehler: für long double nimmt man strtold und nicht strtod siehe https://www.cplusplus.com/reference/cstdlib/strtold/ Damit bekommt man wenigstens 19 Dezimalstellen richtig "hinein": \sourceon nameDerSprache soll: ...(1349630312122629736867982208623247714325561336.0000000000000000000) x^1 + (-391364266793116131369995542312354122742202695217334593... strtod: ...(1349630312122629708819684599067218048754647040.0000000000000000000) x^1 + (-391364266793116149261522841225579724175822126678278144.0000000000000000000) x^0 = 0 strtold: ...(1349630312122629736905449240354283035528527872.0000000000000000000) x^1 + (-391364266793116131358483272997494061002670783527387136.0000000000000000000) x^0 = 0 \sourceoff Dafür schwingt dann selbst nach 10 min und 3 Versuchen nichts mehr ein. -> UNBRAUCHBAR! Wenn man immer nur "kleine Zahlenbeispiele" vorrechnet und 6 Dezimalstellen ausgibt, ist mir völlig schleierhaft, wozu man den langsamen aber etwa 3 Stellen genaueren Datentyp long double verwendet...


   Profil
AlphaSigma
Senior Letzter Besuch: im letzten Monat
Dabei seit: 23.11.2012
Mitteilungen: 360
  Beitrag No.122, eingetragen 2021-12-11

\quoteon(2021-12-11 14:10 - hyperG in Beitrag No. 121) ... -> UNBRAUCHBAR! ... \quoteoff https://www.lamprechts.de/gerd/php/gleichung-6-grades.php Beispiel 18 hat Koeffizienten mit 10 bis 54 Stellen. Was erwartest Du da denn von einer Routine die mit 19 stelligen Zahlen und einem Konvergenzkriterium von 1E-10 rechnet? \sourceon 10 20 30 40 50 12345678901234567890123456789012345678901234567890123456789 ----------------------------------------------------------- 4172632616 6344404029307640093 3603965158510003887102910160 526071972220794201468221896772894941 1349630312122629736867982208623247714325561336 391364266793116131369995542312354122742202695217334593 \sourceoff


   Profil
AlphaSigma
Senior Letzter Besuch: im letzten Monat
Dabei seit: 23.11.2012
Mitteilungen: 360
  Beitrag No.123, eingetragen 2021-12-11

Hallo hyperG, geeigneter scheint mir z.B. Bsp. 3 von _gleichung-6-grades.php zu sein. \sourceon 0=x^6+0·x^5-1.5·x^4+0·x^3+0.5625·x^2+0·x-0.046875 www.lamprechts.de x1=0.984807753012208059366743024589523013670643251719842418790025752 durand_kerner_roots.c 0.9848077530122081313+8.509008308892876813e-32j www.lamprechts.de x2=-0.984807753012208059366743024589523013670643251719842418790025752 durand_kerner_roots.c -0.9848077530122081313+8.303372339058206418e-16j www.lamprechts.de x3=0.642787609686539326322643409907263432907559884205681790324977256240837348 durand_kerner_roots.c 0.6427876096865391409-8.141868839897039569e-32j www.lamprechts.de x4=-0.642787609686539326322643409907263432907559884205681790324977256240837348 durand_kerner_roots.c -0.6427876096865391409-1.424296902380042267e-16j www.lamprechts.de x5=0.342020143325668733044099614682259580763083367514160628465048496 durand_kerner_roots.c 0.3420201433256687129-2.414456580381347374e-32j www.lamprechts.de x6=-0.342020143325668733044099614682259580763083367514160628465048496 durand_kerner_roots.c -0.3420201433256687684+3.951772281082108461e-17j \sourceoff Da stimmen alle Nullstellen von durand_kerner_roots.c auf 15 Stellen. Als "unbrauchbar" würde ich das nicht bezeichnen, auch wenn es deutlich langsamer ist. Wobei die Zeiten hier mit 0.002087 sec, 0.004367 sec und 0.004581 sec auch nicht so lang sind.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1681
  Beitrag No.124, eingetragen 2021-12-11

\quoteon(2021-12-11 16:39 - AlphaSigma in Beitrag No. 123) Hallo hyperG, geeigneter scheint mir z.B. Bsp. 3 von _gleichung-6-grades.php zu sein. \sourceon 0=x^6+0·x^5-1.5·x^4+0·x^3+0.5625·x^2+0·x-0.046875 www.lamprechts.de ... \sourceoff ... \quoteoff Dieses Beispiel gehört mit Faktor 1.5 (und kein Faktor für Grad 5 & 3) ja auch zu der von mir bezeichneten "kleine Zahlenbeispiele" Fraktion. Es müssen keine 19stelligen Faktoren sein: schon 8stellige (also da reicht schon fast Typ float) finden mit dieser absoluten Abbruchbedingung keine Konvergenz: durand_kerner_roots.exe 1 -92101235 79301924 -78562746 56528884 81776191 Was hier fehlt ist eine "saubere Abbruchbedingung" wie z.B. Iterationsanzahl 1 Mio. (oder relative Vergleiche), denn dann hat man ja schon um die 15 richtige Dezimalstellen... (wobei 1 Mio. Iterationen mit fast 1 min recht hoch gegriffen ist)


   Profil
AlphaSigma
Senior Letzter Besuch: im letzten Monat
Dabei seit: 23.11.2012
Mitteilungen: 360
  Beitrag No.125, eingetragen 2021-12-11

Hallo, eine Warnung vorab: dieser Beitrag weicht leicht von der ursprünglichen Fragestellung "numerische Näherung schneller als Cardanische Formeln?" ab. Ich finde es generell interessant was bereits zu Beginn des Computerzeitalters mit Sprachen wie dc, Algol60 oder Forth möglich war. Deshalb hier, außer Konkurrenz, eine Routine in Forth aus der Forth Scientific Library. Darin gibt es die Routine cubic zum Berechnen der (komplexen) Nullstellen von Polynomen 3. Grades mit reellen Koeffizienten. Als Quelle wird auch auf Complex roots: Abramowitz & Stegun, p. 17 3.8.2 Real roots: Press, et al., "Numerical Recipes" (1st ed.) p. 146 verwiesen. Die "Numerical Recipes" wurden ja bereits weiter oben genannt und Abramowitz & Stegun sollte auch bekannt sein. Hier denoch der Link Solution of cubic equations 3.8.2. Forth rechnet hier nur mit 32 Bit Floating-Point, daher bitte nicht zu viel erwarten. Hier die Ergebnisse für data1 bis data7. \sourceon Forth Reelle Nullstellen: data1: x = -1 data2: x = 0.1, 0.3, 0.6 data3: x = -1, 1, 2 data4: x = 2, 2, 10 (1 double root!) data5: x = -1, -1, -1 (1 triple root!) data6: x = 1.0, 1.000001, 1.000002 (nasty test proposed by Flocke, 2015, middle root is inflection point) data7: x = 1, 1.0e+07, 1.0e+14 (nasty test proposed by Strobach, 2001) $ gforth cubic.seq data1: % 1 % 0 % 0 % 1 >ROOTS x^3 - 0.00000000000000E0 x^2 - 0.00000000000000E0 x + 1.00000000000000E0 = 0 1 real, 2 complex conjugate roots Programm terminiert nicht. data2: % 1 % -1 % 0.27 % -0.018 >ROOTS x^3 - 1.00000002980232E0 x^2 + 270.000010728836E-3 x - 17.9999992251396E-3 = 0 3 real roots 99.9999869897703E-3 600.000023033657E-3 300.000019775752E-3 ok data3: % 1 % -2 % -1 % 2 >ROOTS x^3 - 2.00000005960464E0 x^2 - 1.00000000000000E0 x + 2.00000000000000E0 = 0 3 real roots -999.999977188346E-3 2.00000006549938E0 999.999971277898E-3 ok data4: % 1 % -14 % 44 % -40 >ROOTS x^3 - 13.9999995231628E0 x^2 + 44.0000000000000E0 x - 40.0000000000000E0 = 0 3 real roots 1.99929692479206E0 9.99999926266843E0 2.00070333563950E0 ok data5: % 1 % 3 % 3 % 1 >ROOTS x^3 + 3.00000000000000E0 x^2 + 3.00000000000000E0 x + 1.00000000000000E0 = 0 3 real roots -na -na -na ok data6: % 1.0 % -3.000003 % 3.000006000002 % -1.000003000002 >ROOTS x^3 - 3.00000286102295E0 x^2 + 3.00000596046448E0 x - 1.00000298023224E0 = 0 1 real, 2 complex conjugate roots 995.095531403422E-3 1.00245366480976E0 + i 4.27618891149372E-3 1.00245366480976E0 - i 4.27618891149372E-3 ok data7: % 1.0e+00 % -1.00000010000001e+14 % 1.00000010000001e+21 % -1.0e+21 >ROOTS x^3 - 100.000012959744E12 x^2 + 1.00000009040962E21 x - 1.00000002004088E21 = 0 1 real, 2 complex conjugate roots Programm terminiert nicht. \sourceoff An data1, data5 und data7 scheitert das Forth Programm. Für alle die sich trotzdem Forth näher anschauen möchten, kann ich das Buch StartingFORTH von Leo Brodie empfehlen. Ein Blick lohnt sich alleine schon wegen der Comics. [Die Antwort wurde nach Beitrag No.123 begonnen.]


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1681
  Beitrag No.126, eingetragen 2021-12-12

\quoteon(2021-12-11 21:48 - AlphaSigma in Beitrag No. 125) Hallo, eine Warnung vorab: dieser Beitrag weicht leicht von der ursprünglichen Fragestellung "numerische Näherung schneller als Cardanische Formeln?" ab. ... \quoteoff Hallo AlphaSigma, ich finde das völlig OK, wenn man leicht vom eigentlichen Thema abschweift. Gerade das "über den Tellerrand-Schauen" ist ja so interessant. So war zwar der Algorithmus zuvor nicht so besonders, aber dafür habe ich viel zum Compiler mingw64, dessen Compilerschalter und die Rechnung mit 80-Bit-Float gelernt (was ich sonst per MASM kompliziert hätte einbauen müssen). Ich bin auch völlig unvoreingenommen neuen Themen gegenüber (auch wenn es nicht immer so rüberkommt). Man muss nur ehrlich die Vor- & Nachteile betrachten & darf nicht nur einseitig nur das Positive oder nur das Negative herauspicken. Auch wenn mal nur "32 Bit Floating-Point" vorliegt, wissen wir ja alle, wie man den Datentyp entweder in Schritten 64.. oder 80 Bit, oder per GMP/mpfr beliebig erweitern kann. Da man bis zum Polynom Grad 4 rein explizit rechnen kann (PQRSTUVW-Formel), finde ich die vielen umständlichen Iterationen oder die zig Abwandlungen (Abramowitz & Stegun mit x1 = K * cos(phi / 3) - a / 3 ist ja auch nur die alt bekannte Cardanische Formeln {mit Fallunterscheidung} als Vorgänger der neuen PQRST-Formel ohne Fallunterscheidung, die wir hier schon gut optimiert hatten), eher als Blick zurück. Grüße Gerd


   Profil
AlphaSigma
Senior Letzter Besuch: im letzten Monat
Dabei seit: 23.11.2012
Mitteilungen: 360
  Beitrag No.127, eingetragen 2021-12-12

Hallo hyperG, ja, ich denke auch Anmerkungen, die wenigstens einen Bezug zum ursprünglichen Thema haben, sollten erlaubt sein. Wenigstens solange es bei einigen wenigen Abschweifungen bleibt. Wenn es mehr wird oder deutlich abweicht, sollte man allerdings besser ein neues Thema aufmachen.


   Profil
MontyPythagoras hat die Antworten auf ihre/seine Frage gesehen.
Seite 4Gehe zur Seite: 1 | 2 | 3 | 4  

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]