QR-алгоритм
QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В. Н. Кублановской и Дж. Фрэнсисом.
Пусть A — вещественная матрица, для которой мы хотим найти собственные числа и векторы. Положим A0=A. На k-ом шаге (начиная с k = 0) вычислим QR-разложение Ak=QkRk, где Qk — ортогональная матрица (то есть QkT = Qk−1), а Rk — верхняя треугольная матрица. Затем мы определяем Ak+1 = RkQk.
Заметим, что
- <math> A_{k+1} = R_k Q_k = Q_k^{-1} Q_k R_k Q_k = Q_k^{-1} A_k Q_k = Q_k^{T} A_k Q_k, </math>
то есть все матрицы Ak являются подобными, то есть их собственные значения равны.
Пусть все диагональные миноры матрицы A не вырождены. Тогда последовательность матриц Ak при k→∞ сходится по форме к клеточному правому треугольному виду, соответствующему клеткам с одинаковыми по модулю собственными значениями. [1]
Для того, чтобы получить собственные векторы матрицы, нужно перемножить все матрицы Qk.
Доказательство для симметричной положительно определённой матрицы
Будем считать, что собственные числа положительно-определённой матрицы A упорядочены по убыванию:
- <math> \lambda_1 > \lambda_2 > ... > \lambda_n > 0. </math>
Пусть
- <math> \Lambda=\mathrm{diag}\left(\lambda_{1},...,\lambda_{n}\right),</math>
а S — матрица, составленная из собственных векторов матрицы A. Тогда, матрица A может быть записана в виде спектрального разложения
- <math>A=S\Lambda S^{T}. </math>
Найдём выражение для степеней исходной матрицы через матрицы Qk и Rk. С одной стороны, по определению QR-алгоритма:
- <math> A^{k}=A_{1}^{k}=\left(Q_{1}R_{1}\right)^{k}=Q_{1}\left(R_{1}Q_{1}\right)^{k-1}R_{1}=Q_{1}A_{2}^{k-1}R_{1}. </math>
Применяя это соотношение рекурсивно, получим:
- <math> A^{k}=Q_{1}\cdot...\cdot Q_{k}\cdot R_{k}\cdot...\cdot R_{1} </math>
Введя следующие обозначения:
- <math> S_{k}=Q_{1}\cdot...\cdot Q_{k}, </math>
- <math> T_{k}=R_{k}\cdot...\cdot R_{1}, </math>
получим
- <math> A^{k}=S_{k}T_{k}. </math>
С другой стороны:
- <math> A^{k}=S\Lambda^{k}S^{T}. </math>
Приравнивая правые части последних двух формул, получим:
- <math>S\Lambda^{k}S^{T}=S_{k}T_{k}.</math>
Предположим, что существует LU-разложение матрицы ST:
- <math>S^{T}=LU,</math>
тогда
- <math>S\Lambda^{k}LU=S_{k}T_{k}.</math>
Умножим справа на обратную к U матрицу, а затем — на обратную к Λk:
- <math>S\Lambda^{k}L=S_{k}T_{k}U^{-1},</math>
- <math>S\Lambda^{k}L\Lambda^{-k}=S_{k}T_{k}U^{-1}\Lambda^{-k}.</math>
Можно показать, что
- <math>\Lambda^{k}L\Lambda^{-k}\to \mathrm{diag}\left(l_{11},...,l_{nn}\right)=L^{\prime}</math>
при <math> k \to \infty,</math> без ограничения общности можно считать, что на диагонали матрицы L стоят единицы, поэтому
- <math> S_{k}T_{k}U^{-1}\Lambda^{-k}\to S. </math>
Обозначим
- <math>P_{k}=T_{k}U^{-1}\Lambda^{-k},</math>
причём матрица Pk является верхнетреугольной, как произведение верхнетреугольных и диагональных матриц.
Таким образом, мы доказали, что
- <math>S_{k}P_{k}\to S</math>.
Можно показать, что если произведение ортогональной и треугольной матрицы сходятся к некоторой матрице, то треугольная матрица сходится к единичной матрице. Из сказанного следует, что
- <math>S_{k}=Q_{1}\cdot...\cdot Q_{k}\to S.</math>
То есть матрицы Sk сходятся к матрице собственных векторов матрицы A.
Так как
- <math> A_{k+1}=Q_{k}^{T}A_{k}Q_{k}=...=\left(Q_{k}^{T}\cdot...\cdot Q_{1}^{T}\right)A_{1}\left(Q_{1}\cdot...\cdot Q_{k}\right)=\left(Q_{1}\cdot...\cdot Q_{k}\right)^{T}A\left(Q_{1}\cdot...\cdot Q_{k}\right),</math>
то
- <math> A_{k+1}=S_{k}^T A S_{k}.</math>
Переходя к пределу, получим:
- <math> \lim_{k\to\infty} A_{k}=\lim_{k\to\infty} A_{k+1} = S^T A S = S^T S \Lambda S^T S = \Lambda. </math>
Итак, мы доказали, что QR-алгоритм позволяет решить полную проблему собственных значений для симметричной положительно-определённой матрицы.
Напишите отзыв о статье "QR-алгоритм"
Примечания
- ↑ Численные методы / Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. — 3-е изд. — М: БИНОМ, Лаборатория знаний, 2004. — С. 321. — 636 с. — ISBN 5-94774-175-X.
Ссылки
- [www.math.umn.edu/~olver/aims_/qr.pdf Заметки Питера Олвера о ортогональных базисах и QR-алгоритме (англ.)]
|
||||||||||||||||||||||||||||||||||||||
Отрывок, характеризующий QR-алгоритм
– Мама, Болконский приехал! – сказала она. – Мама, это ужасно, это несносно! – Я не хочу… мучиться! Что же мне делать?…Еще графиня не успела ответить ей, как князь Андрей с тревожным и серьезным лицом вошел в гостиную. Как только он увидал Наташу, лицо его просияло. Он поцеловал руку графини и Наташи и сел подле дивана.
– Давно уже мы не имели удовольствия… – начала было графиня, но князь Андрей перебил ее, отвечая на ее вопрос и очевидно торопясь сказать то, что ему было нужно.
– Я не был у вас всё это время, потому что был у отца: мне нужно было переговорить с ним о весьма важном деле. Я вчера ночью только вернулся, – сказал он, взглянув на Наташу. – Мне нужно переговорить с вами, графиня, – прибавил он после минутного молчания.
Графиня, тяжело вздохнув, опустила глаза.
– Я к вашим услугам, – проговорила она.
Наташа знала, что ей надо уйти, но она не могла этого сделать: что то сжимало ей горло, и она неучтиво, прямо, открытыми глазами смотрела на князя Андрея.
«Сейчас? Сию минуту!… Нет, это не может быть!» думала она.
Он опять взглянул на нее, и этот взгляд убедил ее в том, что она не ошиблась. – Да, сейчас, сию минуту решалась ее судьба.
– Поди, Наташа, я позову тебя, – сказала графиня шопотом.
Наташа испуганными, умоляющими глазами взглянула на князя Андрея и на мать, и вышла.
– Я приехал, графиня, просить руки вашей дочери, – сказал князь Андрей. Лицо графини вспыхнуло, но она ничего не сказала.
– Ваше предложение… – степенно начала графиня. – Он молчал, глядя ей в глаза. – Ваше предложение… (она сконфузилась) нам приятно, и… я принимаю ваше предложение, я рада. И муж мой… я надеюсь… но от нее самой будет зависеть…
– Я скажу ей тогда, когда буду иметь ваше согласие… даете ли вы мне его? – сказал князь Андрей.
– Да, – сказала графиня и протянула ему руку и с смешанным чувством отчужденности и нежности прижалась губами к его лбу, когда он наклонился над ее рукой. Она желала любить его, как сына; но чувствовала, что он был чужой и страшный для нее человек. – Я уверена, что мой муж будет согласен, – сказала графиня, – но ваш батюшка…
– Мой отец, которому я сообщил свои планы, непременным условием согласия положил то, чтобы свадьба была не раньше года. И это то я хотел сообщить вам, – сказал князь Андрей.
– Правда, что Наташа еще молода, но так долго.
– Это не могло быть иначе, – со вздохом сказал князь Андрей.
– Я пошлю вам ее, – сказала графиня и вышла из комнаты.
– Господи, помилуй нас, – твердила она, отыскивая дочь. Соня сказала, что Наташа в спальне. Наташа сидела на своей кровати, бледная, с сухими глазами, смотрела на образа и, быстро крестясь, шептала что то. Увидав мать, она вскочила и бросилась к ней.
– Что? Мама?… Что?
– Поди, поди к нему. Он просит твоей руки, – сказала графиня холодно, как показалось Наташе… – Поди… поди, – проговорила мать с грустью и укоризной вслед убегавшей дочери, и тяжело вздохнула.
Наташа не помнила, как она вошла в гостиную. Войдя в дверь и увидав его, она остановилась. «Неужели этот чужой человек сделался теперь всё для меня?» спросила она себя и мгновенно ответила: «Да, всё: он один теперь дороже для меня всего на свете». Князь Андрей подошел к ней, опустив глаза.
– Я полюбил вас с той минуты, как увидал вас. Могу ли я надеяться?
Он взглянул на нее, и серьезная страстность выражения ее лица поразила его. Лицо ее говорило: «Зачем спрашивать? Зачем сомневаться в том, чего нельзя не знать? Зачем говорить, когда нельзя словами выразить того, что чувствуешь».
Она приблизилась к нему и остановилась. Он взял ее руку и поцеловал.
– Любите ли вы меня?
– Да, да, – как будто с досадой проговорила Наташа, громко вздохнула, другой раз, чаще и чаще, и зарыдала.
– Об чем? Что с вами?
– Ах, я так счастлива, – отвечала она, улыбнулась сквозь слезы, нагнулась ближе к нему, подумала секунду, как будто спрашивая себя, можно ли это, и поцеловала его.
Князь Андрей держал ее руки, смотрел ей в глаза, и не находил в своей душе прежней любви к ней. В душе его вдруг повернулось что то: не было прежней поэтической и таинственной прелести желания, а была жалость к ее женской и детской слабости, был страх перед ее преданностью и доверчивостью, тяжелое и вместе радостное сознание долга, навеки связавшего его с нею. Настоящее чувство, хотя и не было так светло и поэтично как прежнее, было серьезнее и сильнее.
