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

[Nik_Svan]

drob в сообщении #71364 писал(а):

http://www.drobotenko.com/code_rus.html

drob: "Мат библиотеки от Intel и AMD отличаются большей скоростью. Они неплохо работают с большими матрицами, которые не помещаются в кэш. Основная операция это вычитание из строки другой строки, помноженной на число, которое в регистре с обратной запись результата. Выпадение строк из кэша, а это несколько мегабайт в зависимости от процессора приводит к замедлению на порядок. Это на одно ядро, тоесть для четырехядерных можно сказать, что производительность падает в сорок раз. Библиотеки от Intel и AMD неплохо справляются с этой проблемой."
--------------------------------------------------
Скорость алгоритма прежде всего определяется скоростью перемножения матриц. А скорость этого перемножения высока у Intel прежде всего благодаря грамотному применению блочных методов перемножения матриц. Вообще говоря, много бреда у вас понаписано. Интересно, каким коммерческим структурам вы мозги запудрили?

[ewert]

Ajabsandal в сообщении #250851 писал(а):

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

Если знаменатель объективно велик -- то ничего не поможет (кроме длинной арифметики). Но если заранее известно, что он не слишком велик (ну скажем не больше $10^{10}$, с оговорками насчёт размера матрицы и числа обусловленности), то самый дешёвый способ -- это провести метод Гаусса с полным выбором главного элемента в вещественных числах, а потом привести вещественный ответ к рациональному виду через цепные дроби.

[Ajabsandal]

ewert в сообщении #251046 писал(а):

Ajabsandal в сообщении #250851 писал(а):

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

Если знаменатель объективно велик -- то ничего не поможет (кроме длинной арифметики). Но если заранее известно, что он не слишком велик (ну скажем не больше $10^{10}$, с оговорками насчёт размера матрицы и числа обусловленности), то самый дешёвый способ -- это провести метод Гаусса с полным выбором главного элемента в вещественных числах, а потом привести вещественный ответ к рациональному виду через цепные дроби.

Простая дробь состоит не только из знаменателя. Кроме того простая дробь может иметь числитель больше знаменателя. Проблема только в возможности недопущения роста какой либо из частей простой дроби.
Мне представляется, что есть два аспекта проблемы.
1. Теоретически (нет вопросов!) существуют несократимые дроби, у которых числитель или знаменатель "не влезает" в машинное слово конечной длины.
2. Практически, даже для очень сложных задач (гидродинамика, нейтронная физика ets.) не встречал проблем роста несократимости дробей. Может быть Вы приведете реальный пример, извините за каламбур, для подтверждения своего утверждения.
Еще одно соображение: в задачах матфизики, где возникает проблема эффективного обращения матриц (точнее говорить, эффективного итерационного решения систем нелинейных уравнений), сама матрица обычно разреженная. И чем грамотней проводится декомпозиция задачи, тем более разреженной становится матрица! Как показывает опыт работы с такими матрицами, проблемы несократимости не возникает. Трудно понять, почему, но это факт. (Оговорюсь, что имелось в виду решение систем уравнений методом LU-разложения, а не обращение и операции с обратной матрицей).

-- Пн окт 12, 2009 10:54:02 --

Nik_Svan в сообщении #251019 писал(а):

drob в сообщении #71364 писал(а):

http://www.drobotenko.com/code_rus.html

drob: "Мат библиотеки от Intel и AMD отличаются большей скоростью. Они неплохо работают с большими матрицами, которые не помещаются в кэш. Основная операция это вычитание из строки другой строки, помноженной на число, которое в регистре с обратной запись результата. Выпадение строк из кэша, а это несколько мегабайт в зависимости от процессора приводит к замедлению на порядок. Это на одно ядро, тоесть для четырехядерных можно сказать, что производительность падает в сорок раз. Библиотеки от Intel и AMD неплохо справляются с этой проблемой."
--------------------------------------------------
Скорость алгоритма прежде всего определяется скоростью перемножения матриц. А скорость этого перемножения высока у Intel прежде всего благодаря грамотному применению блочных методов перемножения матриц. Вообще говоря, много бреда у вас понаписано. Интересно, каким коммерческим структурам вы мозги запудрили?

С появлением технологий CUDA и OPEN CL появились и новые возможности дешево повысить эффективность матричных вычислений, пока ни Intel ни AMD адекватного ответа не дали!

[Nik_Svan]

Ajabsandal писал(а):

...

Да вы прямо барон Мюнхаузен.

[ewert]

Ajabsandal в сообщении #251068 писал(а):

2. Практически, даже для очень сложных задач (гидродинамика, нейтронная физика ets.) не встречал проблем роста несократимости дробей.

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

[mavka]

никто не подскажет, какие есть итерационные методы обращения матриц? я слышала что-то про метод Шульца, но информации по нем нашла очень немного...а кроме Шульца еще что-то есть?

[Alik]

drob, а можно, для учебных целей продемонстрировать ваш алгоритм в MATLAB, а то мне все больше кажется что это какая-то модификация Гаусса-Жордана. По поводу точных методов для разряженных матриц: когда-то для этих целей в теории цепей был придуман метод обобщенных чисел. Его описание довольно трудно найти в интернете, однако кой-чего мне все таки удалось: стр. 71,72 в книге
Я. К. Трохименко, Ф. Д. Любич "Инженерные расчеты на микрокалькуляторах"
http://www.toroid.ru/book/trohimenko.zip

[drob]

Alik в сообщении #282810 писал(а):

drob, а можно, для учебных целей продемонстрировать ваш алгоритм в MATLAB, а то мне все больше кажется что это какая-то модификация Гаусса-Жордана.

Да все можно, только со ссылкой

[Alik]

Не в том смысле, что я хочу перевести Си на MATLAB, это дело техники когда понимаешь алгоритм. Так вот, не все (в том числе и я) понимают его до конца. Думаю, что авторское исполнение в MATLAB-e очень поспособствует пониманию.

[drob]

Alik в сообщении #283457 писал(а):

перевести Си на MATLAB

точно не сейчас, может на ЯВУ на досуге когдато. Спрашивайте что не ясно в описании

[vitaly333]

А если в исходной матрице уже содержатся нули на главной диагонали ( т.е. не в процессе обращения) то считается ли такая матрица вырожденной? И как её обращать? Просто переупорядочить строки в которых элемент на главной диагонали - нулевой? Если да то какие строки лучше выбирать?

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

Вообще говоря, не является. Хотя простейший вариант метода Гаусса-Жордана с ней не справляется, и нужно работать с более сложным. Например, с частичным выбором ведущего элемента. Т.е. для i-той строки брать в качестве ведущего не i-тый элемент, а максимальный по модулю (такой выбор даёт некоторые преимущества в точности вычислений; ещё большие даёт полный выбор, когда в качестве ведущего берётся максимальный по модулю из тех строк и столбцов, из которых ведущий элемент не выбирался - но такой выбор резко увеличивает сложность вычислений, требуя порядка $n^2$ операций, при том, что собственно вычислений на шаге O(n), а выигрыш в точности маленький). Естественно, в результате там, где в "простейшем" варианте метода получается единичная матрица - здесь будет перестановочная, но это легко учесть.

[ewert]

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

- но такой выбор резко увеличивает сложность вычислений, требуя порядка $n^2$ операций, при том, что собственно вычислений на шаге O(n),

собственно вычислений на шаге -- тоже $O(n^2)$

vitaly333 в сообщении #289279 писал(а):

А если в исходной матрице уже содержатся нули на главной диагонали ( т.е. не в процессе обращения) то считается ли такая матрица вырожденной?

Нули в исходной матрице ровным счётом ничего не значат (кроме, естественно, левого верхнего) -- уже после первого шага они, скорее всего, исчезнут.

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

Сорри. Действительно тормознул. И там, и там $O(n^2)$

[vitaly333]

Пытаюсь обратить след матрицу:

0.6784979723148752   0.0                                -0.40962684265330723  
0.3691325774395461  -0.580200394845161    -0.2228549212920383  
0.3691325774395462   0.5802003948451616  -0.22285492129203874  

В результате получаются громадные числа:

4.226*10^14   -3.884*10^14      -3.884*10^14
0.234           -1.077               0.646
7*10^14            -6.434*10^14      -6.434*10^14

Если исходную матрицу округлить скажем до 3 знака:

0.678   0.0           -0.410
0.369   -0.580   -0.223
0.369   0.580   -0.223

то результат получается совсем другой:

-2322.9167   2135.4167   2135.4167
0   -0.8621   0.8621
-3843.75   3531.25   3531.25

В чем дело? Почему такие разные результаты? Как контролировать рост элементов в матрице при обращении?
(При обращении используется LU -разложение с последующем решением треугольных систем)