Euklidische Algorithmus auch für Polynome

Neue Frage »

24.11.2006, 21:26	Martin!	Auf diesen Beitrag antworten »
Euklidische Algorithmus auch für Polynome Hallöchen :-) Ich würde mich riesig freuen, wenn ihr mir bei der Aufgabe hier helfen könntet: Mit Satz: $\begin{eqnarray} f,g \in \mathbb K [x] \end{eqnarray}$ seien zwei Polynome mit $\begin{eqnarray} g \neq 0 \end{eqnarray}$ . Dann exestieren eindeutig bestimmte Polynome $\begin{eqnarray} q,r \in \mathbb K [x] \end{eqnarray}$ mit $\begin{eqnarray} f= q g + r \end{eqnarray}$ und $\begin{eqnarray} deg r < deg g \end{eqnarray}$ . Das ist erstmal der Allgemeine Satz. Der also besagt, dass mit diesem Satz der Euklidische Algorithmus auch für Polynome zur Verfügung steht. Nun muss gezeigt werden: Zeigen SIe mit ihm, daß die Polynome $\begin{eqnarray} p:= x^4 + 3x^3 + x +3 \end{eqnarray}$ und $\begin{eqnarray} q:= x^3 + x \end{eqnarray}$ aus $\begin{eqnarray} \mathbb R [x] \end{eqnarray}$ teilerfremd sind (d.h., $\begin{eqnarray} ggT(p,q) = 1 \end{eqnarray}$ ), und bestimmen Sie Polynome $\begin{eqnarray} s,t \in \mathbb R [x] \end{eqnarray}$ mit $\begin{eqnarray} s * p + t* q = 1 \end{eqnarray}$ . So, und es soll ja erstmal der gemeinsame größte Teiler gesucht werden, richtig? Ich habe mir erstmal im internet beispiele gesucht. Und dementsprechend habe ich es veruscht, nach zu machen. Weiß nur nicht ob mir das so 100% gelungen ist. Also, erstmal habe ich wie folgt versucht, den größten gemeinsamen teiler zu finden: Ich habe also nun Polynomdivision durchgeführt: $\begin{eqnarray} (x^4 + 3x^3 + x + 3) : (x^3 + x) = x+3 \end{eqnarray}$ Rest $\begin{eqnarray} -x^2 -2x +3 = -1(x^2 + 2x -3) \end{eqnarray}$ Zweite Polynomdivision: $\begin{eqnarray} (x^3 +x) : (x^2 + 2x - 3) = x-2 \end{eqnarray}$ Rest $\begin{eqnarray} 8x -6 \end{eqnarray}$ Dritte Polynomdivision: $\begin{eqnarray} (x^2 + 2x -3 ) : (8x - 6) = \frac {1}{8} x + \frac {11}{32} \end{eqnarray}$ Rest $\begin{eqnarray} - \frac {15}{16} \end{eqnarray*}$ und wenn ich bis hierher alles richtig gemacht haben sollte, komm ich hier nicht mehr weiter. Was kann man hier tun? oder was habe ich falsch gemacht? Ich bin euch unendlich dankbar, wenn ihr mir hier helfen könntet
25.11.2006, 09:30	Martin!	Auf diesen Beitrag antworten »
Mich irritiert das vor allem, das der rest bei der letzten polynomdivision kein x mehr enthält, und da weiß ich jetzt nicht wirklich was mit anzufangen. hmmmmm grübel
25.11.2006, 13:33	Dr. Logik	Auf diesen Beitrag antworten »
RE: Euklidische Algorithmus auch für Polynome Moin der Herr! Das hat unser Prof. doch in der Vorlesung gesagt: teilerfremd bedeutet, dass beim ggT (p,q) eine Konstante herauskommt. (in der Aufgabe steht zwar 1, aber das stimmt so nicht). wenn bei dir also $\begin{eqnarray} - \dfrac{15} {16} \end{eqnarray}$ herauskommt, ist das doch eine Konstante, also hast du den ersten Teil schon gezeigt, nämlich, dass p und q teilerfremd sind. (Ob die Lösung stimmt, weiß ich noch nicht, hab grad erst mit der Aufgabe begonnen). Naja und jetzt musst du wie bei dem letzten Übungsblatt (Bestimmung von ggT) wieder den Euklidischen Algorithmus "rückwärts" anwenden. So müsste es im Prinzip gehen. Wenn das nicht stimmen sollte, bitte ich um Belehrung Edit: warum klammerst du eigenltich bei Rest1 die (-1) aus? muss man das so machen??? Ich hab das nämlich nicht getan und bekomme dann als letzten Rest 6 raus (was ja auch ne Konstante ist) Dann bis bald, viele Grüße, Dr. Logik
25.11.2006, 17:38	Dr. Logik	Auf diesen Beitrag antworten »
RE: Euklidische Algorithmus auch für Polynome sorry. 6 war falsch. müsste auch $\begin{eqnarray} - \dfrac{15} {16} \end{eqnarray}$ sein. hatte mich verrechnet.
25.11.2006, 19:51	Martin!	Auf diesen Beitrag antworten »
Hi Dr. Logok, danke für die bestättgung meiner rechnung :-) ALso, ist die bisherige Rechnung komplett. Und man hat somit also bewiesen, dass das ganze teilerfremd ist. KAnnst du mir nur mal vielleihct einen kleinen anstoß geben, wie man den ggT bestimmen soll? irgendwie weiß ich bei dieser aufgabe nicht wie. Nur mal so einen anstatz, wie man das ganze beginen soll. wäre super nett
25.11.2006, 21:37	Dr. Logik	Auf diesen Beitrag antworten »
@martin warum klammerst du beim 1. Rest die -1 aus? ich habe das nicht gemacht und komme daher am Ende auf den Rest +15/16. Weiß jetzt allerdings nicht, was richtig ist und was falsch. Wie man dann weiter vorgeht weiß ich auch noch nicht so genau. Nach der Theorie müsstest du wie bereits gesagt den eukl. Algorithmus "rückwärts" ausführen um s und t zu erhalten. So werd ich das jetzt zumindest probieren. Wenn ich ein Ergebnis hab, poste ich es dir! Viele Grüße, Dr. Logik
Anzeige

25.11.2006, 21:49	Martin!	Auf diesen Beitrag antworten »
nee, hast recht. war eigentlich unsinig, die -1 auszuklammern. ich kann das vorzeichen mitsicherheit nicht einfach unterschlagen. Ich schließe mich mit deinem rest an.
25.11.2006, 23:11	Dr. Logik	Auf diesen Beitrag antworten »
glaube ich habe jetzt die Lösung: Also du gehst am besten so vor: schreib dir erstmal die einzelnen Ergebnisse, die du oben ausgerechnet hast so hin, wie wir das beim eukl. Algorithmus schon getan haben. Also z.B.: (i) $\begin{eqnarray} (x^4+3x^3+x+3)=(x+3)(x^3+x)-x^2-2x+3 \end{eqnarray}$ (ii) $\begin{eqnarray} (x^3+x)=(-x+2)(-x^2-2x+3)+8x-6 \end{eqnarray}$ usw. Dann beginnst du das Ganze von hinten zu berechnen. Ich nehme jetzt mal an, dass ggT=15/16 die richtige Lösung ist. Dann fängst du so an: aus der letzten Zeile folgt: $\begin{eqnarray} \dfrac{15} {16}=(-x^2-2x+3)-[(- \dfrac{1} {8} x - \dfrac{11} {32})(8x-6)] \end{eqnarray}$ Dann setzt du da die vorletzte Zeile ein und vereinfachst das ganze! Du musst dabei darauf achten, dass du die Polynome, die du bei der Polynomendivision als Reste erhalten hast nicht ausmultiplizierst, weil du nämlich im nächsten Schritt dafür wieder die nächste Zeile einsetzen musst. Probiers einfach mal aus, du musst halt sehr sorgfältig sein beim Einsetzen, Umformen und Ausmultiplizieren. Meine Lösung lautet übrigens zum Vergleich: $\begin{eqnarray} s= \dfrac{1} {8} x^2+ \dfrac{3} {32} x + \dfrac{5} {16} \end{eqnarray}$ $\begin{eqnarray} t=- \dfrac{1} {8}x^3 - \dfrac{15} {32} x^2 - \dfrac{15} {32} x - \dfrac{19} {32} \end{eqnarray}$ Hoffe, dass dir das weiterhilft. viel Spaß noch, Dr. Logik
26.11.2006, 11:33	Martin!	Auf diesen Beitrag antworten »
Hi Dr. Logik, also, dass rechenchema selbst ist mir jetzt klar. Aber das ist ja eine irrsinige Rechnung. Ich bekomme in meinen rechnungen am ende dann auch x^4 und x^5 rein, die ich hinterher nicht wirklich wegbekomme. Ich schreibe hier mal nach und nach meinen rechenweg hier auf. Dannn könnten wir vielleicht mal schritt für schrittvergleichen, oder? Also, wie du schon sagtest, beginnt die rechnung hier mit: $\begin{eqnarray} \dfrac{15} {16}=(-x^2-2x+3)-[(- \dfrac{1} {8} x - \dfrac{11} {32})(8x-6)] \end{eqnarray}$ dann habe ich, was du als (ii) bezeichnet hast, da eingesetzt: $\begin{eqnarray} (-x^2-2x+3)-[(- \dfrac{1} {8} x - \dfrac{11} {32})(8x-6)] = (-x^2-2x+3)- [(x^3 + x - (-x^2 -2x +3) (-x + 2)) ( - \frac{1}{8} - \frac{11}{32}) \end{eqnarray}$ dann habe ich ein bisschen ausgeklammert: $\begin{eqnarray} (-x^2-2x+3)- [(x^3 + x - (-x^2 -2x +3) (-x + 2)) * ( - \frac{1}{8} - \frac{11}{32} = (-x^2-2x+3)- [(- \frac{1}{8}x^4 - \frac{11}{32}x - \frac{1}{8}x^2 - \frac{11}{32}x^3 -(-x^2 -2x +3) ( \frac{1}{8}x^2 + \frac{11}{32}x - \frac{1}{4}x - \frac{11}{16} )] \end{eqnarray}$ so, und hier müsste an nun (i) einsetzen: $\begin{eqnarray} (-x^2-2x+3)- [(- \frac{1}{8}x^4 - \frac{11}{32}x - \frac{1}{8}x^2 - \frac{11}{32}x^3 -(-x^2 -2x +3) ( \frac{1}{8}x^2 + \frac{11}{32}x - \frac{1}{4}x - \frac{11}{16} )] = (-x^2-2x+3)- [(- \frac{1}{8}x^4 - \frac{11}{32}x - (x^4 + 3x^3 + x + 3 - (x^3 + x) (x+3)) ( \frac{1}{8}x^2 + \frac{11}{32}x - \frac{1}{4}x - \frac{11}{16} )] \end{eqnarray}$ aber wenn ich versuche da irgendwie was auszurechnen, komme ich nicht auf dein ergebniss. weiß soweiso nicht irgendwie, wie ich es hier am geshcicktesten angehen soll. denn p und q muss ja erhalten bleiben. habe ich viellehct ein fehler gemacht? SIehst du ihn vielleicht?
26.11.2006, 11:48	Dr. Logik	Auf diesen Beitrag antworten »
Also ich muss zugeben, ich sehe deinen Fehler jetzt auch nicht so. Ist wirklich ne sehr komplexe Rechnung. Ich kann dir empfehlen, zu versuchen so wenig wie möglich mit Minusklammern zu arbeiten. Denn, wenn du dadurch einmal nen Vorzeichenfehler drin hast, kommst du nie mehr auf nen grünen Zweig. ich habe z.B. bei $\begin{eqnarray} (-x^2-2x+3)-[(- \dfrac{1} {8} x- \dfrac{11} {32})(8x-6)] \end{eqnarray}$ zunächst ersteinmal das Minus vor der eckigen Klammer beseitigt, indem ich es so umgeformt habe: $\begin{eqnarray} (-x^2-2x+3)+( \dfrac{1} {8} x+ \dfrac{11} {32})(8x-6) \end{eqnarray}$ und dann setzt du für 8x-6 die nächste Zeile ein. $\begin{eqnarray} (-x^2-2x+3)+( \dfrac{1} {8} x+ \dfrac{11} {32})[(x^3+x)-(-x+2)(-x^2-2x+3)] \end{eqnarray}$ Dann kannst du ausmultiplizieren und all das zusammenfassen, was nicht Rest aus der Polynomendivision war. Du musst wie gesagt sehr sorgfältig dabei sein. vorteilhaft wäre es, wenn du ein Computeralgebraprogramm wie z.B. derive besitzt, um zu überprüfen, ob deine Umformungen richtig sind. Probiers mal, dann klappts schon
26.11.2006, 13:33	Martin!	Auf diesen Beitrag antworten »
so ein programm habe ich leider nicht. selbst wenn ich es hätte, wüsste ich jetzt nicht, wie man es bedienen sollte. Dann muss ch wohl zu Fuß rechnen ;-) Ich habe es jetzt nochmal durchgerechnet. Ist es normal, dass vor dem ganzen ausdruck sp + tq noch eine reihe von additionen steht?
26.11.2006, 14:45	always	Auf diesen Beitrag antworten »
also ich will eure aufgabe nicht kapuut machen... aber der ggT ist doch der größte gemeinsame teiler... und dieser kann doch nciht kleiner als 1 sein... alles ist durch 1 teilbar oder ?
26.11.2006, 16:43	Martin!	Auf diesen Beitrag antworten »
hey, einen moment mal. Ich glaube an der aufgabe ist wirklich irgendwie was falsch. @Dr. Logik, erinnerst du dich noch an den letzten zettel mit dem euklidischen algorithmus? da war bei den aufgaben kein rest. und bei dieser rechnung haben wir (das ist unumstößlich) einen rest von \frac {15}{16}. bei den anderen aufgaben war es immer 0. Ich glaube, dass man doch somit vielleicht behaupten kann, dass die beiden Polynome keinen gemeinsamen teiler haben, oder? denn sonst hätte man keinen rest haben dürfen. Aber was ich jetzt geschrieben habe, glaube ich nur. wirklich beweisen kann ich es nicht. und 100% wissen tue ich es auch nicht. Was meint ihr?
26.11.2006, 17:29	Dr. Logik	Auf diesen Beitrag antworten »
ich weiß es auch nicht. Den Rest bekommt man aber dabei auch nicht weg, sodass da dann 0 herauskommt. Ich denke mal, dass das das Indiz ist, dass die beiden Polynome teilerfremd sind. Aber wie man dann sp+tq =1 ausrechnen soll, weiß ich auch nicht. So wie ich es gerechnet habe ist sp+tq = 15/16. Also entweder ist die Polynomendivision falsch oder die Aufgabenstellung hat nen Fehler (wegen der 1) oder wir denken komplett falsch. Ich weiß es auch nicht. Lasse jetzt mein Ergebnis erstmal so stehen und vergleiche das mit den anderen morgen (da haben übrigens auch mehrere 15/16 raus...)
26.11.2006, 17:37	Martin!	Auf diesen Beitrag antworten »
also, ich denke mal die polynomdivision ist richtig. da bin ich mir ziemlich sicher. ich habe so das gefühl, das wir einen fehler bei der bestimmung der linearkombination machen. Wobei das wahrscheinlich ja nicht gehen dürfte, weil die beiden teilerfremd sind. hmmmmmmmm, so ein mist. wüsste zu gern, was wir hier falsch machen.
26.11.2006, 17:57	Dr. Logik	Auf diesen Beitrag antworten »
die s und t, die ich angegeben habe stimmen, wenn das richtige ergebnis 15/16 ist. hab das mit nem Pc-programm überprüft

Neue Frage »

Antworten »

Euklidische Algorithmus auch für Polynome

Verwandte Themen