Участник:Малков Кирилл/Алгоритм бидиагонализации матрицы методом отражений

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

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

Матрица [math]B = [b_{ij}][/math] называется (верхней) двухдиагональной, или бидиагональной, если [math]b_{ij} = 0[/math], [math]i \gt j[/math] или [math]i + 1 \lt j[/math]. Алгоритм бидиагонализации матрицы методом отражений приводит произвольную [math]n \times n[/math] матрицу A к бидиагональному виду [math]B = PAQ[/math], где [math]P[/math] и [math]Q[/math] - произведения конечного числа матриц отражения(или вращения).

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

Пусть дана матрица A размера [math]n \times n[/math]. Вычисляется двухдиагональная матрица D размера [math]n \times n[/math], такая что [math]A = P \times D \times Q[/math] для некоторых матриц P и Q, являющихся произведением некоторого числа матриц отражения.Сначала мы умножаем A слева на матрицу отражения, аннулирующую все поддиагональные элементы вервого столбца. Затем умножаем результат справа на матрицу отражения, аннулирующую элементы первой строки в позициях с 3-й по n-ю. Далее умножением слева аннулируем все поддиагональные элементы второго столбца, затем умножением справа аннулируем получаем нули во второй строке в позициях с 4-й по n-ю и т.д. После каждого умножения на матрицу отражения все ранее полученные нули остаются. Формулы метода: Пусть [math]A = [a_1, a_2, ..., a_n][/math] [math]D_1 = A, P_1 = I, Q_1 = I.[/math] [math]Если i четное, то D_i = D_{i-1} * (I - 2 * u_{i-1} * u_{i-1}^*)[/math] [math]u_i = frac{[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]}{||[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]||_2}, Q_i = (I - 2 * u_{i} * u_{i}^*) * Q_{i-1}, P_i = P_{i-1}.[/math] [math]Если i нечетное, то D_i = (I - 2 * u_{i-1} * u_{i-1}^*) * D_{i-1},[/math] [math]u_i = frac{[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]}{||[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]||_2}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).[/math]

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

Вычислительное ядро алгоритма составляет нахождение на каждом этапе матрицы отражения(всего [math]2 * n - 2[/math].

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

Операции скалярного произведения, умножения матрицы на вектор

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

[math]D_1 = A, P_1 = I, Q_1 = I.[/math] [math]1) для четного i : D_i = D_{i-1} * (I - 2 * u_{i-1} * u_{i-1}^*), Q_i = (I - 2 * u_{i} * u_{i}^*) * Q_{i-1}, P_i = P_{i-1};[/math] [math] для нечетного i : D_i = (I - 2 * u_{i-1} * u_{i-1}^*) * D_{i-1}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).[/math] [math]2) для четного i : u_i = \frac{[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]}{||[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]||_2},[/math] [math] для нечетного i : u_i = \frac{[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]}{||[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]||_2}.[/math]

1.6 Последовательная сложность

Для двухдиагонализации матрицы порядка n методом отражений при последовательном варианте требуется: <math>1) 2 * n - 2 вычислений квадратного корня, 2) 4 * n - 4 делений, 3) (4 * n - 4)(1 + n + n^2) умножений, 4) (4 * n - 4)(1 + n + n^2) сложений. Сложность последовательного алгоритма есть <math>O(n^3)<\math>.

1.7 Информационный граф

=== При параллельном вычислении двухдиагональной матрицы методом отражений требуется последовательно выполнить следующие ярусы: <math> -- k ярусов с вычислением 4 * (n/k) - 4 делений, -- k ярусов с вычислением (4 * (n/k) - 4)(1 + n + n^2) умножений, -- k ярусов с вычислением (4 * (n/k) - 4)(1 + n + n^2) сложений. Получим, что параллельная сложность алгоритма есть <math>O(n^2)<\math>

1.8 Входные и выходные данные алгоритма

На вход подается матрица A и ее размер n. Выходные данные -- матрицы P, Q, D, такие что <math>A = P * D * Q <\math>

1.9 Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов является линейным. Вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, линейна.

2 Литература

Е. Е. Тыртышников, "Методы численного анализа".