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

При умножении этой матрицы справа на  получаем

                                              (17)

Матрица  порядка pxk определяет преобразование строк матрицы X из евклидова p–мерного пространства в евклидово k–мерное пространство; уравнение (16) показывает, что существует преобразование матрицы X порядка Nxp в матрицу  порядка Nxk. Матрица X содержит N точек в p–мерном евклидовом пространстве, которые приближенно могут быть спроектированы в k–мерное евклидово пространство. матрица  определяет координаты этих точек в k–мерном евклидовом пространстве.

1.5. QR–разложение

Теорема 2. Пусть А – m´n–матрица. Существует ортогональная m´m–матрица Q такая, что в матрице QA=R под главной диагональю стоят только нулевые элементы.

Доказательство. Выберем ортогональную m´m–матрицу Q в соответствии с преобразованием Хаусхолдера (9), так, чтобы первый столбец Q1A имел нулевые компоненты со 2–ой по m–ю. Далее выбираем ортогональную (m-1)´(m–1)–матрицу P2 следующим образом. Будучи применена к  m–1 вектору, составленному из компонент со 2–ой по m–ю второго столбца матрицы Q1A, она аннулирует компоненты с 3–ей по m–ю этого вектора. Матрица преобразования

ортогональна, и Q2Q1A имеет в первых двух столбцах нули под главной диагональю. Продолжая таким образом, можно построить произведение, состоящее максимум из n ортогональных преобразований, которое трансформирует А к верхней треугольной форме. Формальное доказательство можно получить методом конечной индукции.

Полученное представление матрицы произведением ортогональной и верхней треугольной матриц называется QR–разложением.

Теорема 3. Пусть А – m´n–матрица ранга к, причем k<n£m. Существуют ортогональная m´m–матрица Q и m´n–матрица перестановки P такие, что

,                                                    (18)

где R – верхняя треугольная к´к–матрица ранга к.

Доказательство. Выберем матрицу перестановки Р таким образом, чтобы первые к столбцов матрицы AP, были линейно независимы. Согласно теореме 2, найдется ортогональная m´m–матрица Q такая, что QAP будет верхней треугольной. Поскольку первые к столбцов АР линейно независимы, это будет верно для первых к столбцов QAP.

Все элементы матрицы QAP, стоящие на пересечении строк с номерами к+1,...,m и столбцов с номерами к+1,...,n, будут нулями. В противном случае rankQAP>k, что противоречит предположению rankA=k. Итак, QAP имеет форму, указанную правой частью (4). Теорема доказана.

Подматрицу [R:T] из правой части (18) можно теперь преобразовать к компактной форме, требуемой от матрицы R из теоремы 2. Это преобразование описывает следующая лемма.

Лемма 1. Пусть [R:T] – к´к–матрица, причем R имеет ранг к. Существует ортогональная n´n–матрица W такая, что

где  – нижняя треугольная матрица ранга к.

Доказательство леммы вытекает из теоремы 3, если отождествить величины n, k, [R:T], W из формулировки леммы с соответствующими величинами m, n, AT, QT теоремы 3.

Используя теорему 3 и лемму 1 можно доказать следующую теорему.

Теорема 4. Пусть А – m´n–матрица ранга к . Найдутся ортогональная m´m–матрица Н и ортогональная n´n–матрица К такие, что

                                        (19)

причем R11 – невырожденная треугольная к´к–матрица.

Заметим, что выбором Н и К в уравнении (19) можно добиться, чтобы R11 была верхней или нижней треугольной.

В (19) матрица А представлена произведением A=HRKT, где R – некоторая прямоугольная матрица, ненулевые компоненты которой сосредоточены в невырожденной треугольной подматрице. Далее мы покажем, что эту невырожденную подматрицу R можно упростить далее до невырожденной диагональной матрицы. Это разложение тесно связано со спектральным разложением симметричных неотрицательно определенных матриц ATA и AAT (см. 11).

Теорема 5. Пусть А – m´n–матрица ранга k. Тогда существуют ортогональная m´m–матрица U, ортогональная n´n–матрица V и диагональная m´n–матрица S такие, что

UTAV=S, A=USVT                                      (20)

Матрицу S можно выбрать так, чтобы ее диагональные элементы составляли невозрастающую последовательность; все эти элементы неотрицательны и ровно к из них строго положительны.

Диагональные элементы S называются сингулярными числами А. Докажем сперва лемму для специального случая m=n=rankA.

Лемма 2. Пусть А – n´n–матрица ранга n. Тогда существует ортогональная n´n–матрица U, ортогональная n´n–матрица V и диагональная n´n–матрица S такие, что UTAV=S, A=USVT и последовательные диагональные элементы S положительны и не возрастают.

Доказательство леммы. Положительно определенная симметричная матрица ATA допускает спектральное разложение

ATA=VDVT,                                        (21)

где V – ортогональная n´n–матрица, а D – диагональная матрица, причем диагональные элементы D положительны и не возрастают. Определим S как диагональную n´n–матрицу, диагональные элементы которой суть положительные квадратные корни из соответствующих диагональных элементов D. Таким образом

D=STS=S2, S-1DS-1=I.                                  (22)

Определим матрицу

U=AVS-1                                                     (23)

Из (21), (22), (23) и ортогональности V следует, что

UTU=S-1VTATAVS-1=S-1DS-1=I т.е. U ортогональна. Из (23) и ортогональности V выводим USVT=AVS-1SVT=AVVT=A Лемма доказана.

Доказательство теоремы 5. Пусть A=HRKT, где H, R, KT имеют свойства, указанные в теореме 4. Так как R11 из (19) – невырожденная треугольная к´к–матрица, то согласно лемме 2 , можно написать

                                                  (24)

Здесь  и  – ортогональные к´к–матрицы, а  – невырожденная диагональная матрица, диагональные элементы которой положительны и не возрастают. Из (24) следует, что матрицу R в уравнении (19) можно записать в виде

                                                  (25)

где:

       – ортогональная m´m–матрица;

       – ортогональная n´n–матрица;

           – ортогональная m´n–матрица;

Теперь, определяя U и V формулами

                                       (26)

заключаем из (24) – (26), что A=USVT, где U, S, V имеют свойства, указанные в формулировке теоремы 5. Это завершает доказательство.

  Заметим, что сингулярные числа матрицы А определены однозначно, в то время, как в выборе ортогональных матриц U, V есть произвол. Пусть s – сингулярное число А, имеющее кратность l. Это значит, что для упорядоченных сингулярных чисел найдется индекс I такой, что

  Положим 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)      ;

2)     

3)     

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.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) – преобразований Гивенса. Отсюда,  где

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

Страницы: 1, 2, 3