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

Question

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

X = A - Inv (B) * Y * и (B), X = X + A»* и (B) * A,

я решить проблему таким образом:

С = INV (В) У < => BC = Y, решать С. Д = С INV (В) < => DB = С = < > 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 'to D является грубым O (n^2), однако никаких вычислений не происходит, просто заменяя данные (кроме диагональных элементов, которые, конечно, одинаковы).

Решение E в ВЕ = А во второй формуле имеет обратную замену Холецкого факторизации еще раз, так что O (N^3)

А»* Е п^2 * (п сть и п-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 представляет собой О (п^3) (из-за решения L * L '* INV (В) = I является таким же, как решение BE = А)

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

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