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

Question

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

X = a - inv (b) * y * inv (b), x = x + a ' * vin (b) * a,

Я решаю проблему так:

С = инв(В)Y <=> BC = Y, решить 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 равно n x n), поэтому в общей сложности мы имеем O(n^3).

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

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

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

A' * E равно n^2 * (n множитель и n-1 сложение), что равно 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.Я также пропустил от А до А' по тем же причинам.

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

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+, я не думаю, что это имеет большое значение.