Каков наилучший алгоритм для решения диагональной матрицы?

Question

Я пытаюсь найти лучший способ решить пентадиагональную матрицу. Есть что-то быстрее, чем гауссово уничтожение?

Answer 1

Вы должны сделать LU или Холески разложение матрицы, в зависимости от того, является ли ваша матрица эрмитовым положительно определенной или нет, а затем выполнить замену факторами. Это, по сути, просто гауссово исключение, но имеет тенденцию иметь лучшие численные свойства. Я рекомендую использовать LAPACK, поскольку эти реализации, как правило, являются самыми быстрыми и самыми надежными. Посмотрите на процедуры _GBSV, где пробел является одним из s, d, c, z, в зависимости от вашего типа номера.

Редактировать: Если вы спрашиваете, есть ли алгоритм быстрее метода устранения фактора/решения (гауссово исключение), его нет. Специализированная процедура факторизации для ленточной матрицы занимает около 4n * k^2 операций (k - ширина полосы), а обратная подстановка занимает около 6 * n * k операций. Таким образом, для фиксированной полосы пропускания вы не можете добиться большего, чем линейное время в n.