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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Математический факультет Кафедра прикладной математики ДИПЛОМНЫЙ ПРОЕКТ сингулярное разложение в линейной задаче метода наименьших квадратов Заведующий кафедрой прикладной математики Исполнил Научный руководитель Владикавказ 2002 СОДЕРЖАНИЕ ВВЕДЕНИЕ 3 Глава 1. Метод наименьших квадратов 7 1.1.

Задача наименьших квадратов 2. Ортогональное вращение Гивенса 3. Ортогональное преобразование Хаусхолдера 4. Сингулярное разложение матриц 11 1.5. QR разложение 6. Число обусловленности 20 глава 2. Реализация сингулярного разложения 1. Алгоритмы 2. Реализация разложения 3. Пример сингулярного разложения 29 глава 3.

Использование сингулярного разложения в методе наименьших квадратов 33 ЗАКЛЮЧЕНИЕ 38 ЛИТЕРАТУРА 39 ПРИЛОЖЕНИЕ 1. Исходные тексты программы 40 ПРИЛОЖЕНИЕ 2. контрольный пример 45 ВВЕДЕНИЕ Метод наименьших квадратов обычно используется как составная часть некоторой более общей проблемы. Например, при необходимости проведения аппроксимации наиболее часто употребляется именно метод наименьших квадратов.

На этом подходе основаны регрессионный анализ в статистике, оценивание параметров в технике и т.д. Большое количество реальных задач сводится к линейной задаче наименьших квадратов, которую можно сформулировать следующим образом. Пусть даны действительная mn матрица A ранга kminm,n и действительный m вектор b. Найти действительный n вектор x0, минимизирующий евклидову длину вектора невязки Ax b. Пусть y n мерный вектор фактических значений, x n мерный вектор значений

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

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

Пример. Пусть заданы результаты четырех измерений рис. 1 y0 при x0 y1 при x1 y2 при x3 y5 при x4. Задача заключается в том, чтобы провести через эти точки прямую таким образом, чтобы сумма квадратов отклонений была минимальна. Запишем уравнение, описывающее проведение прямой по результатам измерений. Мы получаем переопределенную систему или Xby. Нам понадобится матрица

XTX и обратная к ней Тогда решение bXTX-1XTy по методу наименьших квадратов будет иметь вид Таким образом, оптимальная прямая задается уравнением Метод точечной квадратичной аппроксимации метод наименьших квадратов не предполагает, что мы должны приближать экспериментальные данные лишь с помощью прямых линий. Во многих экспериментах связи могут быть нелинейными, и было бы глупо искать для этих задач линейные

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

двух экспонент, а не как прямая . 1 На практике, поскольку радиоактивность измеряется дискретно и через различные промежутки времени, показания счетчика не будут точно Рис. 1. Аппроксимация прямой линией. соответствовать 1. Вместо этого мы имеем серию показаний счетчика в различные моменты времени , и 1 выполняется лишь приближенно Если мы имеем более двух показаний, m 2, то точно разрешить эту систему относительно

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

для отыскания оптимальных решений. Глава 1. Метод наименьших квадратов 1. Задача наименьших квадратов Задача наименьших квадратов заключается в минимизация евклидовой длины вектора невязок Ax-b . Теорема 1. Пусть А mn матрица ранга k, представленная в виде AHRKT 2 где H ортогональная mm матрица R mn матрица вида , 3 где R11 kxk матрица ранга k K ортогональная kxk матрица.

Определим вектор 4 и введем новую переменную . 5 Определим как единственное решение системы R11y1g1. Тогда 1. Все решения задачи о минимизации Ax-b имеют вид , где y2 произвольно. 2. Любой такой вектор приводит к одному и тому же вектору невязки . 6 3. Для нормы r справедливо 4. Единственным решением минимальной длины является вектор Доказательство. В выражении для квадрата нормы невязки заменим

A на HRKT в соответствии с 2 и умножая на ортогональную матрицу HT умножение на ортогональную матрицу не меняет евклидову норму вектора получим 7 Далее из 3 и 5 следует, что . Из 4 следует Подставляя оба последних выражения в 7 получим Последнее выражение имеет минимальное значение при R11y1g1, а в этом уравнении единственным решением является , так как ранг матрицы

R11 равен к. Общее решение y выражается формулой , где y2 произвольно. Для вектора имеем , что устанавливает равенство 3. Среди векторов наименьшую длину имеет тот, для которого y20. Отсюда следует, что решением наименьшей длины будет вектор . Теорема доказана. Всякое разложение матрицы А типа 2 мы будем называть ортогональным разложением

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

Хаусхолдера, оставляющие нормы столбцов и строк матриц неизменными. 1.2. Ортогональное вращение Гивенса Лемма. Пусть дан 2 вектор , причем либо .Существует ортогональная 22 матрица такая, что 8 Доказательство. Положим . Далее прямая проверка. Матрица преобразования представляет собой матрицу вращений или отражений 1.3. Ортогональное преобразование Хаусхолдера Применяется для преобразования матриц к диагональному виду.

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

. и унитарна Матрица А унитарная если , где сопряженная матрица Предположим, что дан вектор х размерности m, тогда существует матрица H такая, что , где а 1, при положительной первой компоненте вектора х и 1, при отрицательной. Доказательство. Положим действительная матрица. Любую действительную матрицу можно привести в треугольному виду Далее принимаем во внимание то, что и получаем следующее 1.4.

Сингулярное разложение матриц Пусть X матрица данных порядка Nxp, где N p, и пусть r ранг матрицы X. Чаще всего rp, но приводимый ниже результат охватывает общий случай, он справедлив и при условии r p. Теорема о сингулярном разложении утверждает, что 10 где V матрица порядка Nxr, столбцы которой ортонормированы, т.е. U матрица с ортонормированными столбцами порядка pxr таким образом,

Г диагональная матрица порядка rxr, диагональные элементы которой , называемые сингулярными числами матрицы X, положительны. Используя диагональные элементы матрицы Г, столбцы матрицы V, и столбцы матрицы U, сингулярное разложение матрицы X, определяемое по 10, можно записать в виде 11 Имеют место следующие фундаментальные соотношения. Квадратная симметричная матрица XX порядка NxN, имеет r положительных и

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

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

XX, соответствующие одному и тому же собственному числу , то um и vm связаны следующим соотношением 12 Эти соотношения дают возможность вычислять , зная , и наоборот. В компактной форме эти соотношения можно записать следующим образом . 13 Исследование матрицы XX в факторном анализе называется R-модификацией, а XX Q модификацией. Соотношения 12 13 показывают, что результаты

Q модификации можно получить по результатам R модификации и наоборот. Практическая последовательность нахождения сингулярного разложения следующая. 1. Вычисляется XX или XX, в зависимости от того, порядок какой матрицы меньше. Предположим, что в данном случае это XX. 2. Вычисляются положительные собственные числа матрицы XX и соответствующие им собственные векторы . 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 или функция от нее. Рассмотрим наиболее распространенный случай pr.

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

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

U. поскольку WX, то 16 При умножении этой матрицы справа на получаем 17 Матрица порядка pxk определяет преобразование строк матрицы X из евклидова p мерного пространства в евклидово k мерное пространство уравнение 16 показывает, что существует преобразование матрицы X порядка Nxp в матрицу порядка Nxk. Матрица X содержит N точек в p мерном евклидовом пространстве, которые приближенно могут быть спроектированы

в k мерное евклидово пространство. матрица определяет координаты этих точек в k мерном евклидовом пространстве. 1.5. QR разложение Теорема 2. Пусть А mn матрица. Существует ортогональная mm матрица Q такая, что в матрице QAR под главной диагональю стоят только нулевые элементы. Доказательство. Выберем ортогональную mm матрицу Q в соответствии с преобразованием

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

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

Существуют ортогональная mm матрица Q и mn матрица перестановки P такие, что , 18 где R верхняя треугольная кк матрица ранга к. Доказательство. Выберем матрицу перестановки Р таким образом, чтобы первые к столбцов матрицы AP, были линейно независимы. Согласно теореме 2, найдется ортогональная mm матрица Q такая, что QAP будет верхней треугольной. Поскольку первые к столбцов

АР линейно независимы, это будет верно для первых к столбцов QAP. Все элементы матрицы QAP, стоящие на пересечении строк с номерами к1 m и столбцов с номерами к1 n, будут нулями. В противном случае rankQAP k, что противоречит предположению rankAk. Итак, QAP имеет форму, указанную правой частью 4. Теорема доказана. Подматрицу RT из правой части 18 можно теперь преобразовать к компактной форме, требуемой

от матрицы R из теоремы 2. Это преобразование описывает следующая лемма. Лемма 1. Пусть RT кк матрица, причем R имеет ранг к. Существует ортогональная nn матрица W такая, что где нижняя треугольная матрица ранга к. Доказательство леммы вытекает из теоремы 3, если отождествить величины n, k, RT, W из формулировки леммы с соответствующими величинами m, n,

AT, QT теоремы 3. Используя теорему 3 и лемму 1 можно доказать следующую теорему. Теорема 4. Пусть А mn матрица ранга к . Найдутся ортогональная mm матрица Н и ортогональная nn матрица К такие, что 19 причем R11 невырожденная треугольная кк матрица. Заметим, что выбором Н и К в уравнении 19 можно добиться, чтобы R11 была верхней или нижней треугольной.

В 19 матрица А представлена произведением AHRKT, где R некоторая прямоугольная матрица, ненулевые компоненты которой сосредоточены в невырожденной треугольной подматрице. Далее мы покажем, что эту невырожденную подматрицу R можно упростить далее до невырожденной диагональной матрицы. Это разложение тесно связано со спектральным разложением симметричных неотрицательно определенных матриц

ATA и AAT см. 11. Теорема 5. Пусть А mn матрица ранга k. Тогда существуют ортогональная mm матрица U, ортогональная nn матрица V и диагональная mn матрица S такие, что UTAVS, AUSVT 20 Матрицу S можно выбрать так, чтобы ее диагональные элементы составляли невозрастающую последовательность все эти элементы неотрицательны и ровно к из них строго положительны.

Диагональные элементы S называются сингулярными числами А. Докажем сперва лемму для специального случая mnrankA. Лемма 2. Пусть А nn матрица ранга n. Тогда существует ортогональная nn матрица U, ортогональная nn матрица V и диагональная nn матрица S такие, что UTAVS, AUSVT и последовательные диагональные элементы

S положительны и не возрастают. Доказательство леммы. Положительно определенная симметричная матрица ATA допускает спектральное разложение ATAVDVT, 21 где V ортогональная nn матрица, а D диагональная матрица, причем диагональные элементы D положительны и не возрастают. Определим S как диагональную nn матрицу, диагональные элементы которой суть положительные квадратные корни из соответствующих диагональных элементов

D. Таким образом DSTSS2, S-1DS-1I. 22 Определим матрицу UAVS-1 23 Из 21, 22, 23 и ортогональности V следует, что UTUS-1VTATAVS-1S-1DS-1I т.е. U ортогональна. Из 23 и ортогональности V выводим USVTAVS-1SVTAVVTA Лемма доказана. Доказательство теоремы 5. Пусть AHRKT, где H, R, KT имеют свойства, указанные в теореме 4.

Так как R11 из 19 невырожденная треугольная кк матрица, то согласно лемме 2 , можно написать 24 Здесь и ортогональные кк матрицы, а невырожденная диагональная матрица, диагональные элементы которой положительны и не возрастают. Из 24 следует, что матрицу R в уравнении 19 можно записать в виде 25 где ортогональная mm матрица ортогональная nn матрица ортогональная mn матрица Теперь, определяя U и V формулами 26 заключаем из 24 26, что

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

I такой, что Положим kminm,n, и пусть Q ортогональная кк матрица вида Здесь Р ортогональная ll матрица Если AUSVT сингулярное разложение А и sisil-1, то сингулярным разложением А будет также и , где . 1.6. Число обусловленности Некоторые вычислительные задачи поразительно чувствительны к изменению данных. Этот аспект численного анализа не зависит от плавающей арифметики или выбранного алгоритма.

Например Найти корни полинома x-2210-6 Корни этого уравнения есть 210-3 и 2-10-3. Однако изменение свободного члена на 10-6 может вызвать изменение в корнях, равное 10-3. Операции с матрицами, как правило, приводят к решению систем линейных уравнений. Коэффициенты матрицы в правой части системы линейных уравнений редко известны точно. Некоторые системы возникают из эксперимента, и тогда коэффициенты подвержены ошибкам наблюдения.

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

и матриц. Нормой вектора x в пространстве векторов называется функционал, обозначаемый , удовлетворяющий следующим условиям 1 положительной определенности 2 положительной однородности 3 неравенству треугольника . Нормой квадратной матрицы А в пространстве матриц, согласованной с нормой вектора называется функционал , удовлетворяющий условиям 1 3 для нормы вектора 1 2 3 4 мультипликативное неравенство Наиболее употребимы следующие нормы для векторов норма суммы модулей евклидова норма норма максимума

модуля Нормы матриц Здесь являются сингулярными числами Сингулярным разложением произвольной mn матрицы называется разложение вида , где U и V ортогональные матрицы, а S диагональная матрица с неотрицательными диагональными элементами. Диагональные элементы S , i1 k, где kminm,n называются сингулярными числами А. Это множество чисел однозначно определяется матрицей

А. Число ненулевых сингулярных чисел равно рангу А. матрицы А это положительные значения квадратных корней из собственных значений матрицы АТА которая при невырожденной матрице А положительно определена Симметричная матрица положительно определена, если все ее собственные значения положительны. Положительно определенная матрица P обладает также тем свойством, что для всех в противном случае положительно

полуопределена неотрицательно определена Симметричная матрица неотрицательно определена, если все ее собственные значения неотрицательны. Такая матрица P обладает также тем свойством, что для всех . Для произвольной mxn матрицы А матрица симметрична и неотрицательно определена. Она положительно определена, если rankAn. и поэтому имеет только вещественные собственные значения 0.

Для вещественных симметричных матриц сингулярные числа равны абсолютным величинам собственных значений . Умножение вектора х на матрицу А приводит к новому вектору Ах, норма которого может очень сильно отличаться от нормы вектора х. Область изменений может быть задана двумя числами Максимум и минимум берутся по всем ненулевым векторам.

Заметим, что если А вырождена, то m0. Отношение Mm называется числом обусловленности матрицы А, 7 Рассмотрим норму обратной Обратной матрицей для квадратной невырожденной матрицы А называется такая матрица, для которой . матрицы . Для матрицы А существует сингулярное разложение , тогда , отсюда . Аналогично для обратной матрицы и . Отсюда следует, что собственные числа матрицы 1 есть величины,

обратные собственным числам матрицы . При этом очевидно, что . Из последнего выражения вместе с 7 следует . Таким образом обусловленность матрицы равна произведению нормы матрицы на норму обратной матрицы. Рассмотрим систему уравнений Axb, и другую систему, полученную изменением правой части Axxbb . Будем считать b ошибкой в b, а x соответствующей ошибкой в x, хотя нам нет необходимости считать

ошибки малыми. Поскольку Axb, то определения M и m немедленно приводят к неравенствам Следовательно , при m0, Величина есть относительное изменение правой части, а величина относительная ошибка, вызванная этим изменением. Аналогичные выкладки можно провести не только с элементами вектора правой части но и с элементами самой матрицы А и найти зависимость между относительным изменением элементов матрицы и относительной ошибкой вызванной этим изменением.

Отсюда следует, что число обусловленности выполняет роль множителя в увеличении относительной ошибки. Приведем некоторые свойства числа обусловленности. Ясно, что Mm и поэтому condА1. Если Р матрица перестановок Матрица перестановки - это квадратная матрица, столбцы которой получаются перестановкой столбцов единичной матрицы. Матрица перестановки ортогональна то компоненты вектора

Px лишь порядком отличаются от компонент вектора х. Отсюда следует, что и condP1 . В частности condI1. Если А умножается на скаляр с, то condcА condА. Если D диагональная матрица, то глава 2. Реализация сингулярного разложения 2.1. Алгоритмы QR алгоритм начинается с разложения матрицы по

Грамму-Шмидту , затем меняются местами сомножители Эта матрица подобна первоначальной, Этот процесс продолжается, причем собственные значения не изменяются Эта формула описывает QR алгоритм без сдвигов. Обычно время которое тратится на такой процесс пропорционально кубу размерности матрицы n3. Необходимо процесс ускорить, для чего используется предварительное приведение матрицы А к форме Хессенберга Матрица А хессенбергова верхняя хессенбергова если для j i 1 сохраняется

одна диагональ ниже главной диагонали. Если матрица симметричная то хессенбергова матрица становится трехдиагональной. а также используется алгоритм со сдвигом. Форма Хессенберга представляет из себя верхнюю треугольную матрицу верхняя форма Хессенберга у которой сохранена одна диагональ ниже главной, а элементы ниже этой диагонали равны нулю. Если матрица симметрична, то легко видеть, что матрица

Хессенберга превращается в трехдиагональную матрицу Симметричная матрица А есть трехдиагональная при для i-j 1. Трехдиагональная матрица это частный случай хесенберговой матрицы При использовании матрицы Хессенберга время процесса пропорционально 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 преобразований Гивенса. Отсюда, где а матрица вычисляется аналогично с заменой на . Пусть начальный угол произволен, однако следующие значения угла необходимо выбирать так, чтобы матрица

Ji1 имела ту же форму, что и Ji. Таким образом не аннулирует ни одного элемента матрицы, но добавляет элемент аннулирует но добавляет аннулирует но добавляет и т.д наконец, аннулирует и ничего не добавляет. Этот процесс часто называют процессом преследования. Так как , то , и Mi1 трехдиагональная матрица, точно так же, как и Mi. Начальный угол можно выбрать так, чтобы преобразование было

QR преобразованием со сдвигом, равным s. Обычный QR алгоритм со сдвигом можно записать в следующем виде где верхняя треугольная матрица. Следовательно Параметр сдвига s определяется собственным значением нижнего минора размерности 22 матрицы Mi. При таком выборе параметра s метод обладает глобальной и почти всегда кубичной сходимостью. 2.3. Пример сингулярного разложения Проведем преобразование Хаусхолдера на матрице , К первой компоненте первого столбца прибавляем норму

первого столбца, получим . Пусть Преобразованная матрица A2 вычисляется следующим образом. Для первого столбца имеем так как Таким образом, в первый столбец были введены нули и его длина не изменилась. Получим второй столбец для третьего столбца окончательно, Столбцы матрицы A2 получаются вычитанием кратных вектора v1 из столбцов

A1. Эти кратные порождаются скалярными произведениями, а не отдельными элементами, как в гауссовом исключении. Прежде чем вводить дальнейшие нули под диагональю, преобразованием вида A3A2Q1, получают нули в первой строке. Нули уже стоящие в первом столбце, не должны быть испорчены, длина первого столбца должна быть сохранена поэтому при внесении нулей в первую строку нельзя менять первый элемент строки, изменяем второй элемент и зануляем третий.

Для матрицы большего размера на этом шаге было бы получено n 2 нуля. Преобразование порождается первой строкой A2 Строка матрицы A3 с номером i получается по формуле . Таким образом, из каждой строки A2 вычитается надлежащее кратное . Это дает матрицу Поскольку первая компонента нулевая, то нули первого столбца

A2 сохраняются в A3, Так как Q1 ортогональная, то длина каждой строки в A3 равна длине соответствующей строки в A2. Теперь можно добиться новых нулей под диагональю, не испортив полученных ранее Поскольку ранг этой матрицы равен лишь 2, то теперь третий столбец имеет на диагонали и под диагональю элементы порядка ошибки округления. Эти элементы обозначены в матрице через 0.000, чтобы отличить их от элементов, в точности равных нулю.

Если бы матрица имела полный ранг, то нужно было бы выполнить еще одно преобразование, чтобы получить нули в третьем столбце Если бы не ошибки округлений, то в данном примере третий диагональный элемент был бы точным нулем. Элементы под диагональю во всех столбцах указаны как точные нули, потому что преобразования так и строились, чтобы получить там нули. Последнее преобразование H3 в этом примере могло бы быть тождественным, однако тогда оно не было бы хаусхолдеровым отражением.

Фактически использование H3 попутно изменяет знак элемента 1.080 в матрице A4. Получилась искомая двухдиагональная матрица, и первый этап закончен. Прямое использование ортогональных преобразований не позволяет получить какие либо новые нули. Для общего порядка n нужно n преобразований H и n 2 преобразований Q, чтобы достигнуть данного места. Число преобразований не зависит от строчной размерности m, но от

m зависит работа, затрачиваемая на выполнение каждого преобразования. глава 3. Использование сингулярного разложения в методе наименьших квадратов При использовании метода сингулярного разложения SVD Singular Value Decomposition мы проводим разложение для матрицы плана. При этом основное уравнение yXb приобретает вид yUVTb.

Отсюда следует, что коэффициенты b можно получить решая уравнение UTyVTb. Т.е. если все j, j1 n, являющиеся диагональными элементами отличны от нуля, то последнее уравнение разрешимо и , где . Однако такое решение не всегда желательно, если некоторые j малы. Для правильного использования метода SVD мы должны ввести границу отражающую точность входных данных и точность использованной плавающей арифметики. Всякое j, большее, чем , приемлемо, и соответствующее

вычисляется по 1.20. Любое j, меньшее, чем , рассматривается как пренебрежимо малое, и соответствующему может быть придано произвольное значение. С этой произвольностью значений связана не единственность набора коэффициентов, получаемых методом наименьших квадратов. Изменения входных данных и ошибки округлений, меньшие, чем , могут привести к совершенно другому набору коэффициентов, определяемых этим методом. Поскольку обычно желательно, чтобы эти коэффициенты были по

возможности малы, то полагаем 0, если j . Отбрасывание чисел j, меньших, чем , приводит к уменьшению числа обусловленности с до . Поскольку число обусловленности является множителем в увеличении ошибки, то следствием будет более надежное определение коэффициентов . Продемонстрируем использование метода на следующем примере tY Следует определить значение Y при X 1980. Если аппроксимировать эти данные квадратичным многочленом

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

Y145210000. Ясно, что второй набор коэффициентов бесполезен. Исследуем достоверность результатов. Матрица плана для данного примера имеет размеры 8 3 Рис. 2. Численный пример Ее сингулярные числа . Число обусловленности равно , что говорит о близости базисных функций 1, t и t2 к линейной зависимости. Для того, чтобы исправить ситуацию можно предпринять одну из следующих мер.

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

взаимного уничтожения слагаемых при вычислении квадратичного многочлена. Прогнозное значение Y1980 будет соответственно 212910000 и 214960000. Эффект обычной точности еще заметен, однако результаты уже не являются катастрофическими. Можно также определить набор нулевых коэффициентов, соответствующих пренебрежимо малому сингулярному числу. Вот эти коэффициенты . Для значений t от 1900 до 1970 величина функции не превосходит 0.0017,

поэтому при любом коэффициенты можно изменить , и при этом значения, выдаваемые моделью изменятся не более чем на 0.0017. Любой из четырех перечисленных нами наборов коэффициентов можно получить из другого подобным изменением. Во вторых, можно улучшить ситуацию заменой базиса. Модели гораздо более удовлетворительны. Важно при этом то, что независимая переменная преобразуется из интервала 1900, 1970 в какой нибудь более приемлемый интервал вроде 0, 70 или, еще лучше,

3.5, 3.5. Числа обусловленности при этом равны 5750 и 10.7 соответственно. последнее значение более чем приемлемо даже при счете с обычной точностью. Удобнее всего воспользоваться стандартными способами статистического анализа, т.е. матрицу плана преобразуем к стандартизованному варианту Матрица стандартизованных данных есть матрица наблюдений с нулевым средним и дисперсией 1. Это означает, что данные берутся в виде отклонений от среднего, которое мы считаем равным 0, вводим

нормировку деля каждый член столбца матрицы на корень квадратный из суммы квадратов отклонений. Во втором случае, после преобразования матрицы плана ее обусловленность сильно уменьшается, и, соответственно, повышается точность расчетов. Данную программу можно использовать и при решении системы линейных уравнений вместо методов Гаусса, Жордана, Холесского и пр. В приложении 2 приведен пример расчета линейной системы, которая изначально не может быть решена этими методами вследствие вырожденности матрицы коэффициентов.

Тем не менее, исследуемый метод дает нам правильное решение. ЗАКЛЮЧЕНИЕ В работе описаны компьютерные методы решения задачи наименьших квадратов. Для использования данных методов составлена соответствующая программа на алгоритмическом языке FORTRAN. Программа апробирована, результаты тестирования показывают работоспособность программы. Результаты данной разработки могут быть использованы в самых разнообразных расчетах, где необходимо

провести аппроксимацию данных заданными функциями. ЛИТЕРАТУРА 1. Беллман Р. Введение в теорию матриц. -М. Наука, 1969, 368с. 2. Гантмахер Ф.Р. Теория матриц. -М. Наука, 1988, 548с. 3. Ланкастер П. Теория матриц. -М. Наука, 1982, 387с. 4. Лоусон Ч Хенсон Р. Численное решение задач наименьших квадратов.

М. Статистика, 1979, 447с 5. Марчук Г.И. Методы вычислительной математики. М. Наука, 1980 6. Мэйндоналд Дж. Вычислительные алгоритмы в прикладной статистике. М. Финансы и статистика, 1988, 350с 7. Стренг Г. Линейная алгебра и ее применения. М. Мир, 1980, 454с 8. Уилкинсон Дж Райнш К. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра, М. Машиностроение, 1976, 390с 9.

Фаддеев Д.К Фаддеева В.Н. Вычислительные методы линейной алгебры. -М. Физматгиз, 1963, 536с. 10. Форсайт Дж Малькольм М Моулер К. Машинные методы математических вычислений. М. Мир, 1980, 279с 11. Харебов К.С. Компьютерные методы решения задачи наименьших квадратов и проблемы собственных значений. Владикавказ. Изд-во СОГУ, 1995, 76 с.

ПРИЛОЖЕНИЕ 1. Исходные тексты программы REAL A3,3, U3,3, V3,3, SIGMA3, WORK3,Y3,C3,Y03 INTEGER I,IERR, J, M, N, NM OPEN 6,FILESVD.OUT,STATUSUNKNOWN,FORMFORMATTE D OPEN 5,FILE SVD.IN,STATUSUNKNOWN,FORMFORMATTED 140 FORMAT3I5 150 FORMAT4E15.7 READ5,140 NM,M,N DO 131

I1,M READ5,150 AI,J,J1,N 131 CONTINUE READ 5,150 YI,I1,M CALL SVDNM,M,N,A,SIGMA TRUE U TRUE V,IERR,WORK IFIERR.NE.0 WRITE 6,2 IERR 2 FORMAT15H TROUBLE.IERR,I4 WRITE6,120 120 FORMATМАТРИЦА А DO 121 I1,M WRITE6,130 AI,J,J1,N 130 FORMAT8E15.7 121 CONTINUE WRITE 6,160

YI,I1,N 160 FORMATПРАВЫЕ ЧАСТИ8E15.7 210 FORMATСИНГУЛЯРНЫЕ ЧИСЛА WRITE6,210 DO 3 J1,N WRITE6,6 SIGMAJ 3 CONTINUE SMASIGMA1 SMISIGMA1 DO 211 J2,N IFSIGMAJ.GT.SMA SMASIGMAJ IFSIGMAJ.LT.SMI.AND.SIGMAJ.GT.0. SMISIGMAJ 211 CONTINUE OBUSMASMI 230 FORMATЧИСЛО ОБУСЛОВЛЕННОСТИ,E15.7 WRITE6,230

OBU SIGMA10. DO 30 J1,N IFSIGMAJ .GT. SIGMA1 SIGMA1SIGMAJ CJ0. 30 CONTINUE TAUSIGMA10.1E-6 DO 60 J1,N IFSIGMAJ.LE.TAU GO TO 60 S0. DO 40 I1,N SSUI,JYI 40 CONTINUE SSSIGMAJ DO 50 I1,N CICI SVI,J 50 CONTINUE 60 CONTINUE write 6,560 WRITE 6,6 CI,I1,3 DO 322 J1,N SS0. DO 321 I1,M 321

SSAJ,ICISS 322 Y0JSS write 6,570 WRITE 6,6 Y0I,I1,3 C WRITE6,7 C DO 4 I1,M C WRITE6,6 UI,J,J1,N C4 CONTINUE C WRITE6,7 C DO 5 I1,N C WRITE6,6 VI,J,J1,N C5 CONTINUE 6 FORMAT3E15.7 560 format2x,roots 570 format2x,right 7 FORMAT1H STOP E N D SUBROUTINE SVDNM,M,N,A,W,MATU,U,

MATV,V,IERR,RV1 REAL ANM,N,WN,UNM,N,VNM,N,RV1N LOGICAL MATU,MATV IERR0 DO 100 I1,M DO 100 J1,N UI,JAI,J 100 CONTINUE G0.0 SCALE0.0 ANORM0.0 DO 300 I1,N LI1 RV1ISCALEG G0.0 S0.0 SCALE0.0 IFI.GT.M GO TO 210 DO 120 KI,M 120 SCALESCALEABSUK,I IFSCALE.EQ.0.0 GO TO 210 DO 130 KI,

M UK,IUK,ISCALE SSUK,I2 130 CONTINUE FUI,I G-SIGNSQRTS,F HFG-S UI,IF-G IFI.EQ.N GO TO 190 DO 150 JL,N S0.0 DO 140 KI,M 140 SSUK,IUK,J FSH DO 150 KI,M UK,JUK,JFUK,I 150 CONTINUE 190 DO 200 KI,M 200 UK,ISCALEUK,I 210 WISCALEG G0.0 S0.0 SCALE0.0 IFI.GT.M.OR.I.EQ.N GO TO 290

DO 220 KL,N 220 SCALESCALEABSUI,K IFSCALE.EQ.0.0 GO TO 290 DO 230 KL,N UI,KUI,KSCALE SSUI,K2 230 CONTINUE FUI,L G-SIGNSQRTS,F HFG-S UI,LF-G DO 240 KL,N 240 RV1KUI,KH IFI.EQ.M GO TO 270 DO 260 JL,M S0.0 DO 250 KL,N 250 SSUJ,KUI,K DO 260 KL,N UJ,KUJ,KSRV1K 260 CONTINUE 270

DO 280 KL,N 280 UI,KSCALEUI,K 290 ANORMAMAX1ANORM,ABSWIABSRV1I 300 CONTINUE IF.NOT.MATV GO TO 410 DO 400 II1,N IN1-II IFI.EQ.N GO TO 390 IFG.EQ.0.0 GO TO 360 DO 320 JL,N 320 VJ,IUI,JUI,LG DO 350 JL,N S0.0 DO 340 KL,N 340 SSUI,KVK,J DO 350 KL,N VK,JVK,JSVK,I 350 CONTINUE 360 DO 380

JL,N VI,J0.0 VJ,I0.0 380 CONTINUE 390 VI,I1.0 GRV1I LI 400 CONTINUE 410 IF.NOT.MATU GO TO 510 MNN IFM.LT.N MNM DO 500 II1,MN IMN1-II LI1 GWI IFI.EQ.N GO TO 430 DO 420 JL,N 420 UI,J0.0 430 IFG.EQ.0.0 GO TO 475 IFI.EQ.MN GO TO 460 DO 450 JL,N S0.0 DO 440 KL,M 440 SSUK,

IUK,J FSUI,IG DO 450 KI,M UK,JUK,JFUK,I 450 CONTINUE 460 DO 470 JI,M 470 UJ,IUJ,IG GO TO 490 475 DO 480 JI,M 480 UJ,I0.0 490 UI,IUI,I1.0 500 CONTINUE 510 DO 700 KK1,N K1N-KK KK11 ITS0 520 DO 530 LL1,K L1K-LL LL11 IFABSRV1LANORM.EQ.ANORM GO TO 565 IFABSWL1ANORM.EQ.ANORM GO TO 540 530

CONTINUE 540 C0.0 S1.0 DO 560 IL,K FSRV1I RV1ICRV1I IFABSFANORM.EQ.ANORM GO TO 565 GWI HSQRTFFGG WIH CGH S-FH IF.NOT.MATU GO TO 560 DO 550 J1,M YUJ,L1 ZUJ,I UJ,L1YCZS UJ,I-YSZC 550 CONTINUE 560 CONTINUE 565 ZWK IFL.EQ.K GO TO 650 IFITS.EQ.30 GO TO 1000 ITSITS1 XWL

YWK1 GRV1K1 HRV1K FY-ZYZG-HGH2.0HY GSQRTFF1.0 FX-ZXZHYFSIGNG,F-HX C1.0 S1.0 DO 600 I1L,K1 II11 GRV1I YWI HSG GCG ZSQRTFFHH RV1I1Z CFZ SHZ FXCGS G-XSGC HYS YYC IF.NOT.MATV GO TO 575 DO 570 J1,N XVJ,I1 ZVJ,I VJ,I1XCZS VJ,I-XSZC 570 CONTINUE 575 ZSQRTFFHH WI1Z IFZ.EQ.0.0 GO

TO 580 CFZ SHZ 580 FCGSY X-SGCY IF.NOT.MATU GO TO 600 DO 590 J1,M YUJ,I1 ZUJ,I UJ,I1YCZS UJ,I-YSZC 590 CONTINUE 600 CONTINUE RV1L0.0 RV1KF WKX GO TO 520 650 IFZ.GE.0.0 GO TO 700 WK-Z IF.NOT.MATV GO TO 700 DO 690 J1,N 690 VJ,K-VJ,K 700 CONTINUE GO TO 1001 1000 IERRK 1001 RETURN

E N D ПРИЛОЖЕНИЕ 2. контрольный пример Входные данные матрица изначально сингулярна первая строка равна сумме второй и третьей с обратным знаком 3 3 3 .320E 02 .140E 02 .740E 02 -0.240E 02 -0.10E 02 -0.570E 02 -0.80E 01 -0.40E 01 -0.170E 02 -0.140E 02 0.130E 02 0.10E 01 Полученный результат МАТРИЦА А .320E02 .140E02 .740E02 240E02 10E02 570E02 80E01 40E01 170E02 ПРАВЫЕ ЧАСТИ 140E02 .130E02 .10E01 СИНГУЛЯРНЫЕ ЧИСЛА .1048255E03 .7310871E-06 .1271749E01

ЧИСЛО ОБУСЛОВЛЕННОСТИ .1433830E09 Корни .1215394E01 .1821742E01 1059419E01 Правые корни после проверки 140E02 .130E02 .101E01 Видно, что правые части соответствуют начальным данным. Решение верно.