Семь грехов числовой линейной алгебры — Ник Хайэм

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

1. Обращение матрицы

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

Решение линейной задачи наименьших квадратов , где матрица полного ранга с , удовлетворяет нормальным уравнениям . Поэтому естественно сформировать симметричную положительно определенную матрицу и решить нормальные уравнения методом факторизации Холецкого. Хотя этот метод быстр, он численно нестабилен, когда он плохо обусловлен. Напротив, решение задачи наименьших квадратов с помощью QR-факторизации всегда численно стабильно.

Что не так с матрицей перекрестного произведения (также известной как матрица Грама)? Он возводит данные в квадрат, что может привести к потере информации при арифметике с плавающей запятой. Например, если

где — единица округления арифметики с плавающей запятой, тогда

положительно определена, но, поскольку , в арифметике с плавающей запятой округляется до и так

, которое является единственным, и информация в была потерянный.

Другая проблема, связанная с матрицей перекрестного произведения, заключается в том, что -норма числа обусловленности равна квадрату числа обусловленности , и это приводит к численной нестабильности в алгоритмах, которые работают с большим числом обусловленности.

3. Оценка матричных продуктов в неэффективном порядке

Стоимость оценки матричного продукта зависит от порядка, в котором оценивается продукт (при условии, что матрицы не все ). Точнее, умножение матриц ассоциативно, поэтому и вообще стоимость оценки продукта зависит от того, где поставить скобки. Один заказ может быть намного лучше других, поэтому нельзя просто оценивать продукт в фиксированном порядке слева-направо или справа-налево. Например, если , и являются -векторами, то их можно оценить как

• : векторное внешнее произведение, за которым следует матрично-векторное произведение, операции калькуляции или
• : векторное скалярное произведение, за которым следует векторное масштабирование, стоимость только операций.

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

4. Предположение, что матрица положительно определена

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

Определенность подразумевает, что

• диагональные записи положительные,
• ,
• для всех,

, но ни одно из этих условий, ни даже все вместе взятые, не гарантирует, что матрица имеет положительные собственные значения.

Лучший способ проверить определенность — вычислить факторизацию Холецкого, которая в любом случае часто требуется. Функция MATLAB chol возвращает сообщение об ошибке, если факторизация завершается неудачно, и может быть запрошен второй выходной аргумент, который устанавливается равным номеру этапа, на котором факторизация не удалась, или нулю, если факторизация прошла успешно. В случае неудачи частично вычисленный коэффициент возвращается в первом аргументе, и его можно использовать, например, для вычисления направления отрицательной кривизны (как это необходимо при оптимизации).

Этот грех занимает первое место в книге Шмельцера и Хаузера «Семь грехов в оптимизации портфеля», потому что при оптимизации портфеля отрицательное собственное значение в ковариационной матрице может идентифицировать портфель с отрицательной дисперсией, обещая сколь угодно большие инвестиции без риска!

5. Неиспользование структуры в матрице

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

Матрицы из седловых задач являются симметричными неопределенными и имеют вид

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

Матрицы циркулянтов обладают важным свойством: они диагонализируются унитарной матрицей, называемой матрицей дискретного преобразования Фурье. Используя это свойство, можно решать в операциях, а не в операциях, необходимых, если игнорируется циркулянтная структура.

В идеале программа линейной алгебры должна определять структуру в матрице и вызывать алгоритм, использующий эту структуру. Ярким примером такого метаалгоритма является функция обратной косой черты MATLAB x = A\b для решения . Обратная косая черта проверяет, является ли матрица треугольной (или перестановкой треугольной матрицы), верхней Гессенберговой, симметричной или симметричной положительно определенной, и применяет соответствующий метод. Он также позволяет быть прямоугольным и решает проблему наименьших квадратов, если строк больше, чем столбцов, и недоопределенную систему, если столбцов больше, чем строк.

6. Использование определителя для обнаружения почти сингулярности

Матрица невырожденна тогда и только тогда, когда ее определитель отличен от нуля. Поэтому можно было бы ожидать, что маленькое значение указывает на почти сингулярную матрицу. Однако размер ничего не говорит нам о близкой сингулярности. В самом деле, так как мы можем получить любое значение для определителя, умножая на скаляр, все же он не более или менее почти сингулярен, чем для .

Другое ограничение определителя показано двумя матрицами

Обе матрицы имеют единичные диагональные и недиагональные элементы, ограниченные по модулю величиной . Итак , еще

Так что плохо кондиционируется для больших . На самом деле, если мы изменим элемент на, то матрица станет сингулярной! Напротив, всегда очень хорошо кондиционирован. Определитель не может отличить плохо обусловленное от хорошо обусловленного.

7. Использование собственных значений для оценки обусловленности

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

Но, как показывает матрица в (1), эта граница может быть очень слабой.

Именно сингулярные числа , а не собственных значений характеризуют число обусловленности для 2-нормы. В частности,

где — разложение по сингулярным числам (SVD), с и ортогональное и , . Например, если симметрично, то множества и совпадают, но в общем случае собственные значения и сингулярные значения могут сильно различаться.