Кафедра №31, «НИЯУ МИФИ» Вычислительная линейная алгебра Домашнее задание №4 Кафедра №31 Прикладной математики «НИЯУ МИФИ» Вычислительная линейная алгебра Способ выбора задачи: Определите свою задачу по формуле: № задачи = k mod 3 + 1, где k — ваш номер по списку группы. Задача 1. Пусть A ∈ Rm×n , где m < n. Приведите алгоритм вычисления разложения P T AQ = B|0 , где B|0 — верхняя двухдиагональная матрица размера m × n, P ∈ Rm×m и Q ∈ Rn×n — ортогональные матрицы. Подсказка: используя матрицы Хаусхолдера, приведите A к виду × × 0 ... 0 0 0 0 ... 0 0 × × ... 0 0 0 0 ... 0 .. .. .. . . .. .. .. .. .. , . . . . . . . . ... . 0 0 0 ... × × 0 0 ... 0 0 0 0 ... 0 × × 0 ... 0 а затем вынесите элемент (m, m + 1) вверх по (m + 1)-му столбцу, действуя справа вращениями Гивенса. Задача 2. Результат первого этапа сингулярного разложения, т. е. представление матрицы A в виде B T A = P BQ или A = P QT , 0 где B — двухдиагональная матрица вида p1 q2 0 . . . 0 0 0 p 2 q3 . . . 0 0 .. .. .. . . . . . . B=. . . , . . . 0 0 0 . . . pn−1 qn 0 0 0 ... 0 pn можно использовать для решения СЛАУ Ax = b. 1 Кафедра №31, «НИЯУ МИФИ» Вычислительная линейная алгебра Эта система в рассматриваемом случае равносильна системе BQT x = P T b, которая введением переменного вектора y = QT x = (y1 , . . . , yn )T и фиксированного вектора c = P T b = (c1 , . . . , cm )T приводится к системе p1 y1 +q2 y2 = c1 , p 2 y 2 + q 3 y 3 = c2 , ... pn−1 yn−1 +qn yn = cn−1 , pn yn = cn . Найдя отсюда компоненты вспомогательного вектора y последовательно, начиная с последнего уравнения: yn = cn , pn yk−1 = ck − qk+1 yk+1 , pk где k = n − 1, n − 2, . . . , 1, приходим к искомому решению данной СЛАУ: x = Qy. Требуется: (a) Определить условие, при котором СЛАУ Ax = b будет иметь единственное решение (рассмотреть случаи m > n и m = n). Как это условие можно проверить в рамках описанного алгоритма? (b) Реализовать алгоритм решения СЛАУ с использованием бидиагонального разложения и проверить его работу на примерах. Задача 3. Реализуйте полное сингулярное разложение (SVD) матрицы A ∈ Rm×n вида A = U ΣV, где U ∈ Rm×m и V ∈ Rn×n — ортогональные матрицы, а Σ ∈ Rm×n — матрица, на главной диагонали которой стоят сингулярные числа матрицы A. Требуется: (a) Реализовать алгоритм полного SVD разложения. (b) Сравнить полученные результаты с результатами стандартных библиотечных функций для вычисления SVD. Примечание: Приводить сингулярные числа в порядке невозрастания необязательно. 2
