Алгоритм цілочисельного відношення

Матеріал з testwiki
Перейти до навігації Перейти до пошуку

Алгоритм цілочисельного відношення — це алгоритм знаходження цілочисельного відношення. Цілочисельне відношення між набором дійсних чисел x 1, x 2, …, x n — це набір цілих чисел a 1, a 2, …, a n, з яких не всі дорівнюють 0, такий, що

a1x1+a2x2+⋯+anxn=0.

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

Історія

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

  • Алгоритм Фергюсона-Форкейда був опублікований у 1979 році Шаблон:Iw і Р. В. Форкейдом.[2] Незважаючи на те, що в статті розглядається загальне n, неясно, чи ця стаття повністю вирішує проблему, оскільки в ній відсутні детальні кроки, докази та межа точності, які є вирішальними для надійної реалізації.
  • Першим алгоритмом із повними доказами був Шаблон:Iw, розроблений Шаблон:Iw, Шаблон:Iw та Ласло Ловасом у 1982 році.[3]
  • Алгоритм HJLS, розроблений Шаблон:Iw, Беттіною Юст, Шаблон:Iw і Шаблон:Iw у 1986 році.[4][5]
  • Алгоритм PSOS, розроблений Фергюсоном у 1988 році.[6]
  • Алгоритм PSLQ, розроблений Фергюсоном і Шаблон:Iw в 1992 році та суттєво спрощений Фергюсоном, Бейлі та Арно в 1999 році.[7][8] У 2000 році алгоритм PSLQ був обраний Джеком Донгаррою та Френсісом Салліваном як один із «Десятки найкращих алгоритмів століття»[9], хоча він вважається по суті еквівалентним HJLS.[10][11]
  • Алгоритм LLL був вдосконалений багатьма авторами. Сучасні реалізації LLL можуть вирішувати проблеми цілочисельного відношення з n вище 500.

Застосування

Алгоритми цілочисельних відношень мають численні застосування. Перше застосування полягає в тому, щоб визначити, чи ймовірно дане дійсне число x є алгебраїчним, шляхом пошуку цілочисельного відношення між набором степенів x {1, x, x 2, …, x n }. Друге застосування полягає в пошуку цілочисельного відношення між дійсним числом x і набором математичних констант, таких як e, π і ln(2), що призведе до виразу для x як лінійної комбінації цих констант.

Типовим підходом в експериментальній математиці є використання чисельних методів і арифметики довільної точності для знаходження наближеного значення нескінченного ряду, нескінченного добутку або інтеграла з високою точністю (зазвичай щонайменше 100 значущих цифр), а потім використання цілого числа алгоритм відношення для пошуку цілочисельного відношення між цим значенням і набором математичних констант. Якщо знайдено цілочисельне відношення, це передбачає можливий вираз замкненого вигляду для вихідного ряду, добутку чи інтеграла. Потім цю гіпотезу можна підтвердити формальними алгебраїчними методами. Чим вища точність, з якою відомі вхідні дані для алгоритму, тим більший рівень впевненості в тому, що будь-яке знайдене ціле число не є просто Шаблон:Iw.

Помітним успіхом цього підходу було використання алгоритму PSLQ для знаходження цілочисельного відношення, яке призвело до Шаблон:Iw для значення [[Число пі|Шаблон:Pi]] . PSLQ також допоміг знайти нові ідентичності, що включають Шаблон:Iw та їхню появу в квантовій теорії поля; а також у визначенні точок біфуркації логістичної карти. Наприклад, якщо B4 — четверта точка біфуркації логістичної карти, константа α = − B4(B4 − 2) є коренем многочлена 120-го степеня, найбільший коефіцієнт якого дорівнює 25730 .[12][13] Алгоритми цілочисельних відношень поєднуються з таблицями високоточних математичних констант і евристичними методами пошуку в таких програмах, як Шаблон:Iw або Інвертор Плуффа .

Знаходження цілочисельного відношення можна використовувати для розкладання поліномів високого степеня.[14]

Примітки

Шаблон:Reflist

Посилання


Шаблон:Алгоритми теорії чисел

  1. ↑ Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.
  2. ↑ Шаблон:MathWorld
  3. ↑ Шаблон:MathWorld
  4. ↑ Шаблон:MathWorld
  5. ↑ Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: Polynomial time algorithms for finding integer relations among real numbers.
  6. ↑ Шаблон:MathWorld
  7. ↑ Шаблон:MathWorld
  8. ↑ A Polynomial Time, Numerically Stable Integer Relation Algorithm Шаблон:Webarchive by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992
  9. ↑ Шаблон:Cite journal Шаблон:Webarchive
  10. ↑ Jingwei Chen, Damien Stehlé, Gilles Villard: A New View on HJLS and PSLQ: Sums and Projections of Lattices., ISSAC'13
  11. ↑ Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM:
  12. ↑ David H. Bailey and David J. Broadhurst, "Parallel Integer Relation Detection: Techniques and Applications, " Шаблон:Webarchive Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719—1736; LBNL-44481.
  13. ↑ I. S. Kotsireas, and K. Karamanos, «Exact Computation of the bifurcation Point B4 of the logistic Map and the Bailey–Broadhurst Conjectures», I. J. Bifurcation and Chaos 14(7):2417–2423 (2004)
  14. ↑ M. van Hoeij: Factoring polynomials and the knapsack problem.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Алгоритм_цілочисельного_відношення&oldid=9758