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

Данные достаточно распечатывать с одним десятичным разрядом, поскольку нас интересуют лишь приблизительные значения. Являются ли вычисляемые границы ошибок подлинными оценками? Какова сравнительная скорость программ вяевчх и яеср? На многих системах точное время работы программы зарегистрировать трудно из-за низкой разрешающей способности таймера. Поэтому время работы следует вычислять так: 1г — — текущее время Гог г' = 1 Ьо т сформировать задачу 108 Глава 2.

Решение линейных уравнений решить задачу епс1Еог 1г = текущее время (ог г' = 1 $о т сформировать задачу епсйог 1г = текущее время ((12 сс) (13 сг))/т Значение т нужно брать настолько большим, чтобы разность 1г — 1с составляла хотя бы несколько секунд. В этом случае 1 должно быть надежной оценкой времени решения задачи. Вы должны провести тестирование как на хорошо обусловленных задачах, так и на плохо обусловленных. Чтобы получить хорошо обусловленную матрипу, выберите матрицу-перестановку Р и добавьте к каждому ее элементу малое случайное число.

Чтобы получить плохо обусловленную матрицу, возьмите случайную нижнетреугольную матрипу Ь с малыми диагональными элементами и поддяагональными элементами умеренной величины. Пусть сс — аналогичным образом построенная верхнетреугольная матрица, и пусть А = ЬЬс. (Вы можете также, если захотите, воспользоваться ЬАРАСК-подпрограммой в1авсве, предназначенной для генерирования случайных матриц с требуемым числом обусловленности.) Испытайте обе программы еще на одном классе п х п-матриц для значений и от 1 до ЗО. (Если вы работаете в арифметике двойной точности, то лучше довести вычисления до н = бО.) Устройство этих матриц покажем для п = 5; для других и оно аналогично: 1 — 1 — 1 — 1 — 1 0 1 0 1 0 1 1 1 — 1 1 0 0 1 0 — 1 1 — 1 — 1 — 1 — 1 Вопрос 2.15 (средней трудности программирование).

Этот вопрос связан с вопросом 2.14. Составьте еще один вариант программы еяееох с именем ейевчхйопб1е; в нем невязка должна вычисляться с двойной точностью при итерационном уточнении решения. Измените границу ошибки РЕйй в вйевнх, чтобы отразить увеличившуюся точность. Объясните произведенное изменение. (Это может потребовать от вас разобраться, в первую очередь, с тем, как вычисляется граница ошибки в вяевох). Для того же набора тестовых приме- Объяснить степень точности полученых результатов в терминах анализа ошибок,проведенного в разд. 2.4.

Ваш ответ не должен содержать распечаток матриц и решений линейных систем. Помимо того, чтобы научить вас пользоваться оценками ошибок, данное задание преследует еще цель показать вам, как выглядят хорошо реализованные программы численного анализа. В своей практической работе вам, возможно, не раз придется использовать или модифицировать существующие программы вместо того, чтобы писать свою полностью новую программу. 109 2.9. Вопросы к главе 2 ров, что и в предыдущем вопросе, постройте аналогичную таблипу данных.

В каких случаях программа вйевнхаоиЬ1е более точна, чем вбевгх? Вопрос 2.16 (трудный). Объясните, как следует модифицировать алгоритм Холесского (алгоритм 2.11), чтобы ббльшая часть операций производилась в нем посредством процедур уровня 3 из В1АЯ. Действуйте, как в алгоритме 2.10. Вопрос 2.17 (легкий).

Предположим, что вы имеете в МаС1аЬ'е п х п-матрицу А и и х1-матрицу Ь. Что означают в Ма11аЪ'е записи А1Ь, Ь'/А и А/Ь? Как А1Ь отличается от 1пн(А) * Ь? Вопрос 2.18 (средней трудности). Пусть Аы Агг где й х Ь-подматрица Аы невырожденна. Тогда матрица Я = Агг — Аз~А,,'А~г называется дополнением Шура подматрицы Аы в А или, для краткости, просто дополнением Шура. 1. Показать, что после Ь шагов гауссова исключения без выбора главных элементов на месте Агг находится матрица 5.

2. Предположим, что А = Ат, подматрица Аы положительно определена, а Агг отрицательно определена (т.е. — Агг положительно определена). Показать, что для невырожденной матрицы А будет (в точной арифметике) работать гауссово исключение без выбора главных элементов, но в машинной арифметике оно может быть численно неустойчивым (это можно показать с помощью примера 2 х 2). Вопрос 2.19 (средней трудности). Говорят, что матрица А имеет строгое диагональное преобладание по столбцам, или, для краткости, диагональное преобладание, если )аи! > ~~~ (ай(.

1=1, эвн ° Показать, что А невыроэгденна. Указание: воспользоваться теоремой Гершгорина. ° Показать, что в гауссовом исключении с частичным выбором главных элементов строки такой матрицы в действительности не переставляются, т, е. оно идентично исключению без выбора главных элементов.

Указание: покажите, что после одного шага гауссова исключения оставшаяся подматрица размера (п — 1) х (и — 1) (т.е. дополнение Шура элемента аы в А) по- прежнему имеет диагональное преобладание. (Более подробно дополнения Шура обсуждаются в вопросе 2.18.) Вопрос 2.20 (легкий; Е Ва?). Пусть дана невырожденная и х п-матрица А. Как, используя гауссово исключение с частичным выбором главных элементов, эффективно решать следующие задачи: а) найти решение линейной системы А"х = Ь, где Ь вЂ” натуральное число; 11О Глава 2. Решение линейных уравнений Ь) найти число а = сгА 'Ь; с) решить матричное уравнение АХ = В, где  — матрица размера п х т.

Вы должны: 1) описать свои алгоритмы; 2) представить их псевдокодом (используя язык типа МайаЬ'а; алгоритм СЕРР записывать не нужно); 3) указать требуемое число операций. Вопрос 2.21 (средней трудности). Для п, являющегося степенью двойки, доказать, что алгоритм Штрассена (алгоритм 2.8) правильно перемножает п х и- матрицы. Глава 3 Линейные задачи наименьших квадратов 3.1. Введение Пусть даны т х п-матрица А и т-вектор Ь.

Линейная задача наименьших квадратов заключается в разыскании п-вектора х, минимизирующего величину 3Ах — 65г. Если т = и и матрица А невырожденна, то решением задачи является вектор х = А 16. Если т ) п, т.е. число уравнений больше числа неизвестных, то задача называется переопределенной; в этом случае, вообще говоря, не существует вектора х, точно удовлетворяющего системе Ах = Ь.

Иногда встречаются и педоопределенные задачи, где т < и, однако мы сосредоточимся на более общем переопределенном случае. Данная глава организована следующим образом. В остальной части настоящего введения описаны три приложения задачи наименьших квадратов, а именно анорексия«ация данных, статистическое моделирование при наличии шума и геодезическое моделирование. В разд.

3.2 обсуждаются три стандартных способа решения задачи наименьших квадратов: норл«алиные уравнения, Яг«-разлохсение и сингулярное разложение (ЯЧ0). Последнее часто используется как инструмент в дальнейших главах, поэтому мы выведем некоторые его свойства (хотя описание алгоритмов вычисления ЯЪЧ) отложено до гл. 5). Раздел 3.3 посвящен теории возмущений для задач наименьших квадратов, а разд. 3.4 — деталям реализации и анализу ошибок округлений в нашем главном методе, а именно чгВ;разложении. Этот анализ приложим ко многим алгоритмам, использующим ортогональные матрицы, включая алгоритмы вычисления собственных значений и ЯЪ'П из гл. 4 и 5. В равд. 3.5 рассматривается ситуация особенно плохой обусловленности при неполном ранге задачи наименьших квадратов; мы обсуждаем,как в этом случае получить решение приемлемой точности.

В разделе ЗЛ и вопросах в конце главы даны сведения о других типах задач наименьших квадратов и программах для решения разреженных задач. Пример 3.1. Аппроксимация данных является традиционным приложением метода наименьших квадратов. Пусть даны т пар чисел (уы 61),..., (уы, 6~). Предположим, что мы хотим найти кубический полинам, который бы «наилучшим образомг представлял числа Ь; как функцию от у,.

Это означает, что коэффициенты хы...,х« нужно определить так, чтобы многочлен р(у) = 2'„", х,уд ' минимизировал невязку г; = р(у;) — 6, для «от 1 до т. 112 Глава 3. Линейные задачи наименьших квадратов То же самое означает задача минимизации вектора Р(У») Р(уг) ь, Ь тг тг Р(ут) У| У1 уз 1 у« 1 Уг 6| Ь г г Уо«уь« =А х — Ь, Пример 3.2.

В статистическом моделировании часто приходится оценивать некоторые параметры хи основываясь на наблюдениях, «загрязненных» шумом. Предположим, например, что в рамках кампании по приему в колледж желательно предсказать средний балл (6) будущего обучения в нем, исходя из где т и Ь суть т-векторы, А — матрица размера и» х 4, а х — вектор размерности 4. Для минимизации т можно выбрать любую норму, например [[т[[,, [[т[[г илн [[т[[г. В последнем случае получаем линейную задачу наименьших кеадрап»ое; она соответствует минимизации сумм квадратов невязок >,, тг.

В примере на рис. 3.1 гладкая функция Ь = тйп(яу/5) + у/5 аппроксимируется многочленами возрастающих степеней по 23 точкам у = — 5, — 4.5, — 4,..., 5.5, 6. В левой части рисунка представлены исходные данные (изображены кружками) и четыре аппроксимирующих многочлена степеней 1, 3, 6 и 19. В правой части рисунка норма невязки [[т[[г представлена как функция от степени многочлена для значений степени от 1 до 20. Обратим внимание на то, что норма невязки убывает при возрастании степени от 1 до 17. Этого и следовало ожидать, ведь увеличение степени многочлена должно позволить нам лучше аппроксимировать данные.