Lánczos-algoritmus

• IPA:

Lánczos-algoritmus

1. (matematika)

A Lánczos-algoritmus egy hatékony numerikus módszer, amely a nagy méretű szimmetrikus mátrixok sajátértékeinek és sajátvektorainak meghatározására szolgál. Ez az algoritmus különösen hasznos a numerikus lineáris algebra területén, például a kvantummechanikában, a statisztikai fizikában és a gépi tanulásban.

A Lánczos-algoritmus a teljes mátrix helyett egy kisebb dimenziójú, tridiagonális mátrixot állít elő, amely numerikusan közelíti az eredeti mátrix sajátértékeit és sajátvektorait. Ez a módszer az úgynevezett Krylov-tér fogalmára épül.

A Krylov-tér egy ${\displaystyle \mathbf {A} }$ mátrix és egy ${\displaystyle \mathbf {v} }$ kezdővektor alapján a következő vektorok által generált altér: $${\displaystyle {\mathcal {K}}_{m}(\mathbf {A} ,\mathbf {v} )={\text{span}}(\mathbf {v} ,\mathbf {A} \mathbf {v} ,\mathbf {A} ^{2}\mathbf {v} ,\dots ,\mathbf {A} ^{m-1}\mathbf {v} ).}$$ A Lánczos-algoritmus ezen altérben dolgozik, hogy közelítse az ${\displaystyle \mathbf {A} }$ sajátértékeit.

Az algoritmus a Krylov-térben egy ortogonális bázist konstruál, és az ${\displaystyle \mathbf {A} }$ mátrixot ebben a bázisban egy tridiagonális mátrixszá alakítja: $${\displaystyle \mathbf {T} _{m}={\begin{bmatrix}\alpha _{1}&\beta _{1}&0&\cdots &0\\\beta _{1}&\alpha _{2}&\beta _{2}&\cdots &0\\0&\beta _{2}&\alpha _{3}&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\beta _{m-1}\\0&0&0&\beta _{m-1}&\alpha _{m}\end{bmatrix}}.}$$ Az ${\displaystyle \mathbf {T} _{m}}$ tridiagonális mátrix sajátértékei az ${\displaystyle \mathbf {A} }$ mátrix sajátértékeinek jó közelítését adják.

1. Kezdővektor kiválasztása: Válassz egy véletlen vagy specifikus ${\displaystyle \mathbf {v} _{1}}$ kezdővektort, amelyet normálni kell (${\displaystyle \|\mathbf {v} _{1}\|=1}$).

2. Iteráció:

• Számítsd ki a következő iterált vektort:

$${\displaystyle \mathbf {w} _{k+1}=\mathbf {A} \mathbf {v} _{k}-\alpha _{k}\mathbf {v} _{k}-\beta _{k-1}\mathbf {v} _{k-1},}$$ ahol

$${\displaystyle \alpha _{k}=\mathbf {v} _{k}^{T}\mathbf {A} \mathbf {v} _{k},\quad \beta _{k}=\|\mathbf {w} _{k+1}\|.}$$

  - Ortogonalizálj a korábbi vektorokra.

3. Megállási feltétel: Az iterációt ${\displaystyle m}$-edik lépésben állítsd le, ha ${\displaystyle m}$ kisebb, mint az ${\displaystyle \mathbf {A} }$ mérete, vagy ha ${\displaystyle \beta _{m}}$ kicsi.

4. Tridiagonális mátrix: Az ${\displaystyle \mathbf {T} _{m}}$ mátrix sajátértékeit és sajátvektorait kiszámítva megkapod az eredeti mátrix közelítését.

Az alábbi kód egy egyszerű Python implementációt mutat be a Lánczos-algoritmusra:

import numpy as np

def lanczos_algorithm(A, v, m):
    """
    Lánczos-algoritmus szimmetrikus mátrix tridiagonális közelítéséhez.

    Args:
        A (numpy.ndarray): Szimmetrikus mátrix.
        v (numpy.ndarray): Kezdővektor (normált).
        m (int): Iterációk száma.

    Returns:
        T (numpy.ndarray): Tridiagonális mátrix.
        V (numpy.ndarray): Ortogonális bázisvektorok.
    """
    n = A.shape
    V = np.zeros((n, m))
    T = np.zeros((m, m))
    
    v = v / np.linalg.norm(v)
    V = v
    
    beta = 0
    w = np.zeros_like(v)
    
    for j in range(m):
        w = A @ V - beta * (V if j > 0 else 0)
        alpha = V.T @ w
        w = w - alpha * V
        
        if j < m - 1:
            beta = np.linalg.norm(w)
            if beta < 1e-10:  # Konvergencia
                break
            V = w / beta
        
        T = alpha
        if j < m - 1:
            T = beta
            T = beta
    
    return T, V

# Példa: Egy 5x5-ös szimmetrikus mátrix sajátértékeinek közelítése
A = np.array(,
              ,
              ,
              ,
              ], dtype=float)

v = np.random.rand(A.shape)  # Véletlen kezdővektor
v = v / np.linalg.norm(v)  # Normálás
m = 3  # Iterációk száma

T, V = lanczos_algorithm(A, v, m)

print("Tridiagonális mátrix T:")
print(T)

# Sajátértékek összehasonlítása
eigvals, _ = np.linalg.eig(A)
lanczos_eigvals = np.linalg.eigvals(T)

print("\nEredeti mátrix sajátértékei:")
print(np.sort(eigvals))

print("\nTridiagonális közelítés sajátértékei:")
print(np.sort(lanczos_eigvals))

1. Kvantummechanika: Nagyméretű Hamilton-mátrixok sajátértékeinek meghatározása. 2. Statisztikai fizika: Adatcsökkentés (dimenziócsökkentés) a nagy adathalmazokból. 3. Gépi tanulás: Spektrális elemzés a PCA (főkomponens-analízis) során.

A Lánczos-algoritmus a gyakorlatban gyors és hatékony, különösen akkor, ha csak néhány sajátértékre van szükség, mert nem szükséges az egész mátrixot kezelni.

• Lánczos-algoritmus - Értelmező szótár (MEK)
• Lánczos-algoritmus - Etimológiai szótár (UMIL)
• Lánczos-algoritmus - Szótár.net (hu-hu)
• Lánczos-algoritmus - DeepL (hu-de)
• Lánczos-algoritmus - Яндекс (hu-ru)
• Lánczos-algoritmus - Google (hu-en)
• Lánczos-algoritmus - Helyesírási szótár (MTA)
• Lánczos-algoritmus - Wikidata
• Lánczos-algoritmus - Wikipédia (magyar)