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

'''Алгоритм цілочисельного відношення'''&nbsp;— це [[алгоритм]] знаходження цілочисельного відношення. '''Цілочисельне''' '''відношення''' між набором дійсних чисел ''x'' <sub>1</sub>, ''x'' <sub>2</sub>, …, ''x'' <sub>''n''</sub>&nbsp;— це набір цілих чисел ''a'' <sub>1</sub>, ''a'' <sub>2</sub>, …, ''a'' <sub>''n''</sub>, з яких не всі дорівнюють 0, такий, що

: <math>a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,</math>

Зокрема, коли заданий набір [[Дійсне число|дійсних чисел]], відомих із заданою точністю, алгоритм цілочисельного відношення або знайде цілочисельне відношення між ними, або визначить, що не існує цілочисельного відношення з коефіцієнтами, величини яких менші за певну [[Верхня та нижня межа|верхню межу]].<ref>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.</ref>

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

* Алгоритм Фергюсона-Форкейда був опублікований у 1979 році {{iw|Геламан Фергюсон|Геламаном Фергюсоном||Helaman Ferguson}} і [[RW Forcade|Р.&nbsp;В.&nbsp;Форкейдом]].<ref>{{MathWorld|title=Integer Relation|urlname=IntegerRelation}}</ref> Незважаючи на те, що в статті розглядається загальне ''n'', неясно, чи ця стаття повністю вирішує проблему, оскільки в ній відсутні детальні кроки, докази та межа точності, які є вирішальними для надійної реалізації.
* Першим алгоритмом із повними доказами був '''{{iw|Алгоритм редукції решітки Ленстра–Ленстра–Ловаса|алгоритм LLL||Lenstra–Lenstra–Lovász lattice basis reduction algorithm}}''', розроблений {{iw|Ар'єн Ленстра|Ар'єном Ленстрою||Arjen Lenstra}}, {{iw|Хендрік Ленстра|Хендріком Ленстрою||Hendrik Lenstra}} та [[Ласло Ловас]]ом у 1982 році.<ref>{{MathWorld|urlname=LLLAlgorithm|title=LLL Algorithm}}</ref>
* Алгоритм '''HJLS''', розроблений {{iw|Йохан Хостад|Йоханом Хостадом||Johan Håstad}}, Беттіною Юст, {{iw|Джеффрі Лагаріас|Джеффрі Лагаріасом||Jeffrey Lagarias}} і {{iw|Клаус-Пітер Шнорр|Клаусом-Пітером Шнорром||Claus P. Schnorr}} у 1986 році.<ref>{{MathWorld|urlname=HJLSAlgorithm|title=HJLS Algorithm}}</ref><ref>Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: ''Polynomial time algorithms for finding integer relations among real numbers.'' </ref>
* Алгоритм '''PSOS''', розроблений Фергюсоном у 1988 році.<ref>{{MathWorld|urlname=PSOSAlgorithm|title=PSOS Algorithm}}</ref>
* Алгоритм '''PSLQ''', розроблений Фергюсоном і {{iw|Девід Х. Бейлі (математик)|Бейлі||David H. Bailey (mathematician)}} в 1992 році та суттєво спрощений Фергюсоном, Бейлі та Арно в 1999 році.<ref>{{MathWorld|urlname=PSLQAlgorithm|title=PSLQ Algorithm}}</ref><ref>[http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf ''A Polynomial Time, Numerically Stable Integer Relation Algorithm''] {{Webarchive|url=https://web.archive.org/web/20070717073907/http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf |date=2007-07-17 }} by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992</ref> У 2000 році алгоритм PSLQ був обраний [[Джек Донгарра|Джеком Донгаррою]] та Френсісом Салліваном як один із «Десятки найкращих алгоритмів століття»<ref>{{cite journal |author-first=Barry Arthur |author-last=Cipra |author-link=Barry Arthur Cipra |url=http://www.uta.edu/faculty/rcli/TopTen/topten.pdf |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |issue=4 |accessdate=2022-07-20 |archive-date=2021-04-24 |archive-url=https://web.archive.org/web/20210424004030/https://www.uta.edu/faculty/rcli/TopTen/topten.pdf }} {{Webarchive|url=https://web.archive.org/web/20210424004030/http://www.uta.edu/faculty/rcli/TopTen/topten.pdf |date=2021-04-24 }}</ref>, хоча він вважається по суті еквівалентним HJLS.<ref>Jingwei Chen, Damien Stehlé, Gilles Villard: ''[http://perso.ens-lyon.fr/damien.stehle/downloads/PSLQHJLS.pdf A New View on HJLS and PSLQ: Sums and Projections of Lattices.], [http://www.issac-conference.org/2013/ ISSAC'13]''</ref><ref>Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM: </ref>
* Алгоритм LLL був вдосконалений багатьма авторами. Сучасні реалізації LLL можуть вирішувати проблеми цілочисельного відношення з ''n'' вище 500.

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

Типовим підходом в [[Експериментальна математика|експериментальній математиці]] є використання [[чисельні методи|чисельних методів]] і [[Довга арифметика|арифметики довільної точності]] для знаходження наближеного значення [[Ряд (математика)|нескінченного ряду]], [[Нескінченний добуток|нескінченного добутку]] або [[інтеграл]]а з високою точністю (зазвичай щонайменше 100 значущих цифр), а потім використання [[Цілі числа|цілого числа]] алгоритм відношення для пошуку цілочисельного відношення між цим значенням і набором математичних констант. Якщо знайдено цілочисельне відношення, це передбачає можливий [[вираз замкненого вигляду]] для вихідного ряду, добутку чи інтеграла. Потім цю гіпотезу можна підтвердити формальними алгебраїчними методами. Чим вища точність, з якою відомі вхідні дані для алгоритму, тим більший рівень впевненості в тому, що будь-яке знайдене ціле число не є просто {{iw|Майже ціле число|числовим артефактом||Almost integer}}.

Помітним успіхом цього підходу було використання алгоритму PSLQ для знаходження цілочисельного відношення, яке призвело до {{iw|Формула Бейлі-Борвейна-Плуффе|формули Бейлі–Борвейна–Плуффа||Bailey–Borwein–Plouffe formula}} для значення [[Число пі|{{Pi}}]] . PSLQ також допоміг знайти нові ідентичності, що включають {{iw|Множинна дзета-функція|множинні дзета-функцій||Multiple zeta function}} та їхню появу в [[Квантова теорія поля|квантовій теорії поля]]; а також у визначенні точок біфуркації [[Логістичне відображення|логістичної карти]]. Наприклад, якщо B<sub>4</sub>&nbsp;— четверта точка біфуркації логістичної карти, константа α&nbsp;=&nbsp;− ''B''<sub>4</sub>(''B''<sub>4</sub>&nbsp;−&nbsp;2) є коренем многочлена 120-го степеня, найбільший коефіцієнт якого дорівнює 257<sup>30</sup> .<ref>David H. Bailey and David J. Broadhurst, [http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf "Parallel Integer Relation Detection: Techniques and Applications, "] {{Webarchive|url=https://web.archive.org/web/20110720013234/http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf |date=2011-07-20 }} Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719—1736; LBNL-44481.</ref><ref>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)</ref> Алгоритми цілочисельних відношень поєднуються з таблицями високоточних математичних констант і евристичними методами пошуку в таких програмах, як {{iw|Inverse Symbolic Calculator}} або [[Інвертор Плуффа]] .

Знаходження цілочисельного відношення можна використовувати для [[Факторизація многочленів|розкладання поліномів]] високого степеня.<ref>M. van Hoeij: ''Factoring polynomials and the knapsack problem.'' </ref>

== Примітки ==
{{Reflist|30em}}

== Посилання ==

* [https://web.archive.org/web/20080422084455/http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html ''Recognizing Numerical Constants''] by {{iw|David_H._Bailey_(mathematician)|David H. Bailey}} and {{iw|Simon_Plouffe|Simon Plouffe}}
* [http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf ''Ten Problems in Experimental Mathematics''] by David H. Bailey, [[Джонатан Борвейн|Jonathan M. Borwein]], Vishaal Kapoor, and {{iw|Eric_W._Weisstein|Eric W. Weisstein}}


{{Алгоритми теорії чисел}}
[[Категорія:Алгоритми теорії чисел]]