Численные методы
Численное вычисление собственных значений
1998 год: Google запускается на 25 миллионах страниц. Ранжирование - доминирующий собственный вектор матрицы 25M×25M. Прямое вычисление заняло бы тысячелетия. Алгоритм степенных итераций находит его за несколько десятков умножений матрицы на вектор - потому что сходится экспоненциально к главному собственному направлению. PCA, PageRank, спектральная кластеризация - везде одна задача: найти собственные векторы.
- **PCA в ML:** SVD матрицы данных X даёт главные компоненты; sklearn.decomposition.PCA использует randomized SVD (алгоритм Хальке-Мартинссон-Тропп)
- **Google PageRank:** доминирующий собственный вектор разреженной матрицы 10⁹×10⁹; вычисляется степенной итерацией за ~50 шагов
- **Спектральная кластеризация:** k наименьших собственных значений лапласиана графа; scipy.sparse.linalg.eigsh с k=n_clusters
Предварительные знания
Степенная итерация
Степенная итерация - простейший способ найти **доминирующее** собственное значение (с наибольшим модулем). Начинаем с произвольного вектора v₀ и многократно умножаем на A: vₙ₊₁ = A·vₙ / ||A·vₙ||. Компонента вдоль главного собственного вектора растёт быстрее всех остальных.
**Степенная итерация:** vₙ₊₁ = A·vₙ / ||A·vₙ|| После сходимости: λ₁ ≈ vₙᵀ·A·vₙ (квадратурная форма Релея) **Сходимость:** |λ₂/λ₁|ⁿ → 0 Если |λ₁| >> |λ₂|, метод очень быстрый. **Обратная итерация** для нахождения НАИМЕНЬШЕГО собственного значения: vₙ₊₁ = A⁻¹·vₙ / ||A⁻¹·vₙ|| (решаем A·v = vₙ на каждом шаге)
Для нахождения собственного значения РЯДОМ с σ используют **сдвинутую обратную итерацию**: (A − σI)⁻¹·v. Чем ближе σ к собственному значению, тем быстрее сходимость. Это основа алгоритма Ланцоша.
Степенная итерация сходится медленно, когда:
QR-алгоритм
QR-алгоритм (Фрэнсис, 1961) - стандартный метод вычисления ВСЕХ собственных значений плотной матрицы. Идея: итеративно применяем QR-разложение. Матрица A сходится к треугольной форме (Шур), на диагонали которой - собственные значения.
**QR-алгоритм (базовый):** A₀ = A Для k = 0, 1, 2, ... Qₖ, Rₖ = QR(Aₖ) ← QR-разложение Aₖ₊₁ = Rₖ·Qₖ ← обратное произведение Aₖ → T (треугольная/Шур форма), диагональ T = собственные значения. **Практические улучшения:** - Предварительное приведение к форме Хессенберга: O(n³) → O(n²) на шаг - Двойной сдвиг Фрэнсиса: обработка комплексных пар, ускорение в 10-100× - Сложность полного алгоритма: O(n³)
На практике используйте `numpy.linalg.eig` (несимметричные) или `numpy.linalg.eigh` (симметричные). Для больших разреженных матриц - `scipy.sparse.linalg.eigs` (метод Арнольди/Ланцоша, только несколько собственных значений).
Что находится на диагонали матрицы Шур T, к которой сходится QR-алгоритм?
Метод Ланцоша
QR-алгоритм O(n³) не применим для больших разреженных матриц (n = 10⁶). Метод Ланцоша строит трёхдиагональную матрицу T размера k×k (k << n) за k умножений A·v. Собственные значения T - хорошие приближения k крайних собственных значений A.
**Метод Ланцоша:** Для симметричной A строим ортонормированный базис Крылова: {v₁, Av₁, A²v₁, ...} → ортогонализируем → T трёхдиагональная **k шагов Ланцоша:** - k умножений A·v: O(k·nnz) - Трёхдиагональная T: k×k вместо n×n - Собственные значения T: O(k³) (мало!) **Ritz-значения:** приближения к k крайним λ(A). Для несимметричных: алгоритм Арнольди.
| Задача | Метод | Сложность | Инструмент |
|---|---|---|---|
| Все λ плотной | QR-алгоритм | O(n³) | numpy.linalg.eig/eigh |
| k λ разреженной | Ланцош (symm) | O(k·nnz) | scipy.sparse.linalg.eigsh |
| k λ несимм. | Арнольди | O(k·nnz) | scipy.sparse.linalg.eigs |
| PCA | SVD / Ланцош | O(mn·k) | scipy.sparse.linalg.svds |
Почему метод Ланцоша предпочтителен для больших разреженных матриц перед QR-алгоритмом?
Ключевые идеи
- **Степенная итерация:** доминирующее λ₁; сходимость |λ₂/λ₁|ⁿ; обратная итерация для λ_min
- **QR-алгоритм:** все собственные значения плотной матрицы; O(n³); numpy.linalg.eig/eigh
- **Метод Ланцоша:** k крайних λ разреженной матрицы; k умножений A·v; scipy.sparse.linalg.eigsh
- **Выбор:** numpy.linalg.eigh для плотных SPD, scipy.sparse.linalg.eigsh для разреженных (PCA, PageRank)
Связанные темы
Собственные значения связывают линейную алгебру с ML и анализом графов:
- Разреженные матрицы — Метод Ланцоша работает через SpMV разреженных матриц - граф-лапласианов и матриц смежности
- Numerical Methods в ML — Рандомизированный SVD (Хальке) - современная альтернатива для PCA с огромными матрицами данных
Вопросы для размышления
- Почему numpy.linalg.eigh точнее и быстрее numpy.linalg.eig для симметричных матриц?
- Как алгоритм Ланцоша связан с методом сопряжённых градиентов? (подсказка: одно пространство Крылова)
- Почему PageRank - это задача нахождения собственного вектора, а не решение системы уравнений?