Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 24.05.2011, 14:10   #1
Rekky
Форумчанин
 
Аватар для Rekky
 
Регистрация: 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.
Rekky вне форума Ответить с цитированием
Старый 24.05.2011, 14:56   #2
veniside
Старожил
 
Регистрация: 03.01.2011
Сообщений: 2,508
По умолчанию

> откуда все таки 24 слагаемых..?

а откуда 8? детерминант матрицы 4х4 считается через 4 дополнительных детерминанта матриц 3х3. Для вычисления детерминанта матрицы 3х3 нужно (как вы сами написали) 6 слагаемых. Умножаем 4 на 6 получаем 24.

Вот, кстати кусок моего кода на С, рекурсивно считающий определитель матрицы любого порядка. Могу переписать его на паскале. Да, сложность его O(n!), ну и ладно )
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
veniside вне форума Ответить с цитированием
Старый 24.05.2011, 15:19   #3
Rekky
Форумчанин
 
Аватар для Rekky
 
Регистрация: 14.01.2009
Сообщений: 312
По умолчанию

Цитата:
считается через 4 дополнительных детерминанта матриц 3х3.
Это обычный метод расчета, а я про метод треугольников..там не считается по матрицам..там считается по треугольникам..на моей картинке он видоизменен..и считается по линиям, но к сожалению там пример для матрицы 3 порядка..
Ваш код считает значит по методу разложения на более мелкие матрицы? Это наверно более грузит процессор нежели метод треугольников, а лучше линий (описанный мной). Если по этому методу ничего не найду или мне докажут, что по производительности нет разницы или ваш алгоритм лучше..то пожалуй возьму ваш код в использование
Вот текстовое его описание:
2.jpg

вот какая сложность у метода трегуольников?
P.S. мне бы не было разницы, но у нас предмет высокой производительности выч. системы.. и надо сделать программку вычисляющую обратную матрицу..на кластере. Естественно, что нужно использоват алгоритмы с наименьшей сложностью..и возможностью распараллеливания. И определитель будет считаться для матрицы размера более 10000
Никому не поставить нас на колени! Мы лежали и будем лежать!

Последний раз редактировалось Rekky; 24.05.2011 в 15:28.
Rekky вне форума Ответить с цитированием
Старый 24.05.2011, 15:47   #4
veniside
Старожил
 
Регистрация: 03.01.2011
Сообщений: 2,508
По умолчанию

Если речь про метод Гаусса, то сложность у него O(n3), что, конечно, несравненно лучше, чем О(n!), особенно, для больших n.

По-поводу распараллеливания ничего не скажу, надо смотреть на реализацию и думать.

> для матрицы размера более 10000

упс, тогда мой код точно не подойдёт )
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
veniside вне форума Ответить с цитированием
Старый 24.05.2011, 17:20   #5
Rekky
Форумчанин
 
Аватар для Rekky
 
Регистрация: 14.01.2009
Сообщений: 312
По умолчанию

Это кажется метод Саррюса известен как правило треугольника..
Тока как его решать при более чем 3 го порядка хз..(
И не известно какая у него сложность
Никому не поставить нас на колени! Мы лежали и будем лежать!
Rekky вне форума Ответить с цитированием
Старый 24.05.2011, 17:46   #6
MyLastHit
Очень суровый
Участник клуба
 
Аватар для MyLastHit
 
Регистрация: 17.12.2009
Сообщений: 1,988
По умолчанию

Метод треугольников не применим к матрице выше третьего порядка... Эта формула чисто случайно получилась, но запоминается она в графическом виде.
Попробуйте сами посчитать определитель матрицы 3х3 по обычному, в итоге получите как раз ту самую формулу треугольников.
А теперь попробуйте точно также вручную посчитать определитель для матрицы 4х4. Будет достаточно сложная формула, запомнить которую ни графически, ни символьно ну никак не получится. 4! слагаемых.
Ненавижу быть как все, но люблю, чтобы все были как я.
MyLastHit вне форума Ответить с цитированием
Старый 24.05.2011, 17:56   #7
Rekky
Форумчанин
 
Аватар для Rekky
 
Регистрация: 14.01.2009
Сообщений: 312
По умолчанию

Нашла таки нормально описание по данной формуле, смысл здесь в перестановках..
form.bmp
Действительно графический подход мой не верен и должно быть 24 слагаемых..тк столько перестановок может быть в матрице 4*4..
Кто нибудь знает достаточно ли хорош данный алгоритм перестановок по производительности, какая у него сложность?
Посоветуйте, пожалуйста, оптимальный алгоритм.
Просто я думаю, что обычный алгоритм громоздок для матриц 10000 размерности

Решила использовать метод Гаусса..он вроде и прост по реализации и сложность не самая худшая..
эээ...есть идеи как его распараллелить?
Например, отдавать процессорам по две строки?
Никому не поставить нас на колени! Мы лежали и будем лежать!

Последний раз редактировалось Rekky; 24.05.2011 в 18:27.
Rekky вне форума Ответить с цитированием
Старый 24.05.2011, 18:33   #8
veniside
Старожил
 
Регистрация: 03.01.2011
Сообщений: 2,508
По умолчанию

> алгоритм перестановок

перестановки == факториал, а факториал от 10000 не есть подъёмное число для любых суперкластеров.

> метод Гаусса

В методе Гаусса вроде как есть одна засада — разрядность, требуемая для хранения промежуточных результатов, растёт экпоненциально.
Вот тут в кратце описаны различные подходы и алгоритмы.

> есть идеи как его распараллелить? отдавать процессорам по две строки?

вобще, судя по внешним признакам, алгоритм должен хорошо распараллеливаться, т.к. есть много вычислений, не зависящих друг от друга (до какого-то момента).

и вам же вроде в соседней теме литературу подбросили, лучше чем в книгах вряд ли кто-то тут напишет
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."

Последний раз редактировалось veniside; 24.05.2011 в 18:38.
veniside вне форума Ответить с цитированием
Старый 24.05.2011, 18:46   #9
Rekky
Форумчанин
 
Аватар для Rekky
 
Регистрация: 14.01.2009
Сообщений: 312
По умолчанию

Цитата:
вам же вроде в соседней теме литературу подбросили, лучше чем в книгах вряд ли кто-то тут напишет
Смотрела\читала, не достаточно сведений..(кстати про треугольники оттуда и вычитала)
Поэтому здесь их пополняю..и в нете роюсь параллельно..причем есть интересная инфа не только в книжках, но и в статьях..очень не плохая..
В каждом алгоритме есть свои недостатки..и Гаусс не самый плохой..большинство алгоритмов имеют еще больше ограничений, чем Гауссовский
Цитата:
засада — разрядность, требуемая для хранения промежуточных результатов
Да есть такое дело к сожалению..но пока выбор пал на него из всех рассмотренных..
Остальные зато по производительности или по ограничениям отходят на второй план..
Цитата:
растёт экпоненциально
Это вы про n^3? так это же не самый страшный..другие похлеще..кажись
Если вы можете назвать метод лучше, я только за!)
К сожалению..сил нет уже читать ничего и разбираться особенно на английском
Самое ужасное, что это только часть проблемы..нахождение обратной матрицы..вот это уже караул..не знаю как все успеть..Наверно осенью буду бегать
Никому не поставить нас на колени! Мы лежали и будем лежать!
Rekky вне форума Ответить с цитированием
Старый 24.05.2011, 20:02   #10
veniside
Старожил
 
Регистрация: 03.01.2011
Сообщений: 2,508
По умолчанию

> Это вы про n^3?

нет, это сложность, тут всё нормально.
Я про разрядность. Как я понимаю, на каком-то этапе прийдётся перейти на длинную арифметику, т.к. стандартных 64 (или 128) бит для хранения промежуточных результатов просто не хватит (т.е. потери точности будут такие, что результат будет сильно далёк от истины).
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
veniside вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Определитель матрицы на 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