Подскажите, пожалуйста, самый быстрый алгоритм для нахождения обратной матрицы небольшого размера (6x6), разреженностью или симметрией не обладает.

Спасибо.

P.S. Или способ решения переопределенных линейных систем уравнений (8 уравнений, 6 неизвестных), обладающий наименьшей вычислительной сложностью.

Сообщение отредактировал Grizzzly - May 16 2016, 21:38

Гаусс с выбором главного элемента. Потом идет хаусхолдер. Потом гивенс. Двое последних - численно устойчивые.

Спасибо.

посмотрите это
+
это

Супер!

для маленьких матриц и это
может пригодиться (по первой ссылке для 3х3), думаю можно увеличить до матрицы 6х6

Спасибо! Попробую.

как я понимаю, исходная задача именно эта, а 6х6 получилась решением наименьших квадратов.

Если таки 8х6 решать, то надо сделать для этой матрицы QR разложение с выбором ведущего столбца, можно сделать даже Грамм-Шмидтом, тогда алгоритм будет помещаться в 5-6 строк. Если на в R на каком-то шаге на диагонали получаемое число будет меньше чем первое в некоторое эпсилон, которое у Вас больше ошибки входных данных, то Вам надобно регуляризовать, так как иначе получится на выходе лажа.

Самым кондовым методом тогда будет оборвать QR как только на диагонали будет такое, и получить Q R_r, где Q матрица 8хr, а R_r матрица rх6 размеров. Для транспонированной R_r повторить разложение, но до конца, получив Q P_2 R Q_r P_1, где P - матрицы перестановки. Если есть возможность не писать, а попользовать лапак, то просто вызвать DGESVD из оного и занулить не нужные сингулярные значения и решить именно так, но, лапак не на всех платформах компилится, а то, что я предложил, при необходимости в атмегу даже засунуть можно, а вот DGESVD уже точно не засунешь

Если Вы до этого никогда не писали софт по линейной алгебре, то самопально написанный аогоритм Грамма-Шмидта или Хаусхолдера с перестановками и всем тем добром, что я написал, точно проиграет по скорости лапаку, хотя арифметическая сложность сингулярного разложения существенно выше Грамма-Шмидта или Хаусхолдера, это утверждение много раз мной было проверенно на куче как физтеховских, так и немецких студентах

Если только в лапаке магия какая реализована. Кроме того, кому нужно сингулярное разложение? Достаточно привести исходную систему к треугольной гауссом, хаусхолдером или гивенсом. После обратной подстановки получим решение. Или вычислить матрицу грама и решить полученную систему тем же методом. Или разложением холецкого, которое подкупает своей простотой, но содержит несколько подводных граблей.

ТС об обусловленности по входным данным ни слова не сказал, то есть скорей всего или не знает какая она, или вообще не знает что это. Поэтому и Гаусс, и Хаусхолдер с Гивенсом получат ему решение, но оно, скорей всего, будет далеким от того, что он ожидает и будет он плясать с бубном, пока годовой курс нумерики не пройдет. С SVD же он получит результат за один вызов.

PS: магия лапака в том, что у него все конвейерно и кеш-оптимизировано, а человек с этим до этого не сталкивавшийся быстро начать в этих терминах программировать не сможет, что я много раз воочию наблюдал

Да нормальное решение выдадут хаусхолдер с гивенсом. Даже в случае совсем плохо обусловленной задачи. В крайнем случае в недрах алгоритмов получится деление на 0.
И пространства для плясок с бубном честно говоря здесь не вижу. Кроме того, кто сказал что это должно работать на пэцэ? Может человек все это в с66xx запихнуть хочет. А лапак, он такой лапак...

Вот интересная статья. Используется некоторая оптимизация поворотов Гивенса с реализацией на систолическом массиве.
https://www.researchgate.net/publication/22..._MIMO_Receivers

Если использовать ПЛИС, ну или что-то с большой параллельностью, то это очень быстрая реализация. Причем как раз эффективно для маленьких матриц.

Огромнейшее спасибо! То что нужно. Еще и с таблицей количества операций. На работе тоже говорили про повороты Гивенса, нашел несколько русскоязычных статей, но эта в разы лучше.

Что-то не совсем понял исходную задачу. Ваша система имеет вид Ax = y, где размерность x - [6x1], y - [8x1], A - [8x6], задача оценить x, имея A и y?
Линейное решение получается через псевдоинверсию: x=(A^TA)^-1A^Ty, если A действительная и x=(A^HA)^-1A^Hy - если комплексная. В первом случае A^TA симметричная матрица, во втором - A^HA эрмитова. Эти матрицы обладают известной симметрией, поэтому на них разумно натравить алгоритм Холецкого, по скорости он выигрывает у методов, которые не используют специальные свойства матриц.

Да, именно так. И решал через псевдообратную матрицу точно так же. С самим решением понятно. А вот с выбором алгоритма, отвечающего минимальной вычислительной сложности, были вопросы. Понял. Спасибо.

P.S. Задача свелась к чисто вещественной.