| @-=ЮрА=- Заблокирован Автор FAQ |
|
29.01.2013, 18:50
Оптимизация алгоритма вычисления определителя матрицы
| |
Сообщение от Lexp  амый нелегкий путь тут - нахождение определителя прямо по определению (сумма всевозможных комбинаций того-то и того-то). Там и сложность по идее меньше будет, только вот как реализовать...
- ну так по линку в посте выше так его и нахожу Не по теме:
Сообщение от -=ЮрА=- При этом, с помощью миноров можно облегчать задачу вычисления определителя матрицы. Надо разложить определитель матрицы по некоторой строке и тогда определитель будет равен сумме всех элементов этой строки на их миноры. Разложение определителя матрицы 3 - его порядка будет выглядеть так:
знак перед произведением равен aij и Mij Добавлено через 1 минуту
Причем ниже в 5.2 уже вообще сингл функция детерминанта идёт Кликните здесь для просмотра всего текста | 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
33
34
35
36
37
38
39
| //Функция возвращает детерминант матрицы
//В функции всё понятно кроме iShowStepsOfCalcs
//iShowStepsOfCalcs - это флаг отвечающий за то чтобы
//светить или нет в консоли результаты промежуточных вычислений
//Вообще вывод промежуточных вычислений полезнаяя штука для понимания
//работы рекурсии, кому понтравится может перенаправить вывод
//промежуточных результатов в файл. Единственный минус промежуточной индика
//ции - существенное увелечиние времени вычислений
double Det(int m, double ** arr, int iShowStepsOfCalcs)
{
int i, j = 0;
double ret = 0;
double A;
double ** _arr;
if(m == 2)//В случаем 2х2 вычисляем детерминант сразу
{
ret =
arr[0][0]*arr[1][1] -
arr[1][0]*arr[0][1];
if(iShowStepsOfCalcs)
printf("Det = %lf\n",ret);
}
else//Иначе находим детерминант рекурсивно
//через алгебраическое дополнение элемента
{
for(j = 0; j < m; j++)
{
_arr = M(m, 0, j, arr);
ret += (A = (arr[0][j])*pow(-1,j)*Det(m - 1, _arr, iShowStepsOfCalcs));
if(iShowStepsOfCalcs)
printf("A[%02d][%02d] = %lf\n",1, j + 1,A);
for(i = m - 2; 0 < i; i--)
free((void *)_arr[i]);
free((void *)_arr);
}
}
return ret;
} |
|
|
