QR-алгоритм: различия между версиями
| [досмотренная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) (Новая страница: «{{level-m}}») |
Frolov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{level-m}} | {{level-m}} | ||
| + | |||
| + | ---- | ||
| + | |||
| + | Задача нахождения собственных значений и собственных векторов для матрицы <math>A</math> заключается в поиске таких соответствующих друг другу чисел <math>\lambda</math> и ''ненулевых'' векторов <math>x</math>, которые удовлетворяют уравнению: | ||
| + | |||
| + | <math style="vertical-align:0%">Ax=\lambda x</math>, при этом, числа <math>\lambda</math> называются собственными значениями, а вектора <math>x</math> - собственными векторами<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. | ||
| + | |||
| + | Данная задача является одной из самых сложных задач линейной алгебры<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>. Собственные вектора и собственные значения применяются в различных областях науки: в аналитической геометрии, при решении систем интегральных уравнений, в математической физике. Однако не существует прямых методов вычисления собственных значений для матриц общего вида, поэтому данная задача на практике решается численными итерационными методами. Одним из них является QR-алгоритм. | ||
| + | |||
| + | == Общее описание метода == | ||
| + | |||
| + | ---- | ||
| + | |||
| + | QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел матрицы. При этом алгоритм позволяет найти и собственные вектора матрицы. Он был разработан в конце 1950-х годов независимо В. Н. Кублановской(Россия) и Дж. Фрэнсисом(Англия). Открытию QR-алгоритма предшествовал LR-алгоритм, который использовал LU-разложение вместо QR-разложения. В настоящее время LR-алгоритм используется очень редко ввиду своей меньшей эффективности, однако он был важным шагом на пути к открытию QR-алгоритма<ref>[https://en.wikipedia.org/wiki/QR_algorithm Wikipedia: QR-algorithm]</ref>. | ||
| + | |||
| + | Суть базового 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> и поиска собственных значений для нее, что является тривиальной задачей. | ||
| + | |||
| + | Однако базовый QR-алгоритм может обладать очень низкой скоростью сходимости, поэтому существует несколько способов ускорить его: | ||
| + | * Перед итерациями привести матрицу <math>A</math> к подобной ей матрице <math>A_H</math>, которая будет иметь форму Хессенберга. Данный шаг позволит ускорить процесс QR-разложения. | ||
| + | * Использовать QR-алгоритм со сдвигами. Это позволит уменьшить количество итераций алгоритма. | ||
| + | В дальнейшем, в данной статье под модифицированным алгоритмом будет пониматься алгоритм, использующий сдвиги и матрицу с формой Хессенберга. Под базовым алгоритмом будет пониматься алгоритм, не использующий данные приемы. | ||
| + | |||
| + | == Литература == | ||
| + | <references /> | ||
Версия 15:47, 20 апреля 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-х годов независимо В. Н. Кублановской(Россия) и Дж. Фрэнсисом(Англия). Открытию QR-алгоритма предшествовал LR-алгоритм, который использовал LU-разложение вместо QR-разложения. В настоящее время LR-алгоритм используется очень редко ввиду своей меньшей эффективности, однако он был важным шагом на пути к открытию QR-алгоритма[3].
Суть базового 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] и поиска собственных значений для нее, что является тривиальной задачей.
Однако базовый QR-алгоритм может обладать очень низкой скоростью сходимости, поэтому существует несколько способов ускорить его:
- Перед итерациями привести матрицу [math]A[/math] к подобной ей матрице [math]A_H[/math], которая будет иметь форму Хессенберга. Данный шаг позволит ускорить процесс QR-разложения.
- Использовать QR-алгоритм со сдвигами. Это позволит уменьшить количество итераций алгоритма.
В дальнейшем, в данной статье под модифицированным алгоритмом будет пониматься алгоритм, использующий сдвиги и матрицу с формой Хессенберга. Под базовым алгоритмом будет пониматься алгоритм, не использующий данные приемы.
2 Литература
- ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
- ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
- ↑ Wikipedia: QR-algorithm
