| |
| Seite 4 [1 2 3 4] | 4 Seiten |
| Autor |
 Kubische Gleichung: numerische Näherung schneller als Cardanische Formeln? |
|
AlphaSigma
Senior 
Dabei seit: 23.11.2012
Mitteilungen: 453
 |  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 
Dabei seit: 03.02.2017
Mitteilungen: 2115
 | 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
Dabei seit: 23.11.2012
Mitteilungen: 453
| 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
Dabei seit: 23.11.2012
Mitteilungen: 453
| 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
Dabei seit: 03.02.2017
Mitteilungen: 2115
| 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
Dabei seit: 23.11.2012
Mitteilungen: 453
| 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
Dabei seit: 03.02.2017
Mitteilungen: 2115
| 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
Dabei seit: 23.11.2012
Mitteilungen: 453
| 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
|
AlphaSigma
Senior
Dabei seit: 23.11.2012
Mitteilungen: 453
| Beitrag No.128, eingetragen 2022-12-28
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2115
| Beitrag No.129, eingetragen 2022-12-28
|
Danke AlphaSigma, Interessante Seite mit vielen Fakten!
Gerade für exotische Funktionen, schlimmer Fehlerfortpflanzung oder extrem hoher Nachkommastellenanzahl ist ein Algorithmusvergleich immer wichtig!
"Solaiman, Hashin MH2" mit Konvergenzordnung 6 und Effizienz 1,565
(Nutzung von bereits berechneten Werten statt 2. Ableitung von komplizierten Funktionen) -> hört sich interessant an!
Oder für universelle hypergeometrische Funktionen (exakte Ableitung nur für wenige Spezialfälle möglich!) hört sich "OGC ableitungsfrei" mit Konvergenzordnung 6 interessant an! Müsste man mal mit AppellF1...F4
(siehe hier)
testen, ab wieviel Soll-Nachkommastellen hier welche Verbesserungen erreicht werden können... Da hatte ich mich mal sehr gequält und das gut gebrauchen können.
Wenn ich mir die Quellenangabe ansehe, scheinen viele Algorithmen auch relativ neu zu sein.
Grüße Gerd
|
Profil
|
| MontyPythagoras hat die Antworten auf ihre/seine Frage gesehen. | | Seite 4 | Gehe zur Seite: 1 | 2 | 3 | 4 |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 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]
|
Home / Seite ohne Frame
2023-09-30 16:09 U <
Wie unterstütze ich den Matheplaneten mit Geld?
