Рівняння Пелля
Мультиплікативні властивості та ациклічний метод вирішення
Повна версія статті: DOC (713 кб).
Хоча рішенню рівняння Пелля і пов'язаних з ним діофантових рівнянь, присвячено багато робіт, інтерес до цих завдань теорії чисел є актуальним і в даний час. Найбільш відомий циклічний метод, який застосовується ще з давніх часів. Є деякі різновиди та варіанти цього методу (англійський метод, метод безперервних дробів, композиції форм тощо), але вони є тією чи іншою інтерпретацією циклічного методу (ЦМ). Виявляється, що зі зростанням характерного параметра рівняння, за деяких його значень, знаходження рішення потребує значних обчислювальних зусиль. Більшість сучасних робіт також використовують як основу ЦМ. Застосування комп'ютерів багато в чому полегшують обчислення, проте з методичної погляду цікавить, як і за часів Ферма можна було сформулювати підхід, ефективно знижує обсяг обчислень, полегшує і прискорює перебування рішення. Значний виграш із цього погляду проявляється, як правило, у «важких» випадках.
Ациклічний метод рішення (АЦМ), що пропонується в даній роботі, включає елементи ЦМ, проте не має жорсткої прив'язки до фіксованого алгоритму обчислень, і є гнучким методом, що дозволяє шукати і знаходити оптимальний алгоритм рішення для конкретних випадків. При цьому використовуються мультиплікативні властивості рівняння Пелля та мультиплікативна структура проміжних рішень. Знайдено такі значення, котрим подальше рішення обчислюється по формулам. Наведено деякі теореми, що дають теоретичне обґрунтування методу, а також введено новий запис послідовності рішення за допомогою нескоротних дробів. Це дозволило досить ощадливо записувати всі етапи рішеннядля дуже великих чисел, величина яких для цієї статті обмежується розміром шрифту та розміром аркуша паперу. Наведено велику кількість прикладів розв'язання рівнянь у порядку зростання складності та обсягу обчислень.
Оцінка ефективності АЦМ проводиться шляхом порівняння кроків рішення з числом кроків ЦМ, отриманого однією з недавніх робіт. Існує очевидна тенденція підвищення ефективності АЦМ зі зростанням складності завдання.
Зазначимо порівняння, що повна запис рішення найскладнішого останнього прикладу становить близько двох сторінок досить великим шрифтом. Повний запис послідовності рішення циклічним методом містить більш ніж тридцять разів більше кроків, і обсяг її тексту набагато перевищить обсяг всієї цієї статті. Отже, запропонований метод реалізує принцип: більше аналізуємо, менше обчислюємо.
Відповідно при конкретній комп'ютерній програмній реалізації буде задіяний значно менший обсяг пам'яті, що дозволить вирішувати рівняння з великими параметрами та знижувати час обчислень.