Детерминант

Я вот тут давно думал написать прогу, считающую детерминант. Одна только мысль - написать через рекурсию. Слышал про метод гаусса. Токо не разу не встретил. Не мог бы кто-нить подкинуть идею про Гаусса или вообще про алгоритм.

Цитата experimenter, 12.12.02, 07:25:05

Я вот тут давно думал написать прогу, считающую детерминант. Одна только мысль - написать через рекурсию. Слышал про метод гаусса. Токо не разу не встретил. Не мог бы кто-нить подкинуть идею про Гаусса или вообще про алгоритм.

никогда не считай определитель матрицы больше чем 3x3 по определению. Эта штука работает с трудоемкостью n! а это при n>10 жуткие тормоза.

А идея метода Гаусса основана на двух фактах:
1. при добавлении к i-ой строке матрицы j-ой строки, умноженной на константу (i не равно j), определитель не меняется.
2. определитель диагональной (или верхне/нижне треугольной) матрицы равен произведению диагональных элементов

Путем линейных комбинаций приводим матрицу к этому виду (трудоемкость n³) и считаем произведение диагональных элементов.

см http://alglib.dore.ru/linalg/index.html#det

эврика! какой я оказывается недогадливый.  ;D спасибо.

дело в следующем.

наша матрица напр такова:

а11 а12 а13 ... a1n
a21 а22 ....
....  .... ... ...
    ... ..
an1 ...             ann

сначала "обнуляем" первый столбец следующим способом.
из всех строк ниже первого вычитается первая строка с такими коэффициентами, чтобы в 1 столбце получился 0, те напр из 2й строки надо вычесть 1ю , умноженную на а21/а11. для каждой строки будет свой коэффициент. таким способом 1й столбец будет содержать нули, кроме 1го элемента, потому обнуляем написано в кавычках.

повторяем вышеописанную операцию со вторым столбцом. вычитаем с вышеописанными коэффициентами вторую строку из всех последующих строк, те напр из 5й строки вычитаем 2ю , умноженную на а52/а22. заметим, что из вышележащих строк не надо ничего вычитать, ибо мы стремимся к нулям только ниже главной диагонали.

сию операцию следует произвести со всеми столбцами. в итоге мы получим матрицу следующего содержания:

а11 а12 а13 ... a1n
0    b22 ....
..0..  .... ... ...
 ...  0 ....bkk .. bkn
..0.. .. 0 ...  .. ...
0 ...      ...    0  bnn

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

круто было! спасибо.

теория также говорит что если в матрице стоят числа то вышеописанный алгоритм
работает за куб времени

но если там стоят буквы икс игрек и т.п то задача превращается в експоненциальную


иногда вместо детерминанта считают перманент матрецы - как и детерминант только все миноры складывают так вот определение перманенты тоже экспоненциально

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

Цитата wormball @ 27.12.02, 19:40

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

Более того, в реальных случаях техники перемещения столбцов/строк (их несколько основных) необходимы, иначе
происходит серьезная потеря точности.

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

Сообщение отредактировано: Adil - 14.09.04, 13:41

тема кстати двухлетней давности

Добавлено в 14.09.04, 16:05:
или ето мне напоминание, чтобы я фак дописывал?
искренне каюсь, при первой же возможности (при первом же желании ) начну дописывать.

Добавлено в 14.09.04, 16:07:
кстати илье кантору пламенный привет

Ребята, кто нибудь может помочь написать программу на с++???
Срочно требуется , не могу додуматься.

Может, но не хочет.

Возьми у меня на сайте.