Какой способ имеет лучшую точность для вычисления матричного матричного векторного произведения, A B u?

Question

Я хочу вычислить вектор,

s = A B u,

где s и u - N-мерный комплексный вектор, A - комплексная матрица N-by-M, B - комплексная матрица M-by-N. Какой из следующих двух способов имеет более высокую точность (более значимые цифры), когда элементы A, B и u представлены в виде чисел с плавающей запятой?

(1) Сначала вычисление B u.

Сначала сделайте умножение матрицы на вектор,

y = B u

Тогда еще одно умножение матрицы на вектор

s = A y

(2) Сначала вычисление A B.

Сначала умножьте матрицу на матрицу,

C = A B

Тогда умножение матрицы на вектор

s = C u

Есть ли какое-то известное общее правило?

Кстати, я понимаю, что метод (1) гораздо более эффективен, чем метод (2).

Answer 1

Матрично-векторное умножение обладает лучшими свойствами числовой стабильности, чем матрично-матричное умножение, поэтому я ожидаю, что метод (1) будет более точным.

Более подробно, умножение матрицы на вектор имеет хороший результати обратная оценка ошибок.Если мы возьмем, например, умножение матрицы на вектор y = B u, то ошибка в y ограничена в 2n раз на единицу округления (1e-16 при использовании стандартных чисел двойной точности), умноженной на наибольшее число в матрице B разнаибольшее число в векторе u.Это ограничение прямой ошибки.

Оценка обратной ошибки состоит в том, что вычисленный y не является точно произведением B и u, но это точно произведение немного другой матрицы B 'и вектора u.Разница между B и B 'ограничена в 2n раз умножением на единицу, умноженным на наибольшее число в матрице B.

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

Это общий принцип: вычисления с меньшим количеством выходных данных (например, умножение матрицы на вектор) с большей вероятностью будут обратно устойчивыми, чем вычисления с большим количествомвыходные данные (такие как матрично-матричные вычисления).

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

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

Добавлено 29 сентября 2011: Мой любимый источник по этой теме - Николас Дж. Хайам, Точность и стабильность численных алгоритмов., SIAM, 2002. Но во многих учебниках по численному анализу обсуждается прямой и обратный анализ ошибок, особенно те, которые посвящены линейной алгебре.

Ошибка пересылки довольно интуитивна.Если вы знаете, что B и u верны, то вас интересует разница между вычисленным произведением B u и точным произведением;это то, что говорит вам прямой анализ ошибок.Обратная ошибка вступает в игру, когда матрица B неверна (это может быть результатом более ранних вычислений, которые допускают ошибку, или это в конечном итоге является результатом измерений, которые страдают от ошибок эксперимента или моделирования).Предположим, что ошибка в B равна 1e-10, а обратная ошибка в умножении меньше, чем, например, 1e-11.Это означает, что хотя результат умножения не верен для B, который вы дали алгоритму, он верен для другой матрицы B, которая настолько близка к исходной B, что с той же вероятностью будет правильным B, чемБ вы дали алгоритм.Так что в некотором смысле это так хорошо, как вы можете надеяться.

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

Answer 2

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

В вашем случае это оказывается совершенно правильным.Не зная ничего априори о конкретных значениях в ваших матрицах, метод (1) должен быть предпочтительным.(Можно построить конкретные случаи, в которых метод (2) был бы более точным, но они, как правило, очень надуманные).