Lánczos-algoritmus

Magyar

Kiejtés

• IPA: [ ˈlaːnd͡zzoʃɒlɡoritmuʃ]

Főnév

Lánczos-algoritmus

1. (matematika)

Lánczos-algoritmus

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.

Az algoritmus lényege

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.

Krylov-tér

A Krylov-tér egy $\mathbf {A}$ mátrix és egy $\mathbf {v}$ kezdővektor alapján a következő vektorok által generált altér: $${\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 $\mathbf {A}$ sajátértékeit.

Tridiagonális mátrix

Az algoritmus a Krylov-térben egy ortogonális bázist konstruál, és az $\mathbf {A}$ mátrixot ebben a bázisban egy tridiagonális mátrixszá alakítja: $$\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 $\mathbf {T} _{m}$ tridiagonális mátrix sajátértékei az $\mathbf {A}$ mátrix sajátértékeinek jó közelítését adják.

Az algoritmus lépései

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

2. Iteráció:

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

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

$$\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 $m$-edik lépésben állítsd le, ha $m$ kisebb, mint az $\mathbf {A}$ mérete, vagy ha $\beta _{m}$ kicsi.

4. Tridiagonális mátrix: Az $\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.

Példa: Python implementáció

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[0]
    V = np.zeros((n, m))
    T = np.zeros((m, m))
    
    v = v / np.linalg.norm(v)
    V[:, 0] = v
    
    beta = 0
    w = np.zeros_like(v)
    
    for j in range(m):
        w = A @ V[:, j] - beta * (V[:, j-1] if j > 0 else 0)
        alpha = V[:, j].T @ w
        w = w - alpha * V[:, j]
        
        if j < m - 1:
            beta = np.linalg.norm(w)
            if beta < 1e-10:  # Konvergencia
                break
            V[:, j + 1] = w / beta
        
        T[j, j] = alpha
        if j < m - 1:
            T[j, j + 1] = beta
            T[j + 1, j] = beta
    
    return T, V

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

v = np.random.rand(A.shape[0])  # 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))

Alkalmazások

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.

Fordítások

Tartalom

angol: Lanczos algorithm (en)

További információk

• 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)