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

2.6. Наконец, в равд. 2.7 рассмотрены более быстрые варианты гауссова исключения, предназначенные для матриц со специальными свойствами, часто встречающимися в практических задачах, такими как симметрия (А = АТ) или разреженность (многие элементы в А являются нулями). 1 Так, в гл.

б будет рассмотрен случай, когда А возникает при приближенном решении конкретного дифференциального уравнения, а именно уравнения Пуассона. 2.2. Теория возмущений В разделах 2.2.1 и 2.5.1 обсуждаются недавние нововведения, используемые программами библиотеки ЬАРАСК. В ходе изложения мы указываем на ряд открытых вопросов, имеющихся в данной области. 2.2. Теории возмущений Пусть имеем системы Ах = Ь и (А+бА)х = Ь+бЬ; нашей целью является оценка нормы вектора бх х— в х — х. В дальнейшем в роли х будет выступать вычисленное решение системы Ах = Ь.

Мы попросту вычтем одно из указанных равенств из другого, а затем найдем бх. Вот как это можно сделать: после вычитания (А+бА)(х+бх) = Ь+бЬ [Ах = Ь[ Ах+ + х= Ь приведем полученное соотношение к виду бх = А '( — бАх + бЬ). (2.1) Веря здесь нормы и используя первую часть леммы 1.7, а также неравенство треугольника для векторных норм, находим Цбх)[ < ЦА 'ЦЯбАЦ [)х)[+ ЦЩ). (2.2) (Предполагается, что векторная и матричная нормы согласованы в том смыс- ле, как это определено в разд. 1.7. Например, можно взять произвольную век- торную норму и индуцированную ею матричную норму.) Трансформируя это неравенство, получаем ЦбхЦ, ([)бАЦ ЦбЬЦ ))х!) ~, ЦА)[ ЦА)[.

ЦхЦ/ ' (2.3) Произведение к(А) = ЦА 1Ц ЦАЦ называется числом обусловленности матрицы Аг, поскольку оно оценивает относительное изменение ЦбхЦ/ЦхЦ как кратное относительного изменения ЦбАЦ/ЦАЦ во входных данных. (Строго говоря, мы должны были бы показать, что неравенство (2.2) превращается в равенство при некотором выборе возмущений бА и бЬ; в противном случае к(А) было бы лишь верхней оценкой для числа обусловленности. См. по этому поводу вопрос 2.3.) Если бА и бЬ малы, то мала и величина, на которую умножается к(А), что приводит к малой верхней границе для относительной ошибки ЦбхЦДх~[. Наша верхняя оценка зависит от бх (входящего в х), что, по видимости, затрудняет ее интерпретацию. В действительности, однако, эта оценка весьма полезна с практической точки зрения, поскольку вычисленное решение х известно, следовательно, и оценка легко может быть вычислена.

Мы покажем теперь, как вывести теоретически более привлекательную оценку, не зависящую от бх. ~ С более педантической точки зрения, это число обусловленности для задачи обращения матрицы. Задаче вычисления собственных значений матрицы А соответствует, например, другое число обусловленности. 42 Глава 2. Решение линейных уравнений Лемма 2.1. Пусть выбранная матричная норма |! . |! обладает свойством ||АВ|! < ||А|| ||В||.

Тогда, если ||Х|| < 1, то матрица Х вЂ” Х обратима, (Х— Х) ' = 2, о Х' и И1 — Х) '|| < «!«х)). Доказательство. МатРичнаЯ сУмма 2,', о Х' сходитсЯ тогда и только тогда, когда сходится каждый элемент этой матрицы. Используем тот факт (получаемый применением леммы 1.4 к примеру 1.б), что для произвольной нормы существует константа с, такая, что |хгь! < с||Х|!. Тогда |(Х')ть! < с||Х'|! < с||Х|!', т.е. каждый элемент матрицы 2 Х' мажорируется сходящейся геометрической прогрессией 1„с||Х|!« = — — — '-!) и, следовательно, сам сходится. Поэтому последовательность Я„= 2,', Х' сходится при п -+ оо к некоторому Я и (1 — Х)Я„= (1 — ХН1+ Хх+.

+ Х") = 1 — Х" "' — «1 при и — > оо, поскольку ||Х'|| < ||Х||' -+ О. Таким образом, (1 — Х)Я = Х и Я = (1 — Х) '. Заключительная оценка выводится так: ||(1 — Х) «|! = ||2', Х'|! < 2'~ ||Х'|! < Я".=. ||Х||' =, +х, П Разрешая наше первое уравнение 6Ах + (А + 6А)бх = 6Ь относительно бх, получаем бх = (А+ 6А) «( — 6Ах+ 6Ь) = |А(1+ А '6А)] «( — 6Ах+ 6Ь) = (1+ А '6А) «А '( — 6Ах+6Ь).

Беря здесь нормы, деля обе части на ||х||, используя первую часть леммы 1.7 и неравенство треугольника, предпола«ая, наконец, что 6А настолько мало, что ||А '6А|| < ||А '|! ||6А|! < 1, приходим к желаемой оценке: — < ||(1+ А '6А) '|!. ||А '|! ~||6А||+ — ) ||6*|! ...Х ||6Ь||ч, — |!.||) ||А '|| ( ||6Ь|!') 1 — ||А '||. ||6А|| «, ||х|! / ||А '|! ||А|| (||НА|! ||6Ь!! =, ~~ -ч~ ~~г~~(в«(ы~~ 'и~ н~~) к(А) (||6А|! ||6Ь!|'1 — ( ~))|зл)( «, ||А|! ||Ь|| / ' поскольку ||Ь|! = ||Ах|| < ||А|| ||х||.

Эта оценка выражает относительную ошибку решения ||6х||/||х|! как кратное относительных ошибок ||6А||/||А|! и ||6Ь||/||Ь|| во входных данных. Если величина ||6А|| достаточно мала, то множитель к(А)/ (1 — к(А))(Гл-!«) близок к числу обусловленности к(А). Следующая теорема полнее раскрывает смысл предположения ||А '|| . ||6А|| = к(А) |(л(г < 1: оно гарантирует, что матрица А+ 6А невырожденна; гзА1 это необходимо для существования бх. Теорема также дает геометрическую характеризацию числа обусловленности. 2.2. Теория возмушелий Теорема 2.1.

Пусть матрица А невырожденна. Тогда Следовательно, расстояние до ближайшей вырожденной матрицы (некорректная задача) = 1/(число обусловленности). Доказательство. Достаточно показать, что 1 ппп([[бА~[г . А + бА вырожденна) = ~[А г~[г Чтобы убедиться, что указанный минимум не меньше, чем ~[А ~[~ ~, заметим; если [[бА[[г < [)А '[) ', то 1 > ![бА[[г ![А '[)г > [)А 'бА)[г. Согласно лемме 2.1, матрица 1+ А 'бА обратима, а потому обратима матрица А + бА. Чтобы показать, что минимум равен ~~А '~~г ~, построим возмущение бА с нормой )[А ' [[г ', такое, что матрица А+ бА вырожденна. Поскольку ![А '))г —— гпах,ко г-[ — *-" — ', найдется вектор х, такой, что )[х[)г = 1 и )[А ' [)г = )[А ~ х[[ > О.

А ге А ег Положим теперь у =,,* = „,*; таким образом, [~у~[а —— 1. Положим [Гл ~~ Тогда ~~ху'г[[г [у'4 ~[х[Ь ~о [)А г)[г[[г[)г то [[г[[г ![А г)[г [)А г [а' где максимум достигается, когда г есть произвольное ненулевое кратное вектора у. Матрица А + бА вырожденна, так как ху у х х [(А — '[[г )[А — '[)г ()А — '[)г Мы видим теперь, что расстояние до ближайшей некорректной задачи и число обусловленности взаимно обратны для двух задач: вычисления много- члена и решения линейных уравнений. Подобная взаимная обратность весьма характерна для численного анализа [7Ц. Имеется несколько иной способ построения теории возмущений для задачи Ах = 6; позже, в разд. 2.4.4 этот способ потребуется нам для вывода практических оценок ошибки.

Пусть х — произвольный вектор, тогда разность бх = х — х = х — А 'Ь может быть оценена следующим образом. Назовем вектор г = Ах — 6 невязкой вектора х; невязка г равна нулю, если х = х. Это позволяет нам написать бх = А ~ г и получить оценку [фх[) = )[А 'г[) < )[А '[[ ([г[[. (2.5) Эта простая оценка привлекательна с практической точки зрения, поскольку г легко вычисляется, если дано приближенное решение х. Кроме того, нет видимой нужды в оценивании бА и бЬ. В действительности, оба описанных подхода весьма тесно связаны, что выявляется следующей теоремой. Теорема 2.2.

Пусть т = Ах — 6. Тогда найдется возмущение бА, такое, что [[бА[~ = )~Ц и (А+бА)х = Ь. Пе существует никакого возмущения бА меньшей Глава 2. Решение линейных уравнений нормы, удовлетпворяющего уравнению (А+ 6А)х = Ь. Таким образом, 6А есть наименьшая возможтшя обратпная ошибка (измеряемая иосредстпвом нормы). Это утпвержденив справедливо для любой вектпорной нормтя и порожденной ею матричной нормы (или выборе Й 'уг для векторов и Й )(р для матриц).

Доказательство. Равенство (А+ 6А)х = Ь эквивалентно соотношениям 6Ах = Ь вЂ” Ах = — т, поэтому Йг!) = Й6А хи < Й6А)! йхй', откуда йбАЙ > Ц. Остальную часть доказательства мы проведем только для 2-нормы и порожденной .т ею матричной нормы. Положим 6А = =-+. Легко проверить, что 6Ах = — т и ~~з!В '06АЙг = ~Ц';. П Таким образом, наименьшее значение йбА0, позволяющее получить вектор х, удовлетворяющий условиям (А+т(А)х = Ь и г = Ах — Ь, указывается теоремой 2.2. Привлекая оценку (2.2) (с 6Ь = 0), получаем '0бх)! < 0А ')! — 'йху = '0А '0 ° 'йг!), т. е.

приходим к оценке (2.5). Все наши оценки зависят от возможности оценить число обусловленности '0А~!. ))А ' й. Мы вернемся к этой задаче в разд. 2А.З. Оценки чисел обусловленности вычисляются программами библиотеки ЬАРАСК, например программой вяевчх.

2.2.1. Теория относительных возмущений В предыдущем разделе мы показали, как оценить норму ошибки бх = х— х приближенного решения х системы Ах = Ь. Наша оценка для йбх0 была пропорциональна числу обусловленности к(А) = 0А)! ()А ')! и нормам 06А!) и ))бЬ|) в предположении, что х удовлетворяет уравнению (А + 6А)х = Ь+ 6Ь. Во многих случаях эта оценка вполне удовлетворительна, но все же не всегда. Наша цель в данном разделе — указать ситуации, когда эта оценка слишком пессимистична, и развить альтернативную теорию возмущений, дающую лучшие оценки.

Позднее, в разд. 2.5.1 эта теория будет использована для обоснования оценок ошибки, вычисляемых подпрограммами библиотеки ЬАРАСК, такими, как вяевчх. При первом чтении книги этот раздел может быть опущен. Вот пример ситуации, где оценка ошибки из предыдущего раздела чересчур пессимистична. Пример 2.1. Пусть А = с)тая(у, 1) (диагональная матрица с диагональными элементами аы = У и ага = 1) и Ь = (.У,Цт, где У > 1.

Тогда х = А 'Ь = [1,Цт. Всякий разумный прямой метод вычислит очень точное приближение х к решению системы Ах = Ь (посредством двух делений Ь;/ан); в то же время число обусловленности к(А) = у может быть как угодно велико. Следовательно, как угодно велика может быть и наша оценка ошибки (2.3). Причина, почему число обусловленности к(А) заставляет нас переоценивать ошибку, состоит в следующем: оценка (2.2), содержащая это число, основана на предположении, что возмущение 6А ограничено по норме, но в остиаьном 45 2.2. Теория возмущений произвольно; на последнем свойстве построено доказательство достижимости оценки (2.2) в вопросе 2.3.

В противоположность этому, возмущения ЬА, отвечающие реальным ошибкам округления, не являются произвольными, а имеют специальную структуру, не отражаемую нормой самой по себе. Наименьшее БА, соответствующее в нашей задаче вектору х, можно определить так: простой анализ огпибок округления показывает, что х, = (Ь,/аи)/(1+ Ье), где !Ь,! < е. Тем самым (аа + Б;аа)хе = Ь;.

Это можно переписать как (А + БА)х = Ь, где бА = б1ая(51 ам, бгагг). Тогда !!ЮА!! может достигать величины шах; !сан! = е7. Применяя оценку ошибки (2.3) с ЬЬ = О, находим В отличие от этого, реальная ошибка удовлетворяет соотношениям !!ох!!, = !!х — х!!, (Ьд/аы)/(1 + 51 ) — (Ь| /аы) ~ (Ьг/агг)/(1 + Ьг) — (Ьг/агг) ~ — б1/(1+ дг) — бг/(1+ дг) < е 1 — е < е/(1 — е) !!х!! что примерно в у раз меньше предыдущей оценки. Для данного примера структуру реального возмущения бА можно описать следующим образом: !Ба;;! < е!а;,!, где е — некоторое очень малое число.

В более сжатой форме это можно описать как !БА! < е!А! (по поводу обозначений см. разд. 1.1). Мы говорим в таких случаях, что бА есть малое относительное покомпонентное возмущение матрицы А. Поскольку на практике часто можно добиться того, чтобы дА удовлетворяла оценке (2.б), а БЬ вЂ” оценке !бЬ! < е!Ь! (см. рэзд. 2.5.1), то мы построим теорию возмущений, основываясь на этих оценках для БА и БЬ. Начнем с уравнения (2.1): Бх = А '( — БАх+ ЬЬ). Переходя к абсолютным величинам и применяя неравенство треугольника, по- лучаем !бх! = !А '( — ЬАх+ ЬЬ! < !А "!(!ЬА! ° !х! + !БЬ!) < !А '!(е!А! !х! + е!Ь!) =е(!А '!)(!А! !х!+!Ь!)). 46 Глава 2.