Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

Ответ
 
Опции темы
Старый 24.05.2011, 14:10   #1
Rekky
Форумчанин
 
Аватар для Rekky
 
Регистрация: 14.01.2009
Адрес: Владимир
Сообщений: 312
Репутация: 179

icq: 482362533
По умолчанию Определитель матрицы

эээ...прошу не смеяться, но задам, наверно, школьный вопрос
Изучаю тут незнакомый мне доселе метод треугольников..
Интересуют матрицы от 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
Репутация: 868
По умолчанию

> откуда все таки 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
Репутация: 179

icq: 482362533
По умолчанию

Цитата:
считается через 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
Репутация: 868
По умолчанию

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

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

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

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

icq: 482362533
По умолчанию

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

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

icq: 482362533
По умолчанию

Нашла таки нормально описание по данной формуле, смысл здесь в перестановках..
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
Репутация: 868
По умолчанию

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

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

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

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

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

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

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

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

icq: 482362533
По умолчанию

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

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

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Определитель матрицы на PHP DenisShash Помощь студентам 1 11.01.2011 09:30
Определитель Матрицы(реккурсия С) XSerGx Общие вопросы C/C++ 1 08.01.2011 20:29
Определитель матрицы 2 на 2 С++ Mashul'ka Помощь студентам 1 03.11.2010 01:08
Определитель матрицы Snake_ua Помощь студентам 7 10.02.2010 11:44
Определитель квадратной матрицы Tomoyo Помощь студентам 22 04.11.2008 23:37


05:16.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru