Finden Sie echte Wurzeln eines Polynoms

24

Schreiben Sie ein in sich geschlossenes Programm, das bei Angabe eines Polynoms und einer Schranke alle reellen Wurzeln dieses Polynoms zu einem absoluten Fehler findet, der die Schranke nicht überschreitet.

Einschränkungen

Ich weiß, dass Mathematica und wahrscheinlich einige andere Sprachen eine Ein-Symbol-Lösung haben, und das ist langweilig, deshalb sollten Sie sich an primitive Operationen halten (Addition, Subtraktion, Multiplikation, Division).

Es gibt eine gewisse Flexibilität bei den Eingabe- und Ausgabeformaten. Sie können Eingaben über stdin oder Befehlszeilenargumente in jedem vernünftigen Format vornehmen. Sie können Gleitkommazahlen zulassen oder verlangen, dass eine Darstellung rationaler Zahlen verwendet wird. Sie können die Schranke oder den Kehrwert der Schranke nehmen, und wenn Sie Gleitkommazahlen verwenden, können Sie davon ausgehen, dass die Schranke nicht weniger als 2 ulp beträgt. Das Polynom sollte als eine Liste von Monomialkoeffizienten ausgedrückt werden, es kann jedoch ein Big- oder Little-Endian sein.

Sie müssen in der Lage sein zu begründen, warum Ihr Programm immer funktioniert (modulo-numerische Probleme), obwohl es nicht erforderlich ist, vollständige Proofs inline bereitzustellen.

Das Programm muss Polynome mit wiederholten Wurzeln verarbeiten.

Beispiel

x^2 - 2 = 0 (error bound 0.01)

Eingabe könnte zB sein

-2 0 1 0.01
100 1 0 -2
1/100 ; x^2-2

Ausgabe könnte zB sein

-1.41 1.42

aber nicht

-1.40 1.40

da das absolute fehler von ca. 0,014 hat ...

Testfälle

Einfach:

x^2 - 2 = 0 (error bound 0.01)

x^4 + 0.81 x^2 - 0.47 x + 0.06 (error bound 10^-6)

Mehrfachwurzel:

x^4 - 8 x^3 + 18 x^2 - 27 (error bound 10^-6)

Wilkinsons Polynom:

x^20 - 210 x^19 + 20615 x^18 - 1256850 x^17 + 53327946 x^16 -1672280820 x^15 +
    40171771630 x^14 - 756111184500 x^13 + 11310276995381 x^12 - 135585182899530 x^11 +
    1307535010540395 x^10 - 10142299865511450 x^9 + 63030812099294896 x^8 -
    311333643161390640 x^7 + 1206647803780373360 x^6 -3599979517947607200 x^5 +
    8037811822645051776 x^4 - 12870931245150988800 x^3 + 13803759753640704000 x^2 -
    8752948036761600000 x + 2432902008176640000  (error bound 2^-32)

NB Diese Frage war ungefähr 3 Monate in der Sandbox . Wenn Sie der Meinung sind, dass es vor dem Posten verbessert werden muss, besuchen Sie die Sandbox und kommentieren Sie die anderen vorgeschlagenen Fragen, bevor sie auf Main veröffentlicht werden.

Peter Taylor
quelle
"Sie müssen in der Lage sein zu rechtfertigen, warum Ihr Programm immer funktioniert." Nur für den Fall, dass jemand dabei Hilfe benötigt
Dr. belisarius
@belisarius, ??
Peter Taylor
3
war als Witz gedacht :(
Dr. belisarius
Ich weiß, dass dies eine alte Herausforderung ist, also fühlen Sie sich nicht gezwungen zu antworten, wenn Sie keine Lust haben, sie erneut zu eröffnen. (a) Können wir eine Funktion schreiben oder nur ein vollständiges Programm? (b) Können wir für den Fall, dass wir eine Funktion schreiben können, annehmen, dass die Eingabe einen geeigneten Datentyp verwendet, z. B. Python's fractions.Fraction(einen rationalen Typ)? (c) Müssen wir mit Polynomen <1 umgehen? (d) Können wir annehmen, dass der führende Koeffizient 1 ist?
Ell
(e) In Bezug auf Polynome mit wiederholten Wurzeln lohnt es sich, zwischen Wurzeln ungerader und gerader Multiplizität zu unterscheiden (die Testfälle haben nur Wurzeln ungerader Multiplizität). Ich bin mir nicht sicher, wie greifbar es ist, Wurzeln mit gerader Multiplizität numerisch korrekt zu behandeln, zumal Sie nur einen Fehlerbereich für die Werte der Wurzeln angeben, nicht für deren Existenz. (...)
Ell

Antworten:

8

Mathematica, 223

r[p_,t_]:=Module[{l},l=Exponent[p[x],x];Re@Select[NestWhile[Table[#[[i]]-p[#[[i]]]/Product[If[i!=j,#[[i]]-#[[j]],1],{j,l}],{i,l}]&,Table[(0.9+0.1*I)^i,{i,l}],2*Max[Table[Abs[#1[[i]]-#2[[i]]],{i,l}]]>t&,2],Abs[Im[#]]<t^.5&]]

Diese Lösung implementiert die Durand-Kerner-Methode zur Lösung von Polynomen. Beachten Sie, dass dies keine vollständige Lösung ist (wie unten gezeigt wird), da ich Wilkinsons Polynom noch nicht mit der angegebenen Genauigkeit verarbeiten kann. Zuerst eine Erklärung, was ich tue: Code in Mathematica-Formatierung

#[[i]]-p[#[[i]]]/Product[If[i!=j,#[[i]]-#[[j]],1],{j,l}]&: So berechnet die Funktion für jeden Index idie nächste Durand-Kerner-Näherung. Dann wird diese Linie in eine Tabelle gekapselt und mit NestWhile auf die von erzeugten Eingabepunkte angewendet Table[(0.9+0.1*I)^i,{i,l}]. Die Bedingung für NestWhile ist, dass die maximale Änderung (über alle Terme hinweg) von einer Iteration zur nächsten größer ist als die angegebene Genauigkeit. Wenn sich alle Terme weniger geändert haben, endet NestWhile und Re@Selectentfernt die Nullen, die nicht auf die reale Linie fallen.

Beispielausgabe:

> p[x_] := x^2 - 2
> r[p, .01]
{1.41421, -1.41421}

> p[x_] := x^4 - 8 x^3 + 18 x^2 - 27
> r[p, 10^-6]
{2.99999, 3., 3.00001, -1.}

> p[x_] := x^20 - 210 x^19 + ... + 2432902008176640000 (Wilkinson's)
> Sort[r[p, 2^-32]]
{1., 2., 3., 4., 5., 6., 7.00001, 7.99994, 9.00018, 10.0002, 11.0007, \
11.9809, 13.0043, 14.0227, 14.9878, 16.0158, 16.9959, 17.9992, \
19.0001, 20.}

Wie Sie wahrscheinlich sehen können, springt diese Methode, wenn der Grad höher wird, um die korrekten Werte herum, ohne wirklich vollständig einzusteigen. Wenn ich die Stoppbedingung meines Codes auf etwas Strengeres als "Von einer Iteration zur nächsten ändern sich die Vermutungen um nicht mehr als Epsilon" einstelle, stoppt der Algorithmus nie. Ich denke, ich sollte nur Durand-Kerner als Input für Newtons Methode verwenden?

Kaya
quelle
Durand-Kerner hat auch potenzielle Probleme mit mehreren Wurzeln. (Newtons Methode könnte auch nicht viel helfen - Wilkinsons Polynom wird speziell ausgewählt, um schlecht konditioniert zu sein).
Peter Taylor
Sie haben völlig recht: Ich habe diese Vorgehensweise abgebrochen, nachdem ich auf Wilkinsons nahe x = 17 gezoomt habe. Es ist ein absolutes Durcheinander. Ich mache mir Sorgen, dass ich eine symbolische Lösung auf Groebner-Basis anstreben muss, um viel mehr Genauigkeit zu erzielen.
Kaya