Введение 4
1 Алгоритмизация метода Рунге для кубических уравнений 7
1.1 Элементарная версия метода Рунге: общий алгоритм 7
1.2 Модификация общего алгоритма в частных случаях 11
1.3 Дополнительные теоретические результаты 17
2 Компьютерная реализация на языке программирования Python 20
2.1 Общий случай 20
2.2 Частные случаи: особенности реализации и статистика 20
Заключение 23
Список использованных источников 24
Приложение А. Программа для решения уравнения (1.2) 26
Приложение Б. Программа для решения уравнения (1.10) 31
Приложение В. Программа для решения уравнения (1.11) 35
Приложение Г. Программа для решения уравнения (1.12) 39
Метод Рунге является одним из самых простых общих методов решения диофантовых уравнений с двумя неизвестными (см., например, монографии [3, 9], а также статью [12]). Под диофантовым уравнением понимается уравнение вида f(x,y) = 0, где f (x,y) — некоторый полином с целыми коэффициентами. Решения этого уравнения — это пары (x,y) целых чисел, при подстановки которых в уравнение получаются верные числовые равенства. Вообще говоря, найти все решения данного диофантова уравнения может представлять собой трудную математическую проблему. Тем не менее существуют классы диофантовых уравнений, для которых удается предложить эффективные методы их решения. К таким методам и относится упомянутый метод Рунге, предложенный немецким математиком Карлом Рунге еще в конце XIX века.
Оригинальная версия метода Рунге предполагает манипуляции со сложными математическими объектами (типа рядов Пюизо, частным случаем которых являются более известные ряды Лорана). Несмотря на теоретическую эффективность метода Рунге, при его практической реализации возникают определенные проблемы даже в случае диофантовых уравнений малой степени (3-й или 4-й), и это заставляет искать альтернативные пути.
Элементарная версия метода Рунге для решения кубических диофантовых уравнений с двумя неизвестными впервые была предложена в статье [1]. Там же было отмечено, что алгоритмическая реализация элементарного под¬хода нуждается в дальнейшей детализации и не представляется очевидной. Такая детализация была дана позже в статье [10]. Для диофантовых уравнений 4-й степени с двумя неизвестными также есть элементарная версия метода Рунге (см. статью [2]), где проблема компьютерной реализации будет, по-видимому, еще сложней.
В современных системах компьютерной алгебры (СКА) общего назначения (типа Maple [14], Mathematica [15] и т.п.) отсутствуют пакеты или моду¬ли, которые позволяли бы решать подобные диофантовы уравнения: обычно СКА или решает уравнение некорректно, или же просто отказывается его решать. Это связано с тем, что имеющиеся теоретические оценки (см., например, [13, 11]) для решений диофантовых уравнений, подпадающих под метод Рунге, оказываются практически непригодными, т. е. компьютерная реализация алгоритма решения диофантовых уравнений на основе этих оценок была бы бесполезной из-за слишком больших констант (подробности см., например, в статье [10]). Таким образом, актуальность настоящей работы выражается в том, что компьютерная реализация элементарной версии метода Рунге способствует усовершенствованию современных систем компьютерной алгебры и развивает алгоритмические подходы к решению диофантовых уравнений в теории чисел.
Для кубических диофантовых уравнений естественно поставить задачу об оптимизации алгоритма решения, учитывающей специфику уравнения. Основной целью работы является компьютерная реализация пригодного для практического применения алгоритма решения уравнений кубических диофантовых уравнений, удовлетворяющих условию Рунге.
Для достижения поставленной цели были сформулированы следующие задачи.
1. Предложить компьютерную реализацию на языке программирования Python элементарной версии метода Рунге для кубических уравнений вида x(Ax2+ Bxy + Cy2) + a1x2+ a2xy + 0 • y2+ a4x + a5y + a6= 0, (Это фактически общий случай, поскольку с помощью линейной замены неизвестных к такому виду можно свести любое кубическое уравнение с двумя неизвестными.)
2. Оптимизировать предложенную компьютерную реализацию алгоритма решения общего кубического уравнения.
3. Оптимизировать алгоритм решения для уравнений частного вида:
x(y2-2x2) + Hx + y+ 1 = 0,
x(y2-2x2) + x+ y+ H = 0,
x(y2-2x2) + x + Hy+ 1 = 0,
где H — целочисленный параметр. С помощью оптимизированной версии алгоритма получить статистику количества решений этих уравнений в достаточно широком диапазоне изменения параметра H.
Основные результаты работы: задачи 1 и 3 полностью решены. Попутно были получены некоторые дополнительные теоретические результаты относительно оценки величины и количества решений уравнений из п. 3.
В работе была рассмотрена алгоритмическая реализация элементарной версии метода Рунге для решения кубических диофантовых уравнений с двумя неизвестными в целых числах (см. раздел 1). Соответствующий алгоритм был запрограммирован на языке Python. К сожалению, оптимизация этого алгоритма была осуществлена только в некоторых частных случаях (см. раз¬дел 1.2). Таким образом, цели работы достигнуты лишь частично. Тем не менее, удалось собрать интересную с теоретической точки зрения статистику количества решений некоторых частных семейств диофантовых уравнений. Отметим также, что попутно были получены дополнительные теоретические результаты о величине и количестве решений некоторых диофантовых уравнений, что представляет несомненный теоретический интерес.
