| |
| Autor |
 PolynomialGCD stimmt nicht immer? |
|
hyperG
Senior 
Dabei seit: 03.02.2017
Mitteilungen: 2164
 |  Themenstart: 2020-12-17
|
Bisher dachte ich, dass "PolynomialGCD" einfach
ggT(Polynom 1, Polynom 2).
Einfache Tests schienen das zu bestätigen:
\sourceon mathematica
PolynomialGCD[4*k, 4*k^2-1]
Out: 1
Probe
Table[GCD[4*k, 4*k^2-1],{k,1,566}]
Out: 1,1,1,1,... -> OK
PolynomialGCD[3 x+9,6x^3-3x+12]
Out: 3
Probe:
Table[GCD[3 x+9,6x^3-3x+12],{x,1,40}]
Out: {3,3,3,3,... scheint zunächst zu stimmen
\sourceoff
ABER weiter hinten gibt es auch Fälle, die nicht stimmen:
\sourceon mathematica
Table[GCD[3 x+9,6x^3-3x+12],{x,40,45}]
Out: {3,3,3,3,141,3}
denn
GCD[141,510984]
Out: 141
\sourceoff
Was ist mit diesem Sonderfall bei x=44 ?
Warum wird da einfach drüber hinweg gesehen?
Oder
\sourceon mathematica
PolynomialGCD[a+2 b,2 a+b]
Out: 1
Probe:
a=3;Table[GCD[a + 2 b, 2 a + b],{b,1,13}]
Out: {1,1,9,1,1,3,1,1,3,1,1,9,1}
\sourceoff
...ist zwar meist 1, aber manchmal auch 3 oder 9 ...
Wie kann man das
a) stimmt "immer"
b) stimmt "meist"
unterscheiden?
|
 Profil
|
zippy
Senior 
Dabei seit: 24.10.2018
Mitteilungen: 5147
 | Beitrag No.1, eingetragen 2020-12-17
|
\quoteon(2020-12-17 22:04 - hyperG im Themenstart)
Bisher dachte ich, dass "PolynomialGCD" einfach
ggT(Polynom 1, Polynom 2).
\quoteoff
So ist es auch. Aber: Es gibt einen gewaltigen Unterschied zwischen dem ggT zweier Polynome und den ggTs der Werte dieser Polynome.
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2164
| Beitrag No.2, vom Themenstarter, eingetragen 2020-12-17
|
\quoteon(2020-12-17 22:17 - zippy in Beitrag No. 1)
... Es gibt einen gewaltigen Unterschied zwischen dem ggT zweier Polynome und den ggTs der Werte dieser Polynome.
\quoteoff
Ja, das hatte ich ja bereits festgestellt.
Meine Frage war ja:
Wie kann man das
a) stimmt "immer"
b) stimmt "meist"
unterscheiden?
|
Profil
|
DerEinfaeltige
Senior 
Dabei seit: 11.02.2015
Mitteilungen: 3303
 | Beitrag No.3, eingetragen 2020-12-17
|
Der ggT der Polynome ist der ggT aller Werte.
Das ist im Allgemeinen natürlich eine stärkere Bedingung als der ggT eines einzelnen Wertepaars.
Die Beispiele mit (bis auf konstante Faktoren) teilerfremden Polynomen wirken im Übrigen recht witzlos.
Die nichttrivialen "Lösungen" findet man bspw., indem man ganzzahlige Werte des Divisionsrestes sucht. (44 und -50 im Beispiel)
Edit:
Gemeinsame Teiler muss es natürlich heißen.
Für ganzzahlige Werte teilt der Divisor den Dividenten wie im Beispiel gesehen komplett.
Gibt es keine, so "stimmt" das Ergebnis auch in deinem Sinne.
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2164
| Beitrag No.4, vom Themenstarter, eingetragen 2020-12-18
|
Da ich mehr Praktiker (bei dem die Probe stimmen muss) als Theoretiker bin, hier meine Vorstellung von exakter Anzeige des Ergebnisses:
Die universelle Formel kann man hier nachlesen und sie funktioniert auch mit Polynomen!
\sourceon mathematica
GCD[m, n] == 2 Sum[Floor[(k n)/m], {k, 1, m - 1}] + m + n - m n
\sourceoff
Angewendet auf mein 2. Beispiel:
\sourceon mathematica
GCD[6 x^3 - 3 x + 12, 3 x + 9]
= -87 - 9 x + 9 x^2 - 48 x^3 - 18 x^4 + 2 Sum[Floor[(k (4 - x + 2 x^3))/(3 + x)], {k, 1, 8 + 3 x}]
Im Falle Mod[ (4 - x + 2 x^3),(3 + x)]==0 kann man Floor weglassen und bekommt:
-87 - 9 x + 9 x^2 - 48 x^3 - 18 x^4 + 3(3 x + 8) (2 x^3 - x + 4)
= 3*x+9 -> bei x=44 ist Modulo 0 und
3*44+9=141
(* -> was auch mit der Praxis übereinstimmt!
Weitere Betrachtungen der Spezialfälle lassen sich nun so zusammenfassen:
if x==47n-3 then Ergebnis =141 mit n>0 & ganzzahlig
ELSE Ergebnis = 3
Probe: *)
Table[GCD[3 x+9,6x^3-3x+12],{x,44,999,47}]
Out: {141,141,141,141,...}
Table[GCD[3 x+9,6x^3-3x+12],{x,1,999,47}]
Out: {3,3,3,3,3,3,...}
Table[GCD[3 x+9,6x^3-3x+12],{x,2,999,47}]
Out: {3,3,3,3,3,3,...}
usw.
\sourceoff
Den Theoretikern mag der ELSE-Zweig (mit dem größeren Anteil) reichen, mir reicht er nicht.
|
Profil
|
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 3303
| Beitrag No.5, eingetragen 2020-12-18
|
\quoteon(2020-12-18 16:35 - hyperG in Beitrag No. 4)
Die universelle Formel kann man hier nachlesen und sie funktioniert auch mit Polynomen!
\sourceon mathematica
GCD[m, n] == 2 Sum[Floor[(k n)/m], {k, 1, m - 1}] + m + n - m n
\sourceoff
\quoteoff
Diese Formel liefert auf den ersten Blick Ganzzahlen.
Den ggT zweier Polynome kann sie also nicht ausrechnen, da dieser im Allgemeinen keine Zahl und schon gar keine Ganzzahl ist.
Was gibt deine Formel denn bspw. für $\operatorname{gcd}(x^3-1,\sqrt{2}(x^2-1))$ aus?
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2164
| Beitrag No.6, vom Themenstarter, eingetragen 2020-12-18
|
\quoteon(2020-12-18 16:50 - DerEinfaeltige in Beitrag No. 5)
... schon gar keine Ganzzahl ist.
Was gibt deine Formel denn bspw. für $\operatorname{gcd}(x^3-1,\sqrt{2}(x^2-1))$ aus?
\quoteoff
Einer Funktion, die schon im Namen das Wort "Teiler" hat, als Übergabeparameter irrationale Zahlen zu übergeben, ist schon gemein.
(etwa so, als wolle man die Sqrt[2]. Primzahl berechnen mit Prime[Sqrt[2]])
Aber ich bin ja offen für solche universellen Betrachtungen.
\sourceon mathematica
2 Sum[Floor[(k Sqrt[2]*(x^2-1))/(x^3-1)],{k,1,(x^3-1)-1}]+(x^3-1)+Sqrt[2]*(x^2-1)-(x^3-1) Sqrt[2]*(x^2-1)
Out[1]= -1 + x^3 + Sqrt[2]*(-1 + x^2) - Sqrt[2]*(-1 + x^2)*(-1 + x^3) + 2*Sum[Floor[(Sqrt[2]*k*(-1 + x^2))/(-1 + x^3)], {k, 1, -2 + x^3}]
\sourceoff
Und selbst wenn man versucht, hier ein x zu finden, welches dann als Übergabeparameter ganzzahlig wird, landet man bei x=1
was dann durch Dein Beispiel auch noch zur Polstelle wird -> da kann nie was brauchbares rauskommen.
Bei ggT(0,0) braucht man auch nicht zu rechnen, weil man die 0 sofort erkennt (nicht nur wegen ggT(x,x)=x ).
Also mal aus einer anderen Richtung:
Mit PolynomialGCD[x^3 - 1, Sqrt[2]*(x^2 - 1)] = x-1 ,
bekommt man durch Gleichsetzung:
\sourceon mathematica
x=x^3 + Sqrt[2]*(-1 + x^2) - Sqrt[2]*(-1 + x^2)*(-1 + x^3) + 2*Sum[Floor[(Sqrt[2]*k*(-1 + x^2))/(-1 + x^3)], {k, 1, -2 + x^3}]
-> eine Lösung bei x=1
-> und abzüglich der 1 (die bei der Gleichsetzung weggelassen) -> die gewünschte 0
\sourceoff
Ich sehe hier keinerlei Bezug zur Praxis:
- Teilerfunktionen machen nur dann Sinn, wenn die Argumente der beteiligten Funktionen auch ganzzahlig sind (sonst fängt hier noch jemand an die Teilbarkeitsregeln zu erweitern...)
Ich kann mir auch nicht vorstellen, dass ich der erste sein soll, der
ggT von Polynomen mal praktisch nachrechnet und weggelassene Spezialfälle findet, die für ein richtiges Ergebnis wichtig sind.
Andererseits habe ich schon viele Beispiele gefunden, wo jemand was vorrechnet und alle anderen stur ohne Nachfrage genau so rechnen.
Und Lehrer stellen ja auch nur immer Teilaufgaben -> und die Aufgabenlöser schreiben nur immer das Ergebnispolynom hin.
Keiner stolpert über seltene Spezialfälle beim Einsetzen von Zahlen...
|
Profil
|
Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1862
 | Beitrag No.7, eingetragen 2020-12-18
|
\quoteon(2020-12-18 21:59 - hyperG in Beitrag No. 6)
Einer Funktion, die schon im Namen das Wort "Teiler" hat, als Übergabeparameter irrationale Zahlen zu übergeben, ist schon gemein.
(etwa so, als wolle man die Sqrt[2]. Primzahl berechnen mit Prime[Sqrt[2]])
...
Ich sehe hier keinerlei Bezug zur Praxis:
- Teilerfunktionen machen nur dann Sinn, wenn die Argumente der beteiligten Funktionen auch ganzzahlig sind (sonst fängt hier noch jemand an die Teilbarkeitsregeln zu erweitern...)
\quoteoff
"Sonst fängt hier noch jemand an die Teilbarkeitsregeln zu erweitern..." Das haben schon viele vor uns gemacht, es gibt in dieser Welt auch andere Ringe als nur $\mathbb{Z}$, in der der Teilbarkeitsbegriff Sinn ergibt. Das gesamte Gebiet der algebraischen Zahlentheorie baut darauf auf.
Ein Beispiel eines solches Ringes ist ein Polynomring über UFDs. Das entsprechende Lemma von Gauß findest du in jedem einführenden Buch zur Algebra.
|
Profil
|
| hyperG hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
2023-12-08 22:11 !
Wie unterstütze ich den Matheplaneten mit Geld?
