Здравствуйте!
Написал на Delphi 6 расчет определителя квадратнойй матрицы, на матрицу 7x7 уходит 1 секунда, 8x8 - 24 секунды. Это нормально?
Для определителя я получаю n^n сочетаний, а из них выделяю n!
Можно ли по-другому, напрмер, получать сразу все нужные перестановки?
Определитель матрицы
- Naeel Maqsudov
- Сообщения: 2551
- Зарегистрирован: 20 фев 2004, 19:17
- Откуда: Moscow, Russia
- Контактная информация:
Итак, проблема заключается в поиске более эффективного алгоритма.
Посему тема пеезжает из Delphi в Алгоритмы.
Посему тема пеезжает из Delphi в Алгоритмы.
-
- Сообщения: 492
- Зарегистрирован: 17 фев 2004, 11:26
- Откуда: Ленинград (который Город на Неве)
- Контактная информация:
Вполне может быть. Там прирост нелинейный.Геннадий писал(а):Здравствуйте!
Написал на Delphi 6 расчет определителя квадратнойй матрицы, на матрицу 7x7 уходит 1 секунда, 8x8 - 24 секунды.
Это нормально?
[/quote]
Для определителя я получаю n^n сочетаний, а из них выделяю n!
Можно ли по-другому, напрмер, получать сразу все нужные перестановки?[/quote]
Можно без перестановок.
1. Рекуррентный алгоритм ( по строчке / столбцу )
2. Численный (Метод Крылова, например)
"Особое внимание начинающих аквариумистов хотим обратить на то, что рыбки никогда не спят на спинке!" (c)
viel spass, DeeJayC
viel spass, DeeJayC
Я написал и через приведение к треугольному виду, и это работает намного быстрее, но в задании необходимо считать и с перестановками.
Рекурентный я до этого тоже пробовал использовать, но там расчётов не меньше, к тому же я его так и не отладил.
А что за метод Крылов, это что такое то?
Рекурентный я до этого тоже пробовал использовать, но там расчётов не меньше, к тому же я его так и не отладил.
А что за метод Крылов, это что такое то?
-
- Сообщения: 492
- Зарегистрирован: 17 фев 2004, 11:26
- Откуда: Ленинград (который Город на Неве)
- Контактная информация:
Метод Крылова - численный, с итерациями. Если очень надо, пороюсьГеннадий писал(а):Я написал и через приведение к треугольному виду, и это работает намного быстрее, но в задании необходимо считать и с перестановками.
Рекурентный я до этого тоже пробовал использовать, но там расчётов не меньше, к тому же я его так и не отладил.
А что за метод Крылов, это что такое то?
в книге и выложу. Но он явно не подойдёт. Описан у
Бахвалова или Мысовских.
"Особое внимание начинающих аквариумистов хотим обратить на то, что рыбки никогда не спят на спинке!" (c)
viel spass, DeeJayC
viel spass, DeeJayC
Ладно, спасибо, поищу ради интереса, может быть.
-
- Сообщения: 55
- Зарегистрирован: 03 май 2004, 11:58
- Откуда: Санкт-Петербург
- Контактная информация:
У меня есть процедура подсчета определителя, только на он на С++, зато считает быстрее. 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;
}
Код в принципе не сложный, так что перевести его на , думаю будет не сложно.
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, а то и больше).
Лучшее решение - алгоритм Гаусса. Простой как сама жизнь.
См. Демидович, Марон "Основы вычислительной математики"
Алгоритмы прямого вычисления - бессмысленны ( мне, как геодезисту приходится работать с определителями порядка 20, 50, а то и больше).
Лучшее решение - алгоритм Гаусса. Простой как сама жизнь.
См. Демидович, Марон "Основы вычислительной математики"
Простой-то понятно. Но не точный. В нем погрешность накапливается от итерации к итерации. Хотя для небольших матриц - самое то, работает быстро, пишется просто.Лучшее решение - алгоритм Гаусса. Простой как сама жизнь.
Это метод-то Гаусса неточный? Он, простите, построен строго в соответсвии с определением:
Определитель матрицы n-го порядка, n>1, равен сумме произведений элементов любой строки (столбца) на их алгебраические дополнения и свойством определителей:
Определитель не изменится, если к элементам любой его строки (столбца) прибавить элементы любой другой строки (столбца), умноженные на одно и то же число.
Так что точнее не бывает
Определитель матрицы n-го порядка, n>1, равен сумме произведений элементов любой строки (столбца) на их алгебраические дополнения и свойством определителей:
Определитель не изменится, если к элементам любой его строки (столбца) прибавить элементы любой другой строки (столбца), умноженные на одно и то же число.
Так что точнее не бывает
Даже самый дурацкий замысел можно воплотить мастерски