Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [выверенная версия] |
ASA (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
=== Общее описание === | === Общее описание === | ||
Алгоритм '''dqds''' (''differential quotient-difference algorithm with shifts'')<ref name="vla">Деммель Д. Вычислительная линейная алгебра. – М : Мир, 2001.</ref><ref name="hola">Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.</ref> позволяет с высокой точностью вычислять сингулярные числа двухдиагональных матриц. | Алгоритм '''dqds''' (''differential quotient-difference algorithm with shifts'')<ref name="vla">Деммель Д. Вычислительная линейная алгебра. – М : Мир, 2001.</ref><ref name="hola">Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.</ref> позволяет с высокой точностью вычислять сингулярные числа двухдиагональных матриц. | ||
| − | Вычислительным ядром алгоритма является [[Итерация алгоритма dqds|dqds-итерация]], вне итераций происходит подбор сдвига <math>\delta</math>, отслеживание сходимости, а также применение различных оптимизационных " | + | Вычислительным ядром алгоритма является [[Итерация алгоритма dqds|dqds-итерация]], вне итераций происходит подбор сдвига <math>\delta</math>, отслеживание сходимости, а также применение различных оптимизационных "хитростей". Отметим, что внеитерационная часть алгоритма не существенна с точки зрения структуры вычислений, т.к. основыне вычислительные затраты ложаться на [[Итерация алгоритма dqds|dqds-итерацию]]. Подробности и варианты внеитерационной части, а также анализ сходимости можно найти в соответствующей литературе |
<ref>Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.</ref> | <ref>Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.</ref> | ||
<ref>Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.</ref> | <ref>Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.</ref> | ||
| Строка 8: | Строка 8: | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| − | В [http://netlib.org/lapack/ LAPACK] реализовано функцией XLASQ1 | + | В [http://netlib.org/lapack/ LAPACK] реализовано функцией XLASQ1. |
== Литература == | == Литература == | ||
Версия 10:55, 25 октября 2017
1 Общее описание
Алгоритм dqds (differential quotient-difference algorithm with shifts)[1][2] позволяет с высокой точностью вычислять сингулярные числа двухдиагональных матриц. Вычислительным ядром алгоритма является dqds-итерация, вне итераций происходит подбор сдвига [math]\delta[/math], отслеживание сходимости, а также применение различных оптимизационных "хитростей". Отметим, что внеитерационная часть алгоритма не существенна с точки зрения структуры вычислений, т.к. основыне вычислительные затраты ложаться на dqds-итерацию. Подробности и варианты внеитерационной части, а также анализ сходимости можно найти в соответствующей литературе [3] [4] [5].
2 Существующие реализации алгоритма
В LAPACK реализовано функцией XLASQ1.
3 Литература
- ↑ Деммель Д. Вычислительная линейная алгебра. – М : Мир, 2001.
- ↑ Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.
- ↑ Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.
- ↑ Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.
- ↑ Aishima K. et al. On convergence of the DQDS algorithm for singular value computation //SIAM Journal on Matrix Analysis and Applications. – 2008. – Т. 30. – №. 2. – С. 522-537.
