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

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

В (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) ;

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

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

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

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

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

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

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