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

Большую помощь в наборе книги и подготовке рисунков оказали мне ВоЬ Ппс!ее!! и Бе!еле ч'!ссог. Фотография для обложки английского издания предоставлена Мекал. Наконец, отмечу Ка!Ьу г'е1!с1с, которая оказывала мне поддержку много лет и как никто другой ожидала завершения этого проекта. Джеймс Деммель Беркли, Калифорния Июнь 1997 г. Глава 1 Введение 1.1. Основные обоэначеннн В этой книге мы будем постоянно оперировать с матрицами, векпгорами и числа.ыи (скаллрами). Всякая матрица будет обозначаться прописной буквой, скажем А, а ее элемент (4, у) будет обозначаться аб. Если матрица задана выражением типа А+В, то будем писать (А+ В) иь В более подробных алгоритмических описаниях будет иногда использоваться символ А (з,у); для обозначения подматрицы, лежащей на пересечении строк с 4'-й по 1-ю и столбцов с й-го по 1-й, используется обозначение А (г: 1, Ь: 1), заимствованное из МанаЬ™ (184).

Вектор обозначается строчной буквой, скажем х, а его 4-й элемент записывается как х,. Почти всюду мы рассматриваем только векторы-столбцы, иначе говоря, одностолбцовые матрицы. Для обозначения скаляров используются строчные греческие (а иногда латинские) буквы. Символы К, Кп и Кгн "и обозначают соответственно множества вещественных чисел, и-мерных вещественных векторов и т х п вещественных матриц, а символы С, С" и С комплексные числа, векторы и матрицы. В некоторых случаях для обозначения т х и-матрицы А используется сокращенная запись А "".

Транспоыировамие матрицы А обозначается символом Ат: (Ат), = а,;. Для комплексной матрицы А используется также понятие сопряженной матрицы А": (А')1 = а,. Символы ЬЬх и сгх обозначают соответственно вещественную и мнимую части комплексного числа ж Для т х и-матрицы А под ~ А ( понимается т х и- матрица, составленная из абсолютных величин элементов А: Д А!);. = )Ао !.

Неравенства типа ! А ! ( ! В ! следует понимать как системы покомпонентных неравенств: ) аг ) ( ! Ье. ! для всех г и у. Аналогичное обозначение используется лля векторов: (( х !)4 = ! х, ). Завершение доказательства помечается символом 1з, а завершение примера — символом О. Прочие обозначения будут вводиться по мере необходимости. ' Мас1аЬ вЂ” зто зарегистрированный торговый знак фирмы ТЬе Мазь'ггогье, 1пс., 24 Ргппе Рагх ЪЧау, Ыас!с$с, МА 017бО, 11ЯА, се1, 508-б47-7000, уак 508-б47-7001, 1псо©пзаеьногхв,согп, Мер Онннзпасьиогхе.согп. 10 Глава 1. Введение 1.2.

Стандартные задачи вычислительной линейной алгебры Мы будем рассматривать следующие стандартные задачи: ° Система линейных уравнений: решить систему Ах = Ь. Здесь А — заданная невырожденная и х п-матрица, вещественная или комплексная, Ь вЂ” заданный и-мерный вектор-столбец и х -- вектор с и компонентами, который мы хотим вычислить. ° Задачи наименьших квадратов: вычислить вектор х, минимизирующий !) А х — Ь '5г. Здесь А, Ь и х имеют размерность соответственно т х и, т х 1 и и х 1, а величина (! у 5г =,„I2 „Гу )г называется 2-нормой вектора у. Если т ) п (т.е. число уравнений превышает число неизвестных), то говорят, что система переопределена.

В этом случае удовлетворить систему Ах = Ь точно, вообще говоря, не удается. Если т < п, то система недоопределена и может иметь бесконечно много решений. ° Задачи па собствеььпые значениль для заданной и х п-матрицы А найти ненулевой вектор х и число Л,такие,что Ах = Лх. ° Задачи на сингулярные значения: для заданной т х и-матрицы А найти ненулевой вектор х и число Л, такие, что АтАх = Лх. Мы увидим, что этот частный тип задач на собственные значения настолько важен, что засауживает отдельного рассмотрения и специальных алгоритмов. Именно эти стандартные задачи выделены по той причине, что они чрезвычайно часто встречаются в инженерной и научной практике. На протяжении всей книги они будут иллюстрироваться простыми примерами, взятыми из инженерных приложений, статистики и других областей.

Эти стандартные задачи допускают много вариантов, которые мы также рассмотрим; упомянем, например, обобщенные задачи на собственные значения Ах = Л Вх (разд. 4.5) и задачи наименьших квадратов, имеющие чнеполный рангы Такая задача ппп, Й А х — Ь 'уг имеет неединственное решение вследствие линейной зависимости столбцов матрицы А (разд. 3.5). Мы убедимся в том, как важно использовать специальную структуру, которую может иметь задача. Например, при решении системы линейных уравнений размера п х и посредством самой общей версии гауссова исключения приходится выполнять 2/3 пг операций с плавающей точкой.

Если дополнительно известно, что система симметрична и положительно определена, то можно сократить работу вдвое, используя иной алгоритм, называемый методом Холесского. Если вдобавок матрица системы ленточная и полуширина лентьь составляет ~/й (т.е. а;, = О, если ~ ь' — у ~ > ~/й), то стоимость решения системы можно уменьшить до О(пг) операций, применяя ленточный вариант метода Холесского. Пусть, наконец, предыдущая информация конкретизируется сообщением, что решается уравнение Пуассона в квадрате, дискретизированное методом конечных разностей на 5-точечном шаблоне. Такое сообщение определяет матрицу почти единственным образом.

В этом случае, используя многосеточный алгоритм, можно снизить стоимость решения системы до О(п) операций, чем достигается уже почти предельная скорость (в том смысле, что на вычисление каждой компоненты решения затрачивается не зависящая от п работа см. разд. 6.4). 1.3. Общие аспекты 1.3. Общие аспекты Мы постоянно будем использовать (и держать в поле зрения) несколько общих понятий и аспектов. Перечислим их: 1. Матричные разложения. 2. Теория возмущений и числа обусловленности. 3.

Влияние погрешностей округления на алгоритмы (учитывающее свойства используемой арифметики с плавающей точкой). 4. Анализ скорости алгоритмов. 5. Программирование численных алгоритмов. 1.3.1. Матричные разложения Разлоэкением матрицы А называется ее представление в виде произведения нескольких «более простых» матриц, облегчающее решение рассматриваемой задачи. Приведем два примера. Пример 1.1.

Пусть нужно решить систему А х = Ь. Есььи А — нижнетреуголь- ная матрица ь, Ьг аьь агь агг хь хг а„ь аьг ... аоь то решение легко достигается посредством прямой подстановки: 1ог ь' = 1 $о и х = (Ь вЂ” 2 ь ь аььхь)/ап еп«1 Гог Теорема 1.1. Пусть и хть-матприца А тьевььрождена. Тогда найдутся матприца-перестпановка Р (т. е. единичная матрица с переставленными строками), невырожденная низкнетпреугольпая мапьрица Т и тьевььрождепььая верхпетреугольная матрица бт, такие, что А = Р Т У. Чтобы решить систпему Ах = 6, мы решаем эквивалентную систему РТЛ7х = Ь следующим образом; 1.0х = Р ьЬ = РтЬ (перестановка компонентп вектора Ь), бтх = 1 ь(РтЬ) (прямая подстановка), х = У ь(й ьРтЬ) (обратная подстановка).

Эта теорема будет доказана в разделе 2.3. О Пример 1.2. Каноническое разложение Жордана А = 1тд1т ь явным образом указывает собственные значения и собственные векторы матрицы А. Здесь»'— невырожденная матрица, в число столбцов которой входят собственные векторы, а .7 — жорданова каноььическая форма матрицы А. Она представляет собой специального вида треугольную матрицу, на диагонали которой находятся Аналогичный прием, называемый обраттьой подстановкой, работает в случае верхнетреугольной матрицы А. Чтобы использовать эти факты для решения системы Ах = Ь общего вида, нам потребуется описываемое ниже матричное разложение. Оно является всего лишь иной формулировкой гауссова исключения.

Глава 1. Введение собственные значения А. Мы увидим, что, с вычислительной точки зрения, предпочтительней находить разловкение Шура А = 0Т1/', где У вЂ унитарн матрица (т.е, столбцы матрицы У ортонормированы), а Т вЂ” верхнетреугольная матрица, содержащая на диагонали собственные значения матрицы А. Форма Шура Т может быть вычислена быстрее и более точно, чем жорданова форма г. Мы обсудим разложения Жордана и Шура в разд. 4.2. О 1.3.2. Теория возмущений н числа обусловленности Результаты, получаемые численными алгоритмами, редко бывают совершенно точными.

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

Требуется вычислить У(х), при этом значение х точно не известно. Предположим, что вместо х заданы значение х + бх и граница для величины бх. Если никакой другой информации нет, то лучшее, что можно сделать, — это вычислить У(х + бх) и попытаться оценить абсолютную погрешность | ((х+ бх) — у(х) ~. Если использовать для у простое линейное приближение, то получим ((х+ бх) ж у(х) + бх~'(х); следовательно, погрешность равна ь((х+ бх) — Дх)! и (бх( )~'(х)~.

Мы назовем ~~'(х)) абсолютным числом обусловленности функции у в точке х. Если число ~ ('(х)! велико, то погрешность может быть большой даже для малого бх. В этом случае мы говорим, что ( плохо обусловлена в точке х. О Мы назвали число обусловленности абсолютным, потому что оно позволяет оценить абсолютную погрешность |Дх + бх) — /(х) ~, если задана граница для абсолютного изменения )бх~ входной величины х.

Для оценивания погрешности будет часто использоваться и следующее, по существу эквивалентное выражение: (((х+ бх) — Дх)) /бх) !~'(х)! . )х/ / ((х) / /х/ / ((х) ! Это выражение оценивает относительную погрешность ~ ((х+бх)— у(х)(/)Дх))произведением относительного изменения входа фх(/)х( и множителя )~'(х)! )х(Я(х)(, называемым относительным числом обусловленности.