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

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Свойства и структура алгоритмов == === Общее описание алгоритма === Матрица <math>B = [b_{ij}]</math>...»)
 
Строка 5: Строка 5:
 
где <math>P</math> и <math>Q</math> - произведения конечного числа матриц отражения(или вращения).
 
где <math>P</math> и <math>Q</math> - произведения конечного числа матриц отражения(или вращения).
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Пусть дана матрица A размера <math>n \times n</math>. Сначала мы умножаем A слева на матрицу отражения, аннулирующую все поддиагональные элементы вервого столбца. Затем умножаем результат справа на матрицу отражения, аннулирующую элементы первой строки в позициях с 3-й по n-ю. Далее умножением слева аннулируем все поддиагональные элементы второго столбца, затем умножением справа аннулируем получаем нули во второй строке в позициях с 4-й по n-ю и т.д. После каждого умножения на матрицу отражения все ранее полученные нули остаются.
+
Пусть дана матрица 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>
 +
=== Вычислительное дро алгоритма ===
 +
Вычислительное ядро алгоритма составляет нахождение на каждом этапе матрицы отражения(всего <math>2 * n - 2</math>.
 +
=== Макроструктура алгоритма ===
 +
Операции скалярного произведения, умножения матрицы на вектор
 +
=== Схема реализации последовательного алгоритма ===
 +
<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>
 +
=== Последовательная сложность ===
 +
Для двухдиагонализации матрицы порядка 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>.
 +
=== Информационный граф ===
 +
=== При параллельном вычислении двухдиагональной матрицы методом отражений требуется последовательно выполнить следующие ярусы:
 +
<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>
 +
=== Входные и выходные данные алгоритма ===
 +
На вход подается матрица A и ее размер n. Выходные данные -- матрицы P, Q, D, такие что <math>A = P * D * Q <\math>
 
== Литература ==  
 
== Литература ==  
 
Е. Е. Тыртышников, "Методы численного анализа".
 
Е. Е. Тыртышников, "Методы численного анализа".

Версия 01:42, 7 декабря 2021

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>

2 Литература

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