Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

QR-алгоритм для отыскания всех собственных чисел и векторов матрицы описание и блок-схема кратко

Лекция



Привет, Вы узнаете о том , что такое 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

qr алгоритм

Пусть A — вещественная матрица, для которой мы хотим найти собственные числа и векторы. Положим A0=A. На k-м шаге (начиная с k = 0) вычислим QR-разложение Ak=QkRk, где Qk — ортогональная матрица (то есть QkT = Qk−1), а Rk — верхняя треугольная матрица. Затем мы определяем Ak+1 = RkQk.

Заметим, что

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

то есть все матрицы Ak являются подобными, то есть их собственные значения равны.

Пусть все диагональные миноры матрицы A не вырождены. Тогда последовательность матриц Ak при QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема сходится по форме к клеточному правому треугольному виду, соответствующему клеткам с одинаковыми по модулю собственными значениями.

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

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

Доказательство для симметричной положительно определенной матрицы

Будем считать, что собственные числа положительно-определенной матрицы A упорядочены по убыванию:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Пусть

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

а S — матрица, составленная из собственных векторов матрицы A. Тогда, матрица A может быть записана в виде спектрального разложения

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Найдем выражение для степеней исходной матрицы через матрицы Qk и Rk. С одной стороны, по определению QR-алгоритма:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Применяя это соотношение рекурсивно, получим:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Введя следующие обозначения:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

получим

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

С другой стороны:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Приравнивая правые части последних двух формул, получим:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Предположим, что существует LU-разложение матрицы ST:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

тогда

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Умножим справа на обратную к U матрицу, а затем — на обратную к Λk:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Можно показать, что

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

При QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема без ограничения общности можно считать, что на диагонали матрицы L стоят единицы, поэтому

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Обозначим

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

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

Таким образом, мы доказали, что

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема.

Из единственности QR-разложения следует, что если произведение ортогональной и треугольной матрицы сходится к ортогональной матрице, то треугольная матрица сходится к единичной матрице. Из сказанного следует, что

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

То есть матрицы Sk сходятся к матрице собственных векторов матрицы A.

Так как

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

то

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Переходя к пределу, получим:

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

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

Реализация QR-алгоритма

При определенных условиях последовательность матриц QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема сходится к треугольной матрице, разложению Шура матрицы QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема. Об этом говорит сайт https://intellect.icu . В этом случае собственные числа треугольной матрицы располагаются на ее диагонали, и задача нахождения собственных чисел считается решенной. В тестах на сходимость не практично требовать точных нулей в нулевой части матрицы, но можно воспользоваться теоремой Гершгорина о кругах[en], задающей пределы ошибок.

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

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

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

Реализация QR-алгоритма в неявном виде

В современной вычислительной практике QR-алгоритм реализуется с использованием его неявной версии, что упрощает добавление множественных «сдвигов». Исходно матрица приводится к форме верхней матрицы Хессенберга QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема, так же как и в явной версии. Затем, на каждом шаге первая колонка QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема преобразуется через малоразмерное преобразование подобия Хаусхолдера к первой колонке QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема (или QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема), где QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема — это полином степени QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема, который определяет стратегию «сдвигов» (обычно QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема, где QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема и QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема — это два собственных числа остаточной подматрицы QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема размера 2×2, это так называемый неявный двойной сдвиг). Затем последовательные преобразования Хаусхолдера размерности QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема производятся с целью вернуть рабочую матрицу QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема к форме верхней матрицы Хессенберга.

Варианты QR-алгоритма

Простая итерация QR

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

QR-алгоритм с простыми сдвигами

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

Владеет QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема Форма Хессенберга, так что надо QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схемакак произведение матрицы с вторичными диагоналями и матрицы без вторичных диагоналей также имеют вид Хессенберга То же самое относится и кQR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема. Итак, при подготовке алгоритма QR вQR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема приведенный к форме Хессенберга, это сохраняется в течение всего алгоритма.

Простые сдвиги для симметричных матриц

Симметричная вещественная матрица QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схемаимеет только действительные собственные значения. Во всех них сохраняется симметрия во время работы QR-алгоритма.QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схемаполучить. Для симметричных матриц Уилкинсон (1965) предположил, что собственное значение нижнего правогоQR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема- подматрица

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

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

QR-алгоритм с двойным сдвигом

Пара простых сдвигов может быть объединена за один шаг итерации. Как следствие, это означает, что для реальных матриц можно обойтись без сложных сдвигов. В приведенных выше обозначениях

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

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

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

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема.

QR-алгоритм с несколькими изменениями

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

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема а также QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

безусловно.

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

Неявная итерация с несколькими изменениями

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

Это позволяет преобразовать алгоритм QR в алгоритм «погони за выпуклостью» , который создает вмятину в форме Гессенберга на верхнем конце диагонали, а затем «преследует» ее по диагонали и выходит из матрицы на нижнем конце. .

  1. для QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема делать
  2. Вычислить многочлен QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема по одному из указанных вариантов,
  3. Найдите вектор QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема.
  4. Определите отражение QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схемак первому единичному вектору. Там вQR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема только первый QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема Компоненты не исчезают, это отражение имеет простую форму блока.
  5. Сформируйте матрицу QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема и преобразовать их так, чтобы QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема вернулся в форму Хессенберга.
  6. конец для

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

Блок-схема алгоритма LC-QR

QR-алгоритм для отыскания всех собственных чисел и  векторов матрицы описание и блок-схема

Вау!! 😲 Ты еще не читал? Это зря!

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

создано: 2021-06-18
обновлено: 2024-11-14
28



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Поделиться:

Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей

Комментарии


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

Численные методы

Термины: Численные методы