Старый новый метод вычисления определителей

[maxal]

В номере 3 второй серии Мат.Проса вычитал такой новый (на 1955 год) метод вычисления определителей.
Интересно, есть ли у него алгоритмическая ценность?

[Руст]

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

[Sonic86]

статья писал(а):

впишем в центр минора его значение, разделенное на уже расположенное в центре минора число

А если уже расположенное в центре число равно нулю?

upd: для понижения размера матрицы на 1 в методе Гаусса надо (если не рассматривать перестановки строк) $n-1$ деление, $n(n-1)$ умножений и $n(n-1)$ сложений. В данном методе надо $(n-1)^2$ делений, $2(n-1)^2$ умножений, $(n-1)^2$ сложений. Вроде.

[maxal]

Оказывается, этот метод называется методом конденсации (condensation method) или методом контрактантов (method of contractants) и впервые описан Льюисом Кэроллом (Charles Dodgson) аж в 1866 году:
http://rspl.royalsocietypublishing.org/ ... 0.full.pdf
Кое-какой исторический очерк есть на MathWorld:
http://mathworld.wolfram.com/Condensation.html

Макмиллан с нулями предлагает бороться двумя способами: либо пеставлять строки/столбцы так, чтобы нули оказывались скраю, либо применять к ним линейные преобразования. Правда, ни в одном из способов успешного результата он не гарантирует.

Лоткин в 1959 году провел численные эксперементы и остался методом доволен:
http://www.jstor.org/discover/10.2307/2310629

[hurtsy]

maxal в сообщении #645872 писал(а):

Интересно, есть ли у него алгоритмическая ценность?

Может для параллельных вычислений и для разреженных матриц сгодится? С уважением,

[ewert]

hurtsy в сообщении #646940 писал(а):

Может для параллельных вычислений и для разреженных матриц сгодится?

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

Соблазнить могла бы и возможность обойтись лишь целочисленной арифметикой, но и это по нынешнем временам выглядит странно: проще провести все вычисления с плавающей точкой, а потом результат просто округлить. Во всяком случае, для не слишком больших матриц с не слишком большими элементами.

[venco]

Гаусс, вроде, тоже неплохо параллелится, и делений использует на порядок меньше, а это существенно более медленная операция, чем умножение.

[Руст]

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

[venco]

Руст в сообщении #646993 писал(а):

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

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

[ewert]

Руст в сообщении #646993 писал(а):

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

В целочисленном методе Гаусса знаменатели склонны катастрофически расти. Возможно, в этом методе рост меньше (хотя и не уверен).

[hurtsy]

Руст в сообщении #646993 писал(а):

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

Здесь вероятность ни при чем. Ведь все вычисляемые величины, являются определителями подматриц исходной матрицы. Следовательно определители целые числа. Равенство нулю индикатор линейной зависимости. Следовательно метод любимого автора англоязычных цитат, хорош для вычисления ранга исходной матрицы.

maxal в сообщении #646810 писал(а):

Макмиллан с нулями предлагает бороться двумя способами: либо пеставлять строки/столбцы так, чтобы нули оказывались скраю, либо применять к ним линейные преобразования. Правда, ни в одном из способов успешного результата он не гарантирует.

Если матрица полного ранга, успешность результата гарантирована. С уважением,

[ewert]

hurtsy в сообщении #647073 писал(а):

Если матрица полного ранга, успешность результата гарантирована.

Нет. Полнота ранга ни разу не избавляет от возможности нарваться на внутренний нуль, ну хоть на один.

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

[hurtsy]

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

Полнота ранга ни разу не избавляет от возможности нарваться на внутренний нуль, ну хоть на один.

Вы знаете, глаза боятся а вы слушайтесь Макмилана и переставляйте, как он советует, и в случае полного ранга все гарантировано. Если же окажется безвыходная ситуация, то значит мы уже нашли ранг данной матрицы. С уважением,

[hurtsy]

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

нарваться на внутренний нуль

Для чего в алгоритме Доджсона производится деление, имхо, если не поделишь окажется вычисленный определитель умноженным на это число. В случае внутреннего нуля вычисленный определитель превращается в 0. Для принятия решения о переносе строчки/столбца нужно вычислить всю промежуточную строчку. Если хоть один промежуточный результат ненулевой, то текущая нижняя строка линейно независима от вышестоящих строк. Зря Макмиллан "не дает гарантии". С уважением,

[ewert]

hurtsy в сообщении #647493 писал(а):

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

Ну и что?... Проблема-то возникает, если хоть один элемент оказывается нулевым. Допустим, нули выстроились по диагонали; и что куда Вы собираетесь переставлять?...