Entscheidbarkeit der Bestimmung von Nullstellen eines Polynoms mit reellen Koeffizienten |
| 14.12.2015, 13:58 | Aldonis | Auf diesen Beitrag antworten » |
| Entscheidbarkeit der Bestimmung von Nullstellen eines Polynoms mit reellen Koeffizienten Gegeben sei ein Polynom Gibt es einen Algorithmus, welcher eine Nullstelle des Polynoms in endlicher Zeit bestimmen kann? sind reellwertige Koeffizienten, die gesuchten Nullstellen dürfem von mir aus gerne auch komplex sein. Als Entscheidungsproblem formuliert wäre es dann z.B. "Hat das Polynom p eine nullstelle n mit n > c". wobei c eine beliebige Konstante ist (z.B. 0) Ich bin nicht unbedingt an einem praktischen Verfahren interessiert, eher an dessen Komplexität (welche vermutlich mehrfahch exponentiell sein dürfte, falls das Problem überhaupt entscheidbar ist) Sobald eine reelle oder komplexe Nullstelle gefunden ist, kann der Grad des Polynoms durch Division reduziert werden, wodruch rekursiv alle Nullstellen gefunden werden können. Meine Ideen: Der Satz von Abel-Ruffini besagt, dass es keine geschlossene Form für Gleichungen 5. oder höheren Grades geben kann. Der Satz von Abel-Ruffini besagt aber NICHT dass das finden von Nullstellen von Polynomen höheren grades unentscheidbar ist. In der Praxis verwendet man deshalb numerische Näherungsverfahren. Diese finden natürlich zumeist recht schnell eine Lösung, die meisten terminieren aber nicht nach endlicher Zeit. Google hilft nicht weiter, da "Entscheidbarkeit" und "Polynome" immer zu Hilberts 10. Problem führt. (und für diophantische Gleichungen ist das Problem unentscheidbar). Ich bin aber nicht an ganzzahligen Lösungen interessiert, und es gibt auch nur eine Unbekannte. Hintergrundwissen: Ich bin Informatiker und habe die Grundvorlesungen in Mathe gehört |
||
| 14.12.2015, 18:38 | Elvis | Auf diesen Beitrag antworten » |
Wie gibst Du die reellen Koeffizienten ein ? In Dezimalzahlen ? Das dauert für jeden Koeffizienten unendlich lange. 
|
||
| 15.12.2015, 11:26 | Aldonis | Auf diesen Beitrag antworten » |
Guter Punkt, das hab ich übersehen! Das macht die numerischen Verfahren natürlich dann wieder sehr attraktiv, und erklärt warum Google nichts über die ursprüngliche Problemstellung ausspuckt 
Dann suche ich also ein Intervall so dass die echte Nullstelle innerhalb dieses Intervalls liegt. Damit wird die Komplexität natürlich auch von der Präzision meiner Zahlendarstellung abhängen. Dann werde ich mir die numerischen Verfahren und ihre Laufzeiten / Konvergenzgeschwindigkeiten jetzt nochmal genauer anschauen. Vielen Dank! |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
