Дж. Деммель - Вычислительная линейная алгебра, страница 36

Насколько велика может быть обратная ошибка? Другими словами, насколько велика может быть матрица 6А, такая, что Я ' 1А+ 6А)Я =,У+ 6 У? Имеем 6А = обло ', поэтому можно лишь сказать, что !)6А)( < '5Щ !)бд)).'ОЯ '!) = 01е)к15)((А)(. Итак, 'пбА!) может быть много больше, чем е!)А)(, что исключает свойство обратной устойчивости. О Вместо того чтобы работать с соотношением Я 'АЯ = д, где о может быть как угодно плохо обусловленной матрицей, мы для обеспечения устойчивости будем брать В из множества ортогональных матриц 1для которых кг(Я) = 1).

При таком ограничении мы не сможем получить столь простую каноническую форму, как форма Жордана, однако форма, которую мы найдем, почти столь же хороша. Теорема 4.2 (каноническая форма Шура). Для произвольной матрицы А найдутся унитарнол матрица ц и верхнетреугольная матрица Т, такие, что Я*АО = Т. Собственными значениями матрицы А являются диагональные элементы матрицьг Т.

Доказательство. Применим индукцию по и. Очевидно, что утверждение теоремы верно для 1 х 1-матрицы А. Пусть теперь Л вЂ” произвольное собственное значение, а и — соответствующий собственный вектор, нормированный так, чтобы ~(ийз = 1. Возьмем У таким образом, чтобы У = [и, У] была квадратной унитарной матрицей. 10тметим, что Л и и могут быть комплексными даже для вещественной матрицы А.) Имеем У* А У= -, А 1гг,У)= Теперь, как и в доказательстве предложения 4.3, можем написать и'Аи = (Л аш Ли"и = Л и У*Аи = ЛУ'и = О поэтому У'АУ = ~ - .

По индуктив~ О Агг ному предположению, существует такая унитарная матрица Р, что матрица Р"АггР = Т верхняя треугольная. Тогда О РТР* О Р О Т О Р' поэтому матрица О Р' О Р О Т 158 Глава 4. Несимметричиаи проблема собственных значений О верхняя треугольная, а Я = У вЂ” унитарная матрица, что и требовалось. О Заметим, что форма Шура ие единственна, поскольку собственные значения могут располагаться на диагонали матрицы Т в произвольном порядке. Описанная нами процедура вводит комплексные числа даже тогда, когда матрица А вещественна. Однако для вещественной А мы предпочитаем каноническую форму, которая сама вещественна, потому что такую форму дешевле вычислять. Как отмечено в начале данного параграфа, это означает, что мы должны пожертвовать треугольной канонической формой и согласиться на использование блочно-треугольной формы. Теорема 4.3 (вещественная каноническая форма Шура).

Для произвольной вещественной матрицы А найдется вещественная ортогональная матрица й такая, что матрица йт АИ = Т верхняя квазитреугвльиая. Это означает, что Т вЂ” верхнял блочно-треугольная матрица с диагональными блохами размеров 1 х 1 и 2 х 2. Собственны.ми значениями матрицьг являются собственные значения ее диагональных блоков. Блохи размера 1 х 1 соответствуют вещественным собственным значениям, а блоки размера 2 х 2 — сопряжен ным нарам колтлексных собственных значений. Доказательство. Как и вьппе, применим рассуждение по индукции. Если собственное значение Л вещественно, то ему соответствует вещественный собственный вектор. В этом случае доказательство проводится, как в предыдущей теореме.

Для комплексного Л обозначим через и соответствующий (необходимо1 комплексный собственный вектор: Аи = Ли. Так как Аи = Ай = Ли, то Л и й также составляют собственную пару. Обозначим через ия = зи + -'й я иг = — ',. и — — ',. и вещественную и мнимую части вектора и. Тогда зрап1ия, иг1 = грал(и,й11 есть двумерное инвариантное надпространство матрицы А.

Положим С = ~ил,иг] и пусть У = ЯЯ есть Я11-разложение матрицы О. Итак, подпространство гран(Я~ = зрап(ия,иг1 инвариантно относительно А. Выберем Я так, чтобы матрица У = [Я,ф была квадратной и ортогональной. Имеем У А У= дт А" ЮФ= дтА~ дтАя Поскольку О определяет инвариантное надпространство, найдется 2 х 2- матрица В, такая, что АЯ = ЯВ. Теперь, как и в доказательстве предложения 4.3, можем написать ЯтАЯ = ЯтЯВ = В и ОтАО = ЦтЯВ = О, так что У АУ = ~ -т - ~. Остается применить индуктивное предположение к матрице ЯтАО..

О 4.2.1. Вычисление собственных векторов с помощью формы Шура Пусть Я*АД = Т есть форма Шура матрицы А. Если Тх = Лх, то АЯх = (~Тх = ЛСдх, т. е. Ях — собственный вектор матрицы А. Таким образом, чтобы найти собственные векторы для А, достаточно найти их для Т. 159 4.3. Теория возмущений Предположим, что кратность собственного значения Л = Хи равна 1 (т. е. Л вЂ” простое собственное значение). Запишем равенство (Т вЂ” ЛХ)х = О в виде = ГГ"~' ...":Л.::1 (Тм — ЛГ)хз + Т1зхз + Т1зхз Тззхз (т — ЛХ)з Здесь блоки Тм, Тзз н Тзз имеют соответственно размеры (1 — 1) х (1 — 1), 1 х 1 и (и — 1) х (и — 1); разбиение вектора х согласовано с разбиением матрицы Т.

Поскольку Л вЂ” простое собственное значение, матрицы Тм — ЛХ и Тзз — ЛХ невырожденны. Поэтому из соотношения (Тзз — ЛХ)хз = О следует, что хз = О. Отсюда (Тм — ЛХ)х, = — Тшхз. Если положить, например, зз = 1, то х1 —— — (Тм — ЛХ) 1Т1з. Следовательно, (лх — т ) 'т, 1 О =[ 4.3. Теории возмущений В этом разделе мы постараемся выяснить, когда собственные значения являются плохо обусловленными и, следовательно, трудно вычислнмыми. Мы не только выведем оценки ошибок в вычисленных собственных значениях, но и свяжем числа обусловленности собственных значений с родственными характеристиками, такими, как число обусловленности матрицы из собственных векторов илн расстояние до ближайшей матрицы с бесконечно плохо обусловленным собственным значением. Начнем наш анализ с вопроса о том, когда числа обусловленности собственных значений могут быть бесконечны. Как показывает приводимый ниже пример, такова ситуация с кратными собственными значениями.

Пример 4.4. Пусть матрица О 1 имеет порядок п. Тогда Л" — е = О есть характеристическое уравнение, так что Л = ~/е (все и значений радикала). Для малых е корень п-й степени из Иначе говоря, нужно лишь решить треугольную систему уравнений относительно хм Чтобы определить из вещественной формы Шура вещественный вектор, понадобится решить квазитреугольную систему.

Вычисление комплексных собственных векторов из вещественной формы Шура с использованием только вещественной арифметики также связано с решением линейных систем, но проводится несколько более хитрым образом. Подробности можно найти в ЬАРАСК-программе всгечс. Г60 Глава 4. Несимметричная проблема собственных значений е значительно больше, чем величина порядка е.

Более формально, число оба т условленности бесконечно, так как вз," = — '"„= оо в точке е = О, если п > 2. Возьмем, например, п = 16 и е = 10 'в. Тогда для каждого собственного значения матрицы А имеем )Л~ = .1. О Итак, следует ожидать, что число обусловленности собственного значения велико, если оно «почти кратно», т.е. найдется малое возмущение бА, такое, что матрица А + бА имеет в точности кратное собственное значение. Однако, даже если число обусловленности собственного значения бесконечно, это не означает, что ни одного верного знака в этом значении определить не удастся.

Предложение 4.4. Собственные значения являются непрертввными функ- циями матрицы, хотя и ие всегда дифференцируемьи Доказательство. Достаточно доказать непрерывность корней многочлена, поскольку коэффициенты характеристического многочлена суть непрерывные (даже полиномиальные) функции от элементов матрицы. Используем принцип аргумента из комплексного анализа )2); число корней многочлена р, находящихся внутри контура у, равно тг у "— фарг. При малом изменении р мало изменится и тЖ а потому мало изменится и — '. у -"-1-)дг. Так как эта вели- и) )' гвг т р(>) чина — целочисленная, она не изменит, в действительности, своего значения, а потому не изменится и число корней внутри у.

Это означает, что корни не могут оказаться снаружи ), как бы мал ни был этот контур, если возмущение многочлена р достаточно мало. Поэтому корни должны быть непрерывными функциями коэффициентов многочлена. О Теперь мы сосредоточимся на вычислении числа обусловленности простого собственного значения. Пусть Л вЂ” простое собственное значение матрицы А, а возмущение бА мало; тогда мы можем опознать собственное значение Л + бЛ матрицы А+ бА, «соответствующее> числу Л: это попросту собственное значение, ближайшее к Л. Число обусловленности простого собственного значения легко может быть найдено.

Теорема 4.4. Пусть Л вЂ” простое собственное значение матприцы А, а х и у — соответствующие правый и левый собстпвенные векторы, нормированные тпак, что ЙхЙг = )(у)(г = 1. Пусть Л + бЛ вЂ” соответствующее собстпвенное значение матрицы А+ бА. Тогда бЛ * + 0(ЦЬА)!г) у'х )бЛ! < + ОЯбА!)г) = весО(у,х)))бА))+ ОНбА)(г), !)бА)) )у*х( где 0(у, х) — острый угол между векторами у и х. Другими словами, зесО(у,х) = 1Ду'х~ есть число обусловленностпи собственного значения Л.

Доказательство. Вычитая равенство Ах = Лх из (А + бА)(х + бх) = (Л + бЛ) (х + ббх), получаем Абх + бАх + бАбх = Лбх + бЛх + бЛбх. 161 4,3. Теория зоэмутпений Отбрасывая члены второго порядка (т. е. те,что содержат два «б-члена» как множители: бАбх и бЛбх) и умножая обе части на у*, имеем у*Абх + у*бАх = у" Лбх + у'бЛх. Сокращая у'Абх и у'Лбх, получаем требуемую формулу бЛ = (у'бАх) /(у* ).