LLL Algorithmus < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:50 Mo 10.08.2009 | | Autor: | Joan2 |
| Aufgabe | [mm] \bruch{d'}{d} [/mm] = [mm] \bruch{det([b_{1},\ldots,b_{i-1},b_{i+1}])^{2}}{det([b_{1},\ldots,b_{i}])^{2}}
[/mm]
= [mm] \bruch {(\produkt_{j=1}^{i-1} \parallel b^{'}_{j} \parallel ^{2})*(\parallel \pi_{i}(b_{i+1})\parallel^{2})}{\produkt_{j=1}^{i} \parallel b^{'}_{j} \parallel ^{2}}
[/mm]
= [mm] \bruch {\parallel \pi_{i}(b_{i+1})\parallel^{2})}{\parallel \pi_{i}(b_{i})\parallel^{2})} [/mm] |
Hallo,
ich versuche gerade den obigen Beweis zu verstehen, hänge allerdings an so einigen Stellen.
Also vorab gelten:
Basis B = [mm] (b_{i},b_{j}) [/mm]
b' ist der Gram-Schmidt orthogonalisierte Vektor von b durch
[mm] $b^{'}_{i} [/mm] = [mm] b_{i} [/mm] - [mm] \summe_{j=i}^{i-1} \mu_{i,j}*b^{'}_{j}$ [/mm] mit [mm] $\mu_{i,j} [/mm] = [mm] \bruch{}{}$
[/mm]
Ganze Zahl, die zur Basis B assoziert wird, ist:
$d = [mm] \produkt_{k=1}^{n} det(\Delta_{k})^{2}$ [/mm] mit [mm] \delta_{k} [/mm] = [mm] L([b_{1}, \ldots, b_{k}])
[/mm]
Nun sind d und d' die Werte von d vor und nach dem Tausch im Algorithmus. Ebenso, sind [mm] \Delta_{k} [/mm] und [mm] \Delta^{'}_{k} [/mm] die Gitter, die von [mm] [b_{1}, \ldots, b_{k}] [/mm] erzeugt werden.
Also, ich verstehe das Ende vom Beweis, allerdings nicht:
1. Wofür steht der Bruch [mm] $\bruch{d'}{d}$ [/mm] ?
2. Wieso ist d = [mm] $det(\Delta_{i})$?
[/mm]
d ist doch definiert als ein Produkt.
3. [mm] \bruch{det([b_{1},\ldots,b_{i-1},b_{i+1}])^{2}}{det([b_{1},\ldots,b_{i}])^{2}}
[/mm]
Woher kommt das hoch 2?
Und ist im Zähler kein [mm] $b_{i}$ [/mm] enthalten, weil gilt [mm] $det(\Delta_{k})$ [/mm] für alle $k [mm] \not= [/mm] i $
Hoffe, jemand kann mir ein paar dieser Fragen beantorten :(
Liebe Grüße
Joan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:57 Di 11.08.2009 | | Autor: | felixf |
Hallo Joan
> [mm]\bruch{d'}{d}[/mm] =
> [mm]\bruch{det([b_{1},\ldots,b_{i-1},b_{i+1}])^{2}}{det([b_{1},\ldots,b_{i}])^{2}}[/mm]
>
> = [mm]\bruch {(\produkt_{j=1}^{i-1} \parallel b^{'}_{j} \parallel ^{2})*(\parallel \pi_{i}(b_{i+1})\parallel^{2})}{\produkt_{j=1}^{i} \parallel b^{'}_{j} \parallel ^{2}}[/mm]
>
> = [mm]\bruch {\parallel \pi_{i}(b_{i+1})\parallel^{2})}{\parallel \pi_{i}(b_{i})\parallel^{2})}[/mm]
>
> Hallo,
>
> ich versuche gerade den obigen Beweis zu verstehen, hänge
> allerdings an so einigen Stellen.
>
> Also vorab gelten:
>
> Basis B = [mm](b_{i},b_{j})[/mm]
>
> b' ist der Gram-Schmidt orthogonalisierte Vektor von b
> durch
>
> [mm]b^{'}_{i} = b_{i} - \summe_{j=i}^{i-1} \mu_{i,j}*b^{'}_{j}[/mm]
> mit [mm]\mu_{i,j} = \bruch{}{}[/mm]
>
> Ganze Zahl, die zur Basis B assoziert wird, ist:
>
> [mm]d = \produkt_{k=1}^{n} det(\Delta_{k})^{2}[/mm] mit [mm]\delta_{k}[/mm]
> = [mm]L([b_{1}, \ldots, b_{k}])[/mm]
>
> Nun sind d und d' die Werte von d vor und nach dem Tausch
> im Algorithmus. Ebenso, sind [mm]\Delta_{k}[/mm] und [mm]\Delta^{'}_{k}[/mm]
> die Gitter, die von [mm][b_{1}, \ldots, b_{k}][/mm] erzeugt werden.
Und dann ist [mm] $\pi_i(v) [/mm] = [mm] \sum_{j=i}^n \frac{\langle v, b_j' \rangle}{\langle b_j', b_j' \rangle}$ [/mm] und [mm] $\pi_i(b_i) [/mm] = [mm] b_i'$.
[/mm]
> Also, ich verstehe das Ende vom Beweis, allerdings nicht:
>
> 1. Wofür steht der Bruch [mm]\bruch{d'}{d}[/mm] ?
Er besagt, wie sich $d$ beim Vertauschen der Vektoren im Algorithmus veraendert. Man zeigt, dass dieser $< 1$ ist (genauer: kleinergleich [mm] $\delta$, [/mm] wobei [mm] $\delta [/mm] < 1$ ein vorgegebener Parameter ist), woraus $d' < d$ folgt. Bei jedem Schritt wird $d$ also kleiner, und irgendwann muss es einen kleinsten Wert erreicht haben -- in dem Fall bricht der Algorithmus ab und ist fertig.
> 2. Wieso ist d = [mm]det(\Delta_{i})[/mm]?
Wie kommst du dadrauf?
> d ist doch definiert als ein Produkt.
Ja, ist es.
> 3.
> [mm]\bruch{det([b_{1},\ldots,b_{i-1},b_{i+1}])^{2}}{det([b_{1},\ldots,b_{i}])^{2}}[/mm]
>
> Woher kommt das hoch 2?
Nun, das kommt daher das man $d$ als Produkt ueber Quadrate von Determianten definiert hat. Da sich ein grossteil der Determinanten von $d$ und $d'$ wegkuerzen, bleiben halt im Nenner und Zaehler je eine Determinante zum Quadrat uebrig.
> Und ist im Zähler kein [mm]b_{i}[/mm] enthalten, weil gilt
> [mm]det(\Delta_{k})[/mm] für alle [mm]k \not= i[/mm]
Weil was gilt?
Schau dir eher an, was genau der Algorithmus vertauscht. Er tauscht naemlich [mm] $b_i$ [/mm] mit [mm] $b_{i+1}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:49 Mi 12.08.2009 | | Autor: | Joan2 |
Ich dank dir so sehr. Das hat mir sehr viel weiter geholfen
Ganz liebe Grüße
Joan
|
|
|
|
