Быстрый поиск

Реферат: СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

Положим k=min(m,n), и пусть Q – ортогональная к´к–матрица вида

Здесь Р – ортогональная l´l–матрица Если A=USVT – сингулярное разложение А и si=…=si+l-1, то сингулярным разложением А будет также и , где .

1.6. Число обусловленности

Некоторые вычислительные задачи поразительно чувствительны к изменению данных. Этот аспект численного анализа не зависит от плавающей арифметики или выбранного алгоритма.

Например:

Найти корни полинома: (x-2)2=10-6

Корни этого уравнения есть 2+10-3 и 2-10-3. Однако изменение свободного члена на 10-6 может вызвать изменение в корнях, равное 10-3.

Операции с матрицами, как правило, приводят к решению систем линейных уравнений. Коэффициенты матрицы в правой части системы линейных уравнений редко известны точно. Некоторые системы возникают из эксперимента, и тогда коэффициенты подвержены ошибкам наблюдения. Коэффициенты других систем записываются формулами, что влечет за собой ошибки округлений. В связи с этим необходимо знать, как влияют ошибки в коэффициентах матрицы на решение. Именно для этого вводится понятие обусловленности матрицы.

По определению число обусловленности есть величина . Для более подробного описания числа обусловленности нам понадобится понятие нормы в пространстве векторов и матриц.

Нормой вектора x в пространстве векторов называется функционал, обозначаемый , удовлетворяющий следующим условиям:

1) положительной определенности –

2) положительной однородности – ;

3) неравенству треугольника – .

Нормой квадратной матрицы А в пространстве матриц, согласованной с нормой вектора называется функционал , удовлетворяющий условиям 1 – 3 для нормы вектора:

1) ;

4) мультипликативное неравенство –

Наиболее употребимы следующие нормы для векторов:

· норма суммы модулей

· евклидова норма

· норма максимума модуля

Нормы матриц:

Здесь являются сингулярными числами[3] матрицы А; это положительные значения квадратных корней из собственных значений матрицы АТА (которая при невырожденной матрице А положительно определена[4], в противном случае положительно полуопределена (неотрицательно определена[5]) и поэтому имеет только вещественные собственные значения ³ 0). Для вещественных симметричных матриц сингулярные числа равны абсолютным величинам собственных значений: .

Умножение вектора х на матрицу А приводит к новому вектору Ах, норма которого может очень сильно отличаться от нормы вектора х.

Область изменений может быть задана двумя числами

Максимум и минимум берутся по всем ненулевым векторам. Заметим, что если А вырождена, то m=0. Отношение M/m называется числом обусловленности матрицы А,

(7)

Рассмотрим норму обратной[6] матрицы .

Для матрицы А существует сингулярное разложение , тогда , отсюда . Аналогично для обратной матрицы и . Отсюда следует, что собственные числа матрицы – 1/ есть величины, обратные собственным числам матрицы – . При этом очевидно, что . Из последнего выражения вместе с (7) следует . Таким образом обусловленность матрицы равна произведению нормы матрицы на норму обратной матрицы.

Рассмотрим систему уравнений Ax=b, и другую систему, полученную изменением правой части: A(x+Dx)=b+Db . Будем считать Db ошибкой в b, а Dx соответствующей ошибкой в x, хотя нам нет необходимости считать ошибки малыми. Поскольку A(Dx)=Db, то определения M и m немедленно приводят к неравенствам Следовательно , при m¹0,

Величина есть относительное изменение правой части, а величина – относительная ошибка, вызванная этим изменением. Аналогичные выкладки можно провести не только с элементами вектора правой части но и с элементами самой матрицы А и найти зависимость между относительным изменением элементов матрицы и относительной ошибкой вызванной этим изменением. Отсюда следует, что число обусловленности выполняет роль множителя в увеличении относительной ошибки.

Приведем некоторые свойства числа обусловленности. Ясно, что M³m и поэтому cond(А)³1. Если Р – матрица перестановок[7], то компоненты вектора Px лишь порядком отличаются от компонент вектора х. Отсюда следует, что и cond(P)=1 . В частности cond(I)=1. Если А умножается на скаляр с, то cond(cА)= cond(А). Если D – диагональная матрица, то

глава 2. Реализация сингулярного разложения

2.1. Алгоритмы

QR–алгоритм начинается с разложения матрицы по Грамму-Шмидту , затем меняются местами сомножители: Эта матрица подобна первоначальной, Этот процесс продолжается, причем собственные значения не изменяются:

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

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

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

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

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

которые определяют матрицу . При этом асимптотическое поведение элемента определено соотношением , а не , как прежде. Если сдвиг 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 определяется собственным значением нижнего минора (размерности 2´2) матрицы Mi. При таком выборе параметра s метод обладает глобальной и почти всегда кубичной сходимостью.