Упрощенный способ вычисления для определителя 4го порядка.

[bitcoin]

Добрый вечер! Есть упрощенные способы вычисления определителей 3-го порядка (через звездочку или через дописывание первых двух столбцов, а далее по диагоналям). Но есть ли подобные способы для определителей 4-го порядка? Кстати, а получится ли дописать первые три столбца и дальше перемножать по диагоналям, по аналогии с определителем 3-го порядка?

[arseniiv]

Не получится. Определитель порядка $n$ — это сумма $n!$ слагаемых, вы их никак туда все не вместите для $n\ne3$ (для второго порядка, например, выходит наоборот слишком много).

Вообще всё довольно просто. Если мы знаем, перестановки с какими матрицами чётные, а какие нечётные, для порядка $n-1$, то мы можем нагенерировать матрицы перестановок порядка $n$ и знать, какие уже из этих чётные, а какие нечётные, на практике* это выливается в разложение определителя по строке/столбцу, потому что это проще делать, чем запоминать 24, 120 и т. д. конфигураций элементов определителя визуально.

* Ручного счёта, конечно.

-- Сб авг 25, 2018 21:41:26 --

(И если включить педанта, упомянутые вами способы — не «упрощённые», это просто мнемоники, ведь объём-то вычислений остаётся таким же.)

[bitcoin]

Спасибо! А есть ли мнемоники для определителя 4-го порядка? Просто мнемоники для 3го порядка для меня существенно ускоряют счет!

[Munin]

«Определитель четвертого порядка»

[bitcoin]

Munin в сообщении #1334508 писал(а):

«Определитель четвертого порядка»

Спасибо, нашел там ключевой момент, так значит все-таки можно приписать 3 столбца, только вот в каком именно порядке?

gris в сообщении #1216049 писал(а):

Может быть имеется в виду Правило Параллельных Полосок (метод Саррюса?).
Матрицу третьего порядка можно расширить справа двумя первыми столбцами и вместо треугольников рисовать диагональные полоски слева направо для плюса и справа налево для минуса. Аналогично как-то делают и для матриц четвёртого порядка, только там приставляют три столбца и в разных порядках. Вроде бы вместо этих фигур Лиссажу получается удобнее.
А вообще определитель любого порядка представим в виде суммы произведений ясно каких. А знак определяется по чётности подстановки.

[Munin]

Ну вот, я хотел помочь, а навредил...

[arseniiv]

bitcoin
Да в самом низу же картинки там. (Посмотрел и теперь точно уверен, что мне было бы проще раскладывать по строке, чем запоминать их все.)

-- Вс авг 26, 2018 02:14:03 --

bitcoin в сообщении #1334511 писал(а):

так значит все-таки можно приписать 3 столбца

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

[Евгений Машеров]

Я не совсем понимаю потребность вручную считать определители 4 порядка (ну, разве что воспитание силы воли). Тем не менее задачи, где нужен именно определитель, существуют. Скажем, он появляется в выражении для плотности многомерного нормального распределения. И если нужно его подсчитать - проще всего использовать алгоритм решения системы линейных уравнений по Гауссу, перемножив ведущие элементы. И запрограммировать это просто, и сложность кубическая. Разложение по строке для общего случая, когда матрица больше, чем 4х4, хуже и по трудоёмкости и по точности. Но для данного случая может быть приемлемо по сложности, выписать 4 матрицы 3х3, а с ними уже умеете обращаться. Ещё преимущество данного подхода перед Гауссом (тем более перед "найти собственные значения и перемножить", более трудоёмким, но и более устойчивым численно), что нет делений, только умножения. Но в какой ситуации нынче это может оказаться важным - не представляю (совсем ручные расчёты без калькулятора? расчёты определителя на цифровых сигнальных процессорах, в которых то ли нет деления вообще, то ли умножение за такт, а деление за 16?).
Что до схем расчёта определителя матрицы 4х4, приведенных уважаемым Munin в предшествующей теме

$$+\left|\,\raisebox{\depth/2}{\[\xymatrix@!0@*-{\circ\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[dr]&\circ\ar@{-}[dl]\\\circ\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[dr]&\circ\ar@{-}[dl]\\\circ\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[dr]&\circ\ar@{-}[dl]\\\circ&\circ&\circ&\circ}\]}\,\right| +\left|\,\raisebox{\depth/2}{\[\xymatrix@!0@*-{\circ&\circ\ar@{-}[ddl]\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[ddr]&\circ\\\circ\ar@{-}[ddr]\ar@{-}[drr]&\circ\ar@{-}[drr]&\circ\ar@{-}[dll]&\circ\ar@{-}[ddl]\ar@{-}[dll]\\\circ&\circ\ar@{-}[dr]&\circ\ar@{-}[dl]&\circ\\\circ&\circ&\circ&\circ}\]}\,\right| +\left|\,\raisebox{\depth/2}{\[\xymatrix@!0@*-{\circ&\circ\ar@{-}[ddr]\ar@{-}[drr]&\circ\ar@{-}[ddl]\ar@{-}[dll]&\circ\\\circ\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[ddr]&\circ\ar@{-}[ddl]\ar@{-}[dr]&\circ\ar@{-}[dl]\\\circ\ar@{-}[drr]&\circ&\circ&\circ\ar@{-}[dll]\\\circ&\circ&\circ&\circ}\]}\,\right|$$

$$-\left|\,\raisebox{\depth/2}{\[\xymatrix@!0@*-{\circ&\circ\ar@{-}[dl]\ar@{-}[ddr]&\circ\ar@{-}[ddl]\ar@{-}[dr]&\circ\\\circ\ar@{-}[drr]&\circ\ar@{-}[ddr]\ar@{-}[drr]&\circ\ar@{-}[ddl]\ar@{-}[dll]&\circ\ar@{-}[dll]\\\circ\ar@{-}[dr]&\circ&\circ&\circ\ar@{-}[dl]\\\circ&\circ&\circ&\circ}\]}\,\right| -\left|\,\raisebox{\depth/2}{\[\xymatrix@!0@*-{\circ\ar@{-}[dddr]\ar@{-}[drrr]&\circ\ar@{-}[dddl]\ar@{-}[dr]&\circ\ar@{-}[dl]\ar@{-}[dddr]&\circ\ar@{-}[dddl]\ar@{-}[dlll]\\\circ\ar@{-}[dr]&\circ\ar@{-}[dl]&\circ\ar@{-}[dr]&\circ\ar@{-}[dl]\\\circ\ar@{-}[drrr]&\circ\ar@{-}[dr]&\circ\ar@{-}[dl]&\circ\ar@{-}[dlll]\\\circ&\circ&\circ&\circ}\]}\,\right| -\left|\,\raisebox{\depth/2}{\[\xymatrix@!0@*-{\circ\ar@{-}[ddr]\ar@{-}[drr]&\circ\ar@{-}[ddl]\ar@{-}[drr]&\circ\ar@{-}[ddr]\ar@{-}[dll]&\circ\ar@{-}[ddl]\ar@{-}[dll]\\\circ\ar@{-}[ddr]&\circ\ar@{-}[ddl]&\circ\ar@{-}[ddr]&\circ\ar@{-}[ddl]\\\circ\ar@{-}[drr]&\circ\ar@{-}[drr]&\circ\ar@{-}[dll]&\circ\ar@{-}[dll]\\\circ&\circ&\circ&\circ}\]}\,\right|$$

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

[Евгений Машеров]

Во избежание.
Замечание о "практической бесполезности" относится отнюдь не к теории групп и не к группе перестановок из 4 элементов, которую картинки иллюстрируют. И уж разумеется, не содержат осуждения автора, давшего эти картинки. Речь лишь о том, что для поставленной ТС задачи, рассчитать определитель 4 порядка, они малопригодны. Вероятность ошибиться, вручную ли считая или программируя, слишком высока. Но, повторюсь, "это красиво".
Кроме того, оценим сложность. 24 слагаемых, в каждом 3 умножения, итого 72 умножения и 24 сложения. При разложении по Гауссу - 4 деления в первой строке, 6 умножений, 6 сложений, для второй 3 деления, 3 умножения, 3 сложения, для третьей 2 деления, 1 умножение, 1 сложение. Плюс 3 умножения для произведения ведущих элементов. Итого 9 делений, 13 умножений, 10 сложений. Если, как в современных процессорах, деление, умножение и сложение одинаковы по времени (или, при ручных расчётах, используется калькулятор, так что затраты труда на любое вычисление это затраты на ввод), расчёт "определителя по определению" в 2.25 раз более трудоёмок.

[teleglaz]

bitcoin в сообщении #1334511 писал(а):

так значит все-таки можно приписать 3 столбца, только вот в каком именно порядке?

Конечно нет. Как вам уже сказали, хотя бы прикиньте количество слагаемых, которое получится при таком аналоге "метода Саррюса для четвёртого порядка" и разложении "в лоб".

Вообще, как уже отмечалось, такое ответственное занятие, как вычисление определителя четвёртого порядка “вручную” поручается, наверное, только первокурсникам в качестве дисциплинарного взыскания (ну и укрощения плоти разве что). А в этом случае, как привило, речь идёт о матрицах целочисленных. В этом случае на практике ручного вычисления удобно пользоваться так называемым методом понижения порядка. А именно, с помощью элементарных преобразований нужно в одном столбце (или строке) сделать равными нулю все элементы, за исключением одного, и затем разложить определитель по этому столбцу (строке) и получить определитель меньшего порядка, чем исходный (в случае исходного четвёртого – третьего). Это позволяет не считать четыре определителя третьего порядка при разложении “в лоб”. Разумеется, здесь нужно не забыть, что при некоторых элементарных преобразованиях определитель может меняться. Так же целесообразно выбирать столбец (строку), где уже есть нули, дабы сэкономить количество операций (в ваших задачах, скорее всего, такой столбец (строка) есть).

[arseniiv]

Евгений Машеров в сообщении #1334800 писал(а):

Если, как в современных процессорах, деление, умножение и сложение одинаковы по времени

Нэ совсэм. На форуме сслылались как-то на инфографику времён выполнения операций на каком-то современном интеловском, плавающее деление всё ещё ой-ой, да и умножение может выполняться дольше сложения (как там карта ляжет).

[Евгений Машеров]

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

[Dmitriy40]

(Скорость деления)

Евгений Машеров в сообщении #1334800 писал(а):

Если, как в современных процессорах, деление, умножение и сложение одинаковы по времени

Деление примерно на полтора порядка медленнее. Кэш вообще ни при чём для таких маленьких матриц, а конвейер деления недостаточно мелко побит чтобы запускать деление каждый такт. Потому деления можно запускать каждые 5-10-20-30-90 тактов (смотря какие, да ещё для целых и от величины чисел зависит), а вот умножения можно запускать каждый такт (или даже полтакта для FMADD операций).
Примеры для плавающих форматов, для SkylakeX: FMUL 1 такт, FMADD 0.5 такта, FDIV 4-5 тактов; VMUL 0.5-1 такт для любых типов данных (хоть 1, хоть 4, хоть 8, хоть 16 чисел в регистрах), VDIV single x1,x4,x8 3-5 тактов, VDIV double x1,x2 4 такта, VDIV single x16 10 тактов, VDIV double x4 8 тактов, VDIV double x8 16 тактов. И это достаточно новый процессор, для распространённого Haswell времена деления: FDIV 8-18 тактов, VDIV single x1 7 тактов, VDIV double x1 8-14 тактов, VDIV single x8 14 тактов, VDIV double x4 16-28 тактов. Под x1-x16 обозначено количество чисел в регистре, FDIV это скалярная команда x87, VDIV это векторная AVX, FMADD выполняет сразу операцию c=ab+c над векторными регистрами и экономит 0.5-1 такта на сложение (т.е. фактически вдвое быстрее).
Так что деление таки на один-полтора-два порядка медленнее.
PS. Покажите процессор с однотактным делением, а? Разве что в GPU такое может быть, ну так там и такты не чета нормальным CPU-шным ...

[Евгений Машеров]

Ну, поскольку там деление на одно и то же, нормальный оптимизирующий компилятор подставит умножение на обратное...

[Dmitriy40]

И всё же в программе выигрыша от делений не будет: они все три зависимы друг от друга и выполняться могут исключительно последовательно, а каждое из них результат выдаёт лишь через 13-14 тактов (для SkylakeX), так что даже если умножения на обратный элемент запустятся параллельно, то всё в сумме займёт не менее 48 тактов (40 тактов деления и дважды по 4 такта умножения со сложениями для диагонали). А вот 72 (точнее хватит и 40) умножений со всеми сложениями теоретически можно выполнить полностью параллельно за 8 тактов (в цепочках лишь два умножения по 4 такта зависимы, а зависимости по сложению/вычитанию маскируются). В 6 раз быстрее Гаусса однако. Накладные расходы на перетасовку чисел в регистрах не учитываю, они по видимому всё сильно испортят.