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 $V$ uno spazio vettoriale di dimensione finita su un campo $K$ di caratteristica diversa da 2, con forma bilineare simmetrica $ϕ$ . L'algoritmo costruisce una base ortogonale a partire da una base $v_{1}, \dots, v_{n}$ data. Si tratta di applicare iterativamente per $i = 1, \dots, n$ le mosse seguenti:

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

v'_{i} = v_{i} - \sum_{j > i} \frac{ϕ (v_{i}, v_{j})}{ϕ (v_{j}, v_{j})} v_{j}

Il risultato è un vettore

v'_{i}

che continua a formare una base con i vettori restanti, ma ortogonale a tutti i vettori successivi: infatti

ϕ ({v_{i}}^{'}, v_{j}) = 0

per ogni

j > i

. Quindi si sostituisce

v_{i}

con

{v_{i}}^{'}

.

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

Voci correlate

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

V · D · M Algebra lineare
Spazio vettoriale	Vettore · Sottospazio vettoriale (Sottospazio generato) · Applicazione lineare (Nucleo · Immagine) · Base · Dimensione · Teorema della dimensione · Formula di Grassmann · Sistema lineare · Algoritmo di Gauss · Teorema di Rouché-Capelli · Regola di Cramer · Spazio duale · Spazio proiettivo · Spazio affine · Teorema della dimensione per spazi vettoriali
Matrici	Identità · Nulla · Quadrata · Invertibile · Simmetrica · Antisimmetrica · Trasposta · Diagonale · Triangolare · Di cambiamento di base · Ortogonale · Normale · Rotazione · Simplettica · Moltiplicazione di matrici · Rango · Teorema di Kronecker · Minore · Matrice dei cofattori · Determinante · Teorema di Binet · Teorema di Laplace · Radice quadrata di una matrice
Diagonalizzabilità	Autovettore e autovalore · Spettro · Polinomio caratteristico · Polinomio minimo · Teorema di Hamilton-Cayley · Matrice a blocchi · Forma canonica di Jordan · Teorema di diagonalizzabilità
Prodotto scalare	Forma bilineare · Sottospazio ortogonale · Spazio euclideo · Base ortonormale · Algoritmo di Lagrange · Segnatura · Teorema di Sylvester · Gram-Schmidt · Forma sesquilineare · Forma hermitiana · Teorema spettrale