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

Решение линейных уравнений Используя любую векторную норму, для которой ][[с]]! = ][х]! (таковы шахнорма, 1-норма и норма Фробениуса) приходим к оценке ]]бх]! < е][]А '](]А! ]х]+ ]Ь!)]!. (2. 7) Предположим на время, что бЬ = О. Тогда (2.7) можно ослабить до оценки []бх]! < е]]]А '! ]А]]! []х[! — < с][]А '! . ]А[[!. ]]бх]! []х]! (2.8) Это неравенство служит обоснованием для того, чтобы назвать величину кон(А) = ]]]А 1! ]А[[! относиглельным покомпоненгпным числом обусловленности матрицы А или, для краткости, ее относительным числом обусловленпостпи. Иногда эту величину называют также числом обусловленности Бауэра [26] или числом обусловленности Скила [225, 226, 227].

По поводу доказательства того, что оценки (2.7) и (2.8) достижимы, см. вопрос 2.4. Напомним, что теорема 2.1 устанавливает связь между числом обусловленности к(А) и расстоянием от А до ближайшей вырожденной матрицы. Относительно аналогичной интерпретации числа кон(А) см. [72, 208). Пример 2.2. Вернемся к нашему предыдущему примеру с А = пйа8(7, 1) и Ь = [7,1)т. Легко проверить, что кол(А) = 1, поскольку ]А '! ]А! = 1.

В действительности, ксн(А) = 1 для любой диагональной матрицы А, что соответствует нашему интуитивному ощущению, согласно которому диагональные системы уравнений должны решаться с высокой точностью. о Рассмотрим более общий случай, где Р— произвольная невырожденная диагональная матрица, а  — произвольная невырожденная матрица. Тогда (РВ) = [][(РВ)-'!. [(РВ)]]! = [][В 'Р '!.

[РВ[[! = [][В 1! ]В]]! = кап(В). ]]бх]! = ]]А 'г]! < ]]]А "! ]г[]!. (2.9) Здесь было применено неравенство треугольника. В равд. 2.4.4 мы увидим, что эта оценка может быть подчас много меньше аналогичной оценки (2.5); так будет, в частности, если А плохо масштабирована. Справедливо, кроме того, утверждение, аналогичное теореме 2.2 [193). Это означает, что если матрица РВ плохо масштабирована, т. е,  — хорошо обусловленная матрица, а РВ обусловлена плохо (из-за того, что диагональные элементы в Р сильно различаются по величине), то мы должны надеяться на возможность решения системы (РВ)х = Ь с высокой точностью, несмотря на плохую обусловленность матрицы РВ.

Эта тема обсуждается в дальнейшем в разд. 2.4.4, 2.5.1 и 2.5.2. В заключение мы приведем, как и в предыдущем разделе, оценку ошибки, использующую только невязку г = Ах — Ь: 47 2.3. Гвуссово исключение Теорема 2.3. Наименьшее число г > О, для которого существуют возмущения бА и бб, удовлетворлющие оценкам !бА! ч г!А! и !6Ь! < г!Ь! и уравнению (А + бА)х = Ь+ бЬ, называетсл покомпонентной относительной обратной ошибкой. Оно вььраэкаетпся через невлзку т = Ах — Ь формулой !ть! (!А! !х! + !Ь!)ь Относительно доказательства теоремы см. вопрос 2.5. Программы библиотеки ЕАРАСК, такие, как айевчх, вычисляют покомпонентную относительную обратную ошибку г (для соответствующей переменной в 1АРАСК'е принято имя Вайа).

2.3. Гауссово исключение Основным алгоритмом решения линейных систем Ах = б является гауссово исключение. Чтобы описать его, нам нужно вначале определить понятие матрицы-перестпановки. Определение 2.1. Матрица-перестановка Р— это матрица, полученная из единичной произвольной перестановкой стирок. Наиболее важные свойства матриц-перестановок даются следующей леммой. Лемма 2.2. Пусть Р, Рь и Рг — зто матрицы-перестановки порядка п, а Х вЂ” произвольнал п х п-матрица.

Тогда 1. РХ отличается от Х только порядком строк. ХР отличается от Х только порядком столбцов. Р— 1 3. ь1еь(Р) = х1. 4. Рь Рг такэке лвляетасл матрицей-перестпановкой. Относительно доказательства см. вопрос 2.6. Теперь можно полностью описать наш алгоритм для решения системы Ах = 6. Алгоритм 2.1. Решение системы Ах = Ь посредством гауссова исключения. 1.

Разлоэкить А в произведетьие А = РТП, где Р— матрица-перестановка, Х,— ниэкнля упитрсугольная матрица (т. е. матрица с единицами на главной диагонали), бт — певыроэкдсннал верхпстреугольная матрица. 2. Решить систему Р111х = 6 относительно вектора И1х, перестаавляя компоненты вектора Ь: 1,11х = Р ьб = РтЬ. 3. Решить систему И7х = Р 'Ь относительно вектора Ух посредством прямой подстановки (прлмого хода): ратх = Т ь(Р ьб). 4. Решить систему У = Т т(Р '6) относительно вектора х посредством обратной подспьановки: х = бт ь(Т "Р ьЬ).

48 Глава 2. Решение линейных уравнений Алгоритм для разложения А = РТЛ1 будет выведен несколькими способами. Начнем с пояснения, почему нужна матрица-перестановка Р. Определение 2.2. Ведущей главной подматрицей порядка у матрицы А на- зъсвается подматрица А1С1: у, 1: 2). Теорема 2.4. Следующие два утверждения эквивалентпыс 1.

Существуют единстветсые нижняя унитреугольная масприца Ь и невырожденноя верхнетреугольная матрица У, такие, что А = Ис. 2. Все ведущие главные подмасприцы матрицы А невырожденны. Доказательство. Покажем вначале, что нз первого утверждения следует вто- рое. Равенство А = ИС может еще быть записано квк ~А, А Е21 з 22 О С22 Ь11У11 ЬНУ12 с'21с'11 х'21С12 + В22С22 где А11, Ьп и У11 — ведущие главные подматрицы порядка у соответствующих матриц. Следовательно, с1есА11 = с1ес(Ь11У11) = десЬ11с)еСС11 = 1 . Пзь 1(011)ьь ~ О, поскольку Ь унитреугольная, а У треугольная матрицы. Докажем, что из второго утверждения следует первое, индукцией по п. Это тривиально для 1 х 1-матриц: а = 1 а. Переходя к п х и-матрице А, мы должны найти однозначно определенные треугольные матрицы Ь и У порядка и — 1, однозначно определенные векторы 1 и и размерности п — 1 и однозначно определенное число 21, такие, что ст д — ~т 1 О „ = 1тгс 1ти + По предположению индукции, существуют единственные матрицы Е и У, для которых А = ИУ.

Положим теперь и = В 1*о, 1т = сз У 1 и 11 = Б — 1ти; все эти величины определены единственным образом. Согласно предположению индукции, диагональные элементы матрицы У отличны от нуля, а ц ~ О по той причине, что О ф с1ес(А) = с1ес(У) . 11. П Таким образом, 1Л1-разложение без выбора главного элемента может оказаться невозможным для (хорошо обусловленных) невырожденных матриц, например для матрицы-перестановки. Р= О О 1 В матрице Р вырожденны ведущие главные подматрицы порядков 1 и 2. Это означает, что мы должны ввести перестановки в гауссово исключение. Теорема 2.5.

Для невырождеппой матрицы А существуют перестановки Р1 и Р2, нижняя униспреугольная матрица Е и невырожденная верхнетпреугольная матрица У, такие, что Р1АР2 — — ИС. Можно ограничиться одной из двух матриц Р1 и Р2 49 2.3. Гауссово исключение Замечание: Р/А переупорлдочиеает строки в А, тогда как АР2 переупорл- дочиоает столбцы; Р1АР2 переупорлдочивает и строки, и столбцы. Ам Агг 121 1 0 Агг Р,'АР' = и/1 1/12 121и/1 12Л12 + Агг (2.10) Здесь Агг и Агг — матрицы порядка и — 1, а 121 и У~г имеют размер (и — 1) х 1. Определяя компоненты этого блочного 2 х 2-разложения, получаем им —— ам ~ О, 1212 = А12 и 12/и/1 — — Аг/. Поскольку иы — — оы ~ О, можно найти А 21 121 = --2".

Наконец, из Ьг/1/12 + Агг = Агг следует, что Агг = Агг — 12/О/22. Мы хотели бы применить к Агг предположение индукции; однако, чтобы сделать это, нужно проверить, что /1ег Агг ~ О. Поскольку бег Р,'АР' х/1еФ А ф О, а также д/е1Р1АР2 = деС ~ 1 ~ .с1ео ~ — = 1 (иы /1есА22), 1 О 1 '/ и11 1А12 ~ 121 1) ~ 0 Агг то число с1ес Агг должно быть ненулевым. Итак, по предположению индукции, найдутся перестановки Р, и Рг, такие, что Р1АггР2 = Ь1/', где Ь нижняя унитреугольная, а 1/' невырожденная верхне- треугольная матрицы. Подставляя это равенство в написанное выше блочное 2 х 2-разложение, получаем иы У12 О Рг 1ЦРт О Рт1 О иы П12Рг Р1 121 1 0 1 0 ~о /*; 1 0 Ь21 Ртй 1112 Р2 1/' 0 Рт Доказательство.

Подобно многим матричным разложениям, достаточно разобраться со случаем блочных 2 х 2-матриц. Говоря более формально, мы применим индукцию по порядку п. Утверждение очевидно для 1 х 1-матриц: Р1 = Рг —— Ь = 1 и 11 = А. Предположим, что утверждение верно для порядка и — 1. Невырожденная матрица А должна иметь ненулевые элементы, поэтому выберем перестановки Р1 и Рг так, чтобы элемент (1, 1) матрицы Р'АР2 был отличен от нуля. (Достаточно использовать только одну из матриц Р,' и Р,', поскольку невыро/кденность А означает, что в каждой ее строке и каждом столбце имеются ненулевые элементы.) Теперь мы запишем требуемое разложение, а затем его неизвестные компоненты: 50 Глава 2. Решение линейных уравнений что дает требуемое разложение матрицы А О Р Рь .4 1» О Р 1 0 иьь Гьгрг П В следующих двух предложениях описаны простые способы выбора перестановок Рь и Рг, гарантирующих, что гауссово исключение будет успешно проведено для невырожденной матрицы А.

Следствие 2.1. Можно положить Рг = 1 и выбрать Р., 'таким образом, чтобы аы был наибольшим по абсолютной величине элементом своего столбца; это означает, что элеменпьы матрицы Хм = -~~ ограничены по абсолютл ной величине числом 1. Более общо, при вычислении ь'-го столбца матрицы Е на ь-м шаге гауссова исключения строки с ь-й по и-ю переупорядочиваются так, чтобы наибольший по абсолютной величине элемент ь-го столбца находился на главной диагонали. Такая организация процесса назъьваетпся «гауссовым исключением с частичны.м выбором главного элемента» или, для краткости, методом СЕРР. Этот метод гарантирует, что все элемеппьы матрицы Е ограничены по абсолютной величшье числом 1.