Xreferat.com » Рефераты по математике » СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

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

что для упорядоченных сингулярных чисел найдется индекс I такой, что

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

Здесь Р – ортогональная ll–матрица Если 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. ;

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

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

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

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

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

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

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

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

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

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

(7)

Рассмотрим норму обратной6 матрицы .

Для матрицы А существует сингулярное разложение , тогда , отсюда . Аналогично для обратной матрицы и . Отсюда следует, что собственные числа матрицы – 1/ есть величины, обратные собственным числам матрицы – . При этом очевидно, что . Из последнего выражения вместе с (7) следует . Таким образом обусловленность матрицы равна произведению нормы матрицы на норму обратной матрицы.

Рассмотрим систему уравнений Ax=b, и другую систему, полученную изменением правой части: A(x+x)=b+b . Будем считать b ошибкой в b, а x соответствующей ошибкой в x, хотя нам нет необходимости считать ошибки малыми. Поскольку A(x)=b, то определения M и m немедленно приводят к неравенствам Следовательно , при m0,

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

Приведем некоторые свойства числа обусловленности. Ясно, что Mm и поэтому cond(А)1. Если Р – матрица перестановок7, то компоненты вектора Px лишь порядком отличаются от компонент вектора х. Отсюда следует, что и cond(P)=1 . В частности cond(I)=1. Если А умножается на скаляр с, то cond(cА)= cond(А). Если D – диагональная матрица, то

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

2.1. Алгоритмы

QR–алгоритм начинается с разложения матрицы по Грамму-Шмидту , затем меняются местами сомножители: Эта матрица подобна первоначальной, Этот процесс продолжается, причем собственные значения не изменяются:

Эта формула описывает QR–алгоритм без сдвигов. Обычно время которое тратится на такой процесс пропорционально кубу размерности матрицы – n3. Необходимо процесс ускорить, для чего используется предварительное приведение матрицы А к форме Хессенберга8 а также используется алгоритм со сдвигом. Форма Хессенберга представляет из себя верхнюю треугольную матрицу (верхняя форма Хессенберга) у которой сохранена одна диагональ ниже главной, а элементы ниже этой диагонали равны нулю. Если матрица симметрична, то легко видеть, что матрица Хессенберга превращается в трехдиагональную матрицу9. При использовании матрицы Хессенберга время процесса пропорционально 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) – преобразований Гивенса. Отсюда, где

а матрица вычисляется аналогично с заменой на .

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

Этот процесс часто называют процессом преследования. Так как , то , и Mi+1 – трехдиагональная матрица, точно так же, как и Mi. Начальный угол можно выбрать так, чтобы преобразование было QR–преобразованием со сдвигом, равным s.

Обычный QR–алгоритм со сдвигом можно записать в следующем виде:

где – верхняя треугольная матрица. Следовательно, . Параметр сдвига s определяется собственным значением нижнего минора (размерности 22) матрицы Mi. При таком выборе параметра s метод обладает глобальной и почти всегда кубичной сходимостью.

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

Проведем преобразование Хаусхолдера на матрице ,

К первой компоненте первого столбца прибавляем норму первого столбца, получим . Пусть

Преобразованная матрица A2 вычисляется следующим образом. Для первого столбца имеем:

так как

Таким образом, в первый столбец были введены нули и его длина не изменилась. Получим второй столбец:

для третьего столбца:

окончательно,

Столбцы матрицы A2 получаются вычитанием кратных вектора v1 из столбцов A1. Эти кратные порождаются скалярными произведениями, а не отдельными элементами, как в гауссовом исключении.

Прежде чем вводить дальнейшие нули под диагональю, преобразованием вида A3=A2Q1, получают нули в первой строке. Нули уже стоящие в первом столбце, не должны быть испорчены, длина первого столбца должна быть сохранена; поэтому при внесении нулей в первую строку нельзя менять первый элемент строки, изменяем второй элемент и зануляем третий. Для матрицы большего размера на этом шаге было бы получено 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) мы проводим разложение для матрицы плана. При этом основное уравнение y=Xb приобретает вид y=UVTb. Отсюда следует, что коэффициенты b можно получить решая уравнение UTy=VTb. Т.е. если все j, j=1,…,n, являющиеся диагональными элементами отличны от нуля, то последнее уравнение разрешимо и

, где .

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

Отбрасывание чисел j, меньших, чем , приводит к уменьшению числа обусловленности с до . Поскольку число обусловленности является множителем в увеличении ошибки, то следствием будет более надежное определение коэффициентов .

Продемонстрируем использование метода на следующем примере:


t

Y

1900 75994575
1910 91972266
1920 105710620
1930 123203000
1940 131669275
1950 150697361
1960 179323175
1970 203211926

Следует определить значение Y при X =1980.

Если аппроксимировать эти данные квадратичным многочленом и использовать двойную точность, то в результате получим следующие коэффициенты . При одинарной точности вычислений коэффициенты будут иметь значения . У этих двух наборов коэффициентов не совпадают даже знаки. Если такую модель использовать для предсказания, то для коэффициентов, вычисленных с двойной точностью, прогноз будет Y=227780000 , а для обычной точности Y=145210000. Ясно, что второй набор коэффициентов бесполезен. Исследуем достоверность результатов. Матрица плана для данного примера имеет размеры 8 3


Рис. 2. Численный пример

Ее сингулярные числа: .

Число обусловленности равно , что говорит о близости базисных функций 1, t и t2 к линейной зависимости. Для того, чтобы исправить ситуацию можно предпринять одну из следующих мер.

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

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

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

Во–вторых, можно улучшить ситуацию заменой базиса. Модели

гораздо более удовлетворительны. Важно при этом то, что независимая переменная преобразуется из интервала [1900, 1970] в какой–нибудь более приемлемый интервал вроде [0, 70] или, еще лучше, [–3.5, 3.5]. Числа обусловленности при этом равны 5750 и 10.7 соответственно. последнее значение более чем приемлемо даже при счете с обычной точностью.

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

Во втором случае, после преобразования матрицы плана ее обусловленность сильно уменьшается, и, соответственно, повышается точность расчетов.

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

ЗАКЛЮЧЕНИЕ

В работе описаны компьютерные методы решения задачи наименьших квадратов. Для использования данных методов составлена соответствующая программа на алгоритмическом языке FORTRAN. Программа апробирована, результаты тестирования показывают работоспособность программы.

Результаты данной разработки могут

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: