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

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

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

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

silent_1991 · 07.11.2012, 14:52

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

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

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

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

@Buckstabue · 07.11.2012, 18:31 **[ТС]**

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

@hoob · 07.11.2012, 18:38

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

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

Байт · 07.11.2012, 18:55

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

silent_1991 · 08.11.2012, 10:13

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

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

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

@hoob · 08.11.2012, 13:00

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

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

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

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

@Buckstabue 175 / 124 / 6 Регистрация: 12.01.2012 Сообщений: 624
	07.11.2012, 18:31 [ТС]	#3
	silent_1991, я уже думал об приведении к диагональной, но боюсь погрешности будут скапливаться. Для их снижения придется еще проектировать класс дробей. А ни кто не располагает достаточно качественным, желательно шаблонным, классом дробей? Было бы супер 0

@hoob 20 / 12 / 1 Регистрация: 04.11.2012 Сообщений: 89 Записей в блоге: 1
	07.11.2012, 18:38	#4
	Для уменьшения погрешностей, которые будут накапливаться при вычислениях, могу могу посоветовать метод выбора ведущего элемента. Основной алгоритм - метод Гаусса, но перед каждой итерацией вы выбираете самый большой элемент в столбике и меняете соответствующие строки местами. Очень хорошо ведет себя даже при слабо обусловленных матрицах) 0

Байт Диссидент 17569 / 11601 / 1850 Регистрация: 24.12.2010 Сообщений: 23,028
	07.11.2012, 18:55	#5
	Buckstabue, Вот тут Найти все возможные перестановки цифр есть алгоритмы перестановок. И рекурсивные, и не. 1

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

@hoob 20 / 12 / 1 Регистрация: 04.11.2012 Сообщений: 89 Записей в блоге: 1
	08.11.2012, 13:00	#7
	Сообщение от silent_1991 Главное при этом не забыть, что каждая перестановка меняет знак определителя на противоположный. Это само собой, так же еще нужно учитывать на что делим и умножаем) 0

Опции темы

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

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