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

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

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

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

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

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

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

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

математики          

Исполнил:                                                           

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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ............................................................................................................................................................................. 3

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

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

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

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

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

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

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

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

2.1. Алгоритмы.................................................................................................................................................. 25

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

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

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

ЗАКЛЮЧЕНИЕ................................................................................................................................................................... 38

ЛИТЕРАТУРА..................................................................................................................................................................... 39

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

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

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

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

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

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

.

Задача состоит в том, чтобы в уравнении подобрать такие b, чтобы минимизировать суммы квадратов отклонений e=y–Xb, где X – есть так называемая матрица плана, в которой строками являются n–мерный вектора с компонентами, зависящими от xj:  каждая строка соответствует определенному значению xj. Коэффициенты можно найти решая нормальные уравнения , откуда . Покажем это. Возведем в квадрат выражение для е:

т. к.   .

Это выражение имеет экстремум в точке, где =0

Откуда и получаем .

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

Пример. Пусть заданы результаты четырех измерений (рис. 1): y=0 при x=0; y=1 при x=1; y=2 при x=3; y=5 при x=4. Задача заключается в том, чтобы провести через эти точки прямую  таким образом, чтобы сумма квадратов отклонений была минимальна. Запишем уравнение, описывающее проведение прямой  по результатам измерений. Мы получаем переопределенную систему:

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

Тогда решение b=(XTX)-1XTy по методу наименьших квадратов будет иметь вид

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

.                                                   (1)

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

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

соответствовать (1). Вместо этого мы имеем серию показаний счетчика  в различные моменты времени , и (1) выполняется лишь приближенно:

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

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

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. Тогда:

1.       Все решения задачи о минимизации ||Ax-b|| имеют вид , где y2 произвольно.

2.       Любой такой вектор  приводит к одному и тому же вектору невязки .                                             (6)

3.       Для нормы r справедливо

4.       Единственным решением минимальной длины является вектор

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

                    (7)

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

.

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

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

Последнее выражение имеет минимальное значение  при R11y1=g1, а в этом уравнении единственным решением является , так как ранг матрицы R11 равен к. Общее решение y выражается формулой , где y2 произвольно. Для вектора  имеем

,

что устанавливает равенство (3). Среди векторов  наименьшую длину имеет тот, для которого y2=0. Отсюда следует, что решением наименьшей длины будет вектор . Теорема доказана.

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

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

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

Лемма. Пусть дан 2–вектор , причем  либо .Существует ортогональная 2´2 матрица такая, что:

                      (8)

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

.

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

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

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

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

Применяется для преобразования матриц к диагональному виду. Матрица преобразования представляет из себя следующее выражение: ,                                    (9)

или, если вектор v нормирован, т.е. используется вектор единичной длины , то . В обоих случаях H – симметричная и ортогональная матрица. Покажем это:

.

Отсюда следует: что , т.е. симметричность и ортогональность. В комплексном случае матрица   эрмитова[1] и унитарна[2]. Предположим, что дан вектор х размерности m, тогда существует матрица H  такая, что , где

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

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

Далее принимаем во внимание то, что  и получаем следующее:

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

Пусть X – матрица данных порядка Nxp, где N>p, и пусть r – ранг матрицы X. Чаще всего r=p, но приводимый ниже результат охватывает общий случай, он справедлив и при условии r<p.

Теорема о сингулярном разложении утверждает, что

                                                            (10)

где V – матрица порядка Nxr, столбцы которой ортонормированы, т.е. ; U – матрица с ортонормированными столбцами порядка pxr; таким образом, ; Г – диагональная матрица порядка rxr, диагональные элементы которой , называемые сингулярными числами матрицы X, положительны. Используя диагональные элементы  матрицы Г, столбцы  матрицы V, и столбцы  матрицы U, сингулярное разложение матрицы X, определяемое по (10), можно записать в виде:

                                      (11)

Имеют место следующие фундаментальные соотношения.

·        Квадратная симметричная матрица XX' порядка NxN, имеет r положительных и N–r нулевых собственных чисел. Положительными собственными числами XX' являются , а соответствующими собственными значениями – . Таким образом, сингулярные значения  – это положительные квадратные корни из положительных собственных чисел матрицы XX', а столбцы матрицы V – соответствующие собственные векторы.

·        Квадратная симметричная матрица X'X порядка pxp, имеет r положительных и p–r нулевых собственных чисел. Положительными собственными числами X'X являются , а соответствующими собственными значениями – , таким образом, сингулярные значения  – это положительные квадратные корни из положительных собственных чисел матрицы X'X, а столбцы матрицы U – соответствующие собственные векторы.

Положительные собственные числа матрицы X'X и XX' совпадают и равны . Более того, если um – собственный вектор матрицы X'X, а vm – собственный вектор матрицы XX', соответствующие одному и тому же собственному числу , то um и vm связаны следующим соотношением

                        (12)

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

.                                                (13)

Исследование матрицы X'X в факторном анализе называется R-модификацией, а XX' – Q–модификацией. Соотношения (12)–(13) показывают, что результаты Q–модификации можно получить по результатам R–модификации и наоборот.

Практическая последовательность нахождения сингулярного разложения следующая.

1.   Вычисляется X'X или XX', в зависимости от того, порядок какой матрицы меньше. Предположим, что в данном случае это X'X.

2.   Вычисляются положительные собственные числа  матрицы X'X и соответствующие им собственные векторы .

3.   Находятся сингулярные числа .

4.   Вычисляются  по соотношению (11).

Пусть в разложении (11) собственные числа расположены в порядке убывания. Аппроксимационные свойства соотношения (11) являются еще более фундаментальными, чем само соотношение. Эти свойства вытекают из решения следующих двух задач.

Задача 1. Дана симметричная матрица S, порядка pxp и ранга r с неотрицательными собственными значениями. Требуется найти симметричную матрицу Т, размерности pxp, с неотрицательными собственным значениями заданного ранга k, k<r, являющуюся наилучшей аппроксимацией матрицы S в смысле наименьших квадратов.

Задача 2. Дана прямоугольная матрица X, порядка Nxp и ранга r и число k<r. требуется найти матрицу W порядка pxp и ранга k, наилучшим образом аппроксимирующую матрицу X в смысле наименьших квадратов.

Решением этих двух задач являются матрицы:

                                  (14)

представляющие собой суммы k первых членов в соответствующем разложении. Матрицы T и W называются наилучшими в смысле наименьших квадратов “матричными аппроксимациями меньшего ранга” для матриц S и X соответственно. Свойство наилучшей аппроксимации в смысле наименьших квадратов можно выразить следующим образом: матрица T ближе всего к матрице S в том смысле, что сумма квадратов всех элементов матрицы S–T минимальна. Аналогично матрица W ближе всего к матрице X в том смысле, что минимальна сумма квадратов элементов матрицы X–W. Мерой близости или качества аппроксимации считается относительная величина , т.е. сумма r–k наименьших собственных чисел матрицы X’X. Иногда мерой качества аппроксимации считается относительная величина

                                              (15)

или функция от нее.

Рассмотрим наиболее распространенный случай p=r.

Матрица S может быть ковариационной матрицей p линейно независимых переменных. Матрица T также может представлять собой ковариационную матрицу p переменных, но так как ранг матрицы T k<p, то эти p переменных линейно зависят от k переменных. Таким образом, p исходных переменных, ковариационная матрица которых есть S, могут быть приближенно выражены через k переменных.

Во второй задаче исходную матрицу X порядка Nxp можно выразить как X=VГU’, где V – матрица порядка Nxp c ортонормированными столбцами; Г – диагональная матрица порядка pxp, а U – квадратная ортогональная матрица порядка pxp.

Матричную аппроксимацию меньшего ранга W можно представить в виде

где  – состоит из первых k столбцов матрицы V,  – из первых k строк или столбцов матрицы Г, а  – из первых k столбцов матрицы U. поскольку W»X, то

                                               (16)

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