Polynomfaktorisierungs - Algorithmus?

Original erstellt von volkard:
wenns um symbolische lösung geht, kann ich dir nur die fertigen formel anempfehlen, und bei polynoen über grad5 haste verloren, da gibts kein patentrezept.

es geht um symbolische Lösungen. Mit Galois geht das ja auch mit bestimmten Polynomen mit Grad >= 5. Aber wie?

volkard

Original erstellt von <iiii>:
Mit Galois geht das ja auch mit bestimmten Polynomen mit Grad >= 5. Aber wie?

aha. endlich weiß ich, was man mir im studium immer verschwiegen hat. jetzt bin ich voll gespannt, wie das geht.

Jester

Hi!

"Galois" ist kein Verfahren zur Bestimmung von Nullstellen. Es gibt die Galoistheorie. Die beschäftigt sich aber mit Körpererweiterungen und Gruppen.

Allerdings kann man, damit immerhin zeigen, ob sich die Nullstellen eines Polynomes überhaupt mit sogenannten Radikalen ausdrücken lassen: Sprich Wurzel, +,-,*,/. Nämlich genau dann, wenn die Galoisgruppe der Gleichung im Sinne der Gruppentheorie auflösbar ist.
Als Buch dazu kann ich Dir "Algebra" von Bosch, erschienen im Springerverlag empfehlen. Ist allerdings recht harter Stoff!

Aber wirklich Polynome knacken geht damit nicht so ohne weiteres.
Über welchem Grundkörper betrachtest Du eigentlich Polynome? Über Q, R oder irgendwas anderes?

Sag mal ein bissel genauer was Du machen willst.

MfG Jester

Original erstellt von Jester:
**"Galois" ist kein Verfahren zur Bestimmung von Nullstellen. Es gibt die Galoistheorie. Die beschäftigt sich aber mit Körpererweiterungen und Gruppen.
**

weiß ich, Galois ist aber kürzer

Original erstellt von Jester:
Aber wirklich Polynome knacken geht damit nicht so ohne weiteres.
Über welchem Grundkörper betrachtest Du eigentlich Polynome? Über Q, R oder irgendwas anderes?

Meint "Grundkörper" aus welchem Körper die Koeffizienten sind? Dann IR.

...und die Faktoren aus IC

Jester

Sorry, da wirste ganz schlechte Karten haben. Über R ist es ziemlich übel. Weil da ja alles schon in lineare / quadratische Faktoren zerfällt. Nur blöderweise lassen sich viele reelle Zahlen nicht gescheit aufschreiben, sondern nur als Grenzwert.

Beispiel: e, Pi
aber das ist noch nicht alles. Manche von denen haben nichtmal so schöne kurze Namen. zum Beispiel Sum(i=0...unendlich) 10^(-i!) ist auch transzendent. Einen solchen Faktor rätst Du niemals.

Über dem Grundkörper Q ist das noch etwas einfacher. Weil Du da wenigstens ne ordentliche Struktur für Deine Lösungen bekommst.

Auf jeden Fall ist es sinnvoll das Polynom in irreduzible Faktoren zu zerlegen. Sprich: Polynome, die noch im Polynomring über dem gleichen Grundkörper liegen und sich nicht mehr weiter zerlegen lassen. Über Q bzw. Z kann man das noch halbwegs lösen. Über R ist genau das das Problem. Wenn Du das fertig hast kannste erst mit der Galoistheorie was anfangen.

MfG Jester

Original erstellt von Jester:
**Sorry, da wirste ganz schlechte Karten haben. Über R ist es ziemlich übel. Weil da ja alles schon in lineare / quadratische Faktoren zerfällt. Nur blöderweise lassen sich viele reelle Zahlen nicht gescheit aufschreiben, sondern nur als Grenzwert.

Beispiel: e, Pi
aber das ist noch nicht alles. Manche von denen haben nichtmal so schöne kurze Namen. zum Beispiel Sum(i=0...unendlich) 10^(-i!) ist auch transzendent. Einen solchen Faktor rätst Du niemals.**

das ist doch die Liouville(?)sche Zahl?

Original erstellt von Jester:
**Über dem Grundkörper Q ist das noch etwas einfacher. Weil Du da wenigstens ne ordentliche Struktur für Deine Lösungen bekommst.

Auf jeden Fall ist es sinnvoll das Polynom in irreduzible Faktoren zu zerlegen. Sprich: Polynome, die noch im Polynomring über dem gleichen Grundkörper liegen und sich nicht mehr weiter zerlegen lassen. Über Q bzw. Z kann man das noch halbwegs lösen.**

gut, sehe ich ein. Die irreduziblen Faktoren sind dann von der Form (X - x_i) mit x_i € C ?

Jester

Jo genau das besagt der Fundamentalsatz der Algebra.

Wußte nicht, daß man diese Zahl so nennt. Aber man kann noch beliebige viele weitere dieser Art konstruieren. Und genau das ist das Problem beim lösen solcher Gleichungen.

Jester

Aber in Q können diese irreduziblen Polynome beliebig großen Grad haben.
Dann bestimmt man die Galoisgruppe dieses Polynoms. Das ist leider mal wieder nicht ganz einfach und ich wüßte kein Patentrezept.
Aber man könnte mal annehmen, man hätte eine Nullstelle a und die dann abdividieren. Vielleicht hat das Polynom dann noch mehr Nullstellen, die sich mit a ausdrücken lassen.
Die Elemente der Galoisgruppe bilden nämlich immer eine Nullstelle eines irreduziblen Polynoms auf eine andere Nullstelle dieses Polynoms ab.
Das heißt, wenn Du die Galoisgruppe hast, dann weißt Du wie man von einer Lösung zur nächsten kommt. Wo Du jetzt allerdings ne konkrete Startlösung herkriegst weiß ich auch nicht. Vor allem wenn die Galoisgruppe nicht auflösbar ist, lassen sich diese Startlösungen nichtmal als Wurzeln / sonstwas von Zahlen in Q darstellen.

x^5 + 3*x^4 - 47*x^3 + 69*x^2 + 46*x - 72

ist ja beispielsweise faktorisierbar. Wie würde ich dabei vorgehen?

ok, den groben Fahrplan erkenne ich. Das Problem ist also 1) Bestimmung der Galoisgruppe des Polynoms 2) Bestimmung eines abspaltbaren Faktors.

Jester

In Deinem Fahrplan fehlt noch:

Zerlegung des Polynoms in irreduzible Faktoren.

Okay, zu Deinem Beispiel:
Das geht völlig ohne Galoistheorie, die Galoisgruppe besteht in diesem Fall aus der Identität, weil alle Nullstellen selbst im Grundkörper liegen.

Wir beginnen damit das Teil in irreduzible Faktoren zu zerlegen:

p(X) = x^5 + 3*x^4 - 47*x^3 + 69*x^2 + 46*x - 72

nehmen wir an, das ist reduzibel, dann kann man entweder was lineares abspalten, oder was quadratisches. hoch 3 brauch ich nicht zu betrachten, da dann der andere Faktor quadratische wäre, hoch 4 analog auch nicht.

Nehmen wir an, wir könntens zerlegen:

1.Fall in linear + Teil vom Grad 4

p(X) = (X + a)(X^4+b*X3 + c*X^2 + dX + e)
= X^5 + (a+b)*X^4 + (ab + c)*X^3 + (ac+d)X^2 + (ad+e)*X + e*a

a,b,c,d,e sind eigentlich in Q, wegen des Lemmas von Gauß, können wir sie aber sogar in Z wählen. Denn nach eben diesem Lemma sind normierte Polynome im Polynomring eines Quotientenkörpers genau dann irreduzibel, wenn sie im Grundring irreduzibel sind.

Und es gilt:
Q ist der Quotienten vom Ring der ganzen Zahlen Z.

Daher können wir sogar annehmen, daß a,b,c,d,e € Z

Koeffizientenvergleich zeigt:
a+b=3, a*b+c=47, a*c+d=69, a*d+e = 46, e*a = 72

die letzte Bedingung ist besonders interessant:
e*a=72.

Das heißt: a€{x| x=2^i*3j*(-¹⁾k mit i=0,1,2,3 und j=0,1,2 und k=0,1}
Das sind grad mal 24 Stück. Die kann man dann sogar einfach mit Polynomdivision abprüfen, oder halt über diese Gleichungen zum Widerspruch führen oder so.

Aber hier landet man nen Treffer, kann nen Faktor abspalten und hat dann nur noch Grad 4 vor sich. Also entweder die Lösungsformel auspacken oder das selbe Spielchen nochmal.

MfG Jester

Original erstellt von Jester:
Okay, zu Deinem Beispiel:
Das geht völlig ohne Galoistheorie, die Galoisgruppe besteht in diesem Fall aus der Identität, weil alle Nullstellen selbst im Grundkörper liegen.

ok, den Weg hab ich verstanden. Ich will aber einen allgemeineren Fall ;-). Was hältst du davon:

x^5 -169/15*x^4 +2608/45*x^3 -2224/15*x^2 +852/5*x -60

Original erstellt von Jester:
Koeffizientenvergleich zeigt:
a+b=3, a*b+c=47, a*c+d=69, a*d+e = 46, e*a = 72

nicht a+b=3, a*b+c=-47, a*c+d=69, a*d+e = 46, e*a = -72 ?

Jester

stimmt, hast Recht. ändert aber an der Sache nix. Die Menge für a bleibt so wie sie war.

x^5 -169/15*x^4 +2608/45*x^3 -2224/15*x^2 +852/5*x -60 = 0

also erstmal durchmultiplizieren mit

HN 45=>

p(X) = 45*x^5-507*x4+2608*x^3-6672*x2+7668*x-2700

Hier ist das zerlegen jetzt recht aufwändig, aber es gibt eine in Z[X], nur daß die Polynome diesmal nicht beide so schön normiert sind.

Aber was ich ganz nett finde:
45*x^5-507*x4+2608*x^3-6672*x2+7668*x-2700 = 0 kann man auch modulo betrachten, z. Bsp. mod 3

=> x^3 = 0 mod 3
=> 3 teilt x
und so trix halt. Das bringt immer ein paar Infos.

oder einfach
(a*X+b) abspalten. Möglichkeiten durchchecken. a kann ja nur 1,3,5,9,27,45 sein.
und b teilt 2700. Sind halt ne Menge Möglichkeiten, aber ich bin im Moment zu faul die anderen Koeffizienten auch zu vergleichen, das gibt ja auch nochmal Informationen. Aber ein Computer müßte sowas können.

Du brauchst also zunächst mal einen Löser für Gleichungen der Form:

sum[i=1...n] (a_i*b_i) = k mit a_i, b_i in Z

damit Du zunächst mal die irreduziblen Polynome kriegst. Danach erst kannste mit Galoistheorie ansetzen.