.

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

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 1094
Скачать документ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Математический факультет

Кафедра прикладной математики

ДИПЛОМНЫЙ ПРОЕКТ

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

Заведующий кафедрой прикладной

математики

Исполнил:

Научный руководитель

Владикавказ 2002

СОДЕРЖАНИЕ

TOC \o “1-2” ВВЕДЕНИЕ PAGEREF _Toc11128507 \h 3

Глава 1. Метод наименьших квадратов PAGEREF _Toc11128508 \h 7

1.1. Задача наименьших квадратов PAGEREF _Toc11128509 \h 7

1.2. Ортогональное вращение Гивенса PAGEREF _Toc11128510 \h 9

1.3. Ортогональное преобразование Хаусхолдера PAGEREF _Toc11128511 \h
10

1.4. Сингулярное разложение матриц PAGEREF _Toc11128512 \h 11

1.5. QR–разложение PAGEREF _Toc11128513 \h 15

1.6. Число обусловленности PAGEREF _Toc11128514 \h 20

глава 2. Реализация сингулярного разложения PAGEREF _Toc11128515 \h
25

2.1. Алгоритмы PAGEREF _Toc11128516 \h 25

2.2. Реализация разложения PAGEREF _Toc11128517 \h 27

2.3. Пример сингулярного разложения PAGEREF _Toc11128518 \h 29

глава 3. Использование сингулярного разложения в методе наименьших
квадратов PAGEREF _Toc11128519 \h 33

ЗАКЛЮЧЕНИЕ PAGEREF _Toc11128520 \h 38

ЛИТЕРАТУРА PAGEREF _Toc11128521 \h 39

ПРИЛОЖЕНИЕ 1. Исходные тексты программы PAGEREF _Toc11128522 \h 40

ПРИЛОЖЕНИЕ 2. контрольный пример PAGEREF _Toc11128523 \h 45

ВВЕДЕНИЕ

Метод наименьших квадратов обычно используется как составная часть
некоторой более общей проблемы. Например, при необходимости проведения
аппроксимации наиболее часто употребляется именно метод наименьших
квадратов. На этом подходе основаны: регрессионный анализ в статистике,
оценивание параметров в технике и т.д.

Большое количество реальных задач сводится к линейной задаче наименьших
квадратов, которую можно сформулировать следующим образом.

Пусть даны действительная m(n–матрица A ранга k(min(m,n) и
действительный m–вектор b. Найти действительный n–вектор x0,
минимизирующий евклидову длину вектора невязки Ax–b.

Пусть y – n–мерный вектор фактических значений, x – n–мерный вектор
значений независимой переменной, b – коэффициенты в аппроксимации y
линейной комбинацией n заданных базисных функций (:

.

. Покажем это. Возведем в квадрат выражение для е:

.

=0

.

Следует отметить, что последнее выражение имеет в определенной степени
формальный характер, т. к. решение нормальных уравнений, как правило,
проводится без вычисления обратной матрицы (метод Крамера) такими
методами как метод Гаусса, Холесского и т. д.

по результатам измерений. Мы получаем переопределенную систему:

или Xb=y. Нам понадобится матрица XTX и обратная к ней:

Метод точечной квадратичной аппроксимации (метод наименьших квадратов)
не предполагает, что мы должны приближать экспериментальные данные лишь
с помощью прямых линий. Во многих экспериментах связи могут быть
нелинейными, и было бы глупо искать для этих задач линейные соотношения.
Пусть, например, мы работаем с радиоактивным материалом. Тогда выходными
данными у являются показания счетчика Гейгера в различные моменты
времени t. Пусть наш материал представляет собой смесь двух
радиоактивных веществ, и мы знаем период полураспада каждого из них, но
не знаем, в каких пропорциях эти вещества смешаны. Если обозначить их
количества через С и D, то показания счетчика будут вести себя подобно
сумме двух экспонент, а не как прямая:

. (1)

На практике, поскольку радиоактивность измеряется дискретно и через
различные промежутки времени, показания счетчика не будут точно

Рис. 1. Аппроксимация прямой линией.

, и (1) выполняется лишь приближенно:

Если мы имеем более двух показаний, m>2, то точно разрешить эту систему
относительно C и D практически невозможно. Но мы в состоянии получить
приближенное решение в смысле минимальных квадратов.

Ситуация будет совершенно иной, если нам известны количества веществ C и
D и нужно отыскать коэффициенты ( и (. Это нелинейная задача наименьших
квадратов, и решить ее существенно труднее. Мы по–прежнему будем
минимизировать сумму квадратов ошибок, но сейчас она уже не будет
многочленом второй степени относительно ( и (, так что приравнивание
нулю производной не будет давать линейных уравнений для отыскания
оптимальных решений.

Глава 1. Метод наименьших квадратов

1.1. Задача наименьших квадратов

Задача наименьших квадратов заключается в минимизация евклидовой длины
вектора невязок (( Ax-b ((.

Теорема 1. Пусть А – m(n–матрица ранга k, представленная в виде

A=HRKT (2)

где H ортогональная m(m матрица; R – m(n–матрица вида

, (3)

где: R11 – kxk–матрица ранга k; K – ортогональная kxk–матрица.
Определим вектор

(4)

и введем новую переменную

. (5)

как единственное решение системы R11y1=g1. Тогда:

, где y2 произвольно.

. (6)

Доказательство. В выражении для квадрата нормы невязки заменим A на HRKT
в соответствии с (2) и умножая на ортогональную матрицу HT (умножение
на ортогональную матрицу не меняет евклидову норму вектора) получим

(7)

Далее из (3) и (5) следует, что

.

Из (4) следует

Подставляя оба последних выражения в (7) получим

имеем

,

. Теорема доказана.

Всякое разложение матрицы А типа (2) мы будем называть ортогональным
разложением А. Заметим, что решение минимальной длины, множество всех
решений и минимальное значение для задачи минимизации ((Ax-b((
определяются единственным образом. Они не зависят от конкретного
ортогонального разложения.

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

1.2. Ортогональное вращение Гивенса

.Существует ортогональная 2(2 матрица такая, что:

(8)

Доказательство. Положим:

.

Далее прямая проверка.

Матрица преобразования представляет собой матрицу вращений

или отражений

1.3. Ортогональное преобразование Хаусхолдера

, (9)

. В обоих случаях H – симметричная и ортогональная матрица. Покажем
это:

.

, где

а ( = +1, при положительной первой компоненте вектора х и = –1, при
отрицательной.

действительная матрица. Любую действительную матрицу можно привести в
треугольному виду

и получаем следующее:

1.4. Сингулярное разложение матриц

Пусть X – матрица данных порядка Nxp, где N>p, и пусть r – ранг матрицы
X. Чаще всего r=p, но приводимый ниже результат охватывает общий случай,
он справедлив и при условии rk, что противоречит предположению 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 есть произвол. Пусть ( –
сингулярное число А, имеющее кратность l. Это значит, что для
упорядоченных сингулярных чисел найдется индекс I такой, что

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

.

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

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

Например:

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

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

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

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

, удовлетворяющий следующим условиям:

;

.

, удовлетворяющий условиям 1 – 3 для нормы вектора:

;

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

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

.

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

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

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

(7)

.

.

0

b

d

f

h

j

l

®

°

a

ae

ae

e

e

h

h

?e

4 6 h j l n p I ?

T

V

?

?

?

?

1/4

i

?

o

oe

o

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

/o{o{o{ouopoioipopo

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

:u?e?eu?eaeYOYae?ae1/2??ae?eae?ae ’?ae?aeu?aeoaehOae

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

?

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

h

Wc h

h

wbwdwOwOw-x
x”x(x:x1. Трехдиагональная матрица – это частный случай
хесенберговой матрицы.

PAGE

PAGE 2

2

/

1

2

2

2

1

2

2

/

1

2

2

2

1

1

)

(

=

,

)

(

v

v

v

s

v

v

v

c

?

?

?

Похожие документы
Обсуждение
    Заказать реферат
    UkrReferat.com. Всі права захищені. 2000-2019