2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Старый новый метод вычисления определителей
Сообщение18.11.2012, 09:06 
Аватара пользователя
В номере 3 второй серии Мат.Проса вычитал такой новый (на 1955 год) метод вычисления определителей.
Интересно, есть ли у него алгоритмическая ценность?


У вас нет доступа для просмотра вложений в этом сообщении.

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение18.11.2012, 10:22 
статья писал(а):
впишем в центр минора его значение, разделенное на уже расположенное в центре минора число
А если уже расположенное в центре число равно нулю?

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 05:03 
Аватара пользователя
Оказывается, этот метод называется методом конденсации (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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 15:25 
maxal в сообщении #645872 писал(а):
Интересно, есть ли у него алгоритмическая ценность?

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 15:41 
hurtsy в сообщении #646940 писал(а):
Может для параллельных вычислений и для разреженных матриц сгодится?

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

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

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

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 16:41 
Руст в сообщении #646993 писал(а):
Даже в смысле целочисленности (меньше делений, соответственно с большей вероятностью сохранятся целочисленные коэффициенты).
Вообще-то метод конденсации сохраняет целочисленность, именно в этом его преимущество перед Гауссом при ручном вычислении - дополнительный контроль ошибок.

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 16:52 
Руст в сообщении #646993 писал(а):
Даже в смысле целочисленности (меньше делений, соответственно с большей вероятностью сохранятся целочисленные коэффициенты).

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 18:45 
Руст в сообщении #646993 писал(а):
Даже в смысле целочисленности (меньше делений, соответственно с большей вероятностью сохранятся целочисленные коэффициенты).

Здесь вероятность ни при чем. Ведь все вычисляемые величины, являются определителями подматриц исходной матрицы. Следовательно определители целые числа. Равенство нулю индикатор линейной зависимости. Следовательно метод любимого автора англоязычных цитат, хорош для вычисления ранга исходной матрицы.
maxal в сообщении #646810 писал(а):
Макмиллан с нулями предлагает бороться двумя способами: либо пеставлять строки/столбцы так, чтобы нули оказывались скраю, либо применять к ним линейные преобразования. Правда, ни в одном из способов успешного результата он не гарантирует.

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 22:17 
hurtsy в сообщении #647073 писал(а):
Если матрица полного ранга, успешность результата гарантирована.

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

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение21.11.2012, 01:00 
ewert в сообщении #647238 писал(а):
Полнота ранга ни разу не избавляет от возможности нарваться на внутренний нуль, ну хоть на один.

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение21.11.2012, 13:57 
ewert в сообщении #647238 писал(а):
нарваться на внутренний нуль

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

 
 
 
 Re: Старый новый метод вычисления определителей
Сообщение21.11.2012, 14:16 
hurtsy в сообщении #647493 писал(а):
Если хоть один промежуточный результат ненулевой, то текущая нижняя строка линейно независима от вышестоящих строк.

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

 
 
 [ Сообщений: 19 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group