Уровень алгоритма

Итерация алгоритма dqds: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 60: Строка 60:
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
  
Отметим, что выходные данные сразу могут быть записаны во взодные (это учтено в схеме), также для хранения вспомогательных <math>t_j</math> и <math>d_j</math> достаточно двух  
+
Отметим, что выходные данные сразу могут быть записаны на место входных (это учтено в схеме), также для хранения вспомогательных переменных <math>t_j</math> и <math>d_j</math> достаточно двух перезаписываемых переменных.
  
перезаписываемых переменных.
+
1. Вычисляется начальное значение вспомогательной переменной <math>d = q_1-\delta.</math>
  
# Вычисляется начальное значение <math>d = q_1-\delta</math>
+
2. Производится цикл по j от 1 до n-1, состоящий из:
  
# Производится цикл по i от 1 до n-1, состоящий из:
+
:2.1 Вычисляется значение <math>q_j = d + e_j;</math>
 +
:2.2 Вычисляется значение вспомогательной переменной <math>t = q_{j+1}/q_j;</math>
 +
:2.3 Вычисляется значение <math>e_j = e_j \cdot t;</math>
 +
:2.4 Вычисляется значение вспомогательной переменной <math>d = d \cdot t - \delta.</math>
 +
:
  
##
+
3. Вычисляется <math>q_n = d.</math>
##
 
##
 
##
 
##
 
 
 
# Вычисляется <math>q_n = d.</math>
 

Версия 14:14, 23 августа 2015



Алгоритм 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-итерации.

1.3 Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является производимое n-1 раз вычисление, содержащие по одной операции сложения, вычитания и деления, а также две операции умножения.

1.4 Макроструктура алгоритма

Алгоритм состоит из отдельного вычисления первого элемента главной диагонали и последующим (n-1)-кратным выполнением повторяющейся последовательности из 5 операций (+,/,*,*,-).

1.5 Схема реализации последовательного алгоритма

Отметим, что выходные данные сразу могут быть записаны на место входных (это учтено в схеме), также для хранения вспомогательных переменных [math]t_j[/math] и [math]d_j[/math] достаточно двух перезаписываемых переменных.

1. Вычисляется начальное значение вспомогательной переменной [math]d = q_1-\delta.[/math]

2. Производится цикл по j от 1 до n-1, состоящий из:

2.1 Вычисляется значение [math]q_j = d + e_j;[/math]
2.2 Вычисляется значение вспомогательной переменной [math]t = q_{j+1}/q_j;[/math]
2.3 Вычисляется значение [math]e_j = e_j \cdot t;[/math]
2.4 Вычисляется значение вспомогательной переменной [math]d = d \cdot t - \delta.[/math]

3. Вычисляется [math]q_n = d.[/math]