Итерация алгоритма dqds

Итерация алгоитма dqds
Последовательный алгоритм
Последовательная сложность	[math]5n-4[/math]
Объём входных данных	[math]2n[/math]
Объём выходных данных	[math]2n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]4n-3[/math]
Ширина ярусно-параллельной формы	[math]2[/math]

Основные авторы описания: А.Ю.Чернявский

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

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

1.2 Математическое описание алгоритма

Формулы алгоритма следующие:

[math] \widehat{q}_j = q_j + e_j - \widehat{e}_{j-1} - \delta \quad j \in [1,n-1]\\ \widehat{e}_j = e_j \cdot q_{j+1} / \widehat{q}_j \quad j \in [1,n-1]\\ \widehat{q}_n = q_n - \widehat{e}_{n-1} - \delta. [/math]

Здесь [math]q_j, \; j \in [1,n][/math] и [math]e_j, \; j \in [1,n-1][/math] - квадраты элемнтов главной и верхней побочной диагональ соответственно. Крышка означает выходные переменные, а [math]\delta[/math] - сдвиг (параметр алгоритма). Такая математическая запись наиболее компактна и соответсвует так называемой qds-итерации.

Представим также математическую запись, приближенную к dqds-итерации (с математической точки зрения qds и dqds-итерации эквивалентны) с введенными вспомогательными переменными [math]t_j[/math] и [math]d_j:[/math]

[math] d_1 = q_1 - \delta, \; q_n = d_n \\ для \; j\in [1,n-1]: \\ \widehat{q}_j = d_j + e_j\\ t_j = q_{j+1}/\widehat{q}_j\\ \widehat{e}_j=e_j \cdot t_j \\ d_{j+1} = d \cdot t - \delta \\ [/math]

Отметим, что при [math]\delta=0[/math] две итерации dqds эквиваленты одной QR-итерации.