Developing.ru

Здравствуйте!

Написал на Delphi 6 расчет определителя квадратнойй матрицы, на матрицу 7x7 уходит 1 секунда, 8x8 - 24 секунды. Это нормально?
Для определителя я получаю n^n сочетаний, а из них выделяю n!
Можно ли по-другому, напрмер, получать сразу все нужные перестановки?

Итак, проблема заключается в поиске более эффективного алгоритма.
Посему тема пеезжает из Delphi в Алгоритмы.

Геннадий писал(а):Здравствуйте!

Написал на Delphi 6 расчет определителя квадратнойй матрицы, на матрицу 7x7 уходит 1 секунда, 8x8 - 24 секунды.
Это нормально?

Вполне может быть. Там прирост нелинейный.

[/quote]
Для определителя я получаю n^n сочетаний, а из них выделяю n!
Можно ли по-другому, напрмер, получать сразу все нужные перестановки?[/quote]

Можно без перестановок.

1. Рекуррентный алгоритм ( по строчке / столбцу )
2. Численный (Метод Крылова, например)

Я написал и через приведение к треугольному виду, и это работает намного быстрее, но в задании необходимо считать и с перестановками.
Рекурентный я до этого тоже пробовал использовать, но там расчётов не меньше, к тому же я его так и не отладил.
А что за метод Крылов, это что такое то?

Геннадий писал(а):Я написал и через приведение к треугольному виду, и это работает намного быстрее, но в задании необходимо считать и с перестановками.
Рекурентный я до этого тоже пробовал использовать, но там расчётов не меньше, к тому же я его так и не отладил.
А что за метод Крылов, это что такое то?

Метод Крылова - численный, с итерациями. Если очень надо, пороюсь
в книге и выложу. Но он явно не подойдёт. Описан у
Бахвалова или Мысовских.

Ладно, спасибо, поищу ради интереса, может быть.

У меня есть процедура подсчета определителя, только на он на С++, зато считает быстрее. 8*8 за 1.5 секунды. Хотя допускаю, что возможно играет роль и скорость самого компьютера.

double Det (double a[], int n)
/* расчет определителя матрицы
а-заданная матрица
n-порядок определителя
возвр. знач. - знач. определителя
*/
{
register int i,j,k;
int m,m1,sign=1;//sign-знак алгебраического дополения

double *a1 /* минор *а1 */,s=0;

if(n==1)
return a[0];
else
{
a1= new double[(n-1)*(n-1)];
for (i=0; i<n; i++)
{
//получение минора
for (j=1, m=0, m1=n; j<n; j++)
for(k=0; k<n; k++, m1++)
if (k!=i)
a1[m++]=a[m1];
//вычисление определителя
sign*=-1;
s+=a*sign*Det(a1,n-1);
}
delete [] a1;
}
return s;
}

Код в принципе не сложный, так что перевести его на , думаю будет не сложно.

Метод Крылова довольно сложен.
Алгоритмы прямого вычисления - бессмысленны ( мне, как геодезисту приходится работать с определителями порядка 20, 50, а то и больше).
Лучшее решение - алгоритм Гаусса. Простой как сама жизнь.
См. Демидович, Марон "Основы вычислительной математики"

Лучшее решение - алгоритм Гаусса. Простой как сама жизнь.

Простой-то понятно. Но не точный. В нем погрешность накапливается от итерации к итерации. Хотя для небольших матриц - самое то, работает быстро, пишется просто.

Это метод-то Гаусса неточный? Он, простите, построен строго в соответсвии с определением:
Определитель матрицы n-го порядка, n>1, равен сумме произведений элементов любой строки (столбца) на их алгебраические дополнения и свойством определителей:
Определитель не изменится, если к элементам любой его строки (столбца) прибавить элементы любой другой строки (столбца), умноженные на одно и то же число.

Так что точнее не бывает