Polynomringe: Multiplikation

Neue Frage »

regxy Auf diesen Beitrag antworten »
Polynomringe: Multiplikation
hallo,
ich versuche die Multiplikation in Polynomringen zu verstehen, kapiere aber gar nichts.
Zitat:

code:
1:
2:
3:
die Multiplikation wird als Faltung definiert:
(a0,a1,a2,…)⋅(b0,b1,b2,…)(a0​,a1​,a2​,…)⋅(b0​,b1​,b2​,…):=(a0⋅b0,a0⋅b1+a1⋅b0,…,cn,…):=(a0​⋅b0​,a0​⋅b1​+a1​⋅b0​,…,cn​,…).
wobei für die n-te Komponente gilt: cn:=∑k=0nak⋅bn−kcn​:=k=0∑n​ak​⋅bn−k​

https://mathepedia.de/Polynomringe.html
(leider geht die Formatierung bei c+p verloren; keinen Zitat-tag gefunden)
Die Tupel (a0,a1,a2,…,am) und (b0,b1,b2,…,bm) sind ja wohl die Koeffizienten der Polynome for x^0 bis x^m.
Die Addition ist komponentenweise, das ist klar.
Aber die Multiplikation....?
Offenbar werden hier für das n-te Glied die Produkte des n-ten a mit allen b0...bn aufsummiert.
Aber was soll das, was ist der Grund dafür? (Warum z.B. nicht gleich mit allen b0...bn...bm?)
Was erreicht man mit dieser "Faltung"?
Oder ist m gar nicht endlich, sondern unendlich?
Malcang Auf diesen Beitrag antworten »

Versuchen wir das doch anhand einer ausführlichen Multiplikation zu verstehen:


Wie kamen wir nun beispielsweise auf ?
regxy Auf diesen Beitrag antworten »

kA, was meinst du damit?
Malcang Auf diesen Beitrag antworten »

Es wird natürlich gemäß Assoziativgesetz ausmultipliziert. Das Monom entsteht dabei durch Multiplikation von
und
und
oder
und .
Im linken Polynom haben wir einmal
links , rechts , also
und
links , rechts , also .

Damit ist -4X^2 - 2X^2 = X^2\cdot(-4-2) = -6X^2
regxy Auf diesen Beitrag antworten »

ich weiß nicht, was ein Monom ist, aber in Tupelschreibweise hätten wir ja für

(1,0,2)*(-1,3,-4)
Nach AG wird jedes a-Glied mit jedem b-Glied multipliziert, und die Einzelprodukte insgesamt aufsummiert.
Bei der "Faltung" wird aber
(a0b0, a1b0+a1b1, a2b0+a2b1+a2b2)
IIUC also :
(-1, 0+0, -2+6-8) = (-1, 0, -4)
gerechnet,
also nur quasi ein Dreieck statt alles mit allem.
Das Ergebnis wäre dann ein Polynom der Form

-1*x° + 0*x - 4*x²
(CMIIW)
Den Sinn dahinter kapiere ich nicht.
Malcang Auf diesen Beitrag antworten »

Im Grunde hast du es damit erklärt.
Um den Koeffizienten für zu berechnen, multipliziere ich
Nun für
Folgen wir diesem Muster weiter für (zum Verständnis: Lege mal jeweils einen Finger auf den entsprechenden Faktor im linken Tupel und einen auf den im rechten Tupel):


Der Sinn dahinter ist der, dass ich auf den Koeffizienten für (m+1 ter Eintrag im Tupel) komme, indem ich alle Potenzen ausmultipliziere, sodass sich als Exponent ergibt. Dies sind
, und dann natürlich deren Koeffizienten aufsummiere.
 
 
regxy Auf diesen Beitrag antworten »

nein, habe ich nicht, denn du hast nach AG ja alle möglichen Exponenten,
inkl. x, x³ und x^4,
bei mir kommen die letzteren aber gar nicht vor, sondern ausschließlich x° und x².
Und für x² hast du den Koeffizienten -6, ich aber -4.
Also kann man es doch wohl gar nicht vergleichen...?!

(hat sich mit deinem edit überschnitten, ist aber jetzt sogar noch unklarer)
Malcang Auf diesen Beitrag antworten »

Zitat:
Original von regxy
Bei der "Faltung" wird aber
(a0b0, a1b0+a1b1, a2b0+a2b1+a2b2)


Nein. Die Faltung ist
Malcang Auf diesen Beitrag antworten »

Oh nein, mein Fehler, bitte vielmals zu entschuldigen. Mein Kopf ist für heute zu matsche. Kann sich vielleicht jemand anders noch als helfer einschalten?
regxy Auf diesen Beitrag antworten »

ok, danke, dann gucken wir nochmal:
(a0b0, a0b1+a1b0, a0b2+a1b1+a2b0)

also für
(1,0,2)*(-1,3,-4) = (-1, 3+0, -4+0-2 ) = (-1, 3, -6)

dann kriege ich jetzt

-1 +3x -6x²

du hast aber raus:
−1+3X−6X²+6X³−8X^4

d.h. du hast die Glieder samt Koeffizienten für x^3 und x^4 zuviel....?
Oder wie oder was?

(DIESER SCHEISS-FORUMS-EDITOR!!)

(edit, wieder Kreuzpost mit deinem edit)
Malcang Auf diesen Beitrag antworten »

So, bitte nochmal vielmals um Entschuldigung.
Du musst due Tupel mit Nullen auffüllen. Wenn wir ein Polynom vom Grad mit einem Polynom vom Grad multiplizieren, erhalten wir eines vom Grad .
Für unser Beispiel genügt also:


Nun das gezeigte Schema anwenden.
regxy Auf diesen Beitrag antworten »

ja, aber das habe ich doch oben gemacht.
Wir hatten 2 Polynome vom Grad 2 (beim ersten habe ich das x'-Glied mit 0 ergänzt)
(1,0,2)
(-1,3,-4)
und bei der Ring-Multiplikation ergibt sich per "Faltung"

(a0b0, a1b0+a1b1, a2b0+a2b1+a2b2)

also:
(1,0,2)*(-1,3,-4)
= (-1, 3+0, -2+6-8 ) = (-1, 3, -4) (edit, hatte mich oben verrechnet)

ausgeschrieben als Summe
-1 +3x -4x²

das ist aber nun wieder ein Polynom vom Grad 2 (nicht 4!),
und es ist etwas völlig anderes als wenn ich 2 Polynome nach AssG, also jedes Glied des 1. mit jedem Glied des 2. ausmultipliziere, so wie du es oben gemacht hast.

Anscheinend ist also die Multiplikation in Polynomringen etwas anderes als das Miteinander-Multiplizieren von 2 einzelnen Polynom-Reihen.

Aber warum macht man das, was ist der Sinn dahinter, was gewinnt man mit dieser Art von Multiplikation, was nützt das für welche Zwecke und Anwendungen?

(wäre schön, wenn man hier im bb-code-Editor auch hoch und tief stelllen könnte)

PS, edit:
scheint übrigens (i. Ggs. zum AssG) auch nicht kommutativ zu sein, denn
per (a0b0, a1b0+a1b1, a2b0+a2b1+a2b2):

(-1,3,-4)*(1,0,2) =
(-1, 3+0, -4+0+-8) = (-1, 3, -8)
=> -1 +3x -12x² (??)
regxy Auf diesen Beitrag antworten »

bescheuert, dass man hier nach 15 Min. nicht mehrTippfehler korrigieren kann! Was soll das?

das PS oben sollte heißen:

scheint übrigens (i. Ggs. zum AssG) auch nicht kommutativ zu sein, denn
per (a0b0, a1b0+a1b1, a2b0+a2b1+a2b2):

(-1,3,-4)*(1,0,2) =
(-1, 3+0, -4+0-8) = (-1, 3, -12)
=> -1 +3x -12x² (??)
regxy Auf diesen Beitrag antworten »

Mist, wieder die falsche Formel erwischt, lässt sich wieder nicht mehr editieren, ist aber auch wurscht, geht ja generell nur ums Prinzip mit der Faltung.
Helferlein Auf diesen Beitrag antworten »

Du machst den Fehler das Tupel zu beschränken. Richtig wäre es, wie Dir oben auch schon gesagt wurde, mit Nullen aufzufüllen. Das mag auf den ersten Blick unnötig aussehen, spielt für die Berechnung aber eine wichtige Rolle.
Wenn Du zwei Polynome vom Grad n und m multipliziert, entsteht ein Polynom mit Höchststand n+m, so dass Du auch entsprechend viele Stellen in den Tupeln berücksichtigen musst.
regxy Auf diesen Beitrag antworten »

ach so, ich dachte nur die mit Nullen auffüllen, wo die x^n-te Position irgendwo mittendrin gar nicht auftaucht.

Ok, also bei 2x 2.Grad dann also noch bis x^4.

Und das soll nun mit dieser Faltung dasselbe ergeben, als wenn ich wie bei 2 Reihen ganz normal jedes mit jedem anderen Element multipliziere, wie sonst auch beim Ausmultiplizieren von Klammern?
regxy Auf diesen Beitrag antworten »

saperlott, update:
nachdem ich mich manuell laufend verrechnet habe, habe ich's programmiert:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <iostream>

using namespace std;


#define num(t) (int)(sizeof(t)/sizeof(t[0]))

double a[] = {1,0,2,0,0};
double b[] = {-1,3,-4,0,0};

int n = num(a);
int m = num(b);

double c[5];


int main()
{
    printf("sizes: a:%d b:%d\n", n,m);
    memset(c, 0, sizeof(c));
    cout << "a: ";
    for (auto x : a) {
        cout << " " << x ;
    }
    cout << endl;
    cout << "b: ";
    for (auto x : b) {
        cout << " " << x;
    }
    cout << endl;


    for(int n=0; n<=5; n++) {
        for(int k=0; k<=n; k++) {
            c[n] = c[n] + a[k]*b[n-k];
        }
    }

    cout << "c=a*b: ";
    for (auto x : c) {
        cout << " " << x;
    }
    cout << endl;


    return 0;
}

und siehe da:
code:
1:
2:
3:
4:
5:
6:
sizes: a:5 b:5
a:  1 0 2 0 0
b:  -1 3 -4 0 0
c=a*b:  -1 3 -6 6 -8


scheint zu passen.... smile Wink
regxy Auf diesen Beitrag antworten »

habe jetzt nochmal in der doppelten for-Schleife ausgeben lassen, was er da eigentlich genau miteinander multipliziert und aufaddiert:

a0*b0

a0*b1
a1*b0

a0*b2
a1*b1
a2*b0

a0*b3
a1*b2
a2*b1
a3*b0

a0*b4
a1*b3
a2*b2
a3*b1
a4*b0

a0*b5
a1*b4
a2*b3
a3*b2
a4*b1
a5*b0

- jetzt ist es mir endlich klar, was hier genau passiert, und wie das Ergebnis zustande kommt.

Vielen Dank an alle!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »