Лекция
Привет, Вы узнаете о том , что такое qr-алгоритм, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое qr-алгоритм, qr алгоритм , настоятельно рекомендую прочитать все из категории Численные методы.
qr-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В. Н. Кублановской и Дж. Фрэнсисом (англ.)русск..
Алгоритму QR предшествовал алгоритм LR , основанный на разложении LU . Алгоритм QR по сравнению с ним более стабилен, поэтому он вытеснил его, и LR сегодня мало используется. Однако это был первый шаг к современным методам QR.
Алгоритм LR был разработан в начале 1950-х годов Хайнцем Рутисхауэром , который работал ассистентом Эдуарда Штифеля в Федеральной политехнической школе в Цюрихе . Штифель Rutishauer предположил , что используется последовательность моментов и 0 Т А К х 0 , K = 0, 1, ... (где х 0 и и 0 произвольные векторы) , чтобы найти собственные значения A . Рутишауэр использовал алгоритм Александра Эйткена для этой задачи и развил его в алгоритм фактор-разности (фактор-разностный алгоритм ), из которого происходит термин алгоритм qd .
После формулировки его подходящим с вычислительной точки зрения способом, он обнаружил, что алгоритм на самом деле представляет собой итерацию A k = L k U k ( LU-разложение ), A k +1 = U k L k , примененную к трехдиагональной матрице, из которой алгоритм выводит LR
Пусть A — вещественная матрица, для которой мы хотим найти собственные числа и векторы. Положим A0=A. На k-м шаге (начиная с k = 0) вычислим QR-разложение Ak=QkRk, где Qk — ортогональная матрица (то есть QkT = Qk−1), а Rk — верхняя треугольная матрица. Затем мы определяем Ak+1 = RkQk.
Заметим, что
то есть все матрицы Ak являются подобными, то есть их собственные значения равны.
Пусть все диагональные миноры матрицы A не вырождены. Тогда последовательность матриц Ak при сходится по форме к клеточному правому треугольному виду, соответствующему клеткам с одинаковыми по модулю собственными значениями.
Для того, чтобы получить собственные векторы матрицы, нужно перемножить все матрицы Qk.
Алгоритм считается вычислительно устойчивым, т. к. производится ортогональными преобразованиями подобия.
Будем считать, что собственные числа положительно-определенной матрицы A упорядочены по убыванию:
Пусть
а S — матрица, составленная из собственных векторов матрицы A. Тогда, матрица A может быть записана в виде спектрального разложения
Найдем выражение для степеней исходной матрицы через матрицы Qk и Rk. С одной стороны, по определению QR-алгоритма:
Применяя это соотношение рекурсивно, получим:
Введя следующие обозначения:
получим
С другой стороны:
Приравнивая правые части последних двух формул, получим:
Предположим, что существует LU-разложение матрицы ST:
тогда
Умножим справа на обратную к U матрицу, а затем — на обратную к Λk:
Можно показать, что
При без ограничения общности можно считать, что на диагонали матрицы L стоят единицы, поэтому
Обозначим
причем матрица Pk является верхнетреугольной, как произведение верхнетреугольных и диагональных матриц.
Таким образом, мы доказали, что
.
Из единственности QR-разложения следует, что если произведение ортогональной и треугольной матрицы сходится к ортогональной матрице, то треугольная матрица сходится к единичной матрице. Из сказанного следует, что
То есть матрицы Sk сходятся к матрице собственных векторов матрицы A.
Так как
то
Переходя к пределу, получим:
Итак, мы доказали, что QR-алгоритм позволяет решить полную проблему собственных значений для симметричной положительно-определенной матрицы.
При определенных условиях последовательность матриц сходится к треугольной матрице, разложению Шура матрицы . Об этом говорит сайт https://intellect.icu . В этом случае собственные числа треугольной матрицы располагаются на ее диагонали, и задача нахождения собственных чисел считается решенной. В тестах на сходимость не практично требовать точных нулей в нулевой части матрицы, но можно воспользоваться теоремой Гершгорина о кругах[en], задающей пределы ошибок.
В исходном состоянии матрицы (без дополнительных преобразований) стоимость итераций относительно высока. Стоимость алгоритма можно уменьшить, сначала приведя матрицу к форме верхней матрицы Хессенберга (стоимость получения которой методом, основанном на преобразовании Хаусхолдера, оценивается как арифметических операций), и затем используя конечную последовательность ортогональных преобразований подобия. Данный алгоритм чем-то похож на двухсторонюю QR-декомпозицию. (В обычной QR-декомпозиции матрица отражений Хаусхолдера умножается на исходную только слева, тогда как в случае использования формы Хессенберга матрица отражений умножается на исходную и слева, и справа.) Нахождение QR-декомпозиции верхней матрицы Хессенберга оценивается как арифметических операций. Из-за того, что форма матрицы Хессенберга почти верхнетреугольная (у нее только один поддиагональный элемент не равен нулю), удается сразу снизить число итераций требуемых для схождения QR-алгоритма.
В случае, если исходная матрица симметричная, верхняя матрица Хессенберга также симметричная и поэтому является трехдиагональной. Этим же свойством обладает вся последовательность матриц . В этом случае стоимость процедуры оценивается как арифметических операций с использованием метода, основанного на преобразовании Хаусхолдера. Нахождение QR-разложения симметричной трехдиагональной матрицы оценивается как операций.
Скорость сходимости зависит от степени разделения собственных чисел, и в практической реализации в явном или неявном виде используюся «сдвиги» для усиления разделения собственных чисел и для ускорения сходимости. В типичном виде для симметричных матриц QR-алгоритм точно находит одно собственное число (уменьшая размерность матрицы) за одну или две итерации, что делает этот подход как эффективным, так и надежным.
В современной вычислительной практике QR-алгоритм реализуется с использованием его неявной версии, что упрощает добавление множественных «сдвигов». Исходно матрица приводится к форме верхней матрицы Хессенберга , так же как и в явной версии. Затем, на каждом шаге первая колонка преобразуется через малоразмерное преобразование подобия Хаусхолдера к первой колонке (или ), где — это полином степени , который определяет стратегию «сдвигов» (обычно , где и — это два собственных числа остаточной подматрицы размера 2×2, это так называемый неявный двойной сдвиг). Затем последовательные преобразования Хаусхолдера размерности производятся с целью вернуть рабочую матрицу к форме верхней матрицы Хессенберга.
Пусть будет избранный. Тогда процедуру можно кратко назвать QR-разложением. с последующим умножением указывается в обратном порядке. Данная процедура является прямым обобщением метода одновременной потенции для определения первойСобственные значения матрицы. Эта связь получена из итерации подпространства . Метод одновременной обратной мощности также выполняется косвенно.
Пусть будет набор. Это означает, что в качестве альтернативы метод также может использоваться как QR-разложение. с последующим умножением вместе с поправкой на сдвиг быть представленным. Обычно попытка делается с помощью Shift.чтобы аппроксимировать наименьшее собственное значение. Последний диагональный элемент может это сделатьчтобы проголосовать. Простая итерация QR является результатом установки всех сдвигов на ноль.
Владеет Форма Хессенберга, так что надо как произведение матрицы с вторичными диагоналями и матрицы без вторичных диагоналей также имеют вид Хессенберга То же самое относится и к. Итак, при подготовке алгоритма QR в приведенный к форме Хессенберга, это сохраняется в течение всего алгоритма.
Симметричная вещественная матрица имеет только действительные собственные значения. Во всех них сохраняется симметрия во время работы QR-алгоритма.получить. Для симметричных матриц Уилкинсон (1965) предположил, что собственное значение нижнего правого- подматрица
чем выбрать shift, тем ближе к ложь. Уилкинсон показал, что определенная таким образом матричная последовательность сходится к диагональной матрице, диагональные элементы которой имеют собственные значения находятся. Скорость сходимости квадратичная.
Пара простых сдвигов может быть объединена за один шаг итерации. Как следствие, это означает, что для реальных матриц можно обойтись без сложных сдвигов. В приведенных выше обозначениях
QR-разложение для квадратичного многочлена , оценивается в . Коэффициенты этого многочлена действительны даже для сопряженной пары комплексных сдвигов. Таким образом, комплексные собственные значения реальных матриц также могут быть аппроксимированы без использования комплексных чисел в вычислениях.
Обычный выбор для этого двойного сдвига состоит из собственных значений в правом нижнем углу. -Подматрица, д. ЧАС. квадратичный многочлен является характеристикой этого блока,
.
Становится числом больше но намного меньше размера матрица набор. Полином можно рассматривать как характеристический многочлен правой нижней квадратичной -Подматрица текущей матрицы чтобы проголосовать. Другая стратегия - использовать Собственные значения в правом нижнем углу -Подматрица подлежит определению и наименьшие собственные значения выберите ниже. С их помощью QR-разложение
а также
безусловно.
При многократном переключении часто достигается, что компоненты левого нижнего -Блоки в последовательности повторяемых матриц особенно быстро становятся маленькими, и, таким образом, достигается расщепление проблемы собственных значений.
Совмещение нескольких смен в общей форме занимает очень много времени. Как упоминалось выше, усилия могут быть уменьшены за счет того, что на подготовительном этапе впроизводится форма Гессенберга. Поскольку каждый шаг с несколькими сменами может состоять из отдельных (даже сложных) смен, форма Хессенберга сохраняется на протяжении всего алгоритма.
Это позволяет преобразовать алгоритм QR в алгоритм «погони за выпуклостью» , который создает вмятину в форме Гессенберга на верхнем конце диагонали, а затем «преследует» ее по диагонали и выходит из матрицы на нижнем конце. .
Получаем состоящий из произведений, , так что пусть эти блоки диагональной формы .
Исследование, описанное в статье про qr-алгоритм, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое qr-алгоритм, qr алгоритм и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Численные методы
Комментарии
Оставить комментарий
Численные методы
Термины: Численные методы