p-adische Approximation < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:07 Sa 17.11.2012 | | Autor: | tagg |
Hallo,
ich will hier keine Aufgabe gelöst bekommen, es geht mir hier einfach ums grundlegende Verständnis der p-adischen Approximation, die ich in Computeralgebra gehört habe. Habe auch beim Prof. nochmal nachgefragt, aber 100% verstanden hab ichs immer noch nicht.
Man will hier Gleichungssysteme Ax=b in [mm] \IZ [/mm] lösen, indem man einem Computeralgebrasystem Rechnen beibringt..
Hier der Text im Skript:
Sei p [mm] \in \IP [/mm] und [mm] \overline{.}:\IZ \to \IF_{p} [/mm] die Restklassenabbildung. Dann schreiben wir [mm] \overline{A} [/mm] und [mm] \overline{b} [/mm] für die Matrizen und Vektoren modulo p. [mm] \overline{A} [/mm] und [mm] \overline{b} [/mm] sind über [mm] \IF_{p}, [/mm] also einem Körper, gegeben und können deshalb ein [mm] x_{1} [/mm] mit Gauß Algorithmus finden, mit [mm] \overline{Ax_{1}}=\overline{b}. [/mm]
Es existieren also [mm] x_{1} \in \IZ^{n}, c_{1} \in \IZ^{m} [/mm] mit [mm] Ax_{1}=b+pc_{1} [/mm] via [mm] c_{1} [/mm] := [mm] (Ax_{1}-b)/p. [/mm] Wenn wir nun [mm] \overline{x}_{2} [/mm] finden können mit [mm] \overline{Ax_{2}}=-\overline{c_{1}}, [/mm] so folgt [mm] A(x_{1}+px_{2})=b+pc_{1}+p(-c_{1}+pc_{2})=b+p^{2}c_{2} [/mm] für [mm] c_{2}=(Ax_{2}-c_{1})/p. [/mm]
Durch Iterieren finden wir also [mm] x_{i}, c_{i} [/mm] mit [mm] A\summe_{}^{}p^{i-1}x_{i}=b+p^{i}c_{i}.
[/mm]
Falls nun Ax=b genau eine Lösung in [mm] \IQ^{n} [/mm] hat und diese in [mm] \IZ^{n} [/mm] lebt, so können wir sie mit dieser Methode finden. Für [mm] p^{i}>2||x||_{\infty} [/mm] muss offensichtlich [mm] x_{i}=x [/mm] gelten, wenn wir [mm] x_{i} [/mm] im symmetrischen Restsystem modulo [mm] p^{i} [/mm] darstellen.
Was ich hier nicht verstanden habe, ist, warum irgendwann [mm] x_{i} [/mm] meine Lösung sein soll. Wenn ich oben für ein genügend großes [mm] p^{i} [/mm] die gleichung modulo [mm] p^{i} [/mm] betrachte, dann müsste doch [mm] A\summe_{}^{}p^{i-1}x_{i} \equiv [/mm] b mod [mm] p^{i} [/mm] da stehen, also müsste doch für großes [mm] p^{i} [/mm] (was ja garantiert, dass wir "fast" in [mm] \IZ [/mm] sind) [mm] x=\summe_{}^{}p^{i-1}x_{i} [/mm] meine Lösung sein, oder?
Wo liegt hier mein Denkfehler und wie stellt man sich das richtig vor?
Danke für eure Hilfe!!!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:55 Sa 17.11.2012 | | Autor: | rainerS |
Hallo!
> Hallo,
>
> ich will hier keine Aufgabe gelöst bekommen, es geht mir
> hier einfach ums grundlegende Verständnis der p-adischen
> Approximation, die ich in Computeralgebra gehört habe.
> Habe auch beim Prof. nochmal nachgefragt, aber 100%
> verstanden hab ichs immer noch nicht.
>
> Man will hier Gleichungssysteme Ax=b in [mm]\IZ[/mm] lösen, indem
> man einem Computeralgebrasystem Rechnen beibringt..
>
> Hier der Text im Skript:
> Sei p [mm]\in \IP[/mm] und [mm]\overline{.}:\IZ \to \IF_{p}[/mm] die
> Restklassenabbildung. Dann schreiben wir [mm]\overline{A}[/mm] und
> [mm]\overline{b}[/mm] für die Matrizen und Vektoren modulo p.
> [mm]\overline{A}[/mm] und [mm]\overline{b}[/mm] sind über [mm]\IF_{p},[/mm] also
> einem Körper, gegeben und können deshalb ein [mm]x_{1}[/mm] mit
> Gauß Algorithmus finden, mit
> [mm]\overline{Ax_{1}}=\overline{b}.[/mm]
> Es existieren also [mm]x_{1} \in \IZ^{n}, c_{1} \in \IZ^{m}[/mm] mit
> [mm]Ax_{1}=b+pc_{1}[/mm] via [mm]c_{1}[/mm] := [mm](Ax_{1}-b)/p.[/mm] Wenn wir nun
> [mm]\overline{x}_{2}[/mm] finden können mit
> [mm]\overline{Ax_{2}}=-\overline{c_{1}},[/mm] so folgt
> [mm]A(x_{1}+px_{2})=b+pc_{1}+p(-c_{1}+pc_{2})=b+p^{2}c_{2}[/mm] für
> [mm]c_{2}=(Ax_{2}-c_{1})/p.[/mm]
> Durch Iterieren finden wir also [mm]x_{i}, c_{i}[/mm] mit
> [mm]A\summe_{}^{}p^{i-1}x_{i}=b+p^{i}c_{i}.[/mm]
> Falls nun Ax=b genau eine Lösung in [mm]\IQ^{n}[/mm] hat und diese
> in [mm]\IZ^{n}[/mm] lebt, so können wir sie mit dieser Methode
> finden. Für [mm]p^{i}>2||x||_{\infty}[/mm] muss offensichtlich
> [mm]x_{i}=x[/mm] gelten, wenn wir [mm]x_{i}[/mm] im symmetrischen Restsystem
> modulo [mm]p^{i}[/mm] darstellen.
>
>
> Was ich hier nicht verstanden habe, ist, warum irgendwann
> [mm]x_{i}[/mm] meine Lösung sein soll.
[mm]p^{i}>2||x||_{\infty}[/mm] bedeutet doch, dass jede Komponente des Vektors x zwischen [mm] $-p^i/2$ [/mm] und [mm] $+p^i/2$ [/mm] liegt. Wird [mm]x_{i}[/mm] im symmetrischen Restsystem dargestellt, so liegt jede Komponente des Vektors [mm] $x_i$ [/mm] auch zwischen [mm] $-p^i/2$ [/mm] und [mm] $+p^i/2$. [/mm] Das bedeutet aber, dass die Differenz der jeweiligen Komponenten in [mm] $x-x_i$ [/mm] kleiner als [mm] $p^i$ [/mm] ist. Andererseits ist per Konstruktion jede Komponente von [mm] $x-x_i$ [/mm] ein Vielfaches von [mm] $p^i$. [/mm] Das geht nur, wenn [mm] $x-x_i=0$ [/mm] ist.
> Wenn ich oben für ein
> genügend großes [mm]p^{i}[/mm] die gleichung modulo [mm]p^{i}[/mm]
> betrachte, dann müsste doch [mm]A\summe_{}^{}p^{i-1}x_{i} \equiv[/mm]
> b mod [mm]p^{i}[/mm] da stehen, also müsste doch für großes [mm]p^{i}[/mm]
> (was ja garantiert, dass wir "fast" in [mm]\IZ[/mm] sind)
> [mm]x=\summe_{}^{}p^{i-1}x_{i}[/mm] meine Lösung sein, oder?
Wieso? Zunächst mal ist nur [mm]x=\summe_{}^{}p^{i-1}x_{i} \pmod{p^i}$[/mm] .
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:48 Sa 17.11.2012 | | Autor: | tagg |
Hallo Rainer,
danke für deine schnelle und ziemlich aufschlussreiche Antwort! In der Tat habe ich bisher die Sache mit [mm] p^{i}>2||x||_{\infty} [/mm] und dem symmetrischen Restsystem nicht in Verbindung gebracht...
Jetzt bleibt für mich bei deiner Antwort nur noch die Frage offen, warum jede Komponente von [mm] x-x_{i} [/mm] per Konstruktion ein Vielfaches von [mm] p^{i} [/mm] ist und warum daraus dann [mm] x-x_{i}=0 [/mm] folgt?
Wie stelle ich mir mein x überhaupt vor? Du sagtest, dass [mm] x=\summe_{}^{}p^{i-1}x_{i} \pmod{p^i} [/mm] ist. Aber i ist doch der Laufindex von der Summe, wie kann ich da denn etwas mod [mm] p^{i} [/mm] betrachten?
Nach nem Tag voller Mathe Lernen scheine ich das alles gerade nicht mehr zu sehen :)
Vielen Dank fürs auf die Sprünge Helfen!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:16 So 18.11.2012 | | Autor: | felixf |
Moin!
> Jetzt bleibt für mich bei deiner Antwort nur noch die
> Frage offen, warum jede Komponente von [mm]x-x_{i}[/mm] per
> Konstruktion ein Vielfaches von [mm]p^{i}[/mm] ist und warum daraus
> dann [mm]x-x_{i}=0[/mm] folgt?
Vorsicht. Die beiden Fragen gehoeren zusammen:
> Wie stelle ich mir mein x überhaupt vor? Du sagtest, dass
> [mm]x=\summe_{}^{}p^{i-1}x_{i} \pmod{p^i}[/mm] ist. Aber i ist doch
> der Laufindex von der Summe, wie kann ich da denn etwas mod
> [mm]p^{i}[/mm] betrachten?
In deiner ersten Frage gibt es ein Notations-Chaos. Und zwar in den Zeilen
"Durch Iterieren finden wir also $ [mm] x_{i}, c_{i} [/mm] $ mit $ [mm] A\summe_{}^{}p^{i-1}x_{i}=b+p^{i}c_{i}.$"
[/mm]
und
"Für $ [mm] p^{i}>2||x||_{\infty} [/mm] $ muss offensichtlich $ [mm] x_{i}=x [/mm] $ gelten, wenn wir $ [mm] x_{i} [/mm] $ im symmetrischen Restsystem modulo $ [mm] p^{i} [/mm] $ darstellen."
Du meinst eher sowas wie:
"Durch Iterieren finden wir also $ [mm] x_{i}, c_{i} [/mm] $ mit $ [mm] A\summe_{i=1}^{k}p^{i-1}x_{i}=b+p^{k}c_{k}.$"
[/mm]
und
"Für $ [mm] p^{k}>2||x||_{\infty} [/mm] $ muss offensichtlich [mm] $\sum_{i=1}^k p^{i-1} x_i=x [/mm] $ gelten, wenn wir [mm] $\sum_{i=1}^k p^{i-1} x_i$ [/mm] im symmetrischen Restsystem modulo [mm] $p^{k}$ [/mm] darstellen."
In der Aufgabenstellung fehlt uebrigens noch ein wichtiger Hinweis. Es reicht nicht aus, dass es genau eine Loesung von $A x = b$ in [mm] $\IQ^n$ [/mm] gibt (die bereits in [mm] $\IZ^n$ [/mm] liegt), es muss auch sein, dass es modulo $p$ nur genau eine Loesung gibt. (Dies ist etwa dann der Fall, wenn $p$ nicht [mm] $\det [/mm] A$ teilt, falls $n = m$ ist.)
Ist dies naemlich der Fall, so gibt es auch modulo [mm] $p^k$ [/mm] nur genau eine Loesung, und diese muss kongruent zu $x$ modulo [mm] $p^k$ [/mm] sein, da immer $A x [mm] \equiv [/mm] b [mm] \pmod{p^k}$ [/mm] ist. Damit hast du $x [mm] \equiv \summe_{i=1}^{k}p^{i-1}x_{i} \pmod{p^k}$, [/mm] womit jede Komponente von $x - [mm] \summe_{i=1}^{k}p^{i-1}x_{i}$ [/mm] durch [mm] $p^k$ [/mm] teilbar ist. Da jede Komponente im Intervall [mm] $(-p^k, p^k)$ [/mm] liegt, muss sie gleich 0 sein, womit $x = [mm] \summe_{i=1}^{k}p^{i-1}x_{i}$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:48 So 18.11.2012 | | Autor: | tagg |
aah, ich glaube jetzt habe ich es verstanden, vielen Dank!!
Ja, das Notations-Chaos kann einem wirklich zu schaffen machen..! Aber: Damit muss ich zZ leider gerade leben, das Vorlesungsskript ist nicht das aller beste 
Danke nochmal!
|
|
|
|
