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

[fronnya]

Можно ли на паскале написать программу для вычисления определителя матрицы по такому определению

$$\det A=\sum\limits_{j=1}^n (-1)^{i+j} a_{ij} \overline{M}_j^i$$

?
Просто $\overline{M}_j^i$- это ведь тоже определитель, вообще говоря, любого порядка..

[Pphantom]

fronnya в сообщении #955803 писал(а):

Можно ли на паскале написать программу для вычисления определителя матрицы по такому определению

Можно. Только это предельно неэффективный способ.

fronnya в сообщении #955803 писал(а):

Просто $\overline{M}_j^i$- это ведь тоже определитель, вообще говоря, любого порядка..

Да. Есть такая полезная вещь - рекурсия.

[fronnya]

Pphantom в сообщении #955806 писал(а):

fronnya в сообщении #955803 писал(а):

Можно ли на паскале написать программу для вычисления определителя матрицы по такому определению

Можно. Только это предельно неэффективный способ.

А по какому определению лучше всего написать программу?

[Pphantom]

fronnya в сообщении #955809 писал(а):

А по какому определению лучше всего написать программу?

С помощью какого-нибудь подвида метода Гаусса. Приводите матрицу элементарными преобразованиями (за вычетом умножения строки на константу) к треугольному виду (например, верхнему). Тогда, как несложно получить из разложения по минорам, определитель будет равен произведению элементов, стоящих на главной диагонали.

[fronnya]

Pphantom в сообщении #955830 писал(а):

fronnya в сообщении #955809 писал(а):

А по какому определению лучше всего написать программу?

С помощью какого-нибудь подвида метода Гаусса. Приводите матрицу элементарными преобразованиями (за вычетом умножения строки на константу) к треугольному виду (например, верхнему). Тогда, как несложно получить из разложения по минорам, определитель будет равен произведению элементов, стоящих на главной диагонали.

Спасибо, буду пробовать

[Tookser]

Стоит ещё понять рекурсию (чтобы понимать рекурсию решение первым способом).

[ewert]

Pphantom в сообщении #955830 писал(а):

(за вычетом умножения строки на константу)

это как?

Pphantom в сообщении #955806 писал(а):

Только это предельно неэффективный способ.

Смотря что нужно. Если время не критично, размер не слишком велик, а вычисления целочисленные, то это может оказаться и выгоднее.

[iifat]

ewert в сообщении #966010 писал(а):

это как?

Так понимаю, имеется в виду, что в методе Гаусса решения СЛУ мы спокойненько себе умножали всю строку на любое (кроме нуля) число. При вычислении определителя придётся эти умножения запоминать (в смысле, запоминать их произведение).

ewert в сообщении #966010 писал(а):

может оказаться и выгоднее

Организовывать эти самые миноры? Брр... Уж лучше, имхо, перестановки, по базовой формуле.

[Pphantom]

iifat в сообщении #966035 писал(а):

Так понимаю, имеется в виду, что в методе Гаусса решения СЛУ мы спокойненько себе умножали всю строку на любое (кроме нуля) число. При вычислении определителя придётся эти умножения запоминать (в смысле, запоминать их произведение).

Совершенно верно.

-- 21.01.2015, 12:23 --

ewert в сообщении #966010 писал(а):

Смотря что нужно. Если время не критично, размер не слишком велик, а вычисления целочисленные, то это может оказаться и выгоднее.

Гаусс пишется не сложнее, разница во времени появляется для матрицы $5\times 5$ и становится неприемлимой уже для $10 \times 10$, целочисленность ситуацию практически не спасает.

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

-- 21.01.2015, 12:28 --

iifat в сообщении #966035 писал(а):

Организовывать эти самые миноры? Брр... Уж лучше, имхо, перестановки, по базовой формуле.

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

[ewert]

iifat в сообщении #966035 писал(а):

При вычислении определителя придётся эти умножения запоминать

Между прочим, не придётся. После умножения той строки её можно запросто и немедленно поделить.

Pphantom в сообщении #966071 писал(а):

целочисленность ситуацию практически не спасает.

Я и не утверждал, что спасает (кстати, кто кого?...). Речь шла лишь о том, что при непосредственном вычислении определителя в целочисленном случае опасность переполнений, возможно, и меньше. А может, и нет -- не анализировал; это была лишь гипотеза.

-- Ср янв 21, 2015 23:21:47 --

Pphantom в сообщении #966071 писал(а):

генератор перестановок, пожалуй, даже сложнее будет

Сложнее. Здесь ведь достаточно в качестве параметров обращения задать два индикаторных массива активных строк/столбцов (или типа того).

[Pphantom]

ewert в сообщении #966456 писал(а):

Между прочим, не придётся. После умножения той строки её можно запросто и немедленно поделить.

Можно, но без этого проще обойтись.

ewert в сообщении #966456 писал(а):

Я и не утверждал, что спасает (кстати, кто кого?...). Речь шла лишь о том, что при непосредственном вычислении определителя в целочисленном случае опасность переполнений, возможно, и меньше. А может, и нет -- не анализировал; это была лишь гипотеза.

Это скорее уж немного уменьшает время счета. Но не принципиально.

[ewert]

Pphantom в сообщении #966551 писал(а):

Можно, но без этого проще обойтись.

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