Nullstellen von Polynomen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:23 Sa 04.04.2009 | | Autor: | Marc |
Hallo,
ich würde gerne ein Programm schreiben, dass die Nullstellen von Polynomen exakt ermitteln kann. Dazu habe ich das Problem in mehrere Fälle klein gehackt:
Fall 1: Polynom hat nur ganzzahlige Koeffizienten, gesucht werden rationale Nullstellen.
[mm] $a_n*x^n+a_{n-1}*x^{n-1}+\ldots+a_2*x^2+a_1*x+a_0=0$, $a_i\in\IZ$
[/mm]
Hier muss ja für eine rational Nullstellen [mm] $x=\bruch{a}{b}$ [/mm] gelten: [mm] $a|a_0$ [/mm] und [mm] $b|a_n$.
[/mm]
Auf diese Weise lassen sich alle rationalen Nullstellen finden.
Fall 2: Polynom hat nur rationale Koeffizienten, gesucht werden rationale Nullstellen.
Auch kein Problem, es muss die Nullstellengleichung nur mit dem Hauptnenner aller [mm] $a_i$ [/mm] multipliziert werden und man sieht sich auf Fall 1 zurück geführt.
Fall 3: Polynom hat nur ganzzahlige Koeffizienten, gesucht werden komplexe Nullstellen, die gaußsche Zahlen sind (also $a+bi$ mit [mm] $a,b\in\IZ$
[/mm]
Fall 3a)
[mm] $x^n+a_{n-1}*x^{n-1}+\ldots+a_2*x^2+a_1*x+a_0=0$, $a_i\in\IZ$
[/mm]
Hier muss ja gelten [mm] $(a^2+b^2)|a_n$. [/mm] Diese Bedingung liefert auch nur endlich viele Kandidaten, ist also kein Problem.
Jetzt kommen die Fälle, bei denen ich Probleme habe und ich auf Eure Hilfe hoffe:
Fall 3b)
[mm] $\red{a_n}*x^n+a_{n-1}*x^{n-1}+\ldots+a_2*x^2+a_1*x+a_0=0$, $a_i\in\IZ$
[/mm]
???
Fall 4: Polynom hat nur ganzzahlige Koeffizienten, gesucht werden komplexe Nullstellen von der Form $a+bi$ mit [mm] $a,b\in\red{\IQ}$
[/mm]
???
Fall 5: Polynom hat nur gaußsche Zahlen als Koeffizienten, gesucht werden komplexe Nullstellen von der Form $a+bi$ mit [mm] $a,b\in\red{\IZ}$
[/mm]
???
Mit den weiteren Fällen wage ich mich erstmal nicht mich zu beschäftigen...
Hat jemand eine Idee für die Fälle 3b, 4 oder 5, z.B. eine Reduktionsmöglichkeit auf die vorherigen Fälle? Das wäre toll.
Viele Grüße,
Marc
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:40 Sa 04.04.2009 | | Autor: | felixf |
Hallo Marc
> ich würde gerne ein Programm schreiben, dass die
> Nullstellen von Polynomen exakt ermitteln kann.
Du willst also nur Nullstellen finden, die auch in [mm] $\IQ[i]$ [/mm] liegen, und sonst keine? Hab ich das richtig verstanden?
> Dazu habe
> ich das Problem in mehrere Fälle klein gehackt:
>
> Fall 1: Polynom hat nur ganzzahlige Koeffizienten, gesucht
> werden rationale Nullstellen.
>
> [mm]a_n*x^n+a_{n-1}*x^{n-1}+\ldots+a_2*x^2+a_1*x+a_0=0[/mm],
> [mm]a_i\in\IZ[/mm]
>
> Hier muss ja für eine rational Nullstellen [mm]x=\bruch{a}{b}[/mm]
> gelten: [mm]a|a_0[/mm] und [mm]b|a_n[/mm].
>
> Auf diese Weise lassen sich alle rationalen Nullstellen
> finden.
>
> Fall 2: Polynom hat nur rationale Koeffizienten, gesucht
> werden rationale Nullstellen.
>
> Auch kein Problem, es muss die Nullstellengleichung nur mit
> dem Hauptnenner aller [mm]a_i[/mm] multipliziert werden und man
> sieht sich auf Fall 1 zurück geführt.
Genau, diese beiden Faelle sind einfach, und sie reichen auch aus den allgemeinen Fall zu loesen: finden von Nullstellen in [mm] $\IQ[i]$ [/mm] von Polynomen in [mm] $\IQ[i][x]$.
[/mm]
Sei $f [mm] \in \IQ[i][x]$ [/mm] ein Polynom und $t = a + i b [mm] \in \IQ[i]$ [/mm] ein allgemeines Element. Wenn man $f(a + i b) = 0$ ausmultipliziert und aufspaltet in Real- und Imaginaerteil, so bekommt man zwei (nichtlineare, aber polynomielle) Gleichungen in den zwei Unbestimmten $a, b$, sagen wir mal [mm] $g_1(a, [/mm] b) = 0$ und [mm] $g_2(a, [/mm] b) = 0$ mit [mm] $g_1, g_2 \in \IQ[a, [/mm] b]$. Diese sollen jetzt simultan geloest werden.
Kommt in [mm] $g_1$ [/mm] oder [mm] $g_2$ [/mm] nur eine Variable vor, sagen wir mal [mm] $g_1$ [/mm] ist nur ein Polynom von $a$, so kann man bei dem Polynom nach der Methode oben die Nullstellen suchen und in das zweite einsetzen, also fuer jeden Wert von $a$, den man fuer [mm] $g_1$ [/mm] bekommt, schaut man sich [mm] $g_2(a, [/mm] b)$ als Polynom in $b$ an und wendet wieder die obige Methode an.
Also koennen wir annehmen, dass sowohl $a$ und $b$ jeweils in [mm] $g_1$ [/mm] und [mm] $g_2$ [/mm] vorkommen.
Jetzt kann man einen Kniff benutzen, und zwar ![[]](/images/popup.gif) Resultanten. Und zwar schreibt man [mm] $\IQ[a, [/mm] b] = R[b]$ mit $R = [mm] \IQ[a]$ [/mm] und berechnet die Resultante $h [mm] \in [/mm] R$ von [mm] $g_1$ [/mm] und [mm] $g_2$ [/mm] ueber $R$. Dazu benoetigt man nur Polynomarithmetik.
Jetzt hat man folgendes: zu einem festen $a [mm] \in \IQ$ [/mm] gibt es genau dann $b [mm] \in \IC$ [/mm] (bzw genauer: im algebraischen Abschluss von [mm] $\IQ$) [/mm] mit [mm] $g_1(a, [/mm] b) = 0 = [mm] g_2(a, [/mm] b)$, wenn $h(a) = 0$ ist.
Also wendest du den obigen Fall 2 auf $h [mm] \in \IQ[a]$ [/mm] an, und fuer jedes $a$ was du erhaelst setzt du dieses in [mm] $g_1$ [/mm] und [mm] $g_2$ [/mm] ein und guckst ob du $b$ findest, die von beiden Polynomen Nullstellen sind. Dies kannst du sogar noch vereinfachen: berechne den groessten gemeinsamen Teiler $d [mm] \in \IQ[b]$ [/mm] von [mm] $g_1(a, [/mm] b), [mm] g_2(a, [/mm] b) [mm] \in \IQ[b]$ [/mm] mit Hilfe des euklidschen Algorithmus; dann sind die Nullstellen von $d$ genau die $b$s mit $f(a + i b) = 0$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:49 Sa 04.04.2009 | | Autor: | felixf |
Hallo,
noch ein Zusatz zur Berechnung der Resultante. Dazu muss man ja die Determinante einer Matrix mit Eintraegen in [mm] $\IQ[x]$ [/mm] bestimmen. Man kann natuerlich den Quotientenkoerper [mm] $\IQ(x)$ [/mm] von [mm] $\IQ[x]$ [/mm] betrachten und dort die Determinante mit den ueblichen Rechenregeln (z.B. auf Zeilenstufenform bringen) benutzen, aber dazu muss man dann in [mm] $\IQ(x)$ [/mm] rechnen.
Einfacher ist es, die Matrix in Hermitesche Normalform zu ueberfuehren -- dies geht vollstaendig ueber [mm] $\IQ[x]$.
[/mm]
Ich hatte das mal in C++ implementiert, die Polynomarithmetik von NTL nutzend (mit Templates um es nicht auf einen speziellen Grundkoerper festzulegen). Vielleicht kannst du damit was anfangen. Ich hoffe es ist nicht zu unleserlich 
| 1: | template<class Scalar, class Poly>
| | 2: | Poly Determinant(Matrix<Poly> & M)
| | 3: | // Given M, computes the (monic) determinant det of M.
| | 4: | // We assume that M is a square matrix.
| | 5: | // Note that M will be DESTROYED!
| | 6: | {
| | 7: | assert(M.rows() == M.cols());
| | 8: | // Compute something similar to a row HNF
| | 9: | Poly a, b, d, e, f, t;
| | 10: | Scalar ts;
| | 11: | std::vector<Poly> pivots(M.rows());
| | 12: | for (int j = 0; j < M.cols(); ++j)
| | 13: | // iterate through all columns
| | 14: | {
| | 15: | // find first non-zero row
| | 16: | int nzr = -1;
| | 17: | for (int i = j; j < M.rows(); ++i)
| | 18: | if (M(i, j) != Poly::zero())
| | 19: | {
| | 20: | nzr = i;
| | 21: | break;
| | 22: | }
| | 23: | if (nzr == -1)
| | 24: | // Found just zero rows => determinant must be 0
| | 25: | return 0;
| | 26: | // clean up rows nzr to M.rows()-1
| | 27: | for (int i = nzr + 1; i < M.rows(); ++i)
| | 28: | if (M(i, j) != Poly::zero())
| | 29: | {
| | 30: | XGCD(d, a, b, M(nzr, j), M(i, j));
| | 31: | e = -M(i, j) / d;
| | 32: | f = M(nzr, j) / d;
| | 33: | // for column j, this transformation will act as follows:
| | 34: | // [ a b ] [ M(nzr, j) ] [ d ]
| | 35: | // [ e f ] [ M(i, j) ] = [ 0 ]
| | 36: | for (int k = 0; k < M.cols(); ++k)
| | 37: | {
| | 38: | mul(d, M(nzr, k), a);
| | 39: | mul(t, M(i, k), b);
| | 40: | add(d, d, t);
| | 41: | mul(M(i, k), M(i, k), f);
| | 42: | mul(t, M(nzr, k), e);
| | 43: | add(M(i, k), M(i, k), t);
| | 44: | M(nzr, k) = d;
| | 45: | }
| | 46: | }
| | 47: | // put the non-zero row into row r
| | 48: | if (j != nzr)
| | 49: | M.swapRows(nzr, j);
| | 50: | // make the pivot entry monic
| | 51: | ts = inv(LeadCoeff(M(j, j)));
| | 52: | for (int jj = j; jj < M.cols(); ++jj)
| | 53: | M(j, jj) *= ts;
| | 54: | // store current pivot
| | 55: | pivots[j] = M(j, j);
| | 56: | }
| | 57: | // Build d and clear up rows
| | 58: | Poly det = pivots[0];
| | 59: | for (int r = 1; r < M.rows(); ++r)
| | 60: | det *= pivots[r];
| | 61: | return det;
| | 62: | } |
Der XGCD-Aufruf da drinnen ruft den erweiterten euklidischen Algorithmus auf.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:35 Mo 06.04.2009 | | Autor: | Marc |
Lieber Felix,
> > ich würde gerne ein Programm schreiben, dass die
> > Nullstellen von Polynomen exakt ermitteln kann.
>
> Du willst also nur Nullstellen finden, die auch in [mm]\IQ[i][/mm] [/i][/mm]
> [mm][i]liegen, und sonst keine? Hab ich das richtig verstanden?[/i][/mm]
Ich würde natürlich schon gerne alle Nullstellen finden, ich dachte nur, es sei eine gute Idee, schrittweise vorzugehen. Gibt es denn noch Bedingungen, mit denen man weitere Nullstellen erfassen kann? Glücklich wäre ich schon, wenn ich Nullstellen der Form [mm] $\sqrt{\IZ}$, $\sqrt{\IQ}$, $\sqrt[n]{\IZ}$, $\sqrt[n]{\IQ}$ [/mm] finden könnte (für Polynome aus [mm] $\IQ[x]$). [/mm] Nullstellen für Polynome aus [mm] $\IR[x]$ [/mm] oder [mm] $\IC[x]$ [/mm] finden zu wollen, ist wahrscheinlich vermessen, oder?
Mein Programm wird aber in den meisten Fällen sowieso nur Nullstellen zu finden haben, die sich Menschen vorher ausgedacht hatten, und besser noch, dieses mit der Absicht, dass sie von anderen Menschen auch gefunden werden  (m.a.W. also Polynome aus Übungsaufgaben).
Vielen Dank für deine vorherigen Antworten, das ist offensichtlich genau das, was ich gesucht hatte!
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:03 Mo 06.04.2009 | | Autor: | felixf |
Lieber Marc,
> > > ich würde gerne ein Programm schreiben, dass die
> > > Nullstellen von Polynomen exakt ermitteln kann.
> >
> > Du willst also nur Nullstellen finden, die auch in [mm]\IQ[i][/mm][/i][/mm]
> > [mm][i]liegen, und sonst keine? Hab ich das richtig verstanden?[/i][/mm]
>
> Ich würde natürlich schon gerne alle Nullstellen finden,
> ich dachte nur, es sei eine gute Idee, schrittweise
> vorzugehen. Gibt es denn noch Bedingungen, mit denen man
> weitere Nullstellen erfassen kann?
dazu muss man sich erstmal fragen: wie stellt man die ueberhaupt dar? Gewisse Nullstellen lassen sich durch iterierte Wurzelausdruecke darstellen, aber andere eigentlich nur durch Angabe des Minimalpolynoms oder numerisch.
> Glücklich wäre ich
> schon, wenn ich Nullstellen der Form [mm]\sqrt{\IZ}[/mm],
> [mm]\sqrt{\IQ}[/mm], [mm]\sqrt[n]{\IZ}[/mm], [mm]\sqrt[n]{\IQ}[/mm] finden könnte (für
> Polynome aus [mm]\IQ[x][/mm]).
Polynome ueber [mm] $\IQ[x]$ [/mm] kannst du faktorisieren, die Linearfaktoren liefern dir dann die Nullstellen in [mm] $\IQ$, [/mm] die quadratischen Faktoren die Nullstellen in [mm] $\sqrt{\IQ}$, [/mm] und die restlichen Faktoren beschreiben die restlichen Nullstellen.
Algorithmen zum Faktorisieren gibt es (normalerweise fuehrt man es auf primitive Polynome in [mm] $\IZ[x]$ [/mm] zurueck); normalerweise bestimmt man erstmal eine quadratfreie Faktorisierung (mit Hilfe des euklidschen Algorithmus) und dann reduziert man das auf Faktorisieren ueber endlichen Koerpern. Eventuell bietet es sich hier an, einfach eine Library zu benutzen die das schon alles implementiert hat (z.B. NTL), ansonsten wird's eventuell etwas aufwaendig.
> Nullstellen für Polynome aus [mm]\IR[x][/mm]
> oder [mm]\IC[x][/mm] finden zu wollen, ist wahrscheinlich vermessen,
> oder?
Da stellt sich wieder die Frage: wie stellt man das eigentlich da?
Faktorisieren ueber $K[i]$ mit $K [mm] \subseteq \IR$ [/mm] einem Unterkoerper laesst sich mit dem in anderen Post von mir beschriebenen Trick immer zurueckfuehren auf Faktorisieren ueber $K$. Also musst du dir "nur" beim Faktorisieren ueber [mm] $\IR$ [/mm] Gedanken machen.
Aber da hat man allein schon das Problem, wie man Elemente aus [mm] $\IR$ [/mm] eigentlich darstellt. Wenn man sich auf Fliesskommazahlen beschraenkt, so ist man eigentlich in [mm] $\IQ$ [/mm] -- und falls die Fliesskommazahlen approximationen von Elementen aus [mm] $\IR$ [/mm] sind, findet man eh nicht die richtigen Nullstellen sondern nur Approximationen von diesen. Man kann natuerlich versuchen symbolisch zu arbeiten, etwa bei [mm] $x^2 [/mm] - [mm] \pi \in \IR[x]$.
[/mm]
> Mein Programm wird aber in den meisten Fällen sowieso nur
> Nullstellen zu finden haben, die sich Menschen vorher
> ausgedacht hatten, und besser noch, dieses mit der Absicht,
> dass sie von anderen Menschen auch gefunden werden
> (m.a.W. also Polynome aus Übungsaufgaben).
Oder anders gesagt, die Nullstellen sind hoechstens quadratisch ueber [mm] $\IQ$ [/mm]
Da die Polynome vermutlich eher geringe Grade haben bietet sich evtl etwas wie das hier an.
LG Felix
|
|
|
|
