Определитель матрицы NxN

Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain

6y6JIuk
Сообщения: 1
Зарегистрирован: 25 дек 2007, 20:09

Определитель матрицы NxN

Сообщение 6y6JIuk » 25 дек 2007, 20:18

Подскажите плиз какой из способов нахождения определителя матрицы наиболее прост для реализации на С#, либо киньте код. Заранее оч благодарен.

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: Определитель матрицы NxN

Сообщение Romeo » 25 дек 2007, 20:54

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

Известный мне способ - это разложение матрицы, скажем, по первой строке и вычисление n определителей (n-1) степени. Такой подход без проблем переводится на алгоритмический язык и реализовывается в любом языке, поддерживающем рекурсивные функции, не важно Pascal, это, С/С++/C# или ADA :)
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

jeep
Сообщения: 7
Зарегистрирован: 25 дек 2007, 14:36

Re: Определитель матрицы NxN

Сообщение jeep » 28 дек 2007, 01:17

6y6JIuk писал(а):Подскажите плиз какой из способов нахождения определителя матрицы наиболее прост для реализации на С#, либо киньте код. Заранее оч благодарен.
Ну думаю тут нужно отталкиваться от определения определителя матрицы.
|A|=sum[sigma(i1,i2,...,in)*a(i1)*a(i2)*...*a(in)]
т.е. это по-сути сумма произведений, состоящих из элементов матрицы, которые берутся из каждой строки и каждого столбца без повторений. Знак произведения определяется функцией сигма, которая зависит от четности перестановок. Если перестановка четная, то берется плюс, если же нет - минус.

Аватара пользователя
Vladimir89
Сообщения: 75
Зарегистрирован: 21 май 2007, 01:25

Re: Определитель матрицы NxN

Сообщение Vladimir89 » 28 дек 2007, 02:37

Я смарю Ромеро конкретно повезло с образованием... или он ботником был.
Несмотря на то что я это все изучал я уже нифига не помню :)
Си ++
Здоровье --

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: Определитель матрицы NxN

Сообщение Romeo » 28 дек 2007, 15:37

Не, не ботником :) Просто учёба легко даётся. Кстати, это уже оффтоп. Этим не следует злоупотреблять.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: Определитель матрицы NxN

Сообщение somewhere » 28 дек 2007, 15:41

&quot писал(а):Я смарю Ромеро конкретно повезло с образованием... или он ботником был.
Несмотря на то что я это все изучал я уже нифига не помню
Не нужно помнить, нужно понимать. В универе в то время как многие учили, я гулял сдевками и бухал - и по вышке и матану никогда проблем не было - это вовсе не значит что я ботаник или еще кто-то. А по теме, нахождение определителя путем перестановок для больших матриц неприемлемо. Проще свести ее к треугольному виду и простейшим способом вычислить корни.
It's a long way to the top if you wanna rock'n'roll

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: Определитель матрицы NxN

Сообщение Romeo » 28 дек 2007, 15:55

Нет, перестановки предложил jeep. Строго по определению определителя (т.е. использую перестановки) однозначно не эффективно. Я предложил разложение по строке. Можно, конечно, и к треугольному виду приводить, но там кучу проверок нужно делать дополнительных. Хотя, опять-таки, не смертельно. Приведение к треугольному, кстати, даже быстрее работать будет.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: Определитель матрицы NxN

Сообщение somewhere » 28 дек 2007, 16:01

&quot писал(а): Приведение к треугольному, кстати, даже быстрее работать будет.
Это однозначно, сам замерял - пару лет назад нужно было считать определители матриц 256х256(!), а через перестановки :) это уже не шутка. Можно даже у себя код поискать, но он ассемблере, по теме не подойдет. Число проверок там очень мало, и строчных проходов тоже. Зато потом в итоге, получим определитель матрицы как произведение её диагональных элементов. Ну мне там надо было еще и сам вектор найти, но это уже другая история.
It's a long way to the top if you wanna rock'n'roll

jeep
Сообщения: 7
Зарегистрирован: 25 дек 2007, 14:36

Re: Определитель матрицы NxN

Сообщение jeep » 28 дек 2007, 19:19

Romeo писал(а):Нет, перестановки предложил jeep. Строго по определению определителя (т.е. использую перестановки) однозначно не эффективно. Я предложил разложение по строке. Можно, конечно, и к треугольному виду приводить, но там кучу проверок нужно делать дополнительных. Хотя, опять-таки, не смертельно. Приведение к треугольному, кстати, даже быстрее работать будет.
Если матрицы не большие можно и перестановки. В задаче не указан размер.
Если матрица большая, то можно и схему единственного деления использовать.
При такой схеме число умножений и делений для определителя матрицы порядка n равно (n-1)(n^2+n+3)/3.

jeep
Сообщения: 7
Зарегистрирован: 25 дек 2007, 14:36

Re: Определитель матрицы NxN

Сообщение jeep » 28 дек 2007, 19:22

somewhere писал(а):Это однозначно, сам замерял - пару лет назад нужно было считать определители матриц 256х256(!), а через перестановки :) это уже не шутка. Можно даже у себя код поискать, но он ассемблере, по теме не подойдет. Число проверок там очень мало, и строчных проходов тоже. Зато потом в итоге, получим определитель матрицы как произведение её диагональных элементов. Ну мне там надо было еще и сам вектор найти, но это уже другая история.
А вы случаем полную проблему не пробовали решать?

Ответить