Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы

Материал из Алговики
Перейти к навигации Перейти к поиску

1 Общее описание

Алгоритм dqds (differential quotient-difference algorithm with shifts)[1][2] позволяет с высокой точностью вычислять сингулярные числа двухдиагональных матриц. Вычислительным ядром алгоритма является dqds-итерация, вне итераций происходит подбор сдвига [math]\delta[/math], отслеживание сходимости, а также применение различных оптимизационных "хитрости". Отметим, что внеитерационная часть алгоритма не существенна с точки зрения структуры вычислений, т.к. основыне вычислительные затраты ложаться на dqds-итерацию. Подробности и варианты внеитерационной части, а также анализ сходимости можно найти в соответствующей литературе [3] [4] [5].


2 Существующие реализации алгоритма

В LAPACK реализовано функцией XLASQ1

3 Литература

  1. ↑ Деммель Д. Вычислительная линейная алгебра. – М : Мир, 2001.
  2. ↑ Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.
  3. ↑ Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.
  4. ↑ Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.
  5. ↑ 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.
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_dqds_нахождения_сингулярных_чисел_двухдиагональной_матрицы&oldid=2373