СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

[8] а также используется алгоритм со сдвигом. Форма Хессенберга представляет из себя верхнюю треугольную матрицу (верхняя форма Хессенберга) у которой сохранена одна диагональ ниже главной, а элементы ниже этой диагонали равны нулю. Если матрица симметрична, то легко видеть, что матрица Хессенберга превращается в трехдиагональную матрицу[9] . При использовании матрицы Хессенберга время процесса пропорционально n ² , а при использовании трехдиагональной матрицы – n .

Можно использовать другие соотношения

где Q_s – унитарная, а L_s – нижняя треугольная матрица. Такой алгоритм носит название QL –алгоритма.

В общем случае, когда все собственные значения матрицы различны, последовательность матриц A_s имеет пределом нижнюю треугольную матрицу , диагональные элементы которой представляют собой собственные значения матрицы А , расположенные в порядке возрастания их модулей. Если матрица А имеет кратные собственные значения, то предельная матрица не является треугольной, а содержит диагональные блоки порядка p , соответствующие собственному числу кратности p .

В общем случае, наддиагональный элемент матрицы A_s на s -ом шаге асимптотически равен , где k_ij – постоянная величина. Сходимость QL –алгоритма вообще говоря недостаточна. Сходимость можно улучшить, если на каждом шаге вместо матрицы A_s использовать матрицу A_s -k_s I (QL –алгоритм со сдвигом). Последовательность вычислений в этом случае описывается следующими соотношениями:

которые определяют матрицу . При этом асимптотическое поведение элемента определено соотношением , а не , как прежде. Если сдвиг k_s выбрать близко к величине (наименьшее собственное значение), то в пределе внедиагональные элементы первой строки будут очень быстро стремиться к нулю. Когда ими можно пренебречь, элемент с рабочей точностью равен , остальные являются собственными значениями оставшейся матрицы n- 1- го порядка. Тогда, если QL –алгоритм выполнен без ускорения сходимости, то все равно , и поэтому автоматически можно выделить величину сдвига k_s .

Если матрица А эрмитова, то очевидно, что и все матрицы А _s эрмитовы; если А действительная и симметричная, то все Q_s ортогональны и все А _s действительны и симметричны.

2.2. Реализация разложения

Таким образом, разложение производится в два этапа. Сначала матрица А посредством двух конечных последовательностей преобразований Хаусхолдера где , приводится к верхней двухдиагональной форме следующего вида:

Далее реализуется итерационный процесс приведения двухдиагональной матрицы J ₀ к диагональной форме, так что имеет место следующая последовательность: где а S_i и T_i – диагональные матрицы.

Матрицы T_i выбираются так, чтобы последовательность матриц сходилась к двухдиагональной матрице. Матрицы же S_i выбирают так, чтобы все J_i сохраняли двухдиагональную форму. Переход осуществляется с помощью плоских вращений (10) – преобразований Гивенса. Отсюда, где

а матрица вычисляется аналогично с заменой на .

Пусть начальный угол произволен, однако следующие значения угла необходимо выбирать так, чтобы матрица J_{i + 1} имела ту же форму, что и J_i . Таким образом не аннулирует ни одного элемента матрицы, но добавляет элемент ; аннулирует но добавляет ; аннулирует но добавляет и т.д., наконец, аннулирует и ничего не добавляет.

Этот процесс часто называют процессом преследования. Так как , то , и M_{i + 1} – трехдиагональная матрица, точно так же, как и M_i . Начальный угол можно выбрать так, чтобы преобразование было QR –преобразованием со сдвигом, равным s .

Обычный QR –алгоритм со сдвигом можно записать в следующем виде:

где – верхняя треугольная матрица. Следовательно, . Параметр сдвига s определяется собственным значением нижнего минора (размерности 2´2) матрицы M_i . При таком выборе параметра s метод обладает глобальной и почти всегда кубичной сходимостью.

2.3. Пример сингулярного разложения

Проведем преобразование Хаусхолдера на матрице ,

К первой компоненте первого столбца прибавляем норму первого столбца, получим . Пусть

Преобразованная матрица A ₂ вычисляется следующим образом. Для первого столбца имеем:

так как

Таким образом, в первый столбец были введены нули и его длина не изменилась. Получим второй столбец:

для третьего столбца:

окончательно,

Столбцы матрицы A ₂ получаются вычитанием кратных вектора v ₁ из столбцов A ₁ . Эти кратные порождаются скалярными произведениями, а не от

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать