QR-алгоритм: различия между версиями
| [досмотренная версия] | [досмотренная версия] |
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) м |
||
| Строка 17: | Строка 17: | ||
Пусть <math>A_0 = A</math> — исходная матрица. | Пусть <math>A_0 = A</math> — исходная матрица. | ||
| − | Для <math>k = 1, 2, \ldots</math> выполняется QR-разложение: | + | Для <math>k = 0, 1, 2, \ldots</math> выполняется QR-разложение: |
| − | * <math>A_{k | + | * <math>A_{k} = Q_kR_k</math>, где <math>Q_k</math> — унитарная (''ортогональная'') матрица, <math>R_k</math> — верхняя треугольная матрица, и затем найденные матрицы перемножаются в обратном порядке: |
| − | * <math> | + | * <math>A_{k+1} = R_kQ_k</math>. |
| − | Поскольку <math> | + | Поскольку <math>A_{k+1} = R_kQ_k = Q_k^{*}A_{k}Q_k</math>, то матрицы <math>A_{k+1}</math> и <math>A_k</math> унитарно подобны для любого <math>k</math>. Поэтому матрицы <math>A_1, A_2, \ldots</math> унитарно подобны исходной матрице <math>A</math> и имеют те же собственные значения. |
В специальной литературе по численным методам приводится доказательство<ref name="VOLA" /> сходимости получающихся матриц к клеточной правой треугольной матрице с диагональными клетками, размеры которых зависят от размеров канонических ящиков Жордана исходной матрицы. Таким образом, проблема собственных значений матрицы сводится к проблемам собственных значений матриц меньшего размера. QR-алгоритм в узком смысле и есть эта процедура. Однако обычно к нему относят не только её, но и весь комплекс приёмов ускорения этого итерационного метода. | В специальной литературе по численным методам приводится доказательство<ref name="VOLA" /> сходимости получающихся матриц к клеточной правой треугольной матрице с диагональными клетками, размеры которых зависят от размеров канонических ящиков Жордана исходной матрицы. Таким образом, проблема собственных значений матрицы сводится к проблемам собственных значений матриц меньшего размера. QR-алгоритм в узком смысле и есть эта процедура. Однако обычно к нему относят не только её, но и весь комплекс приёмов ускорения этого итерационного метода. | ||
| Строка 31: | Строка 31: | ||
==== Использование хессенберговой формы матрицы ==== | ==== Использование хессенберговой формы матрицы ==== | ||
| − | Хессенбергова (почти треугольная) форма матрицы интересна в приложении к QR-алгоритму тем, что в случае, если <math>A_0 = A</math> имеет эту форму, то имеют её и все матрицы <math>A_k</math>. Если теперь посмотреть на методы [[QR-разложения плотных неособенных матриц]], то видно, что выполнение разложения <math> | + | Хессенбергова (почти треугольная) форма матрицы интересна в приложении к QR-алгоритму тем, что в случае, если <math>A_0 = A</math> имеет эту форму, то имеют её и все матрицы <math>A_k</math>. Если теперь посмотреть на методы [[QR-разложения плотных неособенных матриц]], то видно, что выполнение разложения <math>A_k = Q_kR_k</math> в случае плотной неособенной <math>A_k</math>требует (в последовательном варианте) <math>O(n^3)</math> операций, как и последующий процесс вычисления <math>A_{k+1} = R_kQ_k</math>. В случае же, если матрицы хессенберговы, то как [[Методы QR-разложения плотных хессенберговых матриц|QR-разложения плотных хессенберговых матриц]], так и вычисления <math>A_{k+1} = R_kQ_k</math> потребуют уже по <math>O(n^2)</math> операций. Это позволяет экономить если не время (критические пути графа алгоритма линейны для лучших методов QR-разложения и для плотной матрицы, и для хессенберговой), то довольно большие вычислительные ресурсы. |
Поэтому естественным приёмом ускорения итераций QR-алгоритма является начальное [[Подобные разложения на унитарные и хессенберговы матрицы|унитарно подобное приведение матрицы к хессенбергову виду]]. После этого все процедуры QR-алгоритма следует проводить уже с матрицами хессенберговой формы. | Поэтому естественным приёмом ускорения итераций QR-алгоритма является начальное [[Подобные разложения на унитарные и хессенберговы матрицы|унитарно подобное приведение матрицы к хессенбергову виду]]. После этого все процедуры QR-алгоритма следует проводить уже с матрицами хессенберговой формы. | ||
| Строка 37: | Строка 37: | ||
==== Сдвиги QR-алгоритма ==== | ==== Сдвиги QR-алгоритма ==== | ||
| + | QR-алгоритм со сдвигами позволяет сократить количество итераций, необходимых для сходимости<ref name="bahvalov">Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. "Численный методы"— 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.</ref>. Пусть у нас есть матрица <math>A_k</math>, тогда процесс перехода к матрице <math>A_{k+1}</math> выглядит следующим образом: | ||
| + | * На каждом шаге подбирается число <math>\nu_k</math> и ищется следующее QR-разложение: <math>A_k-\nu_kE=Q_kR_k</math>. | ||
| + | * Вычисляется матрица <math>A_{k+1}</math>: <math>A_{k+1} = R_kQ_k+\nu_kE</math>. | ||
| + | |||
| + | При этом сохраняется свойство подобия матриц <math>A_k</math> и <math>A_{k+1}</math>: | ||
| + | |||
| + | <math>A_{k+1} = R_kQ_k+\nu_kE=Q_{k}^{T}Q_kR_kQ_k+\nu_kE=Q_{k}^{T}(A_k-\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-Q_{k}^{T}(\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-\nu_kE+\nu_kE=Q_{k}^{T}A_kQ_k</math>. | ||
| + | |||
| + | Подбор параметра <math>\nu_k</math> осуществляется в зависимости от элементов матрицы <math>A_k</math>. При удачном алгоритме подбора параметров среднее количество итераций получается порядка 5 на одно собственное значение<ref name="VOLA" />. | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия 12:14, 18 мая 2017
Задача нахождения собственных значений и собственных векторов для матрицы [math]A[/math] заключается в поиске таких соответствующих друг другу чисел [math]\lambda[/math] и ненулевых векторов [math]x[/math], которые удовлетворяют уравнению [math]Ax=\lambda x[/math], при этом числа [math]\lambda[/math] называются собственными значениями, а вектора [math]x[/math] - собственными векторами[1].
Данная задача является одной из самых сложных задач линейной алгебры[2]. Собственные вектора и собственные значения применяются в различных областях науки: в аналитической геометрии, при решении систем интегральных уравнений, в математической физике. Однако не существует прямых методов вычисления собственных значений для матриц общего вида, поэтому данная задача на практике решается численными итерационными методами. Одним из них является QR-алгоритм.
Содержание
1 Общее описание метода
QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел матрицы. При этом алгоритм позволяет найти и собственные вектора матрицы. Он был разработан в конце 1950-х годов независимо В. Н. Кублановской(Россия)[3] и Дж. Фрэнсисом(Англия)[4]. Открытию QR-алгоритма предшествовал LR-алгоритм, который использовал LU-разложение вместо QR-разложения. В настоящее время LR-алгоритм используется очень редко ввиду своей меньшей эффективности, однако он был важным шагом на пути к открытию QR-алгоритма[5].
Суть базового QR-алгоритма заключается в итерационном приведении матрицы [math]A[/math] к некоторой унитарно подобной ей матрице [math]A_N[/math] при помощи QR-разложения. Матрица [math]A_N[/math] является правой верхней треугольной матрицей, а значит ее диагональ содержит собственные значения. В силу подобия матриц [math]A[/math] и [math]A_N[/math] их наборы собственных значений совпадают. Таким образом задача поиска собственных значений матрицы [math]A[/math] сводится к задаче выведения матрицы [math]A_N[/math] и поиска собственных значений для нее, что является тривиальной задачей.
2 Математическое описание
Известно, что произвольная квадратная матрица может быть представлена в виде произведения унитарной (в вещественном случае ортогональной) и верхней треугольной матриц. Такое разложение называется QR-разложением.
Пусть [math]A_0 = A[/math] — исходная матрица. Для [math]k = 0, 1, 2, \ldots[/math] выполняется QR-разложение:
- [math]A_{k} = Q_kR_k[/math], где [math]Q_k[/math] — унитарная (ортогональная) матрица, [math]R_k[/math] — верхняя треугольная матрица, и затем найденные матрицы перемножаются в обратном порядке:
- [math]A_{k+1} = R_kQ_k[/math].
Поскольку [math]A_{k+1} = R_kQ_k = Q_k^{*}A_{k}Q_k[/math], то матрицы [math]A_{k+1}[/math] и [math]A_k[/math] унитарно подобны для любого [math]k[/math]. Поэтому матрицы [math]A_1, A_2, \ldots[/math] унитарно подобны исходной матрице [math]A[/math] и имеют те же собственные значения.
В специальной литературе по численным методам приводится доказательство[2] сходимости получающихся матриц к клеточной правой треугольной матрице с диагональными клетками, размеры которых зависят от размеров канонических ящиков Жордана исходной матрицы. Таким образом, проблема собственных значений матрицы сводится к проблемам собственных значений матриц меньшего размера. QR-алгоритм в узком смысле и есть эта процедура. Однако обычно к нему относят не только её, но и весь комплекс приёмов ускорения этого итерационного метода.
2.1 Ускорение сходимости QR-алгоритма
Применение приёмов ускорения даёт QR-алгоритму существенные преимущества перед альтернативными методами решения проблемы собственных значений. Приёмы делятся по своей сути на две группы - приёмы ускорения одной итерации алгоритма и приёмы ускорения сходимости итерационного процесса, то есть уменьшения числа итераций.
2.1.1 Использование хессенберговой формы матрицы
Хессенбергова (почти треугольная) форма матрицы интересна в приложении к QR-алгоритму тем, что в случае, если [math]A_0 = A[/math] имеет эту форму, то имеют её и все матрицы [math]A_k[/math]. Если теперь посмотреть на методы QR-разложения плотных неособенных матриц, то видно, что выполнение разложения [math]A_k = Q_kR_k[/math] в случае плотной неособенной [math]A_k[/math]требует (в последовательном варианте) [math]O(n^3)[/math] операций, как и последующий процесс вычисления [math]A_{k+1} = R_kQ_k[/math]. В случае же, если матрицы хессенберговы, то как QR-разложения плотных хессенберговых матриц, так и вычисления [math]A_{k+1} = R_kQ_k[/math] потребуют уже по [math]O(n^2)[/math] операций. Это позволяет экономить если не время (критические пути графа алгоритма линейны для лучших методов QR-разложения и для плотной матрицы, и для хессенберговой), то довольно большие вычислительные ресурсы.
Поэтому естественным приёмом ускорения итераций QR-алгоритма является начальное унитарно подобное приведение матрицы к хессенбергову виду. После этого все процедуры QR-алгоритма следует проводить уже с матрицами хессенберговой формы.
2.1.2 Сдвиги QR-алгоритма
QR-алгоритм со сдвигами позволяет сократить количество итераций, необходимых для сходимости[6]. Пусть у нас есть матрица [math]A_k[/math], тогда процесс перехода к матрице [math]A_{k+1}[/math] выглядит следующим образом:
- На каждом шаге подбирается число [math]\nu_k[/math] и ищется следующее QR-разложение: [math]A_k-\nu_kE=Q_kR_k[/math].
- Вычисляется матрица [math]A_{k+1}[/math]: [math]A_{k+1} = R_kQ_k+\nu_kE[/math].
При этом сохраняется свойство подобия матриц [math]A_k[/math] и [math]A_{k+1}[/math]:
[math]A_{k+1} = R_kQ_k+\nu_kE=Q_{k}^{T}Q_kR_kQ_k+\nu_kE=Q_{k}^{T}(A_k-\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-Q_{k}^{T}(\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-\nu_kE+\nu_kE=Q_{k}^{T}A_kQ_k[/math].
Подбор параметра [math]\nu_k[/math] осуществляется в зависимости от элементов матрицы [math]A_k[/math]. При удачном алгоритме подбора параметров среднее количество итераций получается порядка 5 на одно собственное значение[2].
3 Литература
- ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
- ↑ 2,0 2,1 2,2 Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
- ↑ Кублановская В.Н. О некоторых алгоритмах для решения полной проблемы собственных значений // Ж. вычисл. матем. и матем. физ. 1961. Т. 1. № 4. С. 555–570
- ↑ J.G.F. Francis, "The QR Transformation, I", The Computer Journal, 1961, vol. 4, no. 3, pp. 265-271
- ↑ Wikipedia: QR-algorithm
- ↑ Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. "Численный методы"— 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
