Algoritmo di Lagrange

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 finita munito di un prodotto scalare. Viene utilizzato nel 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 definito positivo.

L'algoritmo

Sia ${\displaystyle V}$  uno spazio vettoriale di dimensione finita su un campo ${\displaystyle K}$ , con prodotto scalare ${\displaystyle \phi }$ . L'algoritmo costruisce una base ortogonale a partire da una base ${\displaystyle v_{1},\ldots ,v_{n}}$  data. Si tratta di applicare iterativamente per ${\displaystyle i=1,\ldots n}$  le mosse seguenti:

• Se ${\displaystyle v_{i}}$  non è isotropo, allora ${\displaystyle \phi (v_{i},v_{i})\neq 0}$  e si definisce

${\displaystyle v'_{i}=v_{i}-\sum _{j>i}{\frac {\phi (v_{i},v_{j})}{\phi (v_{j},v_{j})}}v_{j}}$ 

Il risultato è un vettore ${\displaystyle v'_{i}}$  che continua a formare una base con i vettori restanti, ma ortogonale a tutti i vettori successivi: infatti ${\displaystyle \phi (v_{i}',v_{j})=0}$  per ogni ${\displaystyle j>i}$ . Quindi si sostituisce ${\displaystyle v_{i}}$  con ${\displaystyle v_{i}'}$ .

• Se ${\displaystyle v_{i}}$  è un vettore isotropo, viene scambiato con un elemento non isotropo ${\displaystyle v_{j}}$  con ${\displaystyle j>i}$ . Nel caso in cui tutti tali vettori siano isotropi, si cerca un vettore non isotropo tra i ${\displaystyle v_{j}+v_{j'}}$  con ${\displaystyle j,j'\geq i}$ . Se anche tutti questi sono isotropi, allora la base è già ortogonale e l'algoritmo si interrompe.

Voci correlate

• Criterio di Jacobi
• Problemi sui reticoli
• Segnatura (algebra lineare)
• Teorema di Sylvester

Collegamenti esterni

• (EN) Curtis Bright - Algorithms for Lattice Basis Reduction

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica