Есть ли быстрый способ инвертировать матрицу в Matlab?

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

Это неправда, потому что вы все еще можете использовать mldivide, чтобы получить обратное. Обратите внимание, что A-1 = A-1 * I. В MATLAB это эквивалентно

invA = A\speye(size(A));

На моей машине это занимает около 10,5 секунд для 5000x5000 матрицы. Обратите внимание, что в MATLAB есть функция inv для вычисления обратной матрицы . Хотя это займет примерно столько же времени, это менее эффективно с точки зрения числовой точности (подробнее см. Ссылку).

Во-первых, их определитель равен 1, поэтому они определенно обратимы.

Вместо det(A)=1, это номер условия вашей матрицы, который определяет, насколько точным или стабильным обратное будет. Обратите внимание, что det(A)=∏i=1:n λi. Таким образом, просто установив λ1=M, λn=1/M и λi≠1,n=1, вы получите det(A)=1. Однако, как M → ∞, cond(A) = M2 → ∞ и λn → 0, это означает, что ваша матрица приближается к сингулярности, и при вычислении обратного будут большие числовые ошибки.

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

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

Я бы предпочел способ ускорить Matlab

MATLAB использует исключение Гаусса для вычисления обратной матрицы общей матрицы (полный ранг, не разреженный, без каких-либо специальных свойств) с использованием mldivide, и это Θ(n3), где n - размер матрицы. Итак, в вашем случае n=5000 и есть 1.25 x 1011 операций с плавающей запятой. Итак, на разумной машине с вычислительной мощностью около 10 Гфлопс вам потребуется не менее 12,5 секунд для вычисления обратного, и выхода из этого нет, если только вы не воспользуетесь «специальными свойствами» (если они пригодны для использования )

Инвертировать произвольную матрицу размером 5000 x 5000 непросто с вычислительной точки зрения, независимо от того, какой язык вы используете. Я бы порекомендовал посмотреть на приближения. Если ваши матрицы имеют низкий ранг, вы можете попробовать приближение низкого ранга M = USV '

Вот еще несколько идей из math-overflow:

https://mathoverflow.net/search?q=matrix+inversion+approximation

Сначала предположим, что все собственные значения 1. Пусть A будет жордановой канонической формой вашей матрицы. Затем вы можете вычислить A^{-1}, используя только матричное умножение и сложение на

A^{-1} = I + (I-A) + (I-A)^2 + ... + (I-A)^k

где k < dim(A). Почему это работает? Потому что генерирующие функции - это здорово. Напомним расширение

(1-x)^{-1} = 1/(1-x) = 1 + x + x^2 + ...

Это означает, что мы можем инвертировать (1-x), используя бесконечную сумму. Вы хотите инвертировать матрицу A, поэтому вы хотите взять

A = I - X

Решение для X дает X = I-A. Следовательно, путем подстановки имеем

A^{-1} = (I - (I-A))^{-1} = 1 + (I-A) + (I-A)^2 + ...

Здесь я использовал единичную матрицу I вместо числа 1. Теперь у нас есть проблема конвергенции, но на самом деле это не проблема. Исходя из предположения, что A находится в жордановой форме и имеет все собственные значения, равные 1, мы знаем, что A является верхним треугольником со всеми 1 на диагонали. Следовательно, I-A является верхним треугольником со всеми 0 по диагонали. Следовательно, все собственные значения I-A равны 0, поэтому его характеристический полином равен x^dim(A), а его минимальный полином равен x^{k+1} для некоторого k < dim(A). Поскольку матрица удовлетворяет своему минимальному (и характеристическому) многочлену, это означает, что (I-A)^{k+1} = 0. Следовательно, приведенный выше ряд конечен с самым большим ненулевым членом (I-A)^k. Так что сходится.

Теперь для общего случая поместите свою матрицу в форму Жордана, чтобы у вас была блочно-треугольная матрица, например:

A 0 0
0 B 0
0 0 C

Где каждый блок имеет одно значение по диагонали. Если это значение равно a для A, используйте описанный выше трюк, чтобы инвертировать 1/a * A, а затем умножить a обратно. Поскольку полная матрица блочно-треугольная, обратная матрица будет

A^{-1} 0      0
0      B^{-1} 0
0      0      C^{-1}

В наличии трех блоков нет ничего особенного, так что это работает независимо от того, сколько у вас есть.

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