Перейти в начало сайта Перейти в начало сайта
Электронная библиотека «Наука и техника»
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...2017
Об организацииАудиторияСвязаться с намиРазместить рекламуПравовая информация
Яндекс цитирования
Яндекс.Метрика