СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ - (диплом)
p>Некоторые вычислительные задачи поразительно чувствительны к изменению данных. Этот аспект численного анализа не зависит от плавающей арифметики или выбранного алгоритма.Например:
Найти корни полинома: (x-2)2=10-6
Корни этого уравнения есть 2+10-3 и 2-10-3. Однако изменение свободного члена на 10-6 может вызвать изменение в корнях, равное 10-3. Операции с матрицами, как правило, приводят к решению систем линейных уравнений. Коэффициенты матрицы в правой части системы линейных уравнений редко известны точно. Некоторые системы возникают из эксперимента, и тогда коэффициенты подвержены ошибкам наблюдения. Коэффициенты других систем записываются формулами, что влечет за собой ошибки округлений. В связи с этим необходимо знать, как влияют ошибки в коэффициентах матрицы на решение. Именно для этого вводится понятие обусловленности матрицы.
По определению число обусловленности есть величина . Для более подробного описания числа обусловленности нам понадобится понятие нормы в пространстве векторов и матриц.
Нормой вектора x в пространстве векторов называется функционал, обозначаемый , удовлетворяющий следующим условиям: положительной определенности –
положительной однородности – ;
неравенству треугольника – .
Нормой квадратной матрицы А в пространстве матриц, согласованной с нормой вектора называется функционал , удовлетворяющий условиям 1 – 3 для нормы вектора: ;
мультипликативное неравенство –
Наиболее употребимы следующие нормы для векторов:
норма суммы модулей
евклидова норма
норма максимума модуля
Нормы матриц:
Здесь являются сингулярными числами [3 Сингулярным разложением произвольной mґn–матрицы называется разложение вида , где U и V – ортогональные матрицы, а S –диагональная матрица с неотрицательными диагональными элементами. Диагональные элементыS (, i=1, ...., k, где k=min(m, n)) называются сингулярными числами А. Это множество чисел однозначно определяется матрицей А. Число ненулевых сингулярных чисел равно рангу А. ] матрицы А; это положительные значения квадратных корней из собственных значений матрицы АТА (которая при невырожденной матрице А положительно определена [4Симметричная матрица положительно определена, если все ее собственные значения положительны. Положительно определенная матрицаP обладает также тем свойством, что для всех . ], в противном случае положительно полуопределена (неотрицательно определена [5Симметричная матрица неотрицательно определена, если все ее собственные значения неотрицательны. Такая матрицаP обладает также тем свойством, что для всех . Для произвольной mxn–матрицы А матрица симметрична и неотрицательно определена. Она положительно определена, если rankA=n. ]) и поэтому имеет только вещественные собственные значения і0). Для вещественных симметричных матриц сингулярные числа равны абсолютным величинам собственных значений: .
Умножение вектора х на матрицу А приводит к новому вектору Ах, норма которого может очень сильно отличаться от нормы вектора х. Область изменений может быть задана двумя числами
Максимум и минимум берутся по всем ненулевым векторам. Заметим, что если А вырождена, то m=0. Отношение M/m называется числом обусловленности матрицы А, (7)
Рассмотрим норму обратной [6 Обратной матрицей для квадратной невырожденной матрицы А называется такая матрица, для которой . ] матрицы . Для матрицы А существует сингулярное разложение , тогда , отсюда . Аналогично для обратной матрицы и . Отсюда следует, что собственные числа матрицы – 1/ есть величины, обратные собственным числам матрицы – . При этом очевидно, что . Из последнего выражения вместе с (7) следует . Таким образом обусловленность матрицы равна произведению нормы матрицы на норму обратной матрицы.
Рассмотрим систему уравнений Ax=b, и другую систему, полученную изменением правой части: A(x+Dx)=b+Db . Будем считать Db ошибкой в b, а Dx соответствующей ошибкой в x, хотя нам нет необходимости считать ошибки малыми. Поскольку A(Dx)=Db, то определения M и m немедленно приводят к неравенствам Следовательно , при m№0,
Величина есть относительное изменение правой части, а величина –относительная ошибка, вызванная этим изменением. Аналогичные выкладки можно провести не только с элементами вектора правой части но и с элементами самой матрицы А и найти зависимость между относительным изменением элементов матрицы и относительной ошибкой вызванной этим изменением. Отсюда следует, что число обусловленности выполняет роль множителя в увеличении относительной ошибки. Приведем некоторые свойства числа обусловленности. Ясно, что Mіm и поэтому cond(А)і1. Если Р – матрица перестановок [7Матрица перестановки - это квадратная матрица, столбцы которой получаются перестановкой столбцов единичной матрицы. Матрица перестановки ортогональна. ], то компоненты вектора Px лишь порядком отличаются от компонент вектора х. Отсюда следует, что и cond(P)=1 . В частности cond(I)=1. Если А умножается на скаляр с, то cond(cА)= cond(А). Если D – диагональная матрица, то глава 2. Реализация сингулярного разложения
2. 1. Алгоритмы
QR–алгоритм начинается с разложения матрицы по Грамму-Шмидту , затем меняются местами сомножители: Эта матрица подобна первоначальной, Этот процесс продолжается, причем собственные значения не изменяются:
Эта формула описывает QR–алгоритм без сдвигов. Обычно время которое тратится на такой процесс пропорционально кубу размерности матрицы– n3. Необходимо процесс ускорить, для чего используется предварительное приведение матрицыА к форме Хессенберга [8 Матрица А хессенбергова (верхняя хессенбергова) если для j1. Трехдиагональная матрица – это частный случай хесенберговой матрицы. ]. При использовании матрицы Хессенберга время процесса пропорционально 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 определяется собственным значением нижнего минора (размерности 2ґ2) матрицы Mi. При таком выборе параметра s метод обладает глобальной и почти всегда кубичной сходимостью. 2. 3. Пример сингулярного разложения
Проведем преобразование Хаусхолдера на матрице ,
К первой компоненте первого столбца прибавляем норму первого столбца, получим . Пусть Преобразованная матрица A2 вычисляется следующим образом. Для первого столбца имеем:
так как
Таким образом, в первый столбец были введены нули и его длина не изменилась. Получим второй столбец:
для третьего столбца:
окончательно,
Столбцы матрицы A2 получаются вычитанием кратных вектора v1 из столбцов A1. Эти кратные порождаются скалярными произведениями, а не отдельными элементами, как в гауссовом исключении.
