Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
|
|
#1 | |
Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? - C++02.11.2012, 22:48. Просмотров 1273. Ответов 6
Метки нет Все метки)
(
Я в алгебре очень слаб. В голове есть идея вычислить детерминант по перестановкам, но в голову не приходит алгоритм перебора всех перестановок. Есть идея разложить все по первой строке, но тогда придется делать это рекурсивно до тех пор, пока не встретится определитель 2x2, что выглядит не очень красиво, хотя я вряд ли буду вычислять определители выше 6 порядка. Но хотелось бы решить это элегантно. Есть ли у кого какие наработки?
У меня пока идея такова: Заводим double det = 0; в которой будем хранить детерминант для каждого элемента первой строки создать стэк "вычеркиваемых" строк/столбцов и до тех пор пока размер стэка не станет равным (n-2) ложить в него самый верхний левый элемент, среди "невычеркнутых" строк/столбцов. Когда стэк станет таким, то вычисляем этот простейший определитель и прибавляем к переменной det, далее удаляем вершину стэка и пытаемся сместиться относительно новой вершины правее, так чтобы эта столбец не был "зачеркнут", если ничего не выходит, то просто удаляем вершину и делаем все это до тех пор пока стэк не опустеет и первая строка, по которой мы производим разложение, не закончится Добавлено через 16 минут точнее здесь вместо стэка лучше подходит список, ведь в стэке нельзя производить поиск по значению
0
|
|
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
|
02.11.2012, 22:48 |
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Есть ли нерекурсивный алгоритм вычисления детерминанта квадратной матрицы nxn? (C++):
6
Алгоритм Дейкстры для матрицы смежности А размером NxN, нарисовать блок-схему по коду - C++ Составить программу вычисления следа квадратной матрицы - C++ Написать функцию для вычисления следа квадратной матрицы - C++ Есть программный код целочисленная квадратной матрицы - C++ Написать функцию вычисления суммы диагональных элементов заданной квадратной матрицы - C++ Алгоритм определения номера строки квадратной матрицы, сумма элементов которой максимальна - C++ |
silent_1991
![]() |
|
07.11.2012, 14:52 | #2 |
Есть. Основан на методу Гаусса. Смысл в том, чтобы превратить нашу матрицу в верхне- или нижнетреугольную, применив к ней прямой ход метода Гаусса. Тогда определитель будет равен произведению всех элементов на её главной диагонали (потому что все остальные миноры при стандартном вычислении определителя через разложение на миноры будут умножаться на 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
|
|
07.11.2012, 18:38 | #4 |
Для уменьшения погрешностей, которые будут накапливаться при вычислениях, могу могу посоветовать метод выбора ведущего элемента.
Основной алгоритм - метод Гаусса, но перед каждой итерацией вы выбираете самый большой элемент в столбике и меняете соответствующие строки местами. Очень хорошо ведет себя даже при слабо обусловленных матрицах)
0
|
Байт
Диссидент
![]() 17569 / 11601 / 1850
Регистрация: 24.12.2010
Сообщений: 23,028
|
|
07.11.2012, 18:55 | #5 |
Buckstabue, Вот тут
Найти все возможные перестановки цифр есть алгоритмы перестановок. И рекурсивные, и не.
1
|
hoob
|
|
08.11.2012, 13:00 | #7 |
0
|
08.11.2012, 13:00 | |
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
|
08.11.2012, 13:00 |
Привет! Вот еще темы с ответами:
7
Функция вычисления суммы элементов квадратной матрицы, которые расположены ниже главной диагонали - C++ Написать функцию для вычисления суммы элементов квадратной матрицы, расположенных ниже главной диагонали - C++ Нахождение детерминанта (определителя) матрицы - C++
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |