Что лучший алгоритм должен найти детерминантом матрицы?
Может любой говорить мне, который является лучшим алгоритмом для нахождения значения детерминанта матрицы размера N x N?
2 ответа
Если вы провели первоначальное исследование, вы, вероятно, обнаружили, что при N> = 4 вычисление определителя матрицы становится довольно сложным. Что касается алгоритмов, я хотел бы указать вам на статью в Википедии о детерминантах матриц , особенно на раздел «Алгоритмическая реализация».
По моему собственному опыту, вы можете легко найти алгоритм разложения LU или QR в существующих библиотеках матриц, таких как Alglib . Однако сам алгоритм не совсем простой.
Здесь - обширное обсуждение.
Есть много алгоритмов.
Самый простой - взять разложение LU . Тогда, поскольку
det M = det LU = det L * det U
и оба L и U являются треугольными, определитель является произведением диагональных элементов L и U . То есть O (n ^ 3) . Есть более эффективные алгоритмы.