Сингулярное разложение в линейной задаче метода наименьших квадратов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
сдвиг ks выбрать близко к величине (наименьшее собственное значение), то в пределе внедиагональные элементы первой строки будут очень быстро стремиться к нулю. Когда ими можно пренебречь, элемент с рабочей точностью равен , остальные являются собственными значениями оставшейся матрицы n-1-го порядка. Тогда, если QLалгоритм выполнен без ускорения сходимости, то все равно , и поэтому автоматически можно выделить величину сдвига ks.
Если матрица А эрмитова, то очевидно, что и все матрицы Аs эрмитовы; если А действительная и симметричная, то все Qs ортогональны и все Аs действительны и симметричны.
2.2. Реализация разложения
Таким образом, разложение производится в два этапа. Сначала матрица А посредством двух конечных последовательностей преобразований Хаусхолдера где , приводится к верхней двухдиагональной форме следующего вида:
Далее реализуется итерационный процесс приведения двухдиагональной матрицы J0 к диагональной форме, так что имеет место следующая последовательность: где а Si и Ti диагональные матрицы.
Матрицы Ti выбираются так, чтобы последовательность матриц сходилась к двухдиагональной матрице. Матрицы же Si выбирают так, чтобы все Ji сохраняли двухдиагональную форму. Переход осуществляется с помощью плоских вращений (10) преобразований Гивенса. Отсюда, где
а матрица вычисляется аналогично с заменой на .
Пусть начальный угол произволен, однако следующие значения угла необходимо выбирать так, чтобы матрица Ji+1 имела ту же форму, что и Ji. Таким образом не аннулирует ни одного элемента матрицы, но добавляет элемент ; аннулирует но добавляет ; аннулирует но добавляет и т.д., наконец, аннулирует и ничего не добавляет.
Этот процесс часто называют процессом преследования. Так как , то , и Mi+1 трехдиагональная матрица, точно так же, как и Mi. Начальный угол можно выбрать так, чтобы преобразование было QRпреобразованием со сдвигом, равным s.
Обычный QRалгоритм со сдвигом можно записать в следующем виде:
где верхняя треугольная матрица. Следовательно, . Параметр сдвига s определяется собственным значением нижнего минора (размерности 22) матрицы Mi. При таком выборе параметра s метод обладает глобальной и почти всегда кубичной сходимостью.
2.3. Пример сингулярного разложения
Проведем преобразование Хаусхолдера на матрице ,
К первой компоненте первого столбца прибавляем норму первого столбца, получим . Пусть
Преобразованная матрица A2 вычисляется следующим образом. Для первого столбца имеем:
так как
Таким образом, в первый столбец были введены нули и его длина не изменилась. Получим второй столбец:
для третьего столбца:
окончательно,
Столбцы матрицы A2 получаются вычитанием кратных вектора v1 из столбцов A1. Эти кратные порождаются скалярными произведениями, а не отдельными элементами, как в гауссовом исключении.
Прежде чем вводить дальнейшие нули под диагональю, преобразованием вида A3=A2Q1, получают нули в первой строке. Нули уже стоящие в первом столбце, не должны быть испорчены, длина первого столбца должна быть сохранена; поэтому при внесении нулей в первую строку нельзя менять первый элемент строки, изменяем второй элемент и зануляем третий. Для матрицы большего размера на этом шаге было бы получено n2 нуля.
Преобразование порождается первой строкой A2:
Строка матрицы A3 с номером i получается по формуле
.
Таким образом, из каждой строки A2 вычитается надлежащее кратное . Это дает матрицу
Поскольку первая компонента нулевая, то нули первого столбца A2 сохраняются в A3, Так как Q1 ортогональная, то длина каждой строки в A3 равна длине соответствующей строки в A2.
Теперь можно добиться новых нулей под диагональю, не испортив полученных ранее:
Поскольку ранг этой матрицы равен лишь 2, то теперь третий столбец имеет на диагонали и под диагональю элементы порядка ошибки округления. Эти элементы обозначены в матрице через 0.000, чтобы отличить их от элементов, в точности равных нулю. Если бы матрица имела полный ранг, то нужно было бы выполнить еще одно преобразование, чтобы получить нули в третьем столбце:
Если бы не ошибки округлений, то в данном примере третий диагональный элемент был бы точным нулем. Элементы под диагональю во всех столбцах указаны как точные нули, потому что преобразования так и строились, чтобы получить там нули. Последнее преобразование H3 в этом примере могло бы быть тождественным, однако тогда оно не было бы хаусхолдеровым отражением. Фактически использование H3 попутно изменяет знак элемента 1.080 в матрице A4.
Получилась искомая двухдиагональная матрица, и первый этап закончен. Прямое использование ортогональных преобразований не позволяет получить какиелибо новые нули. Для общего порядка n нужно n преобразований H и n2 преобразований Q, чтобы достигнуть данного места. Число преобразований не зависит от строчной размерности m, но от m зависит работа, затрачиваемая на выполнение каждого преобразования.
глава 3. Использование сингулярного разложения в методе наименьших квадратов
При использовании метода сингулярного разложения (SVD Singular Value Decomposition) мы проводим разложение для матрицы пла