Сингулярное разложение в линейной задаче метода наименьших квадратов

Дипломная работа - Математика и статистика

Другие дипломы по предмету Математика и статистика

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



сдвиг 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) мы проводим разложение для матрицы пла

s