Перейти к содержанию
    

Быстрые алгоритмы нахождения обратной матрицы

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

 

Спасибо.

 

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

Изменено пользователем Grizzzly

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

Спасибо.

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Спасибо.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

для маленьких матриц и это

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

P.S. Или способ решения переопределенных линейных систем уравнений (8 уравнений, 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 уже точно не засунешь :)

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

iiv:

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Если только в лапаке магия какая реализована. Кроме того, кому нужно сингулярное разложение?.

 

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

 

 

Да нормальное решение выдадут хаусхолдер с гивенсом. Даже в случае совсем плохо обусловленной задачи. В крайнем случае в недрах алгоритмов получится деление на 0.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вот интересная статья. Используется некоторая оптимизация поворотов Гивенса с реализацией на систолическом массиве.

https://www.researchgate.net/publication/22..._MIMO_Receivers

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вот интересная статья.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Что-то не совсем понял исходную задачу. Ваша система имеет вид Ax = y, где размерность x - [6x1], y - [8x1], A - [8x6], задача оценить x, имея A и y?

Линейное решение получается через псевдоинверсию: x=(ATA)-1ATy, если A действительная и x=(AHA)-1AHy - если комплексная. В первом случае ATA симметричная матрица, во втором - AHA эрмитова. Эти матрицы обладают известной симметрией, поэтому на них разумно натравить алгоритм Холецкого, по скорости он выигрывает у методов, которые не используют специальные свойства матриц.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Что-то не совсем понял исходную задачу. Ваша система имеет вид Ax = y, где размерность x - [6x1], y - [8x1], A - [8x6], задача оценить x, имея A и y?

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...