Учебная работа № 1982. СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

Учебная работа № 1982. СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

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

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

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

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

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

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

математики

Исполнил:

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

Владикавказ 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 –вектор x 0 , минимизирующий евклидову длину вектора невязки Ax–b .

Пусть yn мерный вектор фактических значений, 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 . Нам понадобится матрица XT X и обратная к ней:

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

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

. (1)

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

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

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

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

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

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

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

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

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

A= HRKT (2)

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

, (3)

где: R 11k xk матрица ранга k ; K ортогональная k xk матрица. Определим вектор

(4)

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

. (5)

Определим как единственное решение системы R 11 y 1 =g 1 . Тогда:

1. Все решения задачи о минимизации ||Axb || имеют вид , где y 2 произвольно.

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

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

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

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

(7)

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

.

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

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

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

,

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

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

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

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

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

(8)

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

.

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

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

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

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

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

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

.

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

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

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

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

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

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

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

(10)

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

(11)

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

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

· Квадратная симметричная матрица X’X порядка p xp , имеет 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 , порядка p xp и ранга r с неотрицательными собственными значениями. Требуется найти симметричную матрицу Т , размерности p xp , с неотрицательными собственным значениями заданного ранга k , k<r , являющуюся наилучшей аппроксимацией матрицы S в смысле наименьших квадратов.

Задача 2. Дана прямоугольная матрица X , порядка N xp и ранга r и число k<r . требуется найти матрицу W порядка p xp и ранга 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 порядка N xp можно выразить как X=VГU’ , где V – матрица порядка N xp c ортонормированными столбцами; Г – диагональная матрица порядка p xp , а U – квадратная ортогональная матрица порядка p xp .

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

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

(16)

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

(17)

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

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

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

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

ортогональна, и Q 2 Q 1 A имеет в первых двух столбцах нули под главной диагональю. Продолжая таким образом, можно построить произведение, состоящее максимум из 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 , A T , Q T теоремы 3.

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

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

(19)

Учебная работа № 1982. СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

Яндекс.Метрика