Нахождение собственных чисел и собственных векторов: Собственные числа матрицы онлайн

Нахождение собственных чисел и собственных векторов матриц

        Теорема 19.1   Собственными числами матрицы являются корни уравнения

и только они.

        Доказательство.     Пусть столбец  — собственный вектор матрицы с собственным числом . Тогда, по определению, . Это равенство можно переписать в виде . Так как для единичной матрицы выполнено , то . По свойству матричного умножения и предыдущее равенство принимает вид

Допустим, что определитель матрицы отличен от нуля, . Тогда у этой матрицы существует обратная . Из равенства (19.4) получим, что , что противоречит определению собственного вектора. Значит, предположение, что , неверно, то есть все собственные числа должны являться корнями уравнения .

Пусть  — корень уравнения . Тогда базисный минор матрицы не может совпадать с определителем матрицы и поэтому ,  — порядок матрицы . Уравнение (19.4) является матричной записью однородной системы линейных уравнений с неизвестными , являющимися элементами матрицы-столбца . По  теореме 15.3 число решений в фундаментальной системе решений равно , что больше нуля. Таким образом, система (19.4) имеет хотя бы одно ненулевое решение, то есть числу соответствует хотя бы один собственный вектор матрицы .     

Определитель является многочленом степени от переменного , так как при вычислении определителя никаких арифметических действий кроме сложения, вычитания и умножения выполнять не приходится.

        Определение 19.5   Матрица называется характеристической матрицей матрицы , многочлен называется характеристическим многочленом матрицы , уравнение называется характеристическим уравнением матрицы .         

        Пример 19. 10   Найдите собственные числа и собственные векторы матрицы

Решение. Составляем характеристическую матрицу :

Находим характеристический многочлен

Решим характеристическое уравнение

Подбором находим, что один корень уравнения равен . Есть теорема, которая говорит, что если число является корнем многочлена , то многочлен делится на разность , то есть , где  — многочлен. В соответствии с этой теоремой многочлен должен делиться на . Выделим в характеристическом многочлене этот множитель :

Находим корни трехчлена . Они равны и 3. Таким образом,

 — корень кратности 2 17.7 b,  — простой корень. Итак, собственные числа матрицы равны , . Найдем соответствующие им собственные векторы.

Пусть , тогда для собственного вектора получаем матричное уравнение

что соответствует системе уравнений

Решаем ее методом Гаусса (раздел «Алгоритм нахождения решений произвольной системы линейных уравнений (метод Гаусса)»). Выписываем расширенную матрицу системы

Первую строку, умноженную на числа и прибавляем соответственно ко второй и третьей строкам

Меняем местами вторую и третью строки

Возвращаемся к системе уравнений

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

Полагаем , находим , . Итак, собственному числу соответствует собственный вектор .

Пусть , тогда для собственного вектора получаем матричное уравнение

что соответствует системе уравнений

Решаем ее методом Гаусса. Выписываем расширенную матрицу

Первую строку умножаем на числа 2 и 3 и прибавляем соответственно ко второй и третьей строкам

Вторую строку умножаем на и прибавляем к третьей

Возвращаемся к системе уравнений

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

Полагаем , находим , . Итак, собственному числу соответствует собственный вектор . Чтобы избавиться от дроби, умножим собственный вектор на 2, получим собственный вектор с тем же самым собственным числом. В итоге собственному числу соответствует собственный вектор .

Ответ: Собственные числа: , , соответствующие собственные векторы: , .         

Вычислительные методы для инженеров

Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров: Учеб. пособие. — М.: Высш. шк., 1994. — 544 с. В книге рассматриваются вычислительные методы, наиболее часто используемые в практике инженерных и научно-технических расчетов: методы решения задач линейной алгебры и нелинейных уравнений, проблема собственных значений, методы теории приближения функций, численное дифференцирование и интегрирование, поиск экстремумов функций, решение обыкновенных дифференциальных уравнений. Значительное внимание уделяется особенностям реализации вычислительных алгоритмов на ЭВМ и оценке достоверности полученных результатов. Имеется большое количество примеров и геометрических иллюстраций. Для студентов и аспирантов технических вузов, а также для инженеров и научных работников, применяющих вычислительные методы. Оглавление ПРЕДИСЛОВИЕ Глава 1. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И РЕШЕНИЕ ИНЖЕНЕРНЫХ ЗАДАЧ С ПРИМЕНЕНИЕМ ЭВМ § 1.2. Основные этапы решения инженерной задачи с применением ЭВМ § 1.3. Вычислительный эксперимент § 1.4. Дополнительные замечания Глава 2. ВВЕДЕНИЕ В ЭЛЕМЕНТАРНУЮ ТЕОРИЮ ПОГРЕШНОСТЕЙ § 2.1. Источники и классификация погрешностей результата численного решения задачи § 2.2. Приближенные числа. Абсолютная и относительная погрешности 2. Правила записи приближенных чисел. 3. Округление. § 2.3. Погрешности арифметических операций над приближенными числами § 2. 4. Погрешность функции § 2.5. Особенности машинной арифметики 2. Представление целых чисел. 3. Представление вещественных чисел. 4. Арифметические операции над числами с плавающей точкой. 5. Удвоенная точность. 6. Вычисление машинного эпсилон. § 2.6. Дополнительные замечания Глава 3. ВЫЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, МЕТОДЫ И АЛГОРИТМЫ. ОСНОВНЫЕ ПОНЯТИЯ § 3.2. Обусловленность вычислительной задачи 2. Примеры плохо обусловленных задач. 3. Обусловленность задачи вычисления значения функции одной переменной. 4. Обусловленность задачи вычисления интеграла … 5. Обусловленность задачи вычисления суммы ряда. § 3.3. Вычислительные методы § 3.4. Корректность вычислительных алгоритмов § 3.5. Чувствительность вычислительных алгоритмов к ошибкам округления § 3.6. Различные подходы к анализу ошибок § 3.7. Требования, предъявляемые к вычислительным алгоритмам § 3.8. Дополнительные замечания Глава 4. МЕТОДЫ ОТЫСКАНИЯ РЕШЕНИЙ НЕЛИНЕЙНЫХ УРАВНЕНИЙ § 4. 2. Обусловленность задачи вычисления корня § 4.3. Метод бисекции § 4.4. Метод простой итерации § 4.5. Обусловленность метода простой итерации § 4.6. Метод Ньютона § 4.7. Модификации метода Ньютона § 4.8. Дополнительные замечания Глава 5. ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ § 5.2. Нормы вектора и матрицы § 5.3. Типы используемых матриц § 5.4. Обусловленность задачи решения системы линейных алгебраических уравнений § 5.5 Метод Гаусса § 5.6. Метод Гаусса и решение систем уравнений с несколькими правыми частями, обращение матриц, вычисление определителей § 5.7. Метод Гаусса и разложение матрицы на множители. LU-разложение § 5.8. Метод Холецкого (метод квадратных корней) § 5.9. Метод прогонки § 5.10. QR-разложение матрицы. Методы вращений и отражений § 5.11. Итерационное уточнение § 5.12. Дополнительные замечания Глава 6. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ § 6. 1. Метод простой итерации § 6.2. Метод Зейделя § 6.3. Метод релаксации § 6.4. Дополнительные замечания Глава 7. МЕТОДЫ ОТЫСКАНИЯ РЕШЕНИЙ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ § 7.2. Метод простой итерации § 7.3. Метод Ньютона для решения систем нелинейных уравнений 7.4. Модификации метода Ньютона § 7.5. О некоторых подходах к решению задач локализации и отыскания решений систем нелинейных уравнений § 7.6. Дополнительные замечания Глава 8. МЕТОДЫ РЕШЕНИЯ ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ § 8.2. Степенной метод § 8.3. Метод обратных итераций § 8.4. QR-алгоритм § 8.5. Дополнительные замечания Глава 9. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ § 9.2. Обусловленность задачи минимизации § 9.3. Методы прямого поиска. Оптимальный пассивный поиск. Метод деления отрезка пополам. Методы Фибоначчи и золотого сечения § 9.4. Метод Ньютона и другие методы минимизация гладких функций § 9.5. Дополнительные замечания Глава 10. МЕТОДЫ МНОГОМЕРНОЙ МИНИМИЗАЦИИ § 10. 1. Задача безусловной минимизации функции многих переменных § 10.2. Понятие о методах спуска. Покоординатный спуск § 10.3. Градиентный метод § 10.4. Метод Ньютона § 10.5. Метод сопряженных градиентов § 10.6. Метода минимизации без вычисления производных § 10.7. Дополнительные замечания Глава 11. ПРИБЛИЖЕНИЕ ФУНКЦИЙ И СМЕЖНЫЕ ВОПРОСЫ § 11.2. Интерполяция обобщенными многочленами § 11.3. Полиномиальная интерполяция. Многочлен Лагранжа § 11.4. Погрешность интерполяции § 11.5. Интерполяция с кратными узлами § 11.6. Минимизация оценки погрешности интерполяции. Многочлены Чебышева § 11.7. Конечные разности § 11.8. Разделенные разности § 11.9. Интерполяционный многочлен Ньютона. Схема Эйткена § 11.10. Обсуждение глобальной полиномиальной интерполяции. Понятие о кусочно-полиномиальной интерполяции § 11.11. Интерполяция сплайнами § 11.12. Понятие о дискретном преобразовании Фурье и тригонометрической интерполяции § 11.13. Метод наименьших квадратов § 11.14. Равномерное приближение функций § 11.15. Дробно-рациональные аппроксимации и вычисление элементарных функций § 11.16. Дополнительные замечания Глава 12. ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ § 12.1. Простейшие формулы численного дифференцирования § 12.2. О выводе формул численного дифференцирования § 12.3. Обусловленность формул численного дифференцирования § 12.4. Дополнительные замечания Глава 13. ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ 13.2. Квадратурные формулы интерполяционного типа § 13.3. Квадратурные формулы Гаусса § 13.4. Апостериорные оценки погрешности. Понятие об адаптивных процедурах численного интегрирования § 13.5. Вычисление интегралов в нерегулярных случаях § 13.6. Дополнительные замечания Глава 14. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ § 14.1. Задача Коши для дифференциального уравнения первого порядка § 14.2. Численные методы решения задачи Коши. Основные понятия и определения § 14. 3. Использование формулы Тейлора § 14.4. Метод Эйлера § 14.5. Модификации метода Эйлера второго порядка точности § 14.6. Методы Рунге-Кутты § 14.7. Линейные многошаговые методы. Методы Адамса § 14.8. Устойчивость численных методов решения задачи Коши § 14.9. Неявный метод Эйлера § 14.10. Решение задачи Коши для систем обыкновенных дифференциальных уравнений и дифференциальных уравнений m-го порядка § 14.11. Жесткие задачи § 14.12. Дополнительные замечания Глава 15. РЕШЕНИЕ ДВУХТОЧЕЧНЫХ КРАЕВЫХ ЗАДАЧ § 15.1. Краевые задачи для одномерного стационарного уравнения теплопроводности § 15.2. Метод конечных разностей: основные понятия § 15.3. Метод конечных разностей: аппроксимации специального вида § 15.4. Понятие о проекционных и проекционно-разностных методах. Методы Ритца и Гадеркина. Метод конечных элементов § 15.5. Метод пристрелки § 15.6. Дополнительные замечания

Собственные значения, собственные векторы и PCA | На пути к науке о данных

Что они говорят нам о наших данных?

Я узнал о собственных значениях и собственных векторах в университете на курсе линейной алгебры. Это было очень сухо и математически, так что я не понял, о чем идет речь. Но я хочу представить вам эту тему более интуитивным образом, и я буду использовать множество анимаций, чтобы проиллюстрировать ее.

Сначала мы рассмотрим, как применить матрицу к вектору вращает и масштабирует вектор. Это покажет нам, что такое собственных значений и собственных векторов . Затем мы узнаем о основных компонентах и о том, что они являются собственными векторами ковариационной матрицы . Эти знания помогут нам понять нашу последнюю тему, анализ основных компонентов .

Чтобы понять собственные значения и собственные векторы, мы должны сначала взглянуть на умножение матриц.

Рассмотрим следующую матрицу.

Когда мы берем скалярное произведение матрицы и вектора, результирующий вектор представляет собой версию исходного вектора, повернутую на и масштабированную на на .

 импортировать numpy как np 
 C = np. cov(X, rowvar = False) 

 import numpy as np 
 eigenvalues,eigenvectors = np.linalg.eig(C) 

 print(iris_df.head()) 

 print(iris_transformed[:5,:]) 

 import numpy as np 
 eigenvalues,eigenvectors = np.linalg.eig(M) 

Где I — это единичная матрица, которая имеет единицы по диагонали и нули в других местах. Он имеет ту же форму, что и 9.0009 А .

И единственный способ, чтобы это уравнение было верным.

Это верно только тогда, когда определитель матрицы ( A -𝜆⋅ I ) становится равным 0.

Определитель матрицы — это коэффициент, на который матрица масштабирует площадь в случае матрицы 2×2 и объем в случае матрицы 3×3. Если определитель равен нулю, то матрица ( A -𝜆⋅ I ) сжимает точек в начало координат (начало — нулевая точка). Это единственный способ для ненулевого вектора стать нулевым вектором.

Итак, мы ищем все собственные значения 𝜆, которые составляют определитель 0.

После того, как мы нашли собственные значения, мы можем решить это уравнение:

И мы находим собственные векторы.

Ковариационная матрица

Матрица дисперсии-ковариации может быть оценена на основе данных по следующей формуле:

Как компьютер вычисляет собственные значения?

Две наиболее важные с практической точки зрения задачи вычислительной математики — это решение систем линейных уравнений и вычисление собственных значений и собственных векторов матрицы. Мы уже обсуждали метод решения линейных уравнений в «Глубоком погружении в то, как R соответствует линейной модели», поэтому я подумал, что в этом посте мы должны завершить круг обсуждением методов, вычисляющих собственные значения и собственные векторы.

Читатель, знакомый со стандартным учебным планом по линейной алгебре, может задаться вопросом, почему этот вопрос вообще интересен, ведь все, что нужно сделать, — это вычислить характеристическое уравнение матрицы, а затем вычислить ее корни. Хотя это метод из учебника, это плохой метод для численных вычислений, потому что

• Вычисление характеристического уравнения матрицы включает в себя символическое вычисление определителя, что требует больших затрат, и его следует по возможности избегать.
• Вычисление корней полиномиального уравнения также является трудной задачей. Несмотря на то, что методы, подобные методу Ньютона, существуют, наборы начальных точек, которые сходятся к каждому отдельному корню, чрезвычайно сложны, поэтому выбрать набор начальных точек так, чтобы были найдены все 90 324 всех 90 325 корней, очень сложно. На самом деле, популярные методы нахождения корней многочленов тесно связаны с алгоритмами нахождения собственных значений, обсуждаемыми ниже.

Стандартный алгоритм вычисления собственных значений называется -алгоритмом. Как читатель может догадаться, это связано с -факторизацией рассматриваемой матрицы (напомню, -факторизация кодирует процесс Грама-Шмидта для ортонормирования базиса).

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

Следующий шаг — тайна, мы умножаем множители в обратном порядке

Это довольно странная вещь. Не существует непосредственной геометрической или интуитивной интерпретации умножения двух матриц в обратном порядке.

Алгоритм затем повторяет этот факторно-обратный процесс

… и так далее. Этот процесс в конце концов приводит нас (в пределе) к верхней треугольной матрице (хотя совершенно не очевидно, почему это так), а диагональные элементы в этом пределе являются собственными значениями матрицы .

В этом эссе мы надеемся демистифицировать этот процесс и дать читателю некоторое представление об этом важном алгоритме.

Программное обеспечение

Я впервые узнал об -алгоритме, когда писал эту библиотеку C, которая реализует многие стандартные алгоритмы численной линейной алгебры. В этом посте я буду предоставлять код Python, реализующий различные алгоритмы; надеюсь, это будет более доступно для многих читателей.

Чтобы помочь с многочисленными массивами numpy, которые необходимо было набрать как матрицы в латексе, я написал этот небольшой пакет Python: np2latex. Пусть это каким-то образом облегчит скуку читателя, как и мою.

Благодарности

Толчком к записи этого материала был вопрос моего студента Майкла Кэмпбелла.

Примечания Грега Фассхауэра здесь и здесь были очень полезны, как и исходная статья Джона Фрэнсиса: The QR Transformation, I.

Настройка

будем считать, что не имеет повторяющихся собственных значений и нулевых собственных значений ¹ . Это наиболее полезный случай на практике (например, при нахождении главных компонентов набора данных). Из этого предположения вытекает несколько важных следствий, на которые мы отметим:

1. Все симметричные матрицы (с действительными числами) имеют полный набор собственных значений и собственных векторов.
2. Все собственные значения являются действительными числами.
3. Собственные векторы, соответствующие разным собственным значениям, ортогональны (собственные векторы с разными собственными значениями всегда линейно независимы, симметрия матрицы покупает нам ортогональность).

В качестве рабочего примера возьмем матрицу

Эта матрица была построена как произведение , где

— ортогональная матрица, а

Отсюда сразу следует, что она симметрична (что также можно проверить путем проверки) и что она имеет собственные значения , и . Связанные собственные векторы являются столбцами ² .

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

Power Iteration

Основная идея, лежащая в основе алгоритмов нахождения собственных значений, называется итерацией мощности , и она проста.

Начните с любого вектора и постоянно умножайте на

Предположим на данный момент, что этот процесс сходится к некоторому вектору (это почти наверняка не сходится, но мы скоро это исправим). Назовите предельный вектор . Тогда должно удовлетворяться ³

Итак, собственный вектор с соответствующим собственным значением .

Теперь мы видим, почему этот процесс не может всегда сходиться: должно иметь собственное значение . Чтобы все исправить, давайте нормализуем вектор произведения после каждого этапа алгоритма

С помощью этого простого добавления нетрудно показать, что процесс всегда сходится к некоторому вектору. Теперь вместо того, чтобы предельный вектор оставался инвариантным при умножении на , он должен оставаться инвариантным при умножении на с последующей нормализацией на . То есть должно быть пропорционально .

Таким образом, сходящийся вектор является собственным вектором , на этот раз с неизвестным собственным значением.

 def power_iteration (A, tol = 0,0001):
    v = np.random.normal (размер = A.shape [1])
    v = v / np.linalg.norm(v)
    предыдущий = np.empty (форма = A.shape [1])
    пока верно:
        предыдущий [:] = v
        v = А@v
        v = v / np.linalg.norm(v)
        если np.allclose(v, предыдущий, atol=tol):
            перерыв
    вернуться v 

Применяя степенную итерацию к матрице нашего примера, мы можем наблюдать сходимость вектора итерации к собственному вектору

Собственный вектор равен

Собственное значение, соответствующее этому собственному вектору, которое оказывается наибольшим собственным значением матрицы. В целом это верно: почти для всех начальных векторов степенная итерация сходится к собственному вектору , соответствующему наибольшему собственному значению матрицы ⁴ .

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

К счастью, есть простой способ охарактеризовать исходные векторы, которые являются исключительными, то есть те, которые , а не сходятся к наибольшему собственному вектору.

Сходимость с ортогональным вектором

Вспомните из нашей предыдущей установки, что собственные векторы симметричной матрицы всегда ортогональны друг другу. Это означает, что если мы возьмем любой вектор, ортогональный наибольшему собственному вектору , то он все равно будет ортогонален .

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

Те же рассуждения, что и раньше (но применительно к ограничению на ортогональное дополнение к ) подразумевают, что эта итерация ортогональной мощности должна сходиться к нечто , и это нечто должно быть другим собственным вектором! В этом случае мы почти всегда оказываемся на 90 324, втором по величине 90 325 собственном векторе .

Теперь очевидно, что мы можем продолжить этот процесс, сосредоточив внимание на меньшем ортогональном подпространстве собственных векторов, которые мы уже нашли, и применить степенную итерацию для вычисления следующего собственного вектора. Таким образом, мы в конечном итоге найдем всю последовательность собственных векторов : .

Так что в принципе проблема решена! Тем не менее, на практике это обычно не делается, есть еще некоторые интересные усовершенствования базового алгоритма, которые мы должны обсудить.

Одновременная ортогонализация

В нашем предыдущем обсуждении степенной итерации нам нужно было перезапускать алгоритм после нахождения каждого собственного вектора. Если нам нужен полный набор собственных векторов матрицы, нам нужно запустить последовательность итераций полной мощности (размерность матрицы ) раз.

Причина, по которой мы не могли просто одновременно запускать степенные итерации, засеянные базисом векторов, заключается в том, что мы были более или менее гарантированы, что все они сойдутся к одному и тому же вектору (с наибольшим собственным значением). Если мы хотим найти все собственные векторы сразу, нам нужно предотвратить это.

Предположим, что мы корректируем базис на каждой итерации, ортогонализируя его . То есть, на каждом шаге мы вставляем операцию

Если нам повезет, это предотвратит сходимость всех отдельных степенных итераций в одно и то же место. Вместо этого они (надеюсь) сойдутся к ортогональному базису. Это действительно так, и получившийся алгоритм называется одновременной ортогонализации .

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

Начать с . Затем выполните следующие действия:

… и так далее. Сгенерированная таким образом последовательность ортогональных матриц сходится, и пределом является матрица собственных векторов .

В коде

 def одновременной_ортогонализации (A, tol = 0,0001):
    Q, R = np. linalg.qr(A)
    предыдущий = np.empty (форма = Q.shape)
    для i в диапазоне (100):
        предыдущий [:] = Q
        Х = А@Q
        Q, R = np.linalg.qr(X)
        если np.allclose(Q, предыдущий, atol=tol):
            перерыв
    вернуть вопрос 

Если мы применим этот алгоритм к нашей примерной матрице , последовательность сгенерированных матриц будет

Мы видим, что, по крайней мере, с точностью до знака, алгоритм одновременной ортогонализации воспроизводит матрицу собственных векторов , как предполагалось.

Математическое свойство одновременной ортогонализации

Нам понадобится интересное свойство итераций алгоритма одновременной ортогонализации для дальнейшего использования, так что давайте отвлечемся на мгновение, чтобы обсудить его.

Шаги алгоритма одновременной ортогонализации можно перегруппировать, чтобы изолировать верхние треугольные матрицы

Если мы перемножим получившиеся последовательности вместе, мы получим, например,

Используя ортогональность результатов ‘s в

Легко видеть, что это относится к любому этапу расчета; поэтому мы получаем тождества

или, переформулировав

Теперь, поскольку мы предположили, что у него нет нулевых собственных значений, оно обратимо. -факторизации обратимых матриц уникальны ⁵ . Это означает, что мы можем интерпретировать приведенное выше тождество как выражение уникальной -факторизации степеней

QR-алгоритма

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

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

Эта процедура сходится к диагональной матрице ⁶ , а диагональные элементы являются собственными значениями .

Мы находимся в запутанной ситуации с обозначениями, так как теперь у нас есть два разных алгоритма, использующих последовательность ортогональных и верхнетреугольных матриц. Чтобы отличить, украсим последовательность, возникающую из -алгоритма, тильдами

В коде

 по умолчанию qr_algorithm(A, tol=0,0001):
    Q, R = np. linalg.qr(A)
    предыдущий = np.empty (форма = Q.shape)
    для я в диапазоне (500):
        предыдущий [:] = Q
        Х = R@Q
        Q, R = np.linalg.qr(X)
        если np.allclose(X, np.triu(X), atol=tol):
            перерыв
    return Q 

Визуализация итераций -алгоритма обнаруживает интересную закономерность.

В то время как итерации алгоритма одновременной ортогонализации сходятся к базе собственных векторов , итерации -алгоритма, кажется, сходятся к единичной матрице ⁷ .

Это предполагает, что итерации могут сообщать корректировки чему-то, и что продукт

может быть важен.

Давайте посмотрим, сможем ли мы понять, что происходит, вычислив эти продукты

Это наилучшая возможная ситуация! Произведения матриц сходятся к базе собственных векторов.

Это здорово, но все еще очень загадочно, что именно здесь происходит. Чтобы немного прояснить это, мы теперь обратимся к раскрытию связи между алгоритмом одновременной ортогонализации и -алгоритмом.

Связь между QR и алгоритмами одновременной ортогонализации

Напомним наше тождество, связывающее итерации одновременной ортогонализации со степенями

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

Алгоритм начинается с разложения на множители

Это означает, что, например,

Теперь в каждом произведении находятся именно те матрицы, которые факторизуются в вторая итерация алгоритма, так что

Мы можем применить этот трюк еще раз, это в точности матрица, разложенная на третью итерацию алгоритма, так что

Итак, у нас есть две конкурирующие факторизации в ортогональную матрицу и верхнетреугольная матрица

Учитывая, что -факторизации обратимых матриц единственны, мы заключаем отношения

и

Это объясняет наше наблюдение, сделанное ранее: мы уже знаем, что , поэтому мы сразу же можем заключить и это.

Произведения RQ

Осталось подвести итог: ранее мы утверждали, что произведения в алгоритме сходятся к диагональной матрице, а диагональные элементы являются собственными значениями , почему это так?

Давайте сначала продемонстрируем, что это так, в нашем рабочем примере.

Чтобы понять, почему это так, начнем с того факта, что при достаточно большом матрица произведения является матрицей собственных векторов. Обозначая диагональную матрицу ассоциированных собственных значений, это означает, что ⁸

Немного перетасовать вещи

Но, так что

Итак, все вместе

Что объясняет конвергенцию продуктов.

Выводы

Алгоритм, представленный в этом посте, еще не готов к работе, есть различные приемы, которые можно использовать, чтобы сделать его более численно стабильным и быстрее сходиться. Мы оставим исследование этих идей пользователю.

Собственные значения и собственные векторы матриц, несомненно, являются одним из наиболее важных математических понятий, когда-либо открытых. Они снова и снова встречаются в анализе, топологии, геометрии, статистике, физике и, вероятно, в любом предмете, который каким-либо нетривиальным образом использует математику. Приятно знать хотя бы немного о том, как их практически можно вычислить, хотя бы для того, чтобы воздать должное их невероятной полезности.

1. Случай с нулевыми собственными значениями несложно обработать, так как мы можем просто ограничить действие ортогональным дополнением нулевого пространства, где оно имеет все ненулевые собственные значения. Случай повторных собственных значений более сложен, и мы оставляем его читателю для дальнейшего изучения, если это интересно. ↩

2. Это легко увидеть при осмотре: . ↩

3. Принимая пределы уравнения . ↩

4. Самый большой по абсолютной величине. ↩

5. Доказательство см. в статье Фрэнсиса. ↩

6. В общем случае, когда собственные значения могут повторяться, эти матрицы сходятся к верхней треугольной матрице, форме Шура матрицы A.

   No related posts.