Algoritme de Lanczos

El algoritme de Lanczos és un algoritme iterativo creat per Cornelius Lanczos, est és una adaptació dels métodos iterativos per a trobar els valors propis més útils i vectores propis d'un sistema llineal de dimensió $n*n$ realisant un número d'operacions, $m$, a on $m$ és més chicotet que $n$.

Encara que computacionalment eficient, en principi, el método formulat inicialment no era útil, per la seua inestabilitat numèrica. En 1970, Ojalvo i Newman varen mostrar cóm fer el método numèricament estable. Açò es va conseguir utilisant un método per a la correcció dels vectores a qualsevol grau de precisió que, quan no es realisa, produïx una série de vectores que estan altament contaminats pels associats en les freqüències naturals més baixes. En el seu treball original, estos autors també varen sugerir cóm seleccionar un vector de partida (utilisen un generador de números aleatoris per a seleccionar cada element del vector de partida) i varen propondre un método determinat empíricamente per a determinar $m$, el reduït número de vectores (deu ser seleccionat per a ser d'aproximadament 1 ½ voltes el número de valors propis exactes que es desija).

Poc despuix el seu treball va ser seguit per més artículs que també varen proporcionar un anàlisis de l'error comés. En l'any 1988, Ojalvo va produir una història més detallada d'este algoritme i una prova d'error eficient per a un valor propi. Actualment, el método és àmpliament utilisat en una varietat de camps tècnics i ha donat lloc una série de variants.

Método iterativo per a trobar valors propis

El método iterativo per a trobar el major valor propi d'una matriu $A$ pot resumir-se senyalant que si $x_0$ és un vector aleatori i $x_{n+1}=A{x}_n$, llavors per a un $n$ gran llímit $x_n/\Vert x_n\Vert$ s'acosta al vector propi normalisat corresponent al valor propi més gran.

Si $A=U\mathrm{diag}({\sigma }_i)U^{\prime }$ és la descomposició en valors propis d'una matriu de $A$, llavors $A^n=U\mathrm{diag}({\sigma }_i^n)U^{\prime }$. Com $n$ es fa gran, la matriu diagonal de valors propis estarà acotada pel valor propi més gran(despreciant el cas en que el valor més gran este repetit ). Mentres, $\Vert x_{n+1}\Vert /\Vert x_n\Vert$ convergiran al major valor propi i $x_n/\Vert x_n\Vert$ al vector propi associat. Si el major valor propi és múltiple, llavors $x_n$ convergirà a un vector en el subespacio generat pels vectores propis associats en eixos valors propis més grans. Després d'haver trobat el primer vector propi / valor, un pot restringir successivament l'algoritme per a l'espai nul (kernel) dels vectores propis coneguts per a obtindre el segon major vector propi / valors i aixina successivament.

En la pràctica, este senzill algoritme no funciona molt be per al càlcul de molts dels vectores propis, ya que qualsevol error de grosseig podria introduir llaugers canvis als components dels vectores propis més significatius de nou en el càlcul, degradant l'exactitut del càlcul.

Método de Lanczos

Durant el procediment d'aplicació del método, en obtindre l'últim valor propi $A^{n-1}v$, també s'obté una série de vectores $A^{j}v,j=0,1,\cdots ,n-2$ els quals són descartats. Com $n$ és en freqüència gran, pot ser que es tinga una gran cantitat d'informació que no s'utilise. Els algoritmes més alvançats, com l'algoritme de Arnoldi, l'algoritme de Lanczos, guarden esta informació i utilisen el procés de Gram–Schmidt o l'algoritme Householder per a ortogonalizar novament en una base que comprén el subespacio de Krylov corresponent a la matriu $A$.

L'algoritme

L'algoritme de Lanczos pot ser vist com un sistema simplificat del algoritme de Arnoldi que s'aplica a matrius hermitianas. El $m-esimo$ pas de l'algoritme transforma la matriu $A$ en una matriu tridiagonal $T_{mm}$; quan $m$ és igual a la dimensió de $A$, $T_{mm}$ és semblant a $A$.

Definicions

Es vol calcular la matriu tridiagonal i simètrica $T_{mm}=V_m^{*}A{V}_m.$

Els elements de la diagonal es denoten per ${\alpha }_j=t_{jj}$, I els elements fòra de la diagonal són denotats per ${\beta }_j=t_{j-1,j}$.

Notar que $t_{j-1,j}=t_{j,j-1}$, per la simetria de la matriu.

Iteración

(Nota: seguint estos passos solament no es trobaren correctament els valors i vectores propis. Es deuen tindre en conte més consideracions per a corregir errors numèrics. Vore la secció Estabilitat numèrica.)

En principi, hi ha quatre maneres d'escriure el procediment de iteración. Paige[1972] i atres treballs mostren que el següent procediment és el més estable numèricament.

 $v_1\leftarrow$ vector aleatori en norma 1.
 $v_0\leftarrow 0$
 ${\beta }_1\leftarrow 0$

 for $j=1,2,\cdots ,m-1$
   $w_j\leftarrow A{v}_j$
   ${\alpha }_j\leftarrow w_j\cdot v_j$
   $w_j\leftarrow w_j-{\alpha }_j{v}_j-{\beta }_j{v}_{j-1}$
   ${\beta }_{j+1}\leftarrow \Vert w_j\Vert$
   $v_{j+1}\leftarrow w_j/{\beta }_{j+1}$
 endfor

 $w_m\leftarrow A{v}_m$
 ${\alpha }_m\leftarrow w_m\cdot v_m$
 return

Ací, $x\cdot y$ representa el producte escalar de vectores $x$ i $y$.

Despuix de la iteración, s'obté la ${\alpha }_j$ and ${\beta }_j$ en els que es forma una matriu tridiagonal.

$T_{mm}=\left(\begin{array}{cccccc}{\alpha }_1& {\beta }_2& & & & 0\\ {\beta }_2& {\alpha }_2& {\beta }_3& & & \\ & {\beta }_3& {\alpha }_3& \ddots & & \\ & & \ddots & \ddots & {\beta }_{m-1}& \\ & & & {\beta }_{m-1}& {\alpha }_{m-1}& {\beta }_m\\ 0& & & & {\beta }_m& {\alpha }_m\end{array}\right)$

Els vectores $v_j$ (vectores de Lanczos) generats sobre la marcha formen la matriu de transformació $V_m=(v_1,v_2,\cdots ,v_m)$, que és útil per al càlcul dels vectores propis (vore més avall). En la pràctica, es podria guardar en cada iteración (pero ocupa memòria), o es podria recalcular quan es necessite, sempre i quan es tinga el primer vector $v_1$. En cada iteración de l'algoritme realisa una multiplicació matriu-vector i atres operacions de punt flotants.

Trobant valors i vectores propis

En acabant de que la matriu $T_{mm}$ és calculada, es poden trobar els seus valors propis ${\lambda }_i^{(m)}$ i els seus corresponents vectores propis $u_i^{(m)}$ (Per eixemple, usant l'algoritme QR o Multiple Relatively Robust Representations (MRRR)). Els valors i vectores propis de$T$ es poden obtindre en $𝒪(m^2)$ usant MRRR; si es vol buscar solament els valors propis estos es calculen en $𝒪(m^2)$ usant bisecció espectral.

Es pot demostrar que els valors propis són valors propis aproximats de la matriu original $A$.

Els vectores propis $y_i$ de $A$ es poden calcular $y_i=V_m{u}_i^{(m)}$, a on $V_m$ és la matriu de transformació que els seus vectores columna són $v_1,v_2,\cdots ,v_m$.

Estabilitat Numèrica

Estabilitat significa quànt es vorà afectat l'algoritme (és dir, es trobara un resultat aproximat propenc l'original) si hi ha menuts errors numèrics introduïts i acumulats. Estabilitat numèrica és el criteri central per a jujar l'utilitat d'una implementació d'un algoritme en un ordenador en grosseig. Per a l'algoritme de Lanczos, es pot demostrar que en una aritmètica exacta, el conjunt de vectores $v_1,v_2,\cdots ,v_{m+1}$ formen una base ortonormal, els valors i vectores propis trobats són bones aproximacions als de la matriu original. No obstant, en la pràctica (com els càlculs es realisen en aritmètiques de punt flotant a on la inexactitud és inevitable, la ortogonalidad es pert ràpidament i en alguns casos el nou vector inclús podria ser linealment dependent del conjunt que ya està construït. Com a resultat, alguns dels valors propis de la matriu tridiagonal resultant no són bones aproximacions per als de la matriu original. Per lo que, l'algoritme de Lanczos no és molt estable.

Els que usen l'algoritme deuen ser capaç de trobar i eliminar els valors propis "en errors". Les implementacions pràctiques de l'algoritme de Lanczos van en tres direccions per a lluitar contra este problema d'estabilitat:

1. Previndre la pèrdua de ortogonalidad
2. Recuperar la ortogonalidad en acabant de que es genera la base.
3. Despuix d'identificar els valors propis "en errors", eliminar-los.