Форум программистов, компьютерный форум CyberForum.ru

Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
02.11.2012, 22:48     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? #1
Я в алгебре очень слаб. В голове есть идея вычислить детерминант по перестановкам, но в голову не приходит алгоритм перебора всех перестановок. Есть идея разложить все по первой строке, но тогда придется делать это рекурсивно до тех пор, пока не встретится определитель 2x2, что выглядит не очень красиво, хотя я вряд ли буду вычислять определители выше 6 порядка. Но хотелось бы решить это элегантно. Есть ли у кого какие наработки?
У меня пока идея такова:
Заводим double det = 0; в которой будем хранить детерминант
для каждого элемента первой строки создать стэк "вычеркиваемых" строк/столбцов и до тех пор пока размер стэка не станет равным (n-2) ложить в него самый верхний левый элемент, среди "невычеркнутых" строк/столбцов. Когда стэк станет таким, то вычисляем этот простейший определитель и прибавляем к переменной det, далее удаляем вершину стэка и пытаемся сместиться относительно новой вершины правее, так чтобы эта столбец не был "зачеркнут", если ничего не выходит, то просто удаляем вершину и делаем все это до тех пор пока стэк не опустеет и первая строка, по которой мы производим разложение, не закончится

Добавлено через 16 минут
точнее здесь вместо стэка лучше подходит список, ведь в стэке нельзя производить поиск по значению
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2012, 22:48     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn?
Посмотрите здесь:

Нахождение детерминанта (определителя) матрицы C++
Написать функцию для вычисления суммы элементов квадратной матрицы, расположенных ниже главной диагонали C++
C++ Алгоритм определения номера строки квадратной матрицы, сумма элементов которой максимальна
C++ Составить программу вычисления следа квадратной матрицы
Есть программный код целочисленная квадратной матрицы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
07.11.2012, 14:52     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? #2
Цитата Сообщение от Buckstabue Посмотреть сообщение
Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn?
Есть. Основан на методу Гаусса. Смысл в том, чтобы превратить нашу матрицу в верхне- или нижнетреугольную, применив к ней прямой ход метода Гаусса. Тогда определитель будет равен произведению всех элементов на её главной диагонали (потому что все остальные миноры при стандартном вычислении определителя через разложение на миноры будут умножаться на 0).

Добавлено через 3 минуты
А, ну ещё можно провести LU-разложение, которое достаточно похоже приведённый выше метод. В итоге исходная матрица разложится на две - L (нижнетреугольную) и U (верхнетреугольную). Определитель исходной матрицы равен произведению определителей L- и U-матрицы. Их же определители, как я сказал выше, равны произведению элементов на главных диагоналях.
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
07.11.2012, 18:31  [ТС]     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? #3
silent_1991, я уже думал об приведении к диагональной, но боюсь погрешности будут скапливаться. Для их снижения придется еще проектировать класс дробей. А ни кто не располагает достаточно качественным, желательно шаблонным, классом дробей? Было бы супер
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
07.11.2012, 18:38     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? #4
Для уменьшения погрешностей, которые будут накапливаться при вычислениях, могу могу посоветовать метод выбора ведущего элемента.

Основной алгоритм - метод Гаусса, но перед каждой итерацией вы выбираете самый большой элемент в столбике и меняете соответствующие строки местами. Очень хорошо ведет себя даже при слабо обусловленных матрицах)
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,989
07.11.2012, 18:55     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? #5
Buckstabue, Вот тут
Найти все возможные перестановки цифр
есть алгоритмы перестановок. И рекурсивные, и не.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.11.2012, 10:13     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? #6
Цитата Сообщение от hoob Посмотреть сообщение
меняете соответствующие строки местами
Главное при этом не забыть, что каждая перестановка меняет знак определителя на противоположный.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2012, 13:00     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn?
Еще ссылки по теме:

Написать функцию для вычисления следа квадратной матрицы C++
C++ Алгоритм Дейкстры для матрицы смежности А размером NxN, нарисовать блок-схему по коду
C++ Функция вычисления суммы элементов квадратной матрицы, которые расположены ниже главной диагонали

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
08.11.2012, 13:00     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? #7
Цитата Сообщение от silent_1991 Посмотреть сообщение
Главное при этом не забыть, что каждая перестановка меняет знак определителя на противоположный.
Это само собой, так же еще нужно учитывать на что делим и умножаем)
Yandex
Объявления
08.11.2012, 13:00     Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn?
Ответ Создать тему
Опции темы

Текущее время: 21:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru