LLL Algorithmus - Warum ändern sich die Gram-Schmidt-Vektoren nicht?

29.03.2012, 18:42	Lorenz Ipsum	Auf diesen Beitrag antworten »
LLL Algorithmus - Warum ändern sich die Gram-Schmidt-Vektoren nicht? Meine Frage: Hallo zusammen, ich habe folgendes Problem, beim Beweis der Korrektheit des LLL Algorithmus (http://en.wikipedia.org/wiki/Lenstra?Lenstra?Lovász_lattice_basis_reduction_algorithm#LLL_Algorithm) ist es wichtig zu zeigen das sich während der Reduktion der Vektoren, die Gram-Schmidt-Vektoren dazu nicht ändern. Genau dass gelingt mir aber nich zu zeigen, ich wäre für Hilfe und Tipps dankbar. Meine Ideen: Das einzige was ich gefunden habe ist, dass sich die Gram-Schmidt-Vektoren von $\begin{eqnarray} b_1,b_2, \dots,b_k \end{eqnarray}$ angeblich nicht verändern falls man folgende Operation durchführt. $\begin{eqnarray} b_l = b_l - \sum\limits_{k=1}^{l-1}a_k b_k \end{eqnarray}$ und $\begin{eqnarray} a_k \in \mathbb Z \end{eqnarray}$ Um dass zu beweisen habe ich schon versucht den Gram-Schmidt vektor von dem neuen $\begin{eqnarray} b_l \end{eqnarray}$ auszurechnen, allerdings bisher ohne Erfolg

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »