Алгоритм целочисленного отношения
Целочисленное отношение между набором действительных чисел x 1 , x 2 , ..., x n и набором целых чисел a 1 , a 2 , ..., an что , не всеми 0, такое,
Алгоритм целочисленных отношений — это алгоритм поиска целочисленных отношений. В частности, при наличии набора действительных чисел, известного с заданной точностью, алгоритм целочисленных отношений либо найдет целочисленное отношение между ними, либо определит, что целочисленное отношение не существует с коэффициентами, величины которых меньше определенной верхней границы . [1]
История [ править ]
В случае n = 2 расширение алгоритма Евклида может найти любое целочисленное отношение, существующее между любыми двумя действительными числами x 1 и x 2 . Алгоритм генерирует последовательные члены цепной дроби разложения x 1 / x 2 ; если между числами существует целочисленная связь, то их соотношение рационально и алгоритм в конечном итоге завершается.
- Алгоритм Фергюсона-Форкеда был опубликован в 1979 году Хеламаном Фергюсоном и Р.В. Форкейдом . [2] Хотя в статье рассматривается общее n , неясно, полностью ли она решает проблему, поскольку в ней отсутствуют подробные шаги, доказательства и границы точности, которые имеют решающее значение для надежной реализации.
- Первым алгоритмом с полными доказательствами был алгоритм LLL , разработанный Арьеном Ленстрой , Хендриком Ленстрой и Ласло Ловасом в 1982 году. [3]
- Алгоритм HJLS , разработанный Йоханом Хостадом , Беттиной Джаст, Джеффри Лагариасом и Клаусом-Питером Шнорром в 1986 году. [4] [5]
- Алгоритм PSOS , разработанный Фергюсоном в 1988 году. [6]
- Алгоритм PSLQ , разработанный Фергюсоном и Бейли в 1992 году и существенно упрощенный Фергюсоном, Бейли и Арно в 1999 году. [7] [8] в качестве одного из «десяти лучших алгоритмов века». В 2000 году алгоритм PSLQ был выбран Джеком Донгаррой и Фрэнсисом Салливаном [9] хотя по сути он считается эквивалентом HJLS. [10] [11]
- Алгоритм LLL был улучшен многими авторами. Современные реализации LLL могут решать задачи целочисленных отношений с n выше 500.
Приложения [ править ]
Алгоритмы целочисленных отношений имеют множество приложений. Первое применение — определить, может ли данное действительное число x быть алгебраическим , путем поиска целочисленного отношения между набором степеней x {1, x , x 2 , ..., Икс н }. Второе приложение — поиск целочисленной связи между действительным числом x и набором математических констант, таких как e , π и ln(2), что приведет к выражению x как линейной комбинации этих констант.
Типичный подход в экспериментальной математике — использовать численные методы и арифметику произвольной точности, чтобы найти приблизительное значение для бесконечного ряда , бесконечного произведения или интеграла с высокой степенью точности (обычно не менее 100 значащих цифр), а затем использовать целое число. Алгоритм отношения для поиска целочисленного отношения между этим значением и набором математических констант. Если найдено целочисленное отношение, это предполагает возможное выражение в замкнутой форме для исходного ряда, произведения или интеграла. Эту гипотезу затем можно проверить формальными алгебраическими методами. Чем выше точность, с которой известны входные данные для алгоритма, тем выше уровень уверенности в том, что любое найденное целочисленное соотношение не является просто числовым артефактом .
Заметным успехом этого подхода стало использование алгоритма PSLQ для нахождения целочисленного соотношения, которое привело к формуле Бейли-Борвейна-Плуффа для значения π . PSLQ также помог найти новые тождества, включающие множественные дзета-функции и их появление в квантовой теории поля ; и в выявлении точек бифуркации логистической карты . Например, где B 4 — четвертая точка бифуркации логистической карты, константа α = − B 4 ( B 4 − 2) является корнем полинома 120-й степени, наибольший коэффициент которого равен 257. 30 . [12] [13] Алгоритмы целочисленных отношений сочетаются с таблицами математических констант высокой точности и эвристическими методами поиска в таких приложениях, как Обратный символьный калькулятор или Инвертор Плуффа .
Нахождение целочисленных отношений можно использовать для факторизации полиномов высокой степени. [14]
Ссылки [ править ]
- ^ Поскольку набор действительных чисел можно указать только с конечной точностью, алгоритм, который не налагал ограничений на размер своих коэффициентов, всегда будет находить целочисленное соотношение для достаточно больших коэффициентов. Интересные результаты возникают, когда размер коэффициентов в целочисленном отношении мал по сравнению с точностью, с которой указаны действительные числа.
- ^ Вайсштейн, Эрик В. «Целочисленное отношение» . Математический мир .
- ^ Вайсштейн, Эрик В. «Алгоритм LLL» . Математический мир .
- ^ Вайсштейн, Эрик В. «Алгоритм HJLS» . Математический мир .
- ^ Йохан Хостад, Беттина Джаст, Джеффри Лагариас, Клаус-Питер Шнорр: Алгоритмы полиномиального времени для поиска целочисленных отношений между действительными числами. Предварительная версия: STACS 1986 ( Теоретический симпозиум. Аспекты информатики ) Конспекты лекций Computer Science 210 (1986), стр. 105–118. СИАМ Дж. Компьютер. , Том. 18 (1989), стр. 859–881.
- ^ Вайсштейн, Эрик В. «Алгоритм PSOS» . Математический мир .
- ^ Вайсштейн, Эрик В. «Алгоритм PSLQ» . Математический мир .
- ^ Полиномиальное время, численно стабильный алгоритм целочисленных отношений. Архивировано 17 июля 2007 г. в Wayback Machine Хеламаном Р.П. Фергюсоном и Дэвидом Х. Бейли; Технический отчет РНР РНР-91-032; 14 июля 1992 г.
- ^ Сипра, Барри Артур . «Лучшее 20-го века: редакторы назвали 10 лучших алгоритмов» (PDF) . СИАМ Новости . 33 (4). Архивировано из оригинала (PDF) 24 апреля 2021 г. Проверено 17 августа 2012 г.
- ^ Цзинвэй Чен, Дэмиен Стеле, Жиль Виллар: новый взгляд на HJLS и PSLQ: суммы и проекции решеток. , ИССАК'13
- ^ Хеламан Р.П. Фергюсон, Дэвид Х. Бейли и Стив Арно, АНАЛИЗ PSLQ, АЛГОРИТМ НАХОЖДЕНИЯ ЦЕЛОГО ОТНОШЕНИЯ: [1]
- ^ Дэвид Х. Бейли и Дэвид Дж. Бродхерст, «Обнаружение параллельных целочисленных отношений: методы и приложения», Архивировано 20 июля 2011 г. в Wayback Machine Mathematics of Computation, vol. 70, нет. 236 (октябрь 2000 г.), стр. 1719–1736; ЛБНЛ-44481.
- ^ И. С. Коциреас и К. Караманос, «Точное вычисление точки бифуркации B4 логистической карты и гипотезы Бейли – Бродхерста», IJ Bifurcation and Chaos 14 (7): 2417–2423 (2004)
- ^ М. ван Хой: Факторизация полиномов и проблема о рюкзаке. Журнал теории чисел, 95, 167–189 (2002).
Внешние ссылки [ править ]
- Распознавание числовых констант Дэвид Х. Бэйли и Саймон Плуфф
- Десять задач по экспериментальной математике. Архивировано 10 июня 2011 г. в Wayback Machine Дэвидом Х. Бэйли, Джонатаном М. Борвейном , Вишаалом Капуром и Эриком В. Вайсстейном.