Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Целое отношение между набором действительных чисел х 1 , х 2 , ..., х п представляет собой набор целых чисел 1 , 2 , ..., п , не все 0, таким образом, что

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

История [ править ]

Для случая n = 2 расширение алгоритма Евклида может найти любое целочисленное отношение, которое существует между любыми двумя действительными числами x 1 и x 2 . Алгоритм генерирует последовательные члены разложения непрерывной дроби x 1 / x 2 ; если между числами существует целочисленная связь, то их соотношение является рациональным, и алгоритм в конечном итоге завершается.

  • Алгоритм Фергюсона – Форкейда был опубликован в 1979 году Геламаном Фергюсоном и Р.В. Форкейдом . [2] Хотя в статье рассматриваются общие n , неясно, полностью ли она решает проблему, поскольку в ней отсутствуют подробные шаги, доказательства и оценка точности, которые имеют решающее значение для надежной реализации.
  • Первым алгоритмом с полными доказательствами был алгоритм LLL , разработанный Арьеном Ленстрой , Хендриком Ленстрой и Ласло Ловасом в 1982 г. [3]
  • HJLS алгоритм , разработанный Джоенного Хастадом, Беттин Жюст, Джеффри Лагариасом и Клаус-Питер Шнорр в 1986. [4] [5]
  • Алгоритм ОПМ , разработанный в 1988 году Фергюсон [6]
  • Алгоритм PSLQ , разработанный Фергюсон и Бейли в 1992 году и существенно упростить Фергюсон, Бейли и Арно в 1999 году [7] [8] В 2000 году алгоритм PSLQ был выбран в качестве одного из «Top Ten алгоритмов века» Джек Донгарра и Фрэнсис Салливан [9], хотя он считается по существу эквивалентом HJLS. [10] [11]
  • Алгоритм LLL был улучшен многими авторами. Современные реализации LLL могут решать проблемы с целочисленными отношениями с n выше 500.

Приложения [ править ]

Алгоритмы целочисленных отношений имеют множество приложений. Первое приложение состоит в том, чтобы определить, может ли данное действительное число x быть алгебраическим , путем поиска целочисленного отношения между набором степеней x {1, x , x 2 , ..., x n }. Второе приложение - поиск целочисленного отношения между действительным числом x и набором математических констант, таких как e , π и ln (2), что приведет к выражению для x как линейной комбинации этих констант.

Типичный подход в экспериментальной математике - использовать численные методы и арифметику произвольной точности для нахождения приблизительного значения для бесконечного ряда , бесконечного произведения или интеграла с высокой степенью точности (обычно не менее 100 значащих цифр), а затем использовать целое число. алгоритм отношения для поиска целочисленного отношения между этим значением и набором математических констант. Если найдено целочисленное отношение, это предполагает возможное выражение в замкнутой формедля исходной серии, продукта или интеграла. Затем эта гипотеза может быть подтверждена формальными алгебраическими методами. Чем выше точность, с которой известны входные данные для алгоритма, тем выше уровень уверенности в том, что любое найденное целочисленное отношение не является просто числовым артефактом .

Заметным успехом этого подхода было использование алгоритма PSLQ для нахождения целочисленного отношения, которое привело к формуле Бейли – Борвейна – Плаффа для значения π . PSLQ также помог найти новые тождества, включающие несколько дзета-функций и их появление в квантовой теории поля ; и в определении точек бифуркации логистической карты . Например, где B 4 - четвертая точка бифуркации логистической карты, константа α = - B 4 ( B 4  - 2) является корнем многочлена 120-й степени, наибольший коэффициент которого равен 257 30 . [12] [13]Алгоритмы целочисленных отношений сочетаются с таблицами математических констант высокой точности и методами эвристического поиска в таких приложениях, как калькулятор обратных символьных значений или инвертор Плуффа .

Нахождение целочисленных соотношений может использоваться для факторизации многочленов высокой степени. [14]

Ссылки [ править ]

  1. ^ Поскольку набор действительных чисел может быть указан только с конечной точностью, алгоритм, который не устанавливает ограничений на размер своих коэффициентов, всегда будет находить целочисленное отношение для достаточно больших коэффициентов. Представляющие интерес результаты возникают, когда размер коэффициентов в целочисленном отношении мал по сравнению с точностью, с которой указаны действительные числа.
  2. ^ Вайсштейн, Эрик В. «Целочисленное отношение» . MathWorld .
  3. ^ Вайсштейн, Эрик В. "Алгоритм LLL" . MathWorld .
  4. ^ Вайсштейн, Эрик В. "Алгоритм HJLS" . MathWorld .
  5. ^ Йохан Хастад, Беттина Just, Джеффри Лагариас, Клаус-Питер Шнорр: алгоритмы полиномиального времени для поиска целочисленных отношений между действительными числами. Предварительная версия: STACS 1986 ( Теоретический симпозиум. Аспекты информатики ) Конспект лекций Информатика 210 (1986), с. 105–118. SIAM J. Comput. , Vol. 18 (1989), стр. 859–881.
  6. ^ Вайсштейн, Эрик В. "Алгоритм PSOS" . MathWorld .
  7. ^ Вайсштейн, Эрик В. «Алгоритм PSLQ» . MathWorld .
  8. ^ Полиномиальное время, численно устойчивый алгоритм целочисленных отношений Геламана Р.П. Фергюсона и Дэвида Х. Бейли; Технический отчет РНР РНР-91-032; 14 июля 1992 г.
  9. ^ Cipra, Барри Артур . «Лучшее из 20-го века: редакция назвала 10 лучших алгоритмов» (PDF) . Новости SIAM . 33 (4).
  10. ^ Цзинвэй Чен, Дамиан Stehle, Жиль Виллар: Новый взгляд на HJLS и PSLQ: Суммы и Проекцию решеток. , ISSAC'13
  11. ^ Геламан Р.П. Фергюсон, Дэвид Х. Бейли и Стив Арно, АНАЛИЗ PSLQ, АЛГОРИТМ ПОИСКА ЦЕЛОЙ СВЯЗИ: [1]
  12. ^ Дэвид Х. Бейли и Дэвид Дж. Бродхерст, "Параллельное обнаружение целочисленных отношений: методы и приложения", Математика вычислений, т. 70, нет. 236 (октябрь 2000 г.), стр. 1719–1736; LBNL-44481.
  13. ^ IS Kotsireas, и K. Karamanos, "Точное вычисление точки бифуркации B4 логистической карты и гипотезы Бейли – Бродхерста", IJ Bifurcation and Chaos 14 (7): 2417–2423 (2004)
  14. ^ М. ван Hoeij: Факторизация многочленов и проблема ранца. Журнал теории чисел, 95, 167–189, (2002).

Внешние ссылки [ править ]

  • Признание числовых констант по Дэвид Х. Бейли и Симон Plouffe
  • Десять задач экспериментальной математики Дэвида Х. Бейли, Джонатана М. Борвейна , Вишаала Капура и Эрика У. Вайстайна