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. 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_{k}}$  con ${\displaystyle j,k\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 (PDF), su cs.uwaterloo.ca.

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