QR-алгоритм - История изменений

AntonChupin в 08:55, 7 апреля 2021

2021-04-07T08:55:16Z

← Предыдущая версия		Версия от 08:55, 7 апреля 2021
Строка 102:		Строка 102:

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
			[[Категория:Алгоритмы для матриц]]

	[[en:QR algorithm]]		[[en:QR algorithm]]

ASA в 12:49, 14 марта 2018

2018-03-14T12:49:32Z

← Предыдущая версия		Версия от 12:49, 14 марта 2018
Строка 100:		Строка 100:
	== Литература ==		== Литература ==
	<references />		<references />

			[[Категория:Статьи в работе]]

			[[en:QR algorithm]]

Frolov в 12:12, 27 февраля 2018

2018-02-27T12:12:27Z

← Предыдущая версия		Версия от 12:12, 27 февраля 2018
Строка 54:		Строка 54:
	Хессенбергова (почти треугольная) форма матрицы интересна в приложении к 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-алгоритму тем, что в случае, если <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-алгоритма следует проводить уже с матрицами хессенберговой формы.

	В случае, если исходная матрица эрмитова (в вещественном случае - симметричная), то унитарно подобное приведение к хессенберговому виду становится [[Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной\|приведением к трёхдиагональному симметричному виду]]. В этом случае QR-алгоритм становится ещё		В случае, если исходная матрица эрмитова (в вещественном случае - симметричная), то унитарно подобное приведение к хессенберговому виду становится [[Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной\|приведением к трёхдиагональному симметричному виду]]. В этом случае QR-алгоритм становится ещё

Frolov в 12:11, 27 февраля 2018

2018-02-27T12:11:07Z

← Предыдущая версия		Версия от 12:11, 27 февраля 2018
Строка 56:		Строка 56:
	Поэтому естественным приёмом ускорения итераций QR-алгоритма является начальное [[Подобные разложения на унитарные и хессенберговы матрицы\|унитарно подобное приведение матрицы к хессенбергову виду]]. После этого все процедуры QR-алгоритма следует проводить уже с матрицами хессенберговой формы.		Поэтому естественным приёмом ускорения итераций QR-алгоритма является начальное [[Подобные разложения на унитарные и хессенберговы матрицы\|унитарно подобное приведение матрицы к хессенбергову виду]]. После этого все процедуры QR-алгоритма следует проводить уже с матрицами хессенберговой формы.

	В случае, если исходная матрица эрмитова (в вещественном случае - симметричная), то унитарно подобное приведение к хессенберговому виду становится [[~~Симметричные разложения на унитарные и трёхдиагональные матрицы~~\|приведением к трёхдиагональному симметричному виду]]. В этом случае QR-алгоритм становится ещё		В случае, если исходная матрица эрмитова (в вещественном случае - симметричная), то унитарно подобное приведение к хессенберговому виду становится [[Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной\|приведением к трёхдиагональному симметричному виду]]. В этом случае QR-алгоритм становится ещё
	быстрее, благодаря существенно большему количеству нулей в структурах образующихся матриц..		быстрее, благодаря существенно большему количеству нулей в структурах образующихся матриц..

Frolov: /* Метод для симметричных и эрмитовых матриц */

2017-12-09T12:45:52Z

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

← Предыдущая версия		Версия от 12:45, 9 декабря 2017
Строка 94:		Строка 94:

	В случае симметрии (для вещественных матриц) или эрмитовости (для комплексных) применяемый для решения проблемы собственных значений QR-алгоритм использует особенности как самой задачи (собственные числа таких матриц вещественны), так и получаемых промежуточных результатов (хессенберговы матрицы оказываются трёхдиагональными симметричными), что сокращает расчёты.		В случае симметрии (для вещественных матриц) или эрмитовости (для комплексных) применяемый для решения проблемы собственных значений QR-алгоритм использует особенности как самой задачи (собственные числа таких матриц вещественны), так и получаемых промежуточных результатов (хессенберговы матрицы оказываются трёхдиагональными симметричными), что сокращает расчёты.
	[[QR-алгоритм для симметричных матриц, используемый в SCALAPACK]] для решения проблемы собственных значений у симметричных матриц в настоящее время использует ~~тот~~ подход к выбору сдвигов, ~~который не подтверждён теоретически~~, ~~но имеет лучшие практические показатели. Это выполнение процедуры "двойного сдвига" с величинами~~, ~~равными собственным значениям последней диагональной клетки размера 2х2 у всех диагональных блоков~~, ~~размер которых больше 2~~.		[[QR-алгоритм для симметричных матриц, используемый в SCALAPACK]] для решения проблемы собственных значений у симметричных матриц в настоящее время использует подход к выбору сдвигов, разработанный в начале 90-х гг. XX века<ref>G. HENRY, Improving Data Re-Use in Eigenvalue-Related Computations, PhD thesis, Cornell University, Ithaca, NY, January 1994</ref>.

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

Frolov: /* Метод для матриц общего вида */

2017-12-09T12:41:47Z

Метод для матриц общего вида

← Предыдущая версия		Версия от 12:41, 9 декабря 2017
Строка 88:		Строка 88:
	=== Метод для матриц общего вида ===		=== Метод для матриц общего вида ===

	[[QR-алгоритм, используемый в SCALAPACK]] для решения проблемы собственных значений у матриц общего вида в настоящее время использует тот подход к выбору сдвигов, который не подтверждён теоретически, но ~~имеет~~ лучшие практические показатели. Это выполнение процедуры "двойного сдвига" с величинами, равными собственным значениям последней диагональной клетки размера 2х2 у всех диагональных блоков, больших размером.		[[QR-алгоритм, используемый в SCALAPACK]] для решения проблемы собственных значений у матриц общего вида в настоящее время использует тот подход к выбору сдвигов, который не подтверждён теоретически, но имел лучшие практические показатели на момент создания библиотеки LAPACK. Это выполнение процедуры "двойного сдвига" с величинами, равными собственным значениям последней диагональной клетки размера 2х2 у всех диагональных блоков, больших размером.
	Поскольку существуют матрицы, для которых этот выбор сдвигов не даёт сходимости, то после 10й ~~QR-~~итерации при отсутствии уменьшения поддиагональных элементов выполняется некий "особый" сдвиг.		Поскольку существуют матрицы, для которых этот выбор сдвигов не даёт сходимости, то после 10й итерации при отсутствии уменьшения поддиагональных элементов выполняется некий "особый" сдвиг.

	=== Метод для симметричных и эрмитовых матриц ===		=== Метод для симметричных и эрмитовых матриц ===

Frolov: /* Обнуление поддиагональных элементов (дефляция) */

2017-12-07T16:31:29Z

Обнуление поддиагональных элементов (дефляция)

← Предыдущая версия		Версия от 16:31, 7 декабря 2017
Строка 80:		Строка 80:
	=== Обнуление поддиагональных элементов (дефляция) ===		=== Обнуление поддиагональных элементов (дефляция) ===

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

	== QR-алгоритм в различных вариантах ==		== QR-алгоритм в различных вариантах ==

Frolov: /* Ускорение сходимости QR-алгоритма */

2017-12-07T15:55:58Z

Ускорение сходимости QR-алгоритма

← Предыдущая версия		Версия от 15:55, 7 декабря 2017
Строка 72:		Строка 72:
	Подбор параметра <math>\nu_k</math> осуществляется в зависимости от элементов матрицы <math>A_k</math>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса'', среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычным сдвигом не получилось сходимости, применяют так называемые "особые сдвиги". Для симметрического же случая используется стратегия Уилкинсона<ref name = "Dem" />.		Подбор параметра <math>\nu_k</math> осуществляется в зависимости от элементов матрицы <math>A_k</math>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса'', среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычным сдвигом не получилось сходимости, применяют так называемые "особые сдвиги". Для симметрического же случая используется стратегия Уилкинсона<ref name = "Dem" />.

	Указанные стратегии выбора сдвигов используется в программах библиотек LAPACK и SCALAPACK. Но они не являются наилучшими, поскольку для выбора новых сдвигов нужно провести предшествующие итерации до конца. Поэтому в публикациях XXI века уже появились описания т.н. многосдвиговых итераций. В этой стратегии выбор сдвигов также выполняется с помощью собственных чисел подматриц из нижнего правого угла обрабатываемых блоков, но их размерность уже берётся больше, чем 2<ref>R. Granat, Bo Kagstrom, D. Kressner "LAPACK Working Note #216: A novel parallel QR algorithm for hybrid distributed memory HPC systems".</ref>.		Указанные стратегии выбора сдвигов используется в программах библиотек LAPACK и SCALAPACK. Но они не являются наилучшими, поскольку для выбора новых сдвигов нужно провести предшествующие итерации до конца. Поэтому в публикациях XXI века уже появились описания т.н. многосдвиговых итераций. В этой стратегии выбор сдвигов также выполняется с помощью собственных чисел подматриц из нижнего правого угла обрабатываемых блоков, но их размерность уже берётся больше, чем 2<ref>R. Granat, Bo Kagstrom, D. Kressner "LAPACK Working Note #216: A novel parallel QR algorithm for hybrid distributed memory HPC systems".</ref>.

			=== Неявное проведение итераций ===

			Q-теорема<ref name = "Dem" /> помогает не вычислять в явном виде требуемые матрицы с их последующим перемножением, а выполнять эти операции неявно. При этом в соответствии с [[QR-алгоритм#Особенности вещественного несимметричного варианта QR-алгоритма\|особенностями вещественного случая несимметричных матриц]] удаётся выполнять т.н. неявный двойной сдвиг с использованием двух комплексно сопряжённых сдвигов (например, из правила Фрэнсиса), оставаясь в рамках вещественной арифметрики, с помощью выполнения двусторонними преобразованиями Хаусхолдера т.н. вытеснения выступа. В вещественном случае аналогично (но с преимуществами симметрии) выполняется неявный одинарный сдвиг, вытеснением выступа двусторонними преобразованиями вращения (Гивенса).

	=== Обнуление поддиагональных элементов (дефляция) ===		=== Обнуление поддиагональных элементов (дефляция) ===

Frolov: /* Особенности вещественного несимметричного варианта QR-алгоритма */

2017-12-06T16:19:47Z

Особенности вещественного несимметричного варианта QR-алгоритма

← Предыдущая версия		Версия от 16:19, 6 декабря 2017
Строка 44:		Строка 44:
	\end{bmatrix}</math>.		\end{bmatrix}</math>.

	~~Поэтому выбор сдвигов должен учитывать, что конечные матрицы будут представленного вида.~~ Надо сказать, что при применении QR-алгоритма к симметричным матрицам такой проблемы не возникает, поскольку у них нет комплексных собственных значений. Кроме этого, приведение к хессенберговой форме в силу симметрии автоматически даст трёхдиагональную форму и, как следствие, линейную сложность одной итерации, что существенно ускоряет исполнение в сравнении с матрицами общего вида. В существующих пакетах программ для того, чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг<ref name = "Dem" />.		Надо сказать, что при применении QR-алгоритма к симметричным матрицам такой проблемы не возникает, поскольку у них нет комплексных собственных значений. Кроме этого, приведение к хессенберговой форме в силу симметрии автоматически даст трёхдиагональную форму и, как следствие, линейную сложность одной итерации, что существенно ускоряет исполнение в сравнении с матрицами общего вида. В существующих пакетах программ для того, чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг<ref name = "Dem" />.

	== Ускорение сходимости QR-алгоритма ==		== Ускорение сходимости QR-алгоритма ==

Frolov в 16:18, 6 декабря 2017

2017-12-06T16:18:59Z

@@ Строка 26: / Строка 26: @@
 В специальной литературе по численным методам приводится доказательство<ref name="VOLA" /> сходимости получающихся матриц к клеточной правой треугольной матрице с диагональными клетками, размеры которых зависят от размеров канонических ящиков Жордана исходной матрицы. Таким образом, проблема собственных значений матрицы сводится к проблемам собственных значений матриц меньшего размера. QR-алгоритм в узком смысле и есть эта процедура. Однако обычно к нему относят не только её, но и весь комплекс приёмов ускорения этого итерационного метода.
 == Ускорение сходимости QR-алгоритма ==
@@ Строка 51: / Строка 70: @@
 <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>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса''<ref name = "Dem"> Деммель Д. Вычислительная линейная алгебра. – 2001. - С.261-264. </ref>, среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычным сдвигом не получилось сходимости, применяют так называемые "особые сдвиги". Для симметрического случая используется стратегия Уилкинсона.
+Подбор параметра <math>\nu_k</math> осуществляется в зависимости от элементов матрицы <math>A_k</math>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса'', среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычным сдвигом не получилось сходимости, применяют так называемые "особые сдвиги". Для симметрического же случая используется стратегия Уилкинсона<ref name = "Dem" />.
-==== Особенности вещественного варианта QR-алгоритма ====
+Указанные стратегии выбора сдвигов используется в программах библиотек LAPACK и SCALAPACK. Но они не являются наилучшими, поскольку для выбора новых сдвигов нужно провести предшествующие итерации до конца. Поэтому в публикациях XXI века уже появились описания т.н. многосдвиговых итераций. В этой стратегии выбор сдвигов также выполняется с помощью собственных чисел подматриц из нижнего правого угла обрабатываемых блоков, но их размерность уже берётся больше, чем 2<ref>R. Granat, Bo Kagstrom, D. Kressner "LAPACK Working Note #216: A novel parallel QR algorithm for hybrid distributed memory HPC systems".</ref>.
 === Обнуление поддиагональных элементов (дефляция) ===

← Предыдущая версия		Версия от 12:12, 27 февраля 2018
Строка 54:		Строка 54:
	Хессенбергова (почти треугольная) форма матрицы интересна в приложении к 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-алгоритму тем, что в случае, если <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-алгоритма следует проводить уже с матрицами хессенберговой формы.

	В случае, если исходная матрица эрмитова (в вещественном случае - симметричная), то унитарно подобное приведение к хессенберговому виду становится [[Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной\|приведением к трёхдиагональному симметричному виду]]. В этом случае QR-алгоритм становится ещё		В случае, если исходная матрица эрмитова (в вещественном случае - симметричная), то унитарно подобное приведение к хессенберговому виду становится [[Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной\|приведением к трёхдиагональному симметричному виду]]. В этом случае QR-алгоритм становится ещё