Algoritmo di Lagrange: differenze tra le versioni

Versione delle 17:03, 29 nov 2014

Versione attuale delle 17:46, 28 giu 2025

(8 versioni intermedie di 7 utenti non mostrate)

Riga 1:

{{F|matematicaalgebra|febbraio 2013}}

In [[matematica]], e più precisamente in [[algebra lineare]], l''''algoritmo di Lagrange''' è un [[algoritmo]] utile a trovare una [[base ortogonale]] in uno [[spazio vettoriale]] di [[dimensione (spazio vettoriale)|dimensione]] finita munito di un [[prodotto scalare]]. Viene utilizzato nel [[Problemi sui reticoli|problema]] della ricerca di un vettore di norma minima (''Shortest Vector Problem'', abbreviato in SVP), ed è collegato con l'[[algoritmo LLL]] (algoritmo di Lenstra-Lenstra-Lovász).

Si tratta di una variante del processo di [[ortogonalizzazione di Gram-Schmidt]] utilizzata nel caso in cui il prodotto scalare non sia [[prodotto scalare definito positivo|definito positivo]].

== L'algoritmo ==

Sia <math> V </math> uno spazio vettoriale di dimensione finita su un [[campo (matematica)|campo]] <math> K </math> di caratteristica diversa da 2, con prodottoforma bilineare scalaresimmetrica <math> \phi </math>. L'algoritmo costruisce una base ortogonale a partire da una [[base (algebra lineare)|base]] <math> v_1,\ldots, v_n </math> data. Si tratta di applicare iterativamente per <math> i=1,\ldots, n </math> le mosse seguenti:

* Se <math> v_i </math> non è [[vettore isotropo|isotropo]], allora <math>\phi(v_i,v_i)\neq 0 </math> e si definisce

:<math> v'_i = v_i - \sum_{j>i}\frac{\phi(v_i,v_j)}{\phi(v_j,v_j)}v_j </math>

:Il risultato è un vettore <math>v'_i </math> che continua a formare una base con i vettori restanti, ma ortogonale a tutti i vettori successivi: infatti <math>\phi(v_i',v_j)=0 </math> per ogni <math>j>i </math>. Quindi si sostituisce <math> v_i </math> con <math> v_i' </math>.

* Se <math> v_i </math> è un [[vettore isotropo]], viene scambiato con un elemento non isotropo <math> v_j </math> con <math> j>i</math>. Nel caso in cui tutti tali vettori siano isotropi, si cerca un vettore non isotropo tra i <math> v_j+v_{j'k} </math> con <math>j,j'k\geq i </math>. Se anche tutti questi sono isotropi, allora la base è già ortogonale e l'algoritmo si interrompe.

== Voci correlate ==

Riga 19 ⟶ 18:

==Collegamenti esterni==

* {{en}}cita [web|url=https://cs.uwaterloo.ca/~cbright/reports/latticealgs.pdf |titolo=Curtis Bright - Algorithms for Lattice Basis Reduction]|lingua=en}}

{{Algebra lineare}}

{{Portale|matematica}}

[[Categoria:Algebra lineare]]