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

Определение 1.3. Пусть  — вещественное линейное пространство К" или комплексное линейное пространство С". Пространство называется нормированным, если задана функция 0 '0 г В -э К, называемая нормой и обладающая следующими свойствами: 1.7. Векторные и матричные нормы 29 0.001 ~ ~ 0.01 х~ — — ~ 2 ~, хг = ~ 2.01 ~ и =0.0033. Чтобы привести все компоненты к одной и той же единице, так чтобы одинаковые по важности погрешности различных компонент вносили одинаковый вклад в норму, мы должны были бы при сравнении хг и хг использовать норму 1000 1 1 В линейной алгебре часто используются скалярные проигведенил. Мы определим сейчас зто понятие как обобщение стандартного скалярного произведения 2 'г хгуь [[*[[.

=- Определение 1.4. Пусть  — вещественное (комплексное) линейное про- странство. Функция (, ): В х  — ~ 1ь(С) называется скалярным произве- дением, если она обладает следующими свойствами: 1) (х,у) = (у,х) (или (у,х)), 2) (х, у + г) = (х, у) + (х, г), 3) (сгх,у) = сг(х, у) для всякого вещественного (или комплексного) числа 4) (х,х) > О, и (х,х) = 0 тогда и только тогда, когда х = О. Пример 1.5. Скалярными произведениями являются функции (х, у) = утх = 2,х,у; над Н и (х, у) = у'х = 2,'г х;у; над С. (Напомним, что вектор у' = у называется сопряженным к вектору у.) О Определение 1.5.

Векторы х и у ортогональнм, если (х,у) = О. 1) [[х[[ > О, и [[х[[ = 0 тогда и только тогда, когда х = 0 (положительная определенность), 2) [[сгх[[ = [а[ [[х[[ для всякого вещественного (или комплексного) числа о (однородность), 3) [[х+ у[[ < [[х[[+ [[у[[ (неравенство треугольника).

Пример 1.4. Чаще всего используемыми нормами являются [[х[[р () ',~[х,[г) чг, где 1 < р < оо, (мы называем их р-нормами), а также [[х[[ шах, [х;[ (так называемая оо-норма). Кроме того, если [[х[[ — произвольная нор- ма, а С вЂ” любая невырожденная матрица, то [[Сх[[ — также норма. О Мы видим, что для измерения погрешностей можно использовать много различных норм, и важно уметь выбирать наиболее подходящую из них.

Пусть, например, хг — — [1, 2, 3)т и хг = [1.01, 2.01, 2.99[7, где все компоненты измерены в метрах. Тогда хг есть хорошее приближение к хг, поскольку относительная погрешность [[-*-Дг)[ — 0.0033. Напротив, вектор хг = [10, 2.01, 2.99)т явля- ется плохим приближением, так как )[*-4:*-зла = 3. Предположим, однако, что цх~)) для измерения первых компонент в качестве единицы теперь выбран кило- метр, а не метр.

Если мы по-прежнему работаем с со-нормой, то векторы хг и хг становятся близкими: 30 Глава 1, Введение Наиболее важным из свойств скалярного произведения является то, что оно удовлетворяет неравенству Коши — Шварца. Последнее может быть использовано для доказательства того, что функция /(х, х) есть норма.

Эту норму мы в дальнейшем часто используем. л..1дяя-. -к .-зов~.г*юЗЗ З*,*) ЬО Лемма 1.2. Функция ~/(х,х) является нормой. Имеется взаимно-однозначное соответствие между скалярнымми произведениями и симметричными (эрмитоемми) полоэюительно определенными матрицами, определение которых мы сейчас дадим. Эти матрицы часто встречаются в приложениях.

Определение 1.6. Вещественная симметричная (комплексная эрмитоеа) матрица А положительно определена, если хтАх > 0 (х'Ах > 0) для всех х ф О. Для краткости, мы будем называть симметричные и зрмитовы положительно определенные матрицы соответственно с.п.о. матрицами и з.п.о. матрицами. Лемма 1.3. Пусть В = гь" (или С") и пусть (з ) — скалярное произведение, Тогда существует с.п.о. (э.п.о ) матрица А размера и хи, такая, что (х, у) = утАх (у*Ах). Обратно, если А — с.п.о. (э.п.о.) матрица, то функция утАх (у'Ах) яаллется скалярным произведением. Следующие две леммы полезны в ситуации, когда мы хотим преобразовать границу погрешности, заданную в одной норме, в границу, записанную посредством другой нормы.

Лемма 1.4. Пусть !! !!„и !! !!д — дее нормы на гь" (или С"). Тогда сущестеуют константы с„сг > О, такие, что сг!!х!! < !!х!!з < сг!!х!! для всех векторов х. Мы будем говорить, что нормы !! !!,„и !!. !!д эквивалептни с константами эквивалентности с1 и сг. Лемма 1.5.

!!х!!2 < !!х!!1 < 1/й!!х!!2 !!х!! < !!.!!. < !!*!!, !!х!! < !!х!!1 < п!!х!! Помимо векторных норм, мы нуждаемся еще в матричных нормах, чтобы измерять погрешность в матрицах. Определение 1.7. Функция !! . !! называется матричной нормой на мноэкестее т х п-матриц, если она является векторной нормой на соответствующем тп-мерном пространстве, т.е.: 1) !!А!! > 0 и !!А!! = 0 тогда и только тогда когда А = 0 2) !!оА!! = !сг! !!А!!, 3) !!А + В!! < !!А)! + !!В!!.

1.7, Векторные и матричные нормы Пример 1.6. Функции тоахй (а;,.) и Д; (аг (г)Нг = (~А~(р называются соответственно тах-нормой и нормой Фробениуса. О Следующее определение полезно, если нужно оценить норму произведения матриц. Нам часто придется делать зто при выводе границ для погрешностей. Определение 1.8. Пусть !) . 'й „„, (! . Ц~„хр и )! Й „р — матри иные нормы на множествах соответственно т х и, и х р и т х р-матриц.

Эти нормы называются взаимно согласованными, если ЙА. В~й хр < ЙАяшхп ' 'сВанхр любых т х п-матрицы А и и х р-матприцтя В. Определение 1.9. Пустив А — матрица размера т х п, а (~ . ()и и )~ . ~(а — векторные нормы на простпранствах соответственно К и К". Тогда функция ()Ах)!- йА!)тьа = шах ™ ЕН называется операторной (или индуцироваииой, или подчиненной) нормой. Следующая лемма снабжает нас обильным источником матричных норм, пригодных для оценивания погрешностей. Лемма 1.6. Всякая операторная норма является матпричной нормой.

Определяемые ниже орпсогопальные и утьитарнтяе матрицы являются существенными ингредиентами почти всех алгоритмов для задач наименьших квадратов и задач иа собственные значения. Определение 1.10. Вещестпвенная квадратная матрица Я называетсяортогоиальной, если ез т = с,тт. Комплексная квадратная матрица Я называется унитарной, если с) ' = с)'.

Все строки (а также столбцы) ортогональной (или унитарной) матрицы имеют единичные 2-иормы и попарно ортогональиы, что следует из соотношений ЯЯ~ = Я~Я = ТЯЯ* = Я*Я = Х). Следующая лемма суммирует существенные свойства определенных выше норм и матриц. Эти свойства будут нужны нам в последующем тексте книги. Лемма 1.7. 1. Неравенство ЙАхЙ < йАЙ . йх(~ верно для любой векторной нормы и соответствующей операторной нормы, а также для векторной знормы и матричной нормы Фробе~иуса.

2. Неравенство йАВЙ < йА~~ 'ПВП верно для всякой операторной нормы, а тпакже для нормы Фробениуса. (Интями словами, всякал операторная норма, так же как и норма Фробениуса, сама с собой согласована.) 3. Норма Фробениуса и тах-норма не являются оператаорными нормами. 4. Для нормы Фробепиуса, а тоже для операторной нормы, индуцированной вектпор~ой 2-тюрмой верно равенство ЙЯАЕи = ЙАЙ для любьгх ортогональных или унитарных матриц О. и Я.

В действитпельности, зто не чтпо иное, как теорема Пифагора. 5. Верно равенство ()АИ'— : шах мо Е)( — = тоах, ~ (аи( = (максимальная строчная сумма модулей). 6. ))А()т = шахрае ))((ф = ~)Ат(), = тпах ~ е ~аи) = (максимальная столбцевая сумма модулей). 32 Глава 1. Введение 7. мь: —,~ нес*- = ег (А'А). зд А,„б большее собственное значение. 8. )[А][з = []А~[)з. 9. ]]А][з — — шах; )Л;(А)], если А — нормальная матрица, т.е.

АА' = А"А. 10. Если А — матрица размера п х п, то и ~~~][А]]з < [)А)[~ < п~!~[)А)]з. 11. Если А — матрица размера и х и, то п ~~а[)А([з < [)А[[, < п~!з[]А[)з. 12. Если А — матрица размера и х п, то и ~[[А)[ < ][А[[~ < п[)А)[, 13. Если А — матрица размера и х п, то [[А])з < [[А)[к < п~~~[)А)[з. Доказательствоо. Мы докажем только утверждение 7 и внесем остальные доказательства в вопрос 1.16. Поскольку А'А — эрмитова матрица, то существует спектральное разложение А'А = ДЛЯ', где Я вЂ” унитарная матрица (ее столбцы являются собственными векторами), а Л = йа8(Лы...,Л„) — диагональная матрица, содержащая собственные значения; все они должны быть вещественны.

Заметим, что все Л, неотрицательны. Действительно, если бы какое-то из них, скажем Л, было отрицательно, то с помощью соответствующего собственного вектора д мы пришли бы к противоречию: 0 < [[Ад[Я = дтАтА9 = дтЛд = Л[)9Я < О. Теперь имеем ~]Ах[~а [х*А"Ах) чз (я'ДЛЯ'х)'~~ [)А[)з = гпах = шах = шах тфо [)х)[з я~о [[х[]2 ~Фо [[~][2 [[О*~)*ЛО )"~' [р Лр)'" ~,'Л,ру х~о [[(~*я))[а РФО [)Ц)[з РФО 2 Ц~8 < шах~/Л с ' = 1/Л~,„, Эта оценка достижима: достаточно взять в качестве у подходящий столбец единичной матрицы. П 1.8.

Литература и смежные вопросы к главе 1 В конце каждой главы мы будем перечислять наиболее важные публикации по ее теме. Их библиографические описания можно найти в упорядоченном по алфавиту списке литературы в конце книги. Кроме того, мы будем кратко комментировать смежные вопросы, не обсуждаемые в основном тексте. Наиболее современной и полной книгой по матричным вычислениям является книга Дж. Голуба и Ч.

Ван Лоука [121]; там же содержится обширная библиография. Недавняя книга Д. Уоткинса [252] представляет собой введение в матричные вычисления, рассчитанное на студента или начинающего аспиранта. Книга Л. Трефетена и Д. Бау [243] — еще один хороший учебник для аспирантов. Классическая монография Дж. Уилкинсона [262], хотя и несколько устарела, остается замечательным справочным пособием. Старая книга Дж. Стюарта [235] все еще является отличным учебником того же уровня, что и книга Уоткинса. 33 1.9. Вопросы к главе 1 Более подробную информацию об анализе ошибок можно найти в недавно изданной книге Н.

Хигэма [149]. Старыми, но по-прежнему хорошими источниками являются книги Дж. Уилкинсона [26Ц и В. Кахана [157). Недавно опубликован хороший обзор Д. Гольдберга под названием «Что должен знать об арифметике с плавающей точкой любой специалист по ннформатикеь [119]. Формальное описание 1ЕЕЕ-арифметнки дается в [11, 12, 159), а также в справочных руководствах, публикуемых производителями компьютеров.

Обсуждение анализа погрешностей в рамках 1ЕЕЕ-арифметики можно найти в [54, 70, 159, 158]; см. также библиографические ссылки, даваемые в этих публикациях. Наиболее общее рассмотрение вопроса о числах обусловленности и расстоянии до ближайшей некорректной задачи проводится в работе автора [71] и серии статей С. Смейла и М.