Polynome, Multiplikation < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:12 Do 16.10.2014 | | Autor: | sissile |
| Aufgabe | p,q $ [mm] \in \IR[x] [/mm] $
p(x)= $ [mm] \sum_{i=0}^n a_i x^i [/mm] $
q(x)= $ [mm] \sum_{j=0}^m b_j x^j [/mm] $
Wieso ist dann: pq= [mm] \sum_{j=0}^{m+n} d_j x^j
[/mm]
mit [mm] d_j [/mm] = [mm] \sum_{j=max(0,j-m)}^{min(j,n)} a_i b_{j-i} [/mm] |
Hallo,
Ich schreib das immer anders an, deshalb hab ich Probleme die obige Schreibweise zu verstehen.
[mm] \sum_{i=0}^n a_i x^i *\sum_{j=0}^m b_j x^j [/mm] = [mm] \sum_{s=0}^{n+m} c_s x^s
[/mm]
mit [mm] c_s [/mm] = [mm] \sum_{r=0}^s a_{s-r} b_r [/mm] = [mm] \sum_{i+j=s} a_i b_j
[/mm]
wobei [mm] a_t [/mm] = 0 für t>n und [mm] b_t [/mm] =0 für t>m
LG,
sissi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:10 Do 16.10.2014 | | Autor: | Marcel |
Hallo Sissile,
> p,q [mm]\in \IR[x][/mm]
> p(x)= [mm]\sum_{i=0}^n a_i x^i[/mm]
> q(x)=
> [mm]\sum_{j=0}^m b_j x^j[/mm]
>
> Wieso ist dann: pq= [mm]\sum_{j=0}^{m+n} d_j x^j[/mm]
> mit [mm]d_j[/mm] = [mm]\sum_{j=max(0,j-m)}^{min(j,n)} a_i b_{j-i}[/mm]
was macht das denn für einen Sinn? Linkerhand ist [mm] $j\,$ [/mm] fest, rechterhand
dann eine Laufvariable... Kannst Du das mal korrigieren?
> Hallo,
> Ich schreib das immer anders an, deshalb hab ich Probleme
> die obige Schreibweise zu verstehen.
>
> [mm]\sum_{i=0}^n a_i x^i *\sum_{j=0}^m b_j x^j[/mm] =
> [mm]\sum_{s=0}^{n+m} c_s x^s[/mm]
> mit [mm]c_s[/mm] = [mm]\sum_{r=0}^s a_{s-r} b_r[/mm]
> = [mm]\sum_{i+j=s} a_i b_j[/mm]
> wobei [mm]a_t[/mm] = 0 für t>n und [mm]b_t[/mm] =0
> für t>m
Mach' Dir das doch erstmal an einem Beispiel klar, etwa, berechne etwa:
[mm] $(a_0+a_1x+a_2x^2+a_3x^3)*(b_2x^2+b_3x^3+b_4x^4+b_6x^6)$
[/mm]
Das Ganze hat "mit der natürlichen Vorgehensweise beim Distributivgesetz"
zu tun. Und wenn Du das ganze mit Vektor-Notation machst, wirst Du
sehen, dass da das sogenannte Faltungsprodukt ins Spiel kommt.
Ich bin faul und mache ein einfacheres Beispiel:
[mm] $(a_0+a_2x^2)*(b_1x+b_3x^3)$
[/mm]
berechnet sich zu
[mm] $a_0b_1x+(a_0b_3+a_2b_1)x^3+a_2b_3x^5\,.$
[/mm]
Das passt zum Vektor
[mm] $\blue{(0,\;\;a_0b_1,\;\;0,\;\;a_0b_3+a_2b_1,\;\;0,\;\;a_2b_3)}$
[/mm]
Das Faltungsprodukt der Vektoren
[mm] $(a_0,0,a_2)$ [/mm] und [mm] $(0,b_1,0,b_3)$
[/mm]
ist mit dem folgenden ![[]](/images/popup.gif) Schema, Seite 19, wobei wir den ersten Vektor spiegeln:
Für 1. Komponente
[mm] $\pmat{a_2, & 0, & a_0 & & \\ & & 0, & b_1, & 0, & b_3}$ [/mm]
[mm] $\rightarrow a_0*0=0\,.$
[/mm]
Für 2. Komponente
[mm] $\pmat{a_2, & 0, & a_0, & & \\ & 0, & b_1, & 0, & b_3}$ [/mm]
[mm] $\rightarrow 0*0+a_0b_1=a_0b_1\,.$
[/mm]
Für 3. Komponente
[mm] $\pmat{a_2, & 0, & a_0 & & \\ 0, & b_1, & 0, & b_3}$ [/mm]
[mm] $\rightarrow a_2*0+0*b_1+a_0*0=0\,.$
[/mm]
Für 4. Komponente
[mm] $\pmat{a_2, & 0, & a_0, & & \\ b_1, & 0, & b_3}$ [/mm]
[mm] $\rightarrow a_2*b_1+0*0+a_0*b_3=a_2b_1+a_0b_3\,.$
[/mm]
Für 5. Komponente
[mm] $\pmat{a_2, & 0, & a_0, & & \\ 0, & b_3}$ [/mm]
[mm] $\rightarrow a_2*0+0*b_3=0\,.$
[/mm]
Für 6. Komponente
[mm] $\pmat{a_2, & 0, & a_0, & & \\ b_3}$ [/mm]
[mm] $\rightarrow a_2*b_3\,.$
[/mm]
Damit das Schema vielleicht besser verständlich wird:
Du hast zwei Vektoren
[mm] $(a_0,\;a_1,\;a_2,\;...,\;a_n)$
[/mm]
und
[mm] $(b_0,\;b_1,\;b_2,\;b_3,\;...,\;b_m)\,.$
[/mm]
Einer der beiden wird gespiegelt (geflippt), ich nehme hier den oberen:
Dann haben wir also
[mm] $(a_n,\;...,\;a_2,\;a_1,\;a_0)$
[/mm]
und
[mm] $(b_0,\;b_1,\;b_2,\;b_3,\;...,\;b_m)\,.$
[/mm]
Das Ende des letzten oberen Vektors wird so angelegt, dass es über
dem Anfang des unteren Vektors steht:
[mm] $\begin{matrix}(a_n,&...,&a_2,&a_1,&a_0) &\\ & & & &(b_0,&b_1,&b_2,&b_3,&\;...&b_m)\end{matrix}$
[/mm]
Übereinanderstehende Komponenten werden miteinander multipliziert,
danach das "spaltenweise Ergebnis" addiert, und danach wird der untere
Vektor um 1 nach links verschoben (analog könnte man auch den oberen
um 1 nach rechts verschieben):
Also:
1. Komponente des Faltungsprodukts:
Wegen
[mm] $\begin{matrix}(a_n,&...,&a_2,&a_1,&a_0) &\\ & & & &(b_0,&b_1,&b_2,&b_3,&\;...&b_m)\end{matrix}$
[/mm]
ist sie
[mm] $a_0b_0$
[/mm]
2. Komponente des Faltungsprodukts:
Wegen
[mm] $\begin{matrix}(a_n,&...,&a_2,&a_1,&a_0) &\\& & &(b_0,&b_1,&b_2,&b_3,&\;...&b_m)\end{matrix}$
[/mm]
ist sie
[mm] $a_0b_1+a_1b_0\,$ [/mm] (eigentlich [mm] $a_1b_0+a_0b_1,$ [/mm] was aber das gleiche ist).
3. Komponente des Faltungsprodukts:
Wegen
[mm] $\begin{matrix}(a_n,&...,&a_2,&a_1,&a_0) &\\& &(b_0,&b_1,&b_2,&b_3,&\;...&b_m)\end{matrix}$
[/mm]
ist sie
[mm] $a_0b_2+a_1b_1+a_2b_0\,$ [/mm] (eigentlich [mm] $a_2b_0+a_1b_1+a_0b_2,$ [/mm] was aber das gleiche ist).
etc. pp.
Du siehst dann auch: Die "letzte zu berechnenende Komponente" ist
[mm] $a_n+b_m,$ [/mm] diese entsteht nach [mm] $n+m+1\,$ [/mm] Schritten. Das Faltungsprodukt
hat also $n+m+1$ Komponenten, da wir aber den Eintrag der 1. Komponente
mit [mm] $c_0$ [/mm] bezeichnen, stehen da also die Einträge [mm] $c_0$ [/mm] ... [mm] $c_{n+m}$ [/mm] drin.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:37 Fr 17.10.2014 | | Autor: | sissile |
Diese Methode ist ja toll ;)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:41 Fr 17.10.2014 | | Autor: | sissile |
Hallo Marcel,
>
> > p,q [mm]\in \IR[x][/mm]
> > p(x)= [mm]\sum_{i=0}^n a_i x^i[/mm]
> > q(x)=
> > [mm]\sum_{j=0}^m b_j x^j[/mm]
> >
> > Wieso ist dann: pq= [mm]\sum_{j=0}^{m+n} d_j x^j[/mm]
> > mit [mm]d_j[/mm]
> = [mm]\sum_{j=max(0,j-m)}^{min(j,n)} a_i b_{j-i}[/mm]
>
> was macht das denn für einen Sinn? Linkerhand ist [mm]j\,[/mm]
> fest, rechterhand
> dann eine Laufvariable... Kannst Du das mal korrigieren?
Ups, ich hab das j als Laufvariable durch i verbessert:
pq= $ [mm] \sum_{j=0}^{m+n} d_j x^j [/mm] $
mit $ [mm] d_j [/mm] $ [mm] =\sum_{i=max(0,j-m)}^{min(j,n)} a_i b_{j-i}
[/mm]
LG,
sissi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:02 Fr 17.10.2014 | | Autor: | Marcel |
Hallo Sissi,
> Hallo Marcel,
> >
> > > p,q [mm]\in \IR[x][/mm]
> > > p(x)= [mm]\sum_{i=0}^n a_i x^i[/mm]
> > >
> q(x)=
> > > [mm]\sum_{j=0}^m b_j x^j[/mm]
> > >
> > > Wieso ist dann: pq= [mm]\sum_{j=0}^{m+n} d_j x^j[/mm]
> > > mit
> [mm]d_j[/mm]
> > = [mm]\sum_{j=max(0,j-m)}^{min(j,n)} a_i b_{j-i}[/mm]
> >
> > was macht das denn für einen Sinn? Linkerhand ist [mm]j\,[/mm]
> > fest, rechterhand
> > dann eine Laufvariable... Kannst Du das mal
> korrigieren?
>
> Ups, ich hab das j als Laufvariable durch i verbessert:
>
> pq= [mm]\sum_{j=0}^{m+n} d_j x^j[/mm]
> mit [mm]d_j[/mm]
> [mm]=\sum_{i=max(0,j-m)}^{min(j,n)} a_i b_{j-i}[/mm]
alles klar. Deine Frage war aber nun keine Frage, sondern eher eine
Mitteilung. Oder sehe ich das falsch?
Kommst Du mit obigem zurecht?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:07 Fr 17.10.2014 | | Autor: | sissile |
Hallo Marcel,
Ehrlichgesagt komme ich mit der Darstellung der [mm] d_j [/mm] noch immer nicht ganz zurrecht. Schwierigkeiten bereiten mir die Summengrenzen max(0,j-m) bis min(j,n) .
Warum z.B die untere Grenze nicht 0 ist sondern das max(0, j-m) ist mir unklar.
LG,
sissi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:59 Fr 17.10.2014 | | Autor: | Marcel |
Hallo Sissile,
> Hallo Marcel,
>
> Ehrlichgesagt komme ich mit der Darstellung der [mm]d_j[/mm] noch
> immer nicht ganz zurrecht. Schwierigkeiten bereiten mir die
> Summengrenzen max(0,j-m) bis min(j,n) .
> Warum z.B die untere Grenze nicht 0 ist sondern das max(0,
> j-m) ist mir unklar.
mir auch, darauf habe ich gar nicht geachtet. Von wem stammt das denn?
Ich würde mir erstmal, wie schon öfters gesagt, mal ein einfaches Bsp.
angucken, ob das zusammen passt. Eigentlich hatten wir schonmal
[mm] $p(x)*q(x)=(\sum_{i=0}^n a_ix^i)*\sum_{j=0}^m b_jx^j=\sum_{k=0}^{m+n}\;\;\left\{\left( \sum_{\substack{(i,j) \in \IN_0 \times \IN_0\\i+j=k}}a_ib_j\right)*x^k\right\}=\sum_{k=0}^{m+n}\;\;\left( \sum_{j=0}^k a_{k-j}b_j\right)*x^k$
[/mm]
Wenn die Behauptung stimmt, dann kannst Du das ja kontrollieren, indem
Du nachweist, dass alle Koeffizienten übereinstimmen. Stimmt nur einer
nicht überein, so ist die Behauptung Quatsch.
Und das würde ich, wie gesagt, erstmal an einem einfachen Beispiel prüfen.
Wenn es dann schon nicht klappt, weißt Du, dass die Aussage Quatsch ist.
Wenn es klappt, dann siehst Du vielleicht auch schon, wieso. Und wenn
Du das siehst, dann hast Du vielleicht auch eine Idee, wie man das beweisen
könnte.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:08 Sa 18.10.2014 | | Autor: | sissile |
Hallo Marcel,
Ich hab diese Darstellung aus den Internet-Lösungen des Buches:"Einführung in das mathematische Arbeiten- Schichl&Steinbauer"
Ich hab mir ein Bsp angeschaut mit
p(x)= $ [mm] \sum_{i=0}^n a_i x^i [/mm] $
q(x)= $ [mm] \sum_{j=0}^m b_j x^j [/mm] $
n=3,
m=2
[mm] \sum_{k=0}^{m+n}\;\;\left( \sum_{j=0}^k a_{k-j}b_j\right)\cdot{}x^k [/mm]
führt zu:
[mm] \sum_{k=0}^5 (a_k b_0 [/mm] + [mm] a_{k-1} b_1 [/mm] + [mm] a_{k-2} b_2 +...+a_0 b_k) x^k [/mm] = [mm] a_0 b_0 [/mm] + [mm] (a_1 b_0 [/mm] + [mm] a_0 b_1) x^1 [/mm] + [mm] (a_3 b_0 [/mm] + [mm] a_2 b_1 [/mm] + [mm] a_1 b_2 [/mm] + [mm] a_0 b_3) x^2 [/mm]
[mm] +(a_4 b_0 [/mm] + [mm] a_3 b_1 [/mm] + [mm] a_2 b_2 [/mm] + [mm] a_1 b_3 [/mm] + [mm] a_0 b_4) x^3 [/mm] + [mm] (a_5 b_0 [/mm] + [mm] a_4 b_1 [/mm] + [mm] a_3 b_2 [/mm] + [mm] a_2 b_3 [/mm] + [mm] a_1 b_4 [/mm] + [mm] a_0 b_5)x^4 +(..)x^5
[/mm]
da ja [mm] b_t [/mm] =0 mit t>2, [mm] a_t [/mm] =0 mit t >3 ergibt das
[mm] =a_0 b_0 [/mm] + [mm] (a_1 b_0 [/mm] + [mm] a_0 b_1) x^1 [/mm] + [mm] (a_3 b_0 [/mm] + [mm] a_2 b_1 [/mm] + [mm] a_1 b_2) x^2 +(a_3 b_1 [/mm] + [mm] a_2 b_2) x^3 [/mm] + [mm] (a_3 b_2)x^4 +(..)x^5
[/mm]
[mm] \sum_{j=0}^{m+n} \sum_{i=max(0,j-m)}^{min(j,n)} a_i b_{j-i} [/mm]
Bei der inneren Summe trenne ich zuerst bei der unteren Grenze
i=max(0,k-2)
Also bei k=0,k=1 beginnt die Summe ab 0
Bei k=2, k=3, k=4, k=5 beginnt die Summe ab k-2
Die obere Grenze der inneren Summe
i=min(k,3)
Also bei k=0 geht die Summe bis 0
bei k=1 geht die Summe bis 1
bei k=2 geht die Summe bis 2
bei k=3, k=4, k=5 geht die Summe bis 3
führt zu:
[mm] \underbrace{(a_0 b_0)x^0}_{k=0} [/mm] + [mm] \underbrace{(a_0 b_1 + a_1 b_0) x^1}_{k=1} +\underbrace{(\sum_{0}^{2} a_{i} b_{2-i)}x^2}_{k=2}+\sum_{k=3}^5 (\sum_{i=k-2}^{3} a_i b_{k-i})x^k= [/mm]
[mm] \underbrace{(a_0 b_0)x^0}_{k=0} [/mm] + [mm] \underbrace{(a_0 b_1 + a_1 b_0) x^1}_{k=1} +\underbrace{(a_0 b_2+ a_1 b_1 + a_2 b_0)x^2}_{k=2}+\sum_{k=3}^5(a_{k-2} b_2 +a_{k-1} b_1+..+a_3 b_{k-3})x^k
[/mm]
= [mm] \underbrace{(a_0 b_0)x^0}_{k=0} [/mm] + [mm] \underbrace{(a_0 b_1 + a_1 b_0) x^1}_{k=1} +\underbrace{(a_0 b_2+ a_1 b_1 + a_2 b_0)x^2}_{k=2}+ \underbrace{(a_1 b_2 + a_2 b_1 + a_3 b_0)x^3}_{k=3} +\underbrace{(a_2 b_2 + a_3 b_1)x^4}_{k=4} [/mm] + [mm] \underbrace{(a_3 b_2)x^5}_{k=5} [/mm]
Bei mir stimmt die Formel also hinten und vorne nicht überein.
LG,
sissi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Mo 20.10.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
