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

@Buckstabue · Регистрация: 12.01.2012

Я в алгебре очень слаб. В голове есть идея вычислить детерминант по перестановкам, но в голову не приходит алгоритм перебора всех перестановок. Есть идея разложить все по первой строке, но тогда придется делать это рекурсивно до тех пор, пока не встретится определитель 2x2, что выглядит не очень красиво, хотя я вряд ли буду вычислять определители выше 6 порядка. Но хотелось бы решить это элегантно. Есть ли у кого какие наработки?
У меня пока идея такова:
Заводим double det = 0; в которой будем хранить детерминант
для каждого элемента первой строки создать стэк "вычеркиваемых" строк/столбцов и до тех пор пока размер стэка не станет равным (n-2) ложить в него самый верхний левый элемент, среди "невычеркнутых" строк/столбцов. Когда стэк станет таким, то вычисляем этот простейший определитель и прибавляем к переменной det, далее удаляем вершину стэка и пытаемся сместиться относительно новой вершины правее, так чтобы эта столбец не был "зачеркнут", если ничего не выходит, то просто удаляем вершину и делаем все это до тех пор пока стэк не опустеет и первая строка, по которой мы производим разложение, не закончится

Добавлено через 16 минут
точнее здесь вместо стэка лучше подходит список, ведь в стэке нельзя производить поиск по значению

silent_1991 · Регистрация: 11.11.2009

Сообщение от Buckstabue

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

Есть. Основан на методу Гаусса. Смысл в том, чтобы превратить нашу матрицу в верхне- или нижнетреугольную, применив к ней прямой ход метода Гаусса. Тогда определитель будет равен произведению всех элементов на её главной диагонали (потому что все остальные миноры при стандартном вычислении определителя через разложение на миноры будут умножаться на 0).

Добавлено через 3 минуты
А, ну ещё можно провести LU-разложение, которое достаточно похоже приведённый выше метод. В итоге исходная матрица разложится на две - L (нижнетреугольную) и U (верхнетреугольную). Определитель исходной матрицы равен произведению определителей L- и U-матрицы. Их же определители, как я сказал выше, равны произведению элементов на главных диагоналях.

@Buckstabue · Регистрация: 12.01.2012

silent_1991, я уже думал об приведении к диагональной, но боюсь погрешности будут скапливаться. Для их снижения придется еще проектировать класс дробей. А ни кто не располагает достаточно качественным, желательно шаблонным, классом дробей? Было бы супер

@hoob · Регистрация: 04.11.2012

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

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

Байт · Регистрация: 24.12.2010

Buckstabue, Вот тут
Найти все возможные перестановки цифр
есть алгоритмы перестановок. И рекурсивные, и не.

silent_1991 · Регистрация: 11.11.2009

Сообщение от hoob

меняете соответствующие строки местами

Главное при этом не забыть, что каждая перестановка меняет знак определителя на противоположный.

@hoob · Регистрация: 04.11.2012

Сообщение от silent_1991

Главное при этом не забыть, что каждая перестановка меняет знак определителя на противоположный.

Это само собой, так же еще нужно учитывать на что делим и умножаем)

silent_1991 4960 / 3036 / 149 Регистрация: 11.11.2009 Сообщений: 7,027 Завершенные тесты: 1
	07.11.2012, 14:52 Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn?	#2
	Сообщение от Buckstabue Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? Есть. Основан на методу Гаусса. Смысл в том, чтобы превратить нашу матрицу в верхне- или нижнетреугольную, применив к ней прямой ход метода Гаусса. Тогда определитель будет равен произведению всех элементов на её главной диагонали (потому что все остальные миноры при стандартном вычислении определителя через разложение на миноры будут умножаться на 0). Добавлено через 3 минуты А, ну ещё можно провести LU-разложение, которое достаточно похоже приведённый выше метод. В итоге исходная матрица разложится на две - L (нижнетреугольную) и U (верхнетреугольную). Определитель исходной матрицы равен произведению определителей L- и U-матрицы. Их же определители, как я сказал выше, равны произведению элементов на главных диагоналях.

@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
	Для уменьшения погрешностей, которые будут накапливаться при вычислениях, могу могу посоветовать метод выбора ведущего элемента. Основной алгоритм - метод Гаусса, но перед каждой итерацией вы выбираете самый большой элемент в столбике и меняете соответствующие строки местами. Очень хорошо ведет себя даже при слабо обусловленных матрицах)

Байт 15833 / 10160 / 1522 Регистрация: 24.12.2010 Сообщений: 19,148
	07.11.2012, 18:55 Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn?	#5
	Buckstabue, Вот тут Найти все возможные перестановки цифр есть алгоритмы перестановок. И рекурсивные, и не.

silent_1991 4960 / 3036 / 149 Регистрация: 11.11.2009 Сообщений: 7,027 Завершенные тесты: 1
	08.11.2012, 10:13 Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn?	#6
	Сообщение от hoob меняете соответствующие строки местами Главное при этом не забыть, что каждая перестановка меняет знак определителя на противоположный.

@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?

Опции темы

С++ для начинающих

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