N-T.ru / Текущие публикации / Наука сегодня

Уравнение Пелля

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

Валерий МЕШКОВ

 

Полная версия статьи: DOC (713 кб).

 

Хотя решению уравнения Пелля и связанных с ним диофантовых уравнений, посвящено много работ, интерес к этим задачам теории чисел актуален и в настоящее время. Наиболее известен циклический метод, применяемый еще с древних времен. Имеются некоторые разновидности и варианты этого метода (английский метод, метод непрерывных дробей, композиции форм и т.д.), но все они являются той или иной интерпретацией циклического метода (ЦМ). Оказывается, что с ростом характерного параметра уравнения, при некоторых его значениях, нахождение решения требует значительных вычислительных усилий. Большинство современных работ также используют в качестве основы ЦМ. Применение компьютеров во многом облегчают вычисления, однако с методической точки зрения представляет интерес, что и во времена Ферма можно было сформулировать подход, эффективно снижающий объем вычислений, облегчающий и ускоряющий нахождение решения. Значительный выигрыш с этой точки зрения проявляется, как правило, в «трудных» случаях.

Предлагаемый в данной работе ациклический метод решения (АЦМ) включает элементы ЦМ, однако не имеет жесткой привязки к фиксированному алгоритму вычислений, и является гибким методом, позволяющим искать и находить оптимальный алгоритм решения для конкретных случаев. При этом используются мультипликативные свойства уравнения Пелля и мультипликативная структура промежуточных решений. Найдены такие их значения, для которых дальнейшее решение вычисляется по формулам. Приведены некоторые теоремы, дающие теоретическое обоснование методу, а также введена новая запись последовательности решения с помощью несократимых дробей. Это позволило достаточно экономно записывать все этапы решения для очень больших чисел, величина которых для данной статьи ограничивается размером шрифта и размером листа бумаги. Приведено большое число примеров решения уравнений в порядке возрастания сложности и объема вычислений.

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

Отметим для сравнения, что полная запись решения наиболее сложного последнего примера составляет около двух страниц довольно крупным шрифтом. Полная запись последовательности решения циклическим методом содержит более чем в тридцать раз большее число шагов, и объем ее текста намного превысит объем всей данной статьи. Таким образом, предлагаемый метод реализует принцип: больше анализируем, меньше вычисляем.

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

 

Источники информации:

  1. Эдвардс Г. Последняя Теорема Ферма. Генетическое введение в алгебраическую теорию чисел. М.: Мир, 1980.
  2. Lenstra Jr. H.W. Solving the Pell Equation. Notices of AMS, v. 49, p. 182...192.
  3. Barbeau E.J. Pell’s equation. Problem Books in Mathematics. Springer-Verlag, N.Y., 2003.
  4. Williams H.C. Solving the Pell Equation. Number Theory for the millennium, III (Urbana, IL, 2000), A.K. Peters, Natick, MA, 2002, p. 397...435.
  5. Oliveira e Silva T. Large fundamental solutions of Pell equation.

 

Дата публикации:

13 июля 2006 года

Электронная версия:

© НиТ. Текущие публикации, 1997



В начало сайта | Книги | Статьи | Журналы | Нобелевские лауреаты | Издания НиТ | Подписка
Карта сайта | Cовместные проекты | Журнал «Сумбур» | Игумен Валериан | Техническая библиотека
© МОО «Наука и техника», 1997...2013
Об организацииАудиторияСвязаться с намиРазместить рекламуПравовая информация
Яндекс цитирования