Rekursion und Minimalpolynom < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beispiel:
Gegeben: [mm] s_{n+6}=-s_{n+5}-s_{n+4}-s_{n+3}-s_n [/mm] in [mm] \IZ_2
[/mm]
Gesucht: Minimale Periode der Rekursion |
Das oben ist nur eine Beispielsaufgabe. Ich würde gerne wissen, wie ich hier am effizientesten das Minimalpolynom berechnen kann.
Wenn ich das Minimalpolynom dieser Rekursion habe gilt: Minimale Periode der Rekursion = [mm] 2^{\text{degree}(m(x))}-1 [/mm] mit m(x)=Minimalpolynom unserer Rekursion. Jedenfalls meine ich das so von der Vorlesung her verstanden zu haben, korrekt?
Ich habe hier das charakteristische Polynom
[mm] $x^6+x^5+x^4+x^3+1=\underbrace{(x^4+x+1)}_{p(x):=}*\underbrace{(x^2+x+1)}_{d(x):=}$ [/mm] in [mm] \IZ_2 [/mm] .
p(x) und d(x) haben keine Nullstellen. Reicht das schon, um zu folgern, dass p(x) und d(x) irreduzibel sind?
Wie kann ich hier nun das Minimalpolynom bestimmen?
Grüsse
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:53 Mo 23.12.2013 | | Autor: | Teufel |
Hi!
Ich kann dir leider nicht bei allem helfen, aber weil noch keiner sonst geantwortet hat, sag ich mal das, was ich weiß:
Dass ein Polynom keine Nullstellen hat bedeutet nicht, dass es irreduzibel ist. Das Stimmt nur für Polynome (über Körpern) vom Grad 2 und 3.
Beispiel: [mm] $x^4+2x^2+1\in\IR[x]$ [/mm] hat keine Nullstellen, aber dennoch gilt [mm] $x^4+2x^2+1=(x^2+1)(x^2+1)$. [/mm] Um bei dir Irreduzibilität nachzuweisen, mach einfach den Ansatz [mm] $x^4+x+1=(x^2+ax+b)(x^2+cx+d)$ [/mm] (wieso reicht dieser Ansatz?) und schau, ob du irgendwelche Werte für $a,b,c,d$ rausbekommst.
Wenn es misslingen sollte, dann ist dein Polynom irreduzibel.
|
|
|
| |
|
$ [mm] x^6+x^5+x^4+x^3+1=\underbrace{(x^4+x+1)}_{p(x):=}\cdot{}\underbrace{(x^2+x+1)}_{d(x):=} [/mm] $
Danke p(x) ist irreduzibel über [mm] \IZ_2.
[/mm]
Meine Frage aber nach wie vor:
Wie berechne ich nun hier das Minimalpolynom dieser Rekursion ?
Grüsse
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Fr 27.12.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:08 Di 24.12.2013 | | Autor: | felixf |
Moin!
> Beispiel:
> Gegeben: [mm]s_{n+6}=-s_{n+5}-s_{n+4}-s_{n+3}-s_n[/mm] in [mm]\IZ_2[/mm]
> Gesucht: Minimale Periode der Rekursion
Die minimale Periode? Die ist 1, siehe die Folge [mm] $s_n [/mm] = 0$ fuer alle $n [mm] \in \IZ_2$.
[/mm]
Oder ist hier eher die maximale Periode gefragt?
> Das oben ist nur eine Beispielsaufgabe. Ich würde gerne
> wissen, wie ich hier am effizientesten das Minimalpolynom
> berechnen kann.
Bei linearen Rekurrenzen ueber Koerpern ist das Minimalpolynom doch gleich dem charakteristischem Polynom. Oder wie habt ihr das Minimalpolynom definiert?
> Wenn ich das Minimalpolynom dieser Rekursion habe gilt:
> Minimale Periode der Rekursion = [mm]2^{\text{degree}(m(x))}-1[/mm]
> mit m(x)=Minimalpolynom unserer Rekursion. Jedenfalls meine
> ich das so von der Vorlesung her verstanden zu haben,
> korrekt?
Was genau meinst du mit "minimale Periode"? Die maximal moegliche Periode?
> Ich habe hier das charakteristische Polynom
> [mm]x^6+x^5+x^4+x^3+1=\underbrace{(x^4+x+1)}_{p(x):=}*\underbrace{(x^2+x+1)}_{d(x):=}[/mm]
> in [mm]\IZ_2[/mm] .
>
> p(x) und d(x) haben keine Nullstellen. Reicht das schon, um
> zu folgern, dass p(x) und d(x) irreduzibel sind?
Nein, es reicht nicht (wie Teufel schrieb), aber irreduzibel sind sie beide.
LG Felix
|
|
|
| |
|
| Aufgabe | Betrachte die Rekursion $ [mm] s_{n+6}=-s_{n+5}-s_{n+4}-s_{n+3}-s_n [/mm] $ mit den vorgegebenen Werten [mm] s_0=1 [/mm] , [mm] s_1=0 [/mm] , [mm] s_2=1, s_3=0, s_4=1.
[/mm]
1. Berechne das charakteristische Polynom der Rekursion.
2. Wie gross ist die Periode?
3. Wie gross wäre die Periode, wenn das charakteristische Polynom irreduzibel wäre? |
Hallo
Mal ganz konkret als Aufgabe, siehe oben.
1. $ [mm] x^6+x^5+x^4+x^3+1=\underbrace{(x^4+x+1)}_{p(x):=}\cdot{}\underbrace{(x^2+x+1)}_{d(x):=} [/mm] $ wobei p und d jeweils irreduzibel.
2. 15 . Das kann ich aber nur bestimmen, indem ich die ersten 30 Glieder hinschreibe und dann von Hand nachsehe, wie gross die Periode ist? Wie kommt man also auf [mm] 2^4-1 [/mm] mit Argumentation wie sie hier steht:
http://www.diva-portal.org/smash/get/diva2:507821/FULLTEXT01.pdf
(Theorem 5.3)
Wie lässt sich das Minimalpolynom bestimmen?
3. [mm] 2^6-1 [/mm] ??? Warum ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:20 So 29.12.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
