Русская Википедия:Алгоритм поиска целочисленных соотношений

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Целочисленное соотношение между набором вещественных чисел <math>x_1, x_2, ..., x_n</math> — это набор целых чисел <math>a_1,a_2, ...,a_n</math>, не все из которых равны нулю, таких, что

<math>a_1x_1 + a_2x_2 + ... + a_nx_n = 0.</math>

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

История

Для случая n = 2 расширение алгоритма Евклида может определить, существует ли целочисленное соотношение между двумя вещественными числами <math>x_1</math> и <math>x_2</math>. Алгоритм образует последовательность элементов разложения <math>x_1/x_2</math> в непрерывную дробь. Если существует целочисленная взаимосвязь между числами, то их частное рационально и алгоритм, в конечном счёте, завершится.

  • Алгоритм Фергюсона — Форкейда опубликовали в 1979 Шаблон:Не переведено 5 и Форкейд[2]. Хотя в статье идёт речь о любом n, не совсем ясно, решает ли статья полностью задачу, поскольку в ней отсутствуют некоторые детали алгоритма, нет доказательств и точных границ, что существенно для достоверной имплементации.
  • Первым алгоритмом с полным доказательством был ЛЛЛ-алгоритм, который разработали Арьен Ленстра, Хендрик Ленстра и Ласло Ловас в 1982[3].
  • Юхан Хостад, Беттина Джаст, Джефри Лагариас и Клаус-Петер Шнорр разработали алгоритм HJLS в 1986[4]Шаблон:Sfn.
  • Фергюсон разработал в 1988 алгоритм PSOS[5]
  • Фергюсон и Бейли разработали алгоритм PSLQ в 1992 и в 1999 в значительной степени упростили (вместе с Арно)[6]Шаблон:Sfn. В 2000 Джек Донгарра и Фрэнсис Салливан Шаблон:Sfn включили алгоритм PSLQ в «Первую десятку алгоритмов столетия», хотя и признано, что большей частью он эквивалентен алгоритму HJLSШаблон:SfnШаблон:Sfn.
  • Алгоритм ЛЛЛ улучшали множество авторов. Современная имплементация алгоритма ЛЛЛ может решать задачи поиска целочисленных соотношений с n, большим 500.

Приложения

Алгоритм поиска целочисленных соотношений имеет многочисленные приложения. Первое приложение — определение, не является ли заданное вещественное число x алгебраическим, для чего производится поиск целочисленного соотношения между множеством степеней числа x {1, x, x2, ..., xn}. Второе приложение — поиск целочисленной связи между вещественным числом x и набором математических констант, таких как e, <math>\pi</math> и ln(2), что приводит к выражению x в виде линейной комбинации этих констант.

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

Заметным успехом такого подхода было использование алгоритма PSLQ для поиска целочисленного соотношения, которое привело к формуле Бэйли — Боруэйна — Плаффа для числа <math>\pi</math>. Алгоритм PSLQ также помог найти новые тождества, в которые входит Шаблон:Не переведено 5, и их появление в квантовой теория поля. Алгоритм PSLQ помог в распознании точек бифуркации логистического отображения. Например, если B4 является четвёртой точкой бифуркации логистического отображения, константа α=-B4(B4-2) является корнем многочлена 120-й степени с максимальным коэффициентом 25730Шаблон:SfnШаблон:Sfn. Алгоритмы поиска целочисленных соотношений комбинируются с таблицами математических констант высокой точности и эвристическими методами поиска, такими как Шаблон:Не переведено 5 или Шаблон:Не переведено 5.

Поиск целочисленных соотношений может быть использован для разложения многочленов высокой степениШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Теоретико-числовые алгоритмы Шаблон:Изолированная статья Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Поскольку вещественные числа могут быть заданы только с конечной точностью, алгоритм без задания границы коэффициентов всегда найдёт целочисленную связь при достаточно больших коэффициентах. Результат интересен, только когда величина коэффициентов в целочисленном соотношении мала по сравнению с точностью задания вещественных чисел.
  2. ↑ Шаблон:MathWorld
  3. ↑ Шаблон:MathWorld
  4. ↑ Шаблон:MathWorld
  5. ↑ Шаблон:MathWorld
  6. ↑ Шаблон:MathWorld
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_поиска_целочисленных_соотношений&oldid=8940314