Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.84/38: Рейтинг темы: голосов - 38, средняя оценка - 4.84
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
1

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

22.07.2012, 06:21. Просмотров 7439. Ответов 8
Метки нет (Все метки)

Всем доброго времени суток, я достаточно долго искал шаблон кода для вычисления определителя квадратной матрицы, нашел на просторах рунета более-менее нормальный алгоритм, все считает верно для матрицы размерностей 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. Встречал много отзывов о неправильности использования рекурсии для нахождения детерминанта? С чем это может быть связано?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.07.2012, 06:21
Ответы с готовыми решениями:

Оптимизация алгоритма вычисления определителя матрицы
Здравствуйте! Написал я давеча программку, которая считает определитель. Только вот беда - он не...

Код вычисления определителя матрицы до 10-го порядка
Мне очень нужен код программы для вычисления определителя матрицы до 10-го порядка.

Нахождение определителя матрицы n-го порядка без рекурсии
Здравствуйте, мне на дом дали задачу на С++ написать программу которая находит определитель...

Рекурсивный метод вычисления определителя матрицы
суть в том, что не получается реализовать рекурсивный метод Determinant в классе Matrix. ...

8
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 06:58 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 у нас будет ну очень много всего:<
1
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
22.07.2012, 07:08  [ТС] 3
nexen, получается, что мне придется использовать совершенно другой алгоритм для n>3 && n<10 ? Я где-то видел на этом форуме алгоритм вычисления определителя методом Гаусса, но он был настолько наворочен, что я вообще не понял о чем там речь .
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 07:24 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
1
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
22.07.2012, 07:40  [ТС] 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);
}
Было бы не плохо это перевести на язык обычных массивов, этот шаблон я из книжки одной взял.
Хотя бы тут определитель правильно вычисляется, но вот перенести в мой код никак не удается .
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 08:38 6
Nuclear_Razor, если честно, не понимаю, как это :
C++
1
2
3
4
det = 1.0;
for (i = 0; i < m; ++i) {
det *= *(a+i*n + i);
}
вычисляет определитель

Не по теме:

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

0
Эксперт С++
4251 / 2225 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.07.2012, 08:52 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);
}
Очень даже правильно, НО только для матриц, приведенных к ступенчатому виду. Здесь перемножаются диагональные элементы матрицы. Для произвольной квадратной матрицы алгоритм неверен.
1
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
22.07.2012, 09:00 8
Thinker, вот как, даже не подумал. Тогда да, это как раз и есть Гаусс. Вот только алгоритм приведения к ступенчатому виду будет.. кхм.. более масшатбный что ли.
0
49 / 2 / 0
Регистрация: 22.07.2012
Сообщений: 104
Записей в блоге: 1
23.07.2012, 01:56  [ТС] 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, туча-тучная). По-моему с помощью предложенных там библиотек, все сделать получится труднее, нежели использовать стандартные библиотеки.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.07.2012, 01:56

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Написать функцию для вычисления определителя матрицы
Нужна функция для вычисления ОПРЕДЕЛИТЕЛЯ матрицы, аргументами которой будет количество строк в...

Создать функцию для вычисления определителя матрицы 2х2
Создать функцию для вычисления определителя матрицы 2х2. (в C++) HELP ME PLEASE

Улучшение алгоритма записи строк
В общем код полностью рабочий. В функции fill_start_file происходит запись в файл с условием, что...

Улучшение алгоритма подсчета строк, букв, слов
Данный алгоритм, компилируется. Однако есть недочеты: 1. Не всегда верно считает буквы. Почему не...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.