2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Старый новый метод вычисления определителей
Сообщение18.11.2012, 09:06 
Модератор
Аватара пользователя


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


Вложения:
Комментарий к файлу: Новый метод вычисления определителей
mp2-3.jpg
mp2-3.jpg [ 517.16 Кб | Просмотров: 0 ]
 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение18.11.2012, 10:18 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение18.11.2012, 10:22 
Заслуженный участник


08/04/08
8560
статья писал(а):
впишем в центр минора его значение, разделенное на уже расположенное в центре минора число
А если уже расположенное в центре число равно нулю?

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 
Модератор
Аватара пользователя


11/01/06
5702
Оказывается, этот метод называется методом конденсации (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 


01/07/08
836
Киев
maxal в сообщении #645872 писал(а):
Интересно, есть ли у него алгоритмическая ценность?

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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 15:41 
Заслуженный участник


11/05/08
32166
hurtsy в сообщении #646940 писал(а):
Может для параллельных вычислений и для разреженных матриц сгодится?

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

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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 16:19 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 16:36 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 16:41 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 16:52 
Заслуженный участник


11/05/08
32166
Руст в сообщении #646993 писал(а):
Даже в смысле целочисленности (меньше делений, соответственно с большей вероятностью сохранятся целочисленные коэффициенты).

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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 18:45 


01/07/08
836
Киев
Руст в сообщении #646993 писал(а):
Даже в смысле целочисленности (меньше делений, соответственно с большей вероятностью сохранятся целочисленные коэффициенты).

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

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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение20.11.2012, 22:17 
Заслуженный участник


11/05/08
32166
hurtsy в сообщении #647073 писал(а):
Если матрица полного ранга, успешность результата гарантирована.

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

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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение21.11.2012, 01:00 


01/07/08
836
Киев
ewert в сообщении #647238 писал(а):
Полнота ранга ни разу не избавляет от возможности нарваться на внутренний нуль, ну хоть на один.

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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение21.11.2012, 13:57 


01/07/08
836
Киев
ewert в сообщении #647238 писал(а):
нарваться на внутренний нуль

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

 Профиль  
                  
 
 Re: Старый новый метод вычисления определителей
Сообщение21.11.2012, 14:16 
Заслуженный участник


11/05/08
32166
hurtsy в сообщении #647493 писал(а):
Если хоть один промежуточный результат ненулевой, то текущая нижняя строка линейно независима от вышестоящих строк.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group