Нахождение обратной матрицы

[artful7]

Существуют ли алгоритмы нахождения обратной матрицы, дающие точный результат, или это недостижимо в принципе?

[незваный гость]

Алгоритм Гаусса. А с чего Вы взяли, что результат всегда неточный?! Если у Вас точные данные, и Вы ведете точные вычисления, то Вы получите точный ответ (примером тому — системы компьютерной алгебры). Неточный результат дают итеративные методы.

[artful7]

А ограничения у метода имеются?

[незваный гость]

Да. Матрица не должна быть вырожденной.

Кроме того, я подозреваю, это не самый эффективный метод.

[artful7]

Но у меня в расчетах практически всегда использовались вырожденные матрицы. Для справки - я пробовал обучать нечеткую модель методом Левенберга-Марквардта, так вот, там требуется строить якобиан - по сути матрицу производных, а затем находить обратную ей матрицу. Гаусс не сработал. Пытался для эксперимента найти обратную матрицу в Excel - безрезультатно.
Поэтому и спрашиваю, какие есть эффективные средства нахождения обратной матрицы?

[незваный гость]

Простите, Вы просили не эффективные, а точные методы. Если у Вас небольшая размерность, можете выложить (здесь или на файлообменнике), попробуем понять.

Посмотрите, кстати, обусловленность матриц. И методы уточнения обратной матрицы (самый простой выглядит примерно так: пусть $B$ — обратная матрица, полученная численно. $A B = E +\varepsilon$. Тогда мы можем попытаться улучшить обратную матрицу, умножив ее на $ E - \varepsilon $: $B_1 = B(1-\varepsilon)$. Мы можем продолжать этот процесс до тех пор, пока норма невязки уменьшается).

[Yuri Gendelman]

artful7 писал(а):

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

В первоначальном посте Вы забыли указать, что Ваши матрицы близки к вырожденным. А для них используются специальные методы. Попробуйте, например, метод псевдообращения (обращение Пенроуза).
1) Алберт А. Регрессия, псевдоинверсия, рекуррентное оценивание. 1977
2) Голуб Дж., Ван Лоун Ч. Матричные вычисления. 1999 (раздел 5.5.4)

[drob]

У меня необратимые матрицы обращаются. http://www.drobotenko.com/code_rus.html - здесь в примерах решается СЛАУ для вырожденноц матрицы. Обращение аналогично. СЛАУ для вырожденной использовал. В обращении есть коды для этого случая, но пока не понадобилось.

Естественно ообращение на некотором подпространстве происходит

[artful7]

По описанию выглядит интригующе, т.к. в некоторых случаях обращение матриц - это проблема с "большой буквы".
В Си не силен, поэтому у меня просьба: можно ли обобщенный алгоритм увидеть (мне в ЛС или на емайл), чтобы на Паскале или VB сварганить программу (Ваши авторские права нарушаться, естественно, не будут!)?

Добавлено спустя 1 минуту 43 секунды:

Кстати, метод формальных манипуляций имеет опубликованное описание или это Ваше know-how?

[drob]

artful7 писал(а):

По описанию выглядит интригующе, т.к. в некоторых случаях обращение матриц - это проблема с "большой буквы".
В Си не силен, поэтому у меня просьба: можно ли обобщенный алгоритм увидеть (мне в ЛС или на емайл), чтобы на Паскале или VB сварганить программу (Ваши авторские права нарушаться, естественно, не будут!)?

Такое замечание по поводу текстов там 2 версии И в некоторых местах сложная индексация (l+k*N) вместо [i][k] Еще два массива заводятся внутренних, там индексы от 0 и может быть специальное значение -1

Цитата:

Кстати, метод формальных манипуляций имеет опубликованное описание или это Ваше know-how?

Да простая мысль, методическая. Записываем 2 матрицы исходную и 1 потом делаем преобразования одновременно над обоимя, и когда в первой получаем 1, во второй будет обратная.

Элементарные преобразования бавают левые и правые (строки-столбцы)

Теперь доказательство:
После того ка 1 получили. Эти пары умножаем на левые обратные полевому и по правому на левые просто. Потом перетаскиваем левые через правые и групируя получаем произведение исходной матрицы на результат манипуляций над единичной.

Бонус от этого тот, что можно делать операции со строками или столбцами в произвольном порядке. Перестановки и линейные операции идут какбы в обном пакете. И не нужно доказывать равносильность промежуточных систем.

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

Добавлено спустя 13 минут 42 секунды:

Попробую в выходные на сайте написать. В общем это универсальное доказательство правомощности произвольных методов обращения.
Еще там НЕЧИСЛА задействованы. При переписывании на другие языки, чтоб использовать частичное обращение, нужно массивы флагов-индексов в параметры засунуть.

[Yuri Gendelman]

drob писал(а):

У меня необратимые матрицы обращаются.
...Естественно ообращение на некотором подпространстве происходит

Для этих же целей применяется разложение по сингулярным числам (SVD - singular values decomposition).
См. например: Райнш, Уилкинсон. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. 1976. Алгоритм I.10 (стр.125-139). Тут и прямоугольные матрицы обращаются.

[artful7]

Цитата:

Попробую в выходные на сайте написать. В общем это универсальное доказательство правомощности произвольных методов обращения.

Обязательно сделайте это. Желательно, чтобы и алгоритм был в удобочитаемом виде. Именно алгоритм - как структура не привязанная к языку программирования.

[kontrolnaya-rabota]

Уже все давно до Вас написано, оболочка на python - смотри сюда!
numpy
Примеры для начинающих
[ рекламные ссылки удалены ]

Бан за раскрутку сторонних сайтов!

[Евгений Машеров]

В Вашей постановке по крайней мере три разных задачи.

1. Точное решение задачи обращения.
2. Обращение матрицы с достаточно высокой точностью за разумное время.
3. Решение задачи, требующей обращения матрицы, если она может быть вырождена.

1. Решается переходом к арифметике рациональных чисел. Т.е. числа представляются парой "числитель/знаменатель", и все операции точные (разумеется, "метод квадратного корня" тут не пройдёт, а обычный Гаусс - вполне). Решение для невырожденной матрицы будет точным. Проблема тут в том, что числа, представляющие числитель и знаменатель, чрезвычайно быстро растут. Поэтому нужно не обычные "машинные" целые числа, а использовать арифметику многократной точности. Что весьма скверно сказывается на скорости работы. Рост промежуточных результатов зависит как от размерности матрицы, так и от её обусловленности (чем хуже обусловлена - тем больше; в вырожденном случае вообще делим на 0 и приходим к бесконечности...)
2. Если допустима небольшая погрешность (на самом деле абсолютная точность бывает нужна... Почти никогда не бывает), то хорошим решением может быть использование сингулярного разложения. По времени оно в 3-5 раз хуже Гаусса, что уже приемлемо практически.
Более "грубое" решение получается с использованием регуляризации. Например, прибавляя положительную константу к диагонали матрицы. См. Тихонова и пр.
3. Если в задаче оказывается, что решение требует обращения матрицы, а она вырождена, то целесообразно использовать псевдообращение. Для чего также может быть полезно сингулярное разложение, а также приёмы регуляризации. Иногда, впрочем, оказывается, что вырожденность вызвана тем, что обращаемая матрица имеет неполный ранг по построению. Например, она является произведением двух прямоугольных матриц, и её ранг равен меньшей из размерностей матриц. Тогда целесообразно выразить псевдообратную аналитически. Иногда вовсе обойдясь без численного обращения - всё сокрашается...

[Ajabsandal]

Евгений Машеров в сообщении #231463 писал(а):

В Вашей постановке по крайней мере три разных задачи.

1. Точное решение задачи обращения.

1. Решается переходом к арифметике рациональных чисел. Т.е. числа представляются парой "числитель/знаменатель", и все операции точные (разумеется, "метод квадратного корня" тут не пройдёт, а обычный Гаусс - вполне). Решение для невырожденной матрицы будет точным. Проблема тут в том, что числа, представляющие числитель и знаменатель, чрезвычайно быстро растут. Поэтому нужно не обычные "машинные" целые числа, а использовать арифметику многократной точности. Что весьма скверно сказывается на скорости работы. Рост промежуточных результатов зависит как от размерности матрицы, так и от её обусловленности (чем хуже обусловлена - тем больше; в вырожденном случае вообще делим на 0 и приходим к бесконечности...)

В таких алгоритмах проблема роста числителя и знаменателя решается алгоритмом сокращения простых дробей. Опробовано лет 20 назад. Где-то у меня есть на Фортране.