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

Улучшение алгоритма вычисления определителя матрицы, порядка n>3 - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 52, средняя оценка - 4.83
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 103
Записей в блоге: 1
22.07.2012, 06:21     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #1
Всем доброго времени суток, я достаточно долго искал шаблон кода для вычисления определителя квадратной матрицы, нашел на просторах рунета более-менее нормальный алгоритм, все считает верно для матрицы размерностей n=1,2,3; Но уже при 4-ом порядке считает абсолютно неправильно.

Шаблон программы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int det (int a[10][10], int razm)   //Нахождение определителя
//int a[10][10]; int I=0; - массив и размерность (I-строки) указаны в главной функции
{
int l;
int d;
double sum11=1,sum12=0, sum21=1, sum22=0;
//Находим детерминант
if(razm==1)
{
        return a[0][0];
}
    if(razm==2)
    {
 
            return (a[0][0]*a[1][1]-a[0][1]*a[1][0]);
    
    }
        for (int i=0;i<razm;i++)
        {
                sum11=1; l=2*razm-1-i;sum21=1;
        for (int j=0;j<razm;j++)
        {
            sum21*=a[j][l%razm];
            l--;
            sum11*=a[j][(j+i)%(razm)];
        }
        sum22+=sum21;
        sum12+=sum11;
    }
    d=sum12-sum22;
return d;
}
Честно говоря, я не учусь на программиста, а только на физика), но мне бы хотелось довести до ума мою программу, основная программа производит вычисление СЛАУ методом Гаусса, корни находит верно, но нужен алгоритм, доступный и понятный, без всяких указателей (я ими не умею практически пользоваться).

P.S. Встречал много отзывов о неправильности использования рекурсии для нахождения детерминанта? С чем это может быть связано?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 06:58     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #2
Честно говоря, я не учусь на программиста, а только на физика), но мне бы хотелось довести до ума мою программу, основная программа производит вычисление СЛАУ методом Гаусса, корни находит верно, но нужен алгоритм, доступный и понятный, без всяких указателей (я ими не умею практически пользоваться).

P.S. Встречал много отзывов о неправильности использования рекурсии для нахождения детерминанта? С чем это может быть связано?
Насколько мне известно, основная проблема возникает в исключении строк и слобцов. Т.е, если у тебя матрица 5х5, ты взял некоторую строку и идешь по ней с целью получить 5 матрив 4х4 с умножением на соответствующий элемент. Так вот, эти 4х4-матрицы получаются путем исключения строки и столбца. Некоторые это забывают или просто не знают, как сделать.
p.s Замечу так же, что алгоритм, который я описал хоть и верен, но работать будет дольше всего возможного, ибо для 100х100 матрицы мы получим 100 матриц 99х99, а от каждой из 99х99 получим ещё по 99 98х98, и того за два шага уже 9900 матриц. К матрице 2х2 у нас будет ну очень много всего:<
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 103
Записей в блоге: 1
22.07.2012, 07:08  [ТС]     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #3
nexen, получается, что мне придется использовать совершенно другой алгоритм для n>3 && n<10 ? Я где-то видел на этом форуме алгоритм вычисления определителя методом Гаусса, но он был настолько наворочен, что я вообще не понял о чем там речь .
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 07:24     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #4
Nuclear_Razor, если я правильно помню, то алгоритм Гаусса заключается в том, чтобы привести одну строку/столбец к виду вектора, где только один элемент не 0, благодоря чему из матрицы 100х100 получается матрица 99х99 умноженная на некоторое Aij, при этом матрица 99х99 одна.

Ну так для n>3 больше нет "общей формулы". Для n=2 есть формула перекрестного умножения. У вас это :
C++
1
 return (a[0][0]*a[1][1]-a[0][1]*a[1][0]);
Для n=3 есть метод треугольников или диагоналей/прямых (по-разному называют).
Для n>3 уже нужно приводить к виду n=2 или n=3. Проще всего к n=3, а там уже треугольником, но n=2 тоже нужно прописать по причине того, что матрица изначально может быть 2х2
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 103
Записей в блоге: 1
22.07.2012, 07:40  [ТС]     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #5
nexen, для n=3, данный алгоритм считает все правильно , есть еще другой код:

Инициализация матрицы:

C++
1
2
3
4
5
6
7
8
9
10
a = (double *) malloc(m * n * sizeof(double));
printf("Введите элементы матрицы:\n");
for (i = 0; i < m; ++i) 
{
for (j = 0; j < n; ++j) 
{
// Вводим элемент с индексами i, j
scanf("%lf", (a+i*n + j));
}
}
Код вычисления определителя:

C++
1
2
3
4
5
6
7
8
if (m == n) 
{
// Для квадратной матрицы вычисляем и печатаем
// ее определитель
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
Было бы не плохо это перевести на язык обычных массивов, этот шаблон я из книжки одной взял.
Хотя бы тут определитель правильно вычисляется, но вот перенести в мой код никак не удается .
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 08:38     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #6
Nuclear_Razor, если честно, не понимаю, как это :
C++
1
2
3
4
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
вычисляет определитель

Не по теме:

Наверное мне нужно выспаться

Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2012, 08:52     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #7
Цитата Сообщение от Nuclear_Razor Посмотреть сообщение
Код вычисления определителя:

C++
1
2
3
4
5
6
7
8
if (m == n) 
{
// Для квадратной матрицы вычисляем и печатаем
// ее определитель
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
Очень даже правильно, НО только для матриц, приведенных к ступенчатому виду. Здесь перемножаются диагональные элементы матрицы. Для произвольной квадратной матрицы алгоритм неверен.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 09:00     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #8
Thinker, вот как, даже не подумал. Тогда да, это как раз и есть Гаусс. Вот только алгоритм приведения к ступенчатому виду будет.. кхм.. более масшатбный что ли.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2012, 01:56     Улучшение алгоритма вычисления определителя матрицы, порядка n>3
Еще ссылки по теме:

C++ Написать программу для поиска определителя до 10 порядка включительно
C++ Написать функцию для вычисления определителя матрицы
Создать функцию для вычисления определителя матрицы 2х2 C++

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

Или воспользуйтесь поиском по форуму:
Nuclear_Razor
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 103
Записей в блоге: 1
23.07.2012, 01:56  [ТС]     Улучшение алгоритма вычисления определителя матрицы, порядка n>3 #9
Получается, что мне придется искать алгоритмы для приведения матриц к ступенчатому виду? А потом тестировать на этом алгоритме:

C++
1
2
3
4
5
6
7
8
if (m == n) 
{
// Для квадратной матрицы вычисляем и печатаем
// ее определитель
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
Да, кстати, пытался разобрать с aglib, туча-тучная). По-моему с помощью предложенных там библиотек, все сделать получится труднее, нежели использовать стандартные библиотеки.
Yandex
Объявления
23.07.2012, 01:56     Улучшение алгоритма вычисления определителя матрицы, порядка n>3
Ответ Создать тему
Опции темы

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