IV Канатников А.Н., Крищенко А.П. Линейная алгебра (1081385), страница 44
Текст из файла (страница 44)
Теорема 11.1. Если матрица А невырождена и ))ЬА(( < ))А '~! (11.2) где (( (! — произвольная кольцевая норма матриц, то матрица А = А+ ЬА тоже невырождена и верна следующая оценка для относительной погрешности решения Юх < (БА+ БЬ), с(А) (11. 3) где ох = '9х — х))/))х)(; х — решение возмущенной системы Ах=Ь; Ь=Ь+ЬЬ. 41 Замечание 11.1. Если выполняется неравенство (11.2), то с(А)6А = 9А(()~А '~! — = ((ЬА6 (~А '~! <1.
В этом случае в правой части неравенства (11.3) деления на нуль нет, и она положительная. 11.2. ЯВ-разложение. Сингулярное разложение Одним иэ вариантов мультипликативного разложения матрицы является Яй-раэлохсеиие, т.е. представление матрицы А в виде А = ЯВ, где Я вЂ” ортогональная матрица, а В— верхняя треугольная матрица. Построение ЯВ-разложения матрицы А сводится к преобразованию этой матрицы путем последовательного умножения на ортогональные матрицы Р1, Рг, ..., Р, специального вида так, чтобы в результате получилась верхняя треугольная матрица В = Р,...Р1А.
Полагая Я = (Р,...Р|) ~, получаем представление А = ЯВ, где матрица Я, согласно свойствам 7А и 7.5 ортогональных матриц (см. с. 200), является ортогональной. 11.2. ЯК-рззлолтелие. Сингулярное рлзлотлевие 297 Применяют два основных способа построения последовательности матриц Рт, ..., Р„. Для описания этих способов удобно интерпретировать ортогональные матрицы как матприиы ортпогональных оператпоров в стпандартпном ортпонормированном базисе в Й", а матрицу А как набор столбцов ат, ..., а„,представляющих собой координатны векторов ат, ...,а„ из 'и". Тогда ОА = О(ат ... а„) = (Оат ... Оа„), где использованы свойства умножения блочных матриц, и поэтому умножение матрицы А слева на ортогональную матрицу О равносильно применению к каждому из векторов а; ортогонального оператора О, матрицей которого является О.
Таким образом, задача сводится к последовательности ортпогональных преобразований систпемы вектпоров ам ..., а„, в результате которой столбцы координат этой системы образуют верхнюю треугольную матрицу. Метод вращений. В качестве элементарного ортогонального преобразования рассмотрим преобразование поворота 911(у) в двумерном подпространстве, образованном т-м и т'-м векторами стпандартпного базиса в К" (зто надпространство естественно ассоциировать с плоскостью). Матрица такого преобразования имеет вид сову — вшу 911(У) = втпу сову и отличается от единичной элементами на пересечении тьй и,1-й строк, т'-го и у-го столбцов.
Эти элементы образуют матрицу 298 г е итеРАциОнные метОды второго порядка — я1пф'( з1пх сезар /' которая на плоскости (в пространстве Ъг) определяет поворот вектора на угол у. Если примененить преобразование с матрицей ф (~р) к произвольному вектору а = (ам ...,и„), то изменятся только его 1-я и у-я координаты, а остальные останутся прежними. При этом за счет выбора угла ~р можно добиться, чтобы г-я координата вектора обнулилась. Для этого при 1 ( у достаточно выбрать ~р из условия а;яшар+ аусоя1г = О.
Рассмотрим последовательность преобразований Я11(у1 ), у = 2,в, в результате которых вектор а1, представленный первым столбцом матрицы А, превратится в вектор а1 ~††т = (а1~1 0 ... 0) . При этом векторыаг, ..., а„, представленные остальными столбцами матрицы А, преобразуются в некотот рые векторы аг1, ..., а1 с координатами (а1~ ...
а~~~) = 2,п. Далее рассмотрим последовательность преобразований 1Ъ1(<Ргу) у = З,о, при которой вектор аг~ переходит в вектор т аг ~— — (а1г а~~ 0 ... 0) . При этом вектор а1 ~не изменится, так как преобразуются лишь те координаты, которые у этого вектора равны нулю. Продолжая процесс, мы получим систему векторов а(, ..., а'„', координаты которых составляют верхнюю треугольную матрицу. Последовательность ортогональных матриц Щ~рб), 1 = 1, и — 1, у = 1+1, и, и есть искомая последовательность Рм ..., Р,.
Метод отражений. В этом методе в качестве элементарных ортогональных преобразований берут преобразования симметрии. Рассмотрим произвольный ненулевой веятпор хе из К". Пусть 'Н~. — ортогональное дополнение одномерного линейного подпрострачства Яе = зрап(хе). Согласно следствию 3.1, каждый вектор х Е К" представляется в виде х = Лхе+ хг, 1ЬЗ. ЯВ рееложевие. Сввгулервое резеожевие 299 где Лхв — ортогональная проекция вектора х на Нв, а х1— его ортогональная составллюи4аа. Рассмотрим преобразование Ях = ЩЛхв+ х1) = х1 — Лхе = х — 2Лхв (рис.
11.1). Нетрудно показать, что это преобразование является линейным. Кроме того, согласно теореме Пи4агора, ~фх)~~ = !)х1~~~+ ~~Лхв~~~ = ~~х)~~ (здесь рассматривается евклидова норма, соответствующая стан- ах ',Я е дартному скалярному произведению в ж"). Поэтому линейный оператор Ч является ортогонвльным. Лучше всего в качестве вектора хв взять вектор еь с единичной нормой.
Тогда Л = (х,еь), а линейный оператор Ч записывается в виде Рис. 11.1 Ях = х — 2(х, еь)еь, 9Щ = 1. Линейный оператор Ц указанного вида будем называть оепрахсением. Покажем, что для любых ненулевых векторов х и у из К" найдется такое отражение О, что Ох = ар, т.е. вектор х преобразуется в вектор, коллинеарный и. Из определения отраженил следует, что Ох — х = -2(х, л)еь. Значит, искомое отражение должно определяться единичным вектором еь, коллинеарным вектору Ох — х = ау — х. Отметим, что в этом случае число а определено с точностью до знака, так как йауэ = )(Ох~! = ~)х~! и, значит, )а~ = 9х)~ / Щ~.
Выбор знака— это выбор одного из двух возможных решений (рис. 11.2). Зоо 11. ИТЕРАЦИОННЫЕ МЕТОДЫ Итак, выбираем а = !!х!! /!!у!! и вычисляем вектор хо —— а;у-' х'- — х. Если этот вектор нулеЗЪ1 вои, то векторы х и у коллиггг неарны (любой из них принад- лежит линейной оболочке друогу о,у, гого), и в качестве отражения следует взять тогхдесогоенныа Рис. 11.2 оператпор. Если же хо ф О, то отражение О задается единичным вектором гг = хо/ !!хо!!. Действительно, !!ау — х!!'=(ау-х, и-х) = = а !!у!! — 2а(х, у)+ !!х!!г = 2(!!х !!~ - а(х, у)). Поэтому Ох=х — 2(х,и)тг=х — 2 ' (ау — х) = (х, ау — х) !!г =х+ ' г(ау — х) =х+(ау — х) =ау.
а(х, у) — !!х!! !!г Столбцы матрицы А будем трактовать как столбцы координат некоторых векторов а1, ..., а„из К". Пусть е1, ..., е„— стандартный ортонормированный базис в й". Рассмотрим ортогональное преобразование Рм которое вектор а1 переводит в вектор а1 1— — а1е1. Если вектор а1 ненулевой, это преобразование строится описанным выше способом, а если вектор а1 нулевой, то в качестве Р1 можно взять тождественный оператор. Оператор Р1 преобразует векторы аг, ..., аг в некоторые векторы аг1, ..., а1.
Рассмотрим оператор Рг, который преобРазУет вектоР аг1 = (а1г а~~ ... а~,г) в некотоРый вектоР т Раг =аг г— — (агг аггг 0 ... О) . Длл этого в качестве вектоРа У 11.2. ЯЯ-разложение. Сингуллриое разложение ЗО1 'можно взять любую линейную коаебннанию базисных векторов е1 и е2. Некоторая свобода выбора оператора Р2 позволяет при этом добиться того, чтобы вектор н1, а значит и а11, не изменялся. Действительно, все векторы, попадающие в ортогональное дополнение Я~, остаются без изменений, и нам достаточно потребовать, чтобы вектор же = Рзаз — а2 = ау — а2, задающий отражение Р2, был ортогонален вектору е1.
Это и будет означать, что вектор е1 попадает в линейное подпространство Я~, которое состоит иэ всех векторов, ортогональных же. Указанное условие будет выполняться, если оператор Р2 переводит ВЕКтера2-а12Е1ив л (О а22 ... анз) ВВЕКтера2Е2,таККаКзтОт 1 1 г 1 1 оператор определяется вектором же = сезе2 — (а2 — а12е1), имеющим нулевую первую координату и потому ортогональным е1.
Итак, оператор Р2 не изменяет вектор а1, преобразует вектор а2 в вектор а2 = (а12 а22 0 ... 0), а векторы а1, у = 3, п, в 1 2 2 2 2 1 некоторые векторы а~2. Продолжая процесс, мы на й-м шаге строим преобразование, которое не меняет базисные векторы е;, 1 = 1, и — 1, но Й-1 а-1 ь-1 пРеобРазУет вектоР аь — а ь е1 —...-аь аее 1 в некотоРыи вектор, коллинеарный еа. Если й-й столбец исходной матрицы оказался нулевым, то и вектор аь будет нулевым и в процессе преобразований Р1, ..., Ра 1 он останется нулевым. В этом случае в качестве очередного оператора Рц можно взять тождественный оператор. Процесс ортоаонвлизации. К ЯВ-разложению непосредственное отношение имеет процесс оршогонализапии Грален — Шмидп1а. Любую квадратную невырожденную матрицу А порядка п можно рассматривать как совокупность столбЦов, пРеДставлЯюЩих собой кооРДинаты вектоРов 21, ..., Ун в некотором фиксированном базисе и-мерного евклидова пространства Е.
Так как матрица А невырождена, ее столбцы линейно независимы, поэтому векторы 21, ..., ун образуют в Е базис, вообще говоря, неортонормированный. Процесс ортогоналиэации при- 302 П. ИТЕРАЦИОННЫЕ МЕТОДЫ водит к новому, уже ортонормнрованному базису ег, ..., е„. Характерной особенностью процесса ортогонализации являет-: ся то, что матрица перехода нз нового базиса е к старому Ь является верхней треугольной. Действительно, из соотношений (3.9) следует, что У1 = !!д1!!ем Уг = (Уг, е1) е1 + !!дг!! ег, Уз (Уз е1) е1+ (УЗ е2) е2+ !!дз!1ег У„= (У„, е1) е1 +... + (У„, е„|) е„1+ /!д,Д е„, а матрица перехода из нового базиса е в старый У имеет вид !!д1 !! (Уг, е1) ... (У„, е1) В О !!дг!! " (У, ег) о о ...
!1д„!! Записав координаты векторов е в фиксированном базисе евклидова пространства, получим ортогональную матрицу Я. Исходная матрица А и ортогональная матрица Я связаны между собой соотношениями А = ЯВ, т.е. мы получили ЯВ-разложение матрицы А. Еще раз отметим, что процесс ортогонализации Грама— Шмидта может использоваться для получения ЯВ-разложения, если матрица является невырожденной. Кроме того, оказывается, что такой метод уступает методу вращений и методу отражений с точки зрения точности вычислений. Единственность ЯВ-разложения. Несложно привести пример, показывающий, что ЯВ-разложение данной матрицы не является однозначным. Действительно, представление Е = = ЕЕ единичной матрицы можно рассматривать в качестве ее ЯВ-разложения, так как единичная матрица является одновременно ортогональной и верхней треугольной.
Но и представле- 11.2. ЯК-разлохеяяа Сингулярное раэлохеяие зоз ние Е = (-Е) ( — Е) также является ЯВ-разложением единичной матрицы. Природу неоднозначности, которую иллюстрирует приведенный пример, раскрывает следующее рассуждение. Пусть Р— квадратная матрица, которая одновременно является и ортогональной, и верхней треугольной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
