Диагонализация: матрица в собственном зеркале

Диагонализация матрицы - это нахождение системы координат, в которой преобразование становится просто масштабированием по осям. Именно это делает возможным эффективное вычисление матричных степеней, экспонент и решение систем дифференциальных уравнений - три задачи, которые возникают в ML, физике и управлении ежедневно.

• Нейронные ODE: решение dh/dt = Ah через e^(At) - вычисляется через диагонализацию
• Анализ марковских цепей: долгосрочное поведение P^n - диагонализация матрицы переходов
• Физика: нормальные моды колебаний - собственные вектора матрицы связи
• PageRank: степенная итерация сходится к главному собственному вектору
• Спектральная кластеризация: кластеры из собственных векторов лапласиана графа

Диагонализация: матрица в собственном зеркале

**Марков-цепь PageRank обходит весь граф Интернета миллиарды раз - и находит стационарное распределение.** Без диагонализации это потребовало бы перемножать матрицу 10⁹ × 10⁹ снова и снова. С диагонализацией - это одна формула: Aⁿ = PDⁿP⁻¹, где Dⁿ - просто n-е степени отдельных чисел. Диагонализация - это перевод матрицы на язык, где умножение почти бесплатно.

**О чём этот урок на самом деле**: не просто про разложение A = PDP⁻¹. А про то, почему выбор правильного базиса превращает сложную задачу в элементарную - и как именно это используют PCA, спектральная кластеризация и цепи Маркова.

Геометрический смысл: три шага вместо одной матрицы

Геометрический смысл: три шага вместо одной матрицы

Любое линейное преобразование в собственном базисе - просто растяжение вдоль осей. Диагонализация A = PDP⁻¹ расшифровывается геометрически:

A = P · D · P⁻¹ ШАГ 1 - P⁻¹: перейти в собственный базис Вектор x переписывается в координатах собственных векторов. Вращение, которое выравнивает оси по собственным направлениям. ШАГ 2 - D: растяжение вдоль осей Каждая ось умножается на своё собственное значение λᵢ. D = diag(λ₁, λ₂, ..., λₙ) - диагональная матрица. Самое дешёвое из всех линейных преобразований. ШАГ 3 - P: вернуться в стандартный базис Результат переводится обратно в «обычные» координаты. ИТОГ: A·x = P · diag(λ) · P⁻¹ · x - не одна сложная матрица, а три понятных действия

**Ключевое свойство сцены**: A·v₁ лежит точно вдоль v₁, A·v₂ - вдоль v₂. Направление не меняется, только длина. Это и есть определение собственного вектора - а значит, именно в этих направлениях матрица ведёт себя как умножение на число.

Полный пример: A = PDP⁻¹ по шагам

Полный пример: A = PDP⁻¹ по шагам

A = [ 4 2 ] [ 1 3 ] 1. СОБСТВЕННЫЕ ЗНАЧЕНИЯ (из det(A - λI) = 0): det[ 4-λ 2 ] = (4-λ)(3-λ) - 2 = λ² - 7λ + 10 = 0 [ 1 3-λ ] λ₁ = 5, λ₂ = 2 2. СОБСТВЕННЫЕ ВЕКТОРЫ: λ₁=5: (A - 5I)v = 0 → [-1 2][x] = 0 → x = 2y → v₁ = [2, 1] λ₂=2: (A - 2I)v = 0 → [ 2 2][x] = 0 → x = -y → v₂ = [1,-1] 3. МАТРИЦЫ РАЗЛОЖЕНИЯ: P = [ 2 1 ] D = [ 5 0 ] P⁻¹ = 1/(-3) [ -1 -1 ] = [ 1/3 1/3 ] [ 1 -1 ] [ 0 2 ] [ -1 2 ] [ 1/3 -2/3 ] 4. ПРОВЕРКА A = PDP⁻¹: P·D = [ 10 2 ] (P·D)·P⁻¹ = [ 4 2 ] = A ✓ [ 5 -2 ] [ 1 3 ]

Степени матрицы: Aⁿ за O(n) вместо O(n³·k)

Степени матрицы: Aⁿ за O(n) вместо O(n³·k)

Главное прикладное следствие диагонализации - эффективное возведение в степень. Именно отсюда растут ноги у PageRank, цепей Маркова и многих рекуррентных формул.

A = PDP⁻¹ A² = (PDP⁻¹)(PDP⁻¹) = PD(P⁻¹P)DP⁻¹ = PD²P⁻¹ A³ = PD²P⁻¹ · PDP⁻¹ = PD³P⁻¹ ... Aⁿ = PDⁿP⁻¹ А Dⁿ - диагональная матрица, её степень элементарна: D = diag(λ₁, λ₂, ..., λₖ) Dⁿ = diag(λ₁ⁿ, λ₂ⁿ, ..., λₖⁿ) ПРИМЕР - A¹⁰⁰ для нашей матрицы: D¹⁰⁰ = diag(5¹⁰⁰, 2¹⁰⁰) A¹⁰⁰ = P · diag(5¹⁰⁰, 2¹⁰⁰) · P⁻¹ Вместо 100 матричных перемножений - 2 числа в степени.

ML-применение: PageRank и цепи Маркова

ML-применение: PageRank и цепи Маркова

PageRank Google - это стационарное распределение ~марковской цепи на графе Интернета. Стационарное распределение - предел Aⁿ·x при n → ∞. Алгоритм power iteration буквально повторяет умножение на матрицу A снова и снова - это и есть диагонализация в действии.

Матрица переходов P (стохастическая) имеет: λ₁ = 1 (всегда - стационарное состояние) |λ₂|, ..., |λₙ| < 1 (собственные значения меньше 1 по модулю) Тогда Pⁿ при n → ∞: Pⁿ = P · diag(1ⁿ, λ₂ⁿ, ...) · P⁻¹ → P · diag(1, 0, 0, ...) · P⁻¹ → стационарное распределение Скорость сходимости определяется |λ₂| - вторым наибольшим собственным значением. Чем меньше |λ₂|, тем быстрее PageRank сходится.

**Вот где диагонализация спасает**: power iteration для реального PageRank требует ~50-100 итераций на матрице 10⁹ × 10⁹. Знание спектра (λ₂ < 0.85 по дизайну Google) гарантирует сходимость. Анализ спектра = понимание, зачем вообще что-то считать.

Спектральное разложение симметричных матриц: PCA и Gram matrix

Спектральное разложение симметричных матриц: PCA и Gram matrix

Симметричные матрицы (A = Aᵀ) обладают особым свойством: их собственные векторы всегда ортогональны, а собственные значения - вещественны. Это основа **спектрального разложения** - частного случая диагонализации, где P - ортогональная матрица (P⁻¹ = Pᵀ).

Для симметричной A = Aᵀ: A = Q · Λ · Qᵀ где: Q - ортогональная матрица (столбцы - ортонормированные собственные векторы) Λ = diag(λ₁, ..., λₙ) - вещественные собственные значения Qᵀ = Q⁻¹ (бесплатное обращение!) ПРЕИМУЩЕСТВА перед общей диагонализацией: - λᵢ вещественны всегда (можно сортировать по убыванию) - Q ортогональна: обращение = транспонирование - Геометрически: чистое растяжение/сжатие вдоль ортогональных осей ПРИМЕР - Gram matrix (XᵀX) симметрична и позитивно полуопределена: Xᵀ·X = Q · Λ · Qᵀ Все λᵢ >= 0

**Почему `np.linalg.eigh` вместо `eig`**: `eigh` знает, что матрица симметрична, использует алгоритм Якоби/Ланцоша - в 10-100 раз быстрее и численно точнее. Всегда возвращает вещественные значения. В ML-коде на симметричных матрицах всегда использовать `eigh`.

Когда диагонализация невозможна

Когда диагонализация невозможна

Не каждая матрица диагонализуема. Условие - наличие n линейно независимых собственных векторов.

**Jordan-блок [[1,1],[0,1]]** - канонический пример недиагонализуемой матрицы. У неё λ=1 кратности 2, но только один собственный вектор (1,0). Для неё строится Jordan-форма - ближайший аналог диагонализации. В ML-практике такие матрицы встречаются редко.

Диагонализация в проде

Диагонализация в проде

Диагонализация в индустрии

Где спектральные методы работают прямо сейчас

Практика: диагонализация для динамики популяций

Практика: диагонализация для динамики популяций

Вопросы для собеседования

Что унести из урока

• **A = PDP⁻¹**: P - матрица собственных векторов, D - диагональная с λᵢ
• **Aⁿ = PDⁿP⁻¹**: степень матрицы = степени чисел на диагонали - отсюда PageRank и Марков
• **Симметричная A**: всегда диагонализуема, разложение A = QΛQᵀ с ортогональной Q
• **PCA** = спектральное разложение ковариационной матрицы; λᵢ - объяснённая дисперсия
• **Недиагонализуема**: кратные λ с дефицитом собственных векторов (Jordan-блоки); в ML редко
• **Практически**: `np.linalg.eigh` для симметричных, `eig` для общих - выбор влияет на скорость и точность

Связи

Диагонализация - мост между алгеброй и индустрией

• Собственные векторы — Основа диагонализации: без них разложение невозможно
• SVD — Обобщение диагонализации на прямоугольные матрицы - самый мощный инструмент ML
• PCA — Прямое приложение спектрального разложения к задаче снижения размерности
• Определитель — det(A) = λ₁·λ₂·...·λₙ - произведение собственных значений

Связанные уроки

• stat-14-pca
• ml-19-pca