Какой из них быстрее / стабильнее: инвертирующая матрица или решение трех систем линейных уравнений с несколькими правыми частями?

Question

У меня есть два уравнения, которые я решаю в каждом рекурсивном раунде:

X = A - инв (B) * Y * инв (B), X = X + A '* inv (B) * A,

Я решаю проблему следующим образом:

C = inv (B) Y <=> BC = Y, решить C. D = C inv (B) <=> DB = C <=> B'D '= C', решить D '

E = inv (B) * A <=> BE = A, решить E.

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

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

Спасибо.

Answer 1

Прежде всего, давайте предположим, что все ваши матрицы имеют порядок n x n. Затем разложение по Холески можно выполнить в операциях O (n ^ 3/6) (для больших значений n).

Решение B * c (i) = y (i) или L * L '* c (i) = y (i) (Холецкий) равно 2 * O (n ^ 2/2) или O (n ^ 2) ), но решение BC = Y - это решение n из этих уравнений (потому что Y - nxn), поэтому в сумме имеем O (n ^ 3).

Решение D ', очевидно, аналогично этому, поэтому еще один O (n ^ 3).

Транспонирование D 'в D - это грубая O (n ^ 2), но без вычислений, просто обмен данными (кроме диагональных элементов, которые, конечно, одинаковы).

Решение E в BE = A во второй формуле - это обратная замена разложения по Холески еще раз, поэтому O (n ^ 3)

A '* E равно n ^ 2 * (n mult и n-1 add), что равно O (2 * n ^ 3 - n ^ 2)

Это сумма: O (n ^ 3/6) + 3 * O (n ^ 3) + O (n ^ 2) + O (2 * n ^ 3 - n ^ 2) ~ O (31 * n ^ 3/6) ~ O (5 * n ^ 3) (для больших значений n)

Обратите внимание, что я не рассчитал сложение / вычитание матрицы, но это не имеет значения, потому что они будут одинаковыми, если мы решим инвертировать B. Я также пропустил A до A 'по тем же причинам. *

Хорошо, так сколько стоит инвертировать матрицу? Ну, мы хотим, чтобы решить матричное уравнение:

B * inv (B) = I, что аналогично решению B * x (i) = e (i) для i = 1..n, где e (i) - векторы базовой единицы в I. Обычно это делается с помощью исключения Гаусса, чтобы преобразовать систему в треугольную форму, что занимает около O (n ^ 3/3) операций. Когда триангуляция выполнена, для ее решения требуется O (n ^ 2/2) операций (обратная подстановка). Но это должно быть сделано n раз, что дает нам всего O (n ^ 4/3) + O (n ^ 3/2) операций, так что, как вы можете видеть, мы уже на грани.

Тем не менее, вычисление inv (B) при знании факторизации Холески для B равно O (n ^ 3) (потому что решение L * L '* inv (B) = I аналогично решению BE = A)

Итак, мы имеем: O (n ^ 3/6) (холецкий из B) + O (n ^ 3) (вычисление inv (B) с холеским) + 4 * O (2n ^ 3-n ^ 2) (четыре умножения матрицы) ~ O (9 * n ^ 3), что немного лучше, но все еще хуже.

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