Нахождение обратной матрицы методом LU-разложения

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

0

То есть, среди 18300 результатов выдачи гугла по строке «LU разложение матрицы» нет ни примера, ни алгоритма? Позвольте вам не поверить.

1

iifat, мне нужно именно нахождения обратной матрицы этим методом
а я честно не нашел годного примера или алгоритма

0

https://yandex.ru/search/?lr=4... 0%B5%D1%80
Здесь на форуме тоже была эта тема, смотрите в подвале

Добавлено через 29 минут
Я понял Ваше затруднение LU - разложение матрицы А практически не используется для обращения матрицы (как не очень эффективное). Чтобы найти обратную матрицу А^-1, надо n раз решить СЛАУ: для каждого столбца обратной матрицы ( - столбец с одной единицей на i - строке). Алгоритм трехэтапный:
1) Решаем , где
2) Решаем
3) Собираем все столбцы в одну матрицу

1

Пишут две программы. Первая разлагает матрицу и помещает элементы матриц LU на место исходной матрицы. Диагональные единицы не хранятся и места оказывается достаточно. Кроме того в целом векторе длины n хранится информация о перестановках строк, которые пришлось делать, чтоб не получилось деления на нуль.

Второй этап (обращение) это три шага: обращение U обращение L и перемножение результатов: . Тоже все делается без использования дополнительной памяти. В самом конце переставляются строки в соответствии с информацией, которая хранилась в целом векторе.

1

palva, Проблема ещё в том, что обращение L и U матриц тоже не такая простая задача (она решается примерно также, как я указал выше)

1

Разве непростая задача? Обратим, например L.

Система

Последовательно вычисляем самое правое x и ставим его на место соответствующего l.
Матрица U аналогично, только вычисления производятся начиная с последней строки. Кроме того реальные формулы в программе будут немного сложнее, поскольку одна из матриц имеет по диагонали единицы, которые фактически не хранятся в памяти. Таким образом обе матрицы располагаются на месте исходной матрицы. Ну а уж перемножение этих матриц это задача обратная задаче разложения. И ТС, не имеющий проблем с разложением, успешно справится и с перемножением.

Добавлено через 16 минут

Сообщение от palva В самом конце переставляются строки в соответствии с информацией, которая хранилась в целом векторе.

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

Добавлено через 4 минуты

Сообщение от palva Последовательно вычисляем самое правое x и ставим его на место соответствующего l.

Непонятно получилось. Последовательно перебираем уравнения и из каждого вычисляем самое правое неизвестное

1

Уважаемый palva, я имел в виду как раз такой алгоритм, который сводится к решению СЛАУ, который не очень мне нравится. А по идее должны быть более эффективные алгоритмы обращения матриц L и U, но они куда сложнее и сводятся к так называемой декомпозиции матриц L и U (представление в виде сумм более элементарных матриц)

1

Ну как... Я же представил алгоритм обращения матрицы L. У меня правда представлена только верхушка матрицы L из трех строк. Но по тем же формулам можно вычислять и дальше. Обращение, естественно, немного сложнее, чем решение. Решение системы это два этапа: последовательно решаем систему с матрицей U, а потом с матрицей L. А обращение это три этапа: обращаем L, обращаем U и перемножаем.

Сообщение от mathidiot и сводятся к так называемой декомпозиции матриц L и U

Матрицы L и U еще раз разлагаются на множители? Я о таком не слышал.

1

Нет, представляются в виде сумм. Точнее было это назвать суперпозицией

1

mathidiot, да оно открывает не форум а самый поиск яндекс.. и да вот есть пример
может так надо??

Миниатюры

 

0

palva, а посмотрите может так надо ??
Нахождение обратной матрицы методом LU-разложения

0

Сообщение от Bogdan____2017 может так надо??

Да, это как раз то, о чем говорилось в посте #4 и в посте #7

1

Сообщение от Bogdan____2017 palva, а посмотрите может так надо ??

Так можно. А как надо, трудно сказать. А чем вас не устроило моё предложение?
Здесь требуется дополнительная память n^2 плавающих чисел. У меня n небольших целых чисел.
Трудоемкость можно оценить. Для этого подсчитаем число умножений. Здесь решение с U требует n(n+1)/2 умножений, решение с L еще n(n+1)/2, и для n столбцов, значит умножаем на n. Получается O(n^3). У меня вычисление каждого элемента при обращении имеет порядок O(n) умножить на количество элементов n^2. Получается тоже O(n^3). (Перемножение имеет порядок O(n^2) и его добавление не меняет оценки.)

Получается, что по сложности одно и то же, но по памяти у меня выгода. Но конечно есть нюансы. У меня нельзя итерационно уточнять решение по невязке, поскольку матрицу LU мы разрушили и разместили на ее месте результат.

Вообще у нас странный разговор получается. Вы просите алгоритм, я вам его даю. Вы на это не реагируете, не оцениваете его правильность и эффективность, а просите меня оценить другой алгоритм. А зачем вы тогда спрашивали?

Добавлено через 53 минуты

Сообщение от Bogdan____2017 мне нужно именно нахождения обратной матрицы этим методом

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

1