|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
24.05.2011, 14:10 | #1 |
Форумчанин
Регистрация: 14.01.2009
Сообщений: 312
|
Определитель матрицы
эээ...прошу не смеяться, но задам, наверно, школьный вопрос
Изучаю тут незнакомый мне доселе метод треугольников.. Интересуют матрицы от 4 порядка и выше.. В книге написано, что для 4 порядка вычисление определителя сводится к 24 слагаемым у меня получилось всего 8... но ответ по определителю верный..может я что не так поняла.. Вот вырезки из книги.. Для трех мерной матрицы вот такой метод есть: matr.jpg дает 6 слагаемых, как и описано ниже А вот общее описание по определителям: text.jpg У меня для 4 порядка получилось 8 слагаемых, половина из которых с противоположным знаком..и в каждом слагаемом 4 множителя.. Объясните мне кто нибудь,пожалуйста, откуда все таки 24 слагаемых..? Я брала матрица содержащую по порядку элементы от 1 до 16: 1 2 3 4 5 6 7 8 ... Может быть я сделала не такую разбивку для 4 порядка..делала по аналогии с первым рисунком..только получилось в итоге 4 строки и 3 столбца после черты..и 8 линий..
Никому не поставить нас на колени! Мы лежали и будем лежать!
Последний раз редактировалось Rekky; 24.05.2011 в 14:16. |
24.05.2011, 14:56 | #2 |
Старожил
Регистрация: 03.01.2011
Сообщений: 2,508
|
> откуда все таки 24 слагаемых..?
а откуда 8? детерминант матрицы 4х4 считается через 4 дополнительных детерминанта матриц 3х3. Для вычисления детерминанта матрицы 3х3 нужно (как вы сами написали) 6 слагаемых. Умножаем 4 на 6 получаем 24. Вот, кстати кусок моего кода на С, рекурсивно считающий определитель матрицы любого порядка. Могу переписать его на паскале. Да, сложность его O(n!), ну и ладно )
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
|
24.05.2011, 15:19 | #3 | |
Форумчанин
Регистрация: 14.01.2009
Сообщений: 312
|
Цитата:
Ваш код считает значит по методу разложения на более мелкие матрицы? Это наверно более грузит процессор нежели метод треугольников, а лучше линий (описанный мной). Если по этому методу ничего не найду или мне докажут, что по производительности нет разницы или ваш алгоритм лучше..то пожалуй возьму ваш код в использование Вот текстовое его описание: 2.jpg вот какая сложность у метода трегуольников? P.S. мне бы не было разницы, но у нас предмет высокой производительности выч. системы.. и надо сделать программку вычисляющую обратную матрицу..на кластере. Естественно, что нужно использоват алгоритмы с наименьшей сложностью..и возможностью распараллеливания. И определитель будет считаться для матрицы размера более 10000
Никому не поставить нас на колени! Мы лежали и будем лежать!
Последний раз редактировалось Rekky; 24.05.2011 в 15:28. |
|
24.05.2011, 15:47 | #4 |
Старожил
Регистрация: 03.01.2011
Сообщений: 2,508
|
Если речь про метод Гаусса, то сложность у него O(n3), что, конечно, несравненно лучше, чем О(n!), особенно, для больших n.
По-поводу распараллеливания ничего не скажу, надо смотреть на реализацию и думать. > для матрицы размера более 10000 упс, тогда мой код точно не подойдёт )
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
|
24.05.2011, 17:20 | #5 |
Форумчанин
Регистрация: 14.01.2009
Сообщений: 312
|
Это кажется метод Саррюса известен как правило треугольника..
Тока как его решать при более чем 3 го порядка хз..( И не известно какая у него сложность
Никому не поставить нас на колени! Мы лежали и будем лежать!
|
24.05.2011, 17:46 | #6 |
Очень суровый
Участник клуба
Регистрация: 17.12.2009
Сообщений: 1,988
|
Метод треугольников не применим к матрице выше третьего порядка... Эта формула чисто случайно получилась, но запоминается она в графическом виде.
Попробуйте сами посчитать определитель матрицы 3х3 по обычному, в итоге получите как раз ту самую формулу треугольников. А теперь попробуйте точно также вручную посчитать определитель для матрицы 4х4. Будет достаточно сложная формула, запомнить которую ни графически, ни символьно ну никак не получится. 4! слагаемых.
Ненавижу быть как все, но люблю, чтобы все были как я.
|
24.05.2011, 17:56 | #7 |
Форумчанин
Регистрация: 14.01.2009
Сообщений: 312
|
Нашла таки нормально описание по данной формуле, смысл здесь в перестановках..
form.bmp Действительно графический подход мой не верен и должно быть 24 слагаемых..тк столько перестановок может быть в матрице 4*4.. Кто нибудь знает достаточно ли хорош данный алгоритм перестановок по производительности, какая у него сложность? Посоветуйте, пожалуйста, оптимальный алгоритм. Просто я думаю, что обычный алгоритм громоздок для матриц 10000 размерности Решила использовать метод Гаусса..он вроде и прост по реализации и сложность не самая худшая.. эээ...есть идеи как его распараллелить? Например, отдавать процессорам по две строки?
Никому не поставить нас на колени! Мы лежали и будем лежать!
Последний раз редактировалось Rekky; 24.05.2011 в 18:27. |
24.05.2011, 18:33 | #8 |
Старожил
Регистрация: 03.01.2011
Сообщений: 2,508
|
> алгоритм перестановок
перестановки == факториал, а факториал от 10000 не есть подъёмное число для любых суперкластеров. > метод Гаусса В методе Гаусса вроде как есть одна засада — разрядность, требуемая для хранения промежуточных результатов, растёт экпоненциально. Вот тут в кратце описаны различные подходы и алгоритмы. > есть идеи как его распараллелить? отдавать процессорам по две строки? вобще, судя по внешним признакам, алгоритм должен хорошо распараллеливаться, т.к. есть много вычислений, не зависящих друг от друга (до какого-то момента). и вам же вроде в соседней теме литературу подбросили, лучше чем в книгах вряд ли кто-то тут напишет
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
Последний раз редактировалось veniside; 24.05.2011 в 18:38. |
24.05.2011, 18:46 | #9 | |||
Форумчанин
Регистрация: 14.01.2009
Сообщений: 312
|
Цитата:
Поэтому здесь их пополняю..и в нете роюсь параллельно..причем есть интересная инфа не только в книжках, но и в статьях..очень не плохая.. В каждом алгоритме есть свои недостатки..и Гаусс не самый плохой..большинство алгоритмов имеют еще больше ограничений, чем Гауссовский Цитата:
Остальные зато по производительности или по ограничениям отходят на второй план.. Цитата:
Если вы можете назвать метод лучше, я только за!) К сожалению..сил нет уже читать ничего и разбираться особенно на английском Самое ужасное, что это только часть проблемы..нахождение обратной матрицы..вот это уже караул..не знаю как все успеть..Наверно осенью буду бегать
Никому не поставить нас на колени! Мы лежали и будем лежать!
|
|||
24.05.2011, 20:02 | #10 |
Старожил
Регистрация: 03.01.2011
Сообщений: 2,508
|
> Это вы про n^3?
нет, это сложность, тут всё нормально. Я про разрядность. Как я понимаю, на каком-то этапе прийдётся перейти на длинную арифметику, т.к. стандартных 64 (или 128) бит для хранения промежуточных результатов просто не хватит (т.е. потери точности будут такие, что результат будет сильно далёк от истины).
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Определитель матрицы на PHP | DenisShash | Помощь студентам | 1 | 11.01.2011 08:30 |
Определитель Матрицы(реккурсия С) | XSerGx | Общие вопросы C/C++ | 1 | 08.01.2011 19:29 |
Определитель матрицы 2 на 2 С++ | Mashul'ka | Помощь студентам | 1 | 03.11.2010 00:08 |
Определитель матрицы | Snake_ua | Помощь студентам | 7 | 10.02.2010 10:44 |
Определитель квадратной матрицы | Tomoyo | Помощь студентам | 22 | 04.11.2008 22:37 |