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

Шуба [219 — 222]. Векторные и матричные нормы подробно обсуждаются в [121, равд. 2.2 и 2.3). 1.9. Вопросы к главе 1 Вопрос 1.1 (легкий. Я. Ва1). Пусть А — ортогональная матрица. Показать, что де1(А) = х1. Показать, что если  — также ортогональная матрица и деЦА) = — деЦВ), то матрица А + В вырождена. Вопрос 1.2 (легкий Е Ва«). Рангом матрицы называется размерность линейного подпространства, натянутого на ее столбцы. Показать, что матрица А тогда и только тогда имеет ранг 1, когда она допускает представление А = аЬ для некоторых векторов-столбцов а и Ь. Вопрос 1.3 (легкий; й.

Ва1). Показать, что если матрица одновременно является ортогональной и треугольной, то она диагональная. Что можно сказать о ее диагональных элементах? Вопрос 1.4 [легкий; Т Ва«). Матрица называется строго верхнетреуголь~ой, если она верхнетреугольная и имеет нулевые диагональные элементы.

Показать, что если А — строго верхнетреугольная размера и х н, то А" = О. Вопрос 1.5 (легкий Т Ва1). Пусть )).)) — векторная норма на В.", и пусть С Е Н~"". Показать, что если гапк(С) = и, то ])х))о = ))Сх)] является векторной нормой. Вопрос 1.6 (легкий; Я. Ва1). Показать, что если 0 ~ г Е Нв и Е Е Н""", то Е 1- — ' =])Е))ргт г ])Е ])г т ) р т Вопрос 1.7 (легкий Т Ва1).

Проверить, что ))хун)]р = ))хун])г = )]х)]г))у])г для любых векторов х,у с С". Вопрос 1.8 (средней трудности). Сопоставляя каждому многочлену р(х) = а;х' степени д вектор его коэффициентов, можно отождествить множество таких многочленов с пространством Н +~. Фиксируем число х, и пусть Я, — множество многочленов, для которых относительное число обусловленности по отношению к задаче вычисления в точке х бесконечно (т.е.

такие 34 Глава 1. Введение многочлены равны нулю в точке х). Несколькими словами опишите геометрически Я, как подмножество пространства К"+'. Пусть Я, (к) — множество многочленов, относительное число обусловленности которых не меньше, чем к. В нескольких словах дайте геометрическое описание этого множества. Опишите геометрически, как изменяется Я (к) при к — > оо. Вопрос 1.9 (средней трудностип).

На рисунке, сопровождающем этот вопрос, помещены графики функции у = 1об(1 + т)/х, вычисленной двумя разными способами. С математической точки зрения, у есть гладкая функция от х в окрестности точки я = О, принимающая в нуле значение 1. Однако, если вычислять у по исходной формуле, то будут получены графики в левой части рисунка (верхний показывает функцию в области х е ~ — 1, 1], а нижний — в области х е ~ — 10 'о, 10 го)). Очевидно, что вычисление по этой формуле вблизи х = 0 неустойчиво. С другой стороны, можно использовать следующий алгоритм: к1= 1+* Н д = 1 ФЬеп Я=1 е1эе у = 1ой(к1)Дк1 — 1) епд К Этому способу соответствуют два графика в правой части рисунка с правильным поведением вблизи точки х = О. Объясните это явление, доказав, что в арифметике с плавающей точкой второй алгоритм должен давать результат хорошей точности.

Считайте, что программа для логарифма обеспечивает хорошую точность при любом значении аргумента. ~Это справедливо для любой правильной реализации логарифмической функции.) Если это облегчит ваши рассуждения, считайте, что вы работаете в 1ЕЕЕ-арифметике с плавающей точкой. (На компьютерах Сгау плохие результаты могут давать оба алгоритма.) К - Ьнаакук к ьрпакнп+кмн -ов о ар ккк1+крк -о.а о о.а а у ври +кивая-н -а о а к Маааара -а о а о к Маакоа 1.9. Вопросы к главе 1 35 Вопрос 1.10 (средней трудности). Показать, что в отсутствии переполнений н машинных нулей справедливо соотнОшениеЯ ~,~ .

~ хЩ~) — г' ~ — ~ хек(1+де)~ э 1 э где )Б,! < бе. Опираясь на это, доказать следующее: пусть обычным способом вычисляется произведение матриц А "" и В""г. Тогда, в отсутствие переполнений и машинных нулей, выполняется оценка )Я(А В) — А В! < п е.)А(.)В). Символ ~А~ обозначает матрицу с элементами )ай~, а неравенство между матрицами следует понимать как покомпонентное.

Данный результат будет использован в разд. 2.4.2 при анализе ошибок округлений в гауссовом исключении. Вопрос 1.11 (средней трудности). Пусть 7 — нижнетреугольная матрица, и система Тх = 6 решается прямой подстановкой. Показать, что в отсутствие переполнений и машинных нулей вычисленное решение х удовлетворяет системе (5+ И)х = Ь, где (И;, ~ < пе)1;, ~ и е — машинная точность. Это означает, что прямая подстановка является обратно устойчивым процессом. Показать, что сказанное выше сохраняет силу для решения верхнетреугольной системы методом обратной подстановки. Данный результат будет использован в рэзд. 2.4.2 при анализе ошибок округлений в гауссовом исключении.

Вопрос 1.12 (средней трудности). При анализе влияния ошибок округлений была принята следующая модель (см. (1.1)): Я(а О Ь) = (а О Ь)(1 + Б), где символ О обозначает одну из четырех основных операций +, —,* и /, а ~5) < е. Чтобы утверждать, что результаты нашего анализа справедливы и для вычислений с комплексными числами, нужно доказать аналогичную формулу для четырех основных комплексных операций. Пусть 5 теперь обозначает комплексное число, ограниченное по модулю малым кратным числа е.

Доказать, что формула верна для комплексных операций сложения, вычитания, умножения и деления. Ваш алгоритм для комплексного деления должен давать результаты а/а 1 как в случае очень большого ~а~ (большего, чем квадратный корень из порога переполнения), так и в случае очень малого ~а~ (меньшего, чем квадратный корень из порога машинного нуля). Всегда ли верно, что и вещественная, и мнимая части произведения двух комплексных чисел вычисляются с высокой относительной точностью? Вопрос 1.13 (средней трудности).

Доказать лемму 1.3. Вопрос 1.14 (средней трудности). Доказать лемму 1.5. Вопрос 1.15 (средней трудности). Доказать лемму 1.5. Вопрос 1.16 (средней трудностаи). Доказать все утверждения леммы 1.7, за исключением утверждения 7. Указание к утверждению 8: использовать то обстоятельство, что для и х и-матриц Х и 1' матрицы Х1г и УХ имеют одни и те же собственные значения. Указание к утверждению 9: использовать тот факт, что нормальность матрицы равносильна существованию для нее полной системы ортонормированных собственных векторов. Вопрос 1.17 (трудный; Иг. Кайап).

Мы отмечали, что иа машине Сгау наблюдалась ошибка при вычислении выражения агссоэ(х/х/хэ + уэ), вызванная 36 Глава 1. Введение тем, что вследствие округления аргумент арккосинуса оказывался ббльшим 1. Показать, что в отсутствие переполнений и машинных нулей подобное явление невозможно в 1ЕЕЕ-арифметике.

Указание: вам будет недостаточно простой модели Я(а О Ь) = (а О 6)(1+ Б), где (д~ мало. Продумайте вычисление выражения ~/ххв и покажите, что, в отсутствие переполнений и машинных нулей, равенство Я(н хв) = х выполняется точно. Нь машине же Сгау УМР в численных экспериментах, проведенных Лю (А.

Ьш), это равенство нарушалось в 5% случаев. Вы тоже могли бы провести некоторые численные эксперименты и объяснить их. Вы получите дополнительные баллы по данному заданию, если докажете аналогичный результат для десятичпой арифметики с правильным округлением. (Доказательство в этом случае иное.) Этот вопрос был поставлен У. Каханом (Ка1тап), обнаружившим ошибку в Сгау-программе (автор— 1. ЯесЬ1ап). Вопрос 1.18 (трудный).

Пусть а и Ь вЂ” нормализованные 1ЕЕЕ-числа двойной точности. Рассмотрим следующий алгоритм, выполняемый в 1ЕЕЕ- ьрифметике: если ((а! ( (Ь!), то поменять а и Ь местами з1 — — а+ Ь зг = (а — зг)+Ь Доказать следующие утверждения: 1. В отсутствие переполнений и машинных нулей единственная ошибка округления, совершаемая в этом алгоритме, происходит при вычислении з1 = Я(а+ 6). Другими словами, оба вычитания з1 — а и (з1 — а) — Ь выполняются точно. 2. Равенство з1+зз = а+6 выполняется точно. Это означает, что фактически зг есть ошибка, совершаемая при округлении точной суммы а+ Ь до числа з1 ° Таким образом, данная программа по существу моделирует арифметику учетверенной точности, представляя точную сумму а + Ь с помощью двух чисел: одно (зг) состоит из старших битов, а другое (зг) — младших.

Применяя этот и аналогичные трюки систематическим образом, можно эффективно смоделировать все четыре основные операции для арифметики произвольной разрядности, используя лишь операции стандартной машинной арифметики и не обращаясь к действиям с отдельными битами [204). Именно так реализована 128-битовая арифметика нь машинах 1ВМ В56000 и Сгау (во втором случае реализация значительно менее эффективна, так как компьютеры Сгау не имеют 1ЕЕЕ-арифметики). Вопрос 1.19 (трудный; нрограмирование).