Непарыўны дроб

Непары́ўны дроб (або ланцуго́вы дроб) — гэта матэматычны выраз віду

$[a_{0};a_{1},a_{2},a_{3},\cdots ]=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\ldots }}}}}}\;$

дзе a₀ ёсць цэлы лік, і ўсе астатнія a_n — натуральныя лікі (дадатныя цэлыя).

Любы рэчаісны лік можна прадставіць у выглядзе непарыўнага дробу (канечнага ці бесканечнага). Лік можна прадставіць канечным ланцуговым дробам тады і толькі тады, калі ён рацыянальны. Лік можна прадставіць перыядычным ланцуговым дробам тады і толькі тады, калі ён ёсць квадратычная ірацыянальнасць.

Раскладанне ў непарыўны дроб

Любы рэчаісны лік $x$ можна прадставіць (канечным ці бесканечным, перыядычным ці неперыядычным) ланцуговым дробам $[a_{0};a_{1},a_{2},a_{3},\cdots ]$, дзе

$a_{0}=\lfloor x\rfloor ,x_{0}=x-a_{0},$

$a_{1}=\left\lfloor {\frac {1}{x_{0}}}\right\rfloor ,x_{1}={\frac {1}{x_{0}}}-a_{1},$

$\dots$

$a_{n}=\left\lfloor {\frac {1}{x_{n-1}}}\right\rfloor ,x_{n}={\frac {1}{x_{n-1}}}-a_{n},$

$\dots$

дзе $\lfloor x\rfloor$ абазначае цэлую частку ліку $x$.

Для рацыянальнага ліку $x$ гэта раскладанне абарвецца па дасягненні нулявога $x_{n}$ для некаторага n. У гэтым выпадку $x$ прадстаўляецца канечным непарыўным дробам $x=[a_{0};a_{1},\cdots ,a_{n}]$.

Для ірацыянальнага $x$ усе велічыні $x_{n}$ будуць ненулявыя і працэс раскладання можна працягваць без канца. У гэтым выпадку $x$ прадстаўляецца бесканечным ланцуговым дробам $x=[a_{0};a_{1},a_{2},a_{3},\cdots ]$.

Каб хутка раскласці рацыянальны лік у ланцуговы дроб, можна скарыстаць алгарытм Еўкліда.

Падыходныя дробы

n-ым падыходным дробам (або падыходзячым дробам) для ланцуговага дробу $x=[a_{0};a_{1},a_{2},a_{3},\cdots ]$ называецца канечны ланцуговы дроб $[a_{0};a_{1},\cdots ,a_{n}]$. Значэнне падыходнага дробу раўняецца некатораму рацыянальнаму ліку ${\frac {p_{n}}{q_{n}}}$. Падыходзячыя дробы з цотнымі нумарамі ўтвараюць нарастаючую паслядоўнасць, граніца якой роўная $x$. Аналагічна, падыходзячыя дробы з няцотнымі нумарамі ўтвараюць спадаючую паслядоўнасць, граніца якой таксама роўная $x$.

Эйлер вывеў зваротныя формулы для вылічэння лічнікаў і назоўнікаў падыходных дробаў:

$p_{-1}=1,\quad p_{0}=a_{0},\quad p_{n}=a_{n}p_{n-1}+p_{n-2};$

$q_{-1}=0,\quad q_{0}=1,\quad q_{n}=a_{n}q_{n-1}+q_{n-2}.$

Такім чынам, велічыні $p_{n}$ і $q_{n}$ прадстаўляюцца значэннямі кантынуантаў:

$p_{n}=K_{n+1}(a_{0},a_{1},\cdots ,a_{n})$

$q_{n}=K_{n}(a_{1},a_{2},\cdots ,a_{n})$

Паслядоўнасці $\left\{p_{n}\right\}$ і $\left\{q_{n}\right\}$ нарастаюць.

Лічнікі і назоўнікі суседніх падыходных дробаў звязаны суадносінамі:

$p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1},$     (1)

якія можна перапісаць у выглядзе

${\frac {p_{n}}{q_{n}}}-{\frac {p_{n-1}}{q_{n-1}}}={\frac {(-1)^{n-1}}{q_{n-1}q_{n}}}.$

Адкуль вынікае, што

$\left|x-{\frac {p_{n-1}}{q_{n-1}}}\right|<{\frac {1}{q_{n-1}q_{n}}}<{\frac {1}{q_{n-1}^{2}}}.$

Прыбліжэнне рэчаісных лікаў рацыянальнымі

Непарыўныя дробы дазваляюць эфектыўна знаходзіць добрыя рацыянальныя прыбліжэнні рэчаісных лікаў. А іменна, калі рэчаісны лік $x$ раскласці ў ланцуговы дроб, то яго падыходныя дробы будуць задавальняць няроўнасць

$\left|x-{\frac {p_{n}}{q_{n}}}\right|<{\frac {1}{q_{n}^{2}}}.$

Адсюль, сярод іншага, вынікае:

• падыходны дроб ${\frac {p_{n}}{q_{n}}}$ з'яўляецца найлепшым прыбліжэннем для $x$ сярод усіх дробаў, назоўнік якіх не пераўзыходзіць $q_{n}$;
• мера ірацыянальнасці любога ірацыянальнага ліку не меншая чым 2.

Прыклады

• Раскладзём лік $\pi$=3,14159265… у непарыўны дроб і падлічым яго падыходныя дробы:

  3, 22/7, 333/106, 355/113, 103993/33102, …

Другі падыходны дроб 22/7 — гэта вядомае архімедава прыбліжэнне. Чацвёрты падыходны дроб 355/113 быў упершыю атрыман у Старажытным Кітаі.

• У тэорыі музыкі трэба адшукаць рацыянальнае прыбліжэнне для $\textstyle \log _{2}{\frac {3}{2}}\approx 0{,}585$. Трэці падыходны дроб 7/12 дазваляе абгрунтаваць класічнае дзяленне актавы на 12 паўтонаў.

Уласцівасці і прыклады

• Любы рацыянальны лік можна прадставіць у выглядзе канечнага непарыўнага дробу двума спосабамі, напрыклад:

$9/4=[2;3,1]=[2;4]\;$

• Тэарэма Лагранжа: Лік прадстаўляецца ў выглядзе бесканечнага перыядычнага ланцуговага дробу тады і толькі тады, калі ён з'яўляецца ірацыянальным рашэннем квадратнага ўраўнення з цэлымі каэфіцыентамі.

Напрыклад:

${\sqrt {2}}=[1;2,2,2,2,\dots ]$

залатое сячэнне $\phi =[1;1,1,1,\dots ]$

• Для алгебраічных лікаў ступені, большай за 2, характар раскладанняў у непарыўны дроб невядомы. Напрыклад, нават для ${\sqrt[{3}]{2}}$ невядома, ці канечная колькасць розных лікаў у яго раскладанні (паслядоўнасць A002945 у OEIS).
• Для некаторых трансцэндэнтных лікаў можна знайсці простую заканамернасць. Напрыклад, для асновы натуральнага лагарыфма:

$e-1=[1;1,2,1,1,4,1,1,6,1,1,8,\ldots ,1,1,2n-2,1,1,2n,\ldots ]$

для ліку

$\operatorname {tg} \,1=[1;1,1,3,1,5,1,7,\ldots ,1,2n+1,1,2n+3,\ldots ]$

• У ліку пі простай заканамернасці не відаць:

$\pi =[3;7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1,15,\dots ]$

• Тэарэма Гауса — Кузьміна: Амаль для ўсіх (акрамя мноства нулявой меры) рэчаісных лікаў існуе сярэдняе геаметрычнае каэфіцыентаў адпаведных ім ланцуговых дробаў, і яно роўнае пастаяннай Хінчына.
• Тэарэма Маршала Хола. Калі ў раскладанні ліку $x$ у непарыўны дроб, пачынаючы з другога элемента не сустракаюцца лікі, большыя за $n$, то кажуць, што лік $x$ адносіцца да класа $F(n)$. Любы рэчаісны лік можна прадставіць у выглядзе сумы двух лікаў з класа $F(4)$ і ў выглядзе здабытку двух лікаў з класа $F(4)$. У далейшым было паказана, што любы рэчаісны лік можна прадставіць сумаю трох лікаў з класа $F(3)$ і сумаю чатырох лікаў з класа $F(2)$. Колькасць неабходных складнікаў у гэтай тэарэме нельга паменшыць — для прадстаўлення некаторых лікаў названым спосабам меншай колькасці складнікаў недастаткова.

Прыкладанні непарыўных дробаў

Тэорыя календара

Пры распрацоўцы сонечнага календара неабходна знайсці рацыянальнае прыбліжэнне для ліку дзён у годзе, які роўны 365,2421988… Падлічым падыходныя дробы для дробнай часткі гэтага ліку:

${\frac {1}{4}};{\frac {7}{29}};{\frac {8}{33}};{\frac {31}{128}};{\frac {132}{545}}\cdots$

Першы дроб азначае, што раз у 4 гады трэба дабаўляць дадатковы дзень; гэты прынцып лёг у аснову юліянскага календара. Пры гэтым памылка ў 1 дзень набіраецца за 128 гадоў. Другое значэнне (7/29) ніколі не выкарыстоўвалася. Трэці дроб (8/33), г.зн. 8 высакосных гадоў за перыяд у 33 гады, быў прапанован Амарам Хаямам у XI ст. і даў пачатак персідскаму календару, у якім памылка ў дзень набіраецца за 4500 гадоў (у грыгарыянскім — за 3280 гадоў). Вельмі дакладны варыянт з чацвёртым дробам (31/128, памылка ў суткі набіраецца толькі за 100000 гадоў) прапагандаваў нямецкі астраном Іаган фон Медлер (1864), аднак вялікай цікавасці ён не выклікаў.

Рашэнне параўнанняў першай ступені

Разгледзім параўнанне:

$ax\equiv b{\pmod {m}},$

дзе $a,\ b$ зададзеныя, прычым можна лічыць, што $a$ узаемна простае з $m$. Трэба знайсці $x$.

Раскладзём ${\frac {m}{a}}$ у непарыўны дроб. Ён будзе канечны, і апошні падыходны дроб ${\frac {p_{n}}{q_{n}}}={\frac {m}{a}}$. Падставім у формулу (1):

$mq_{n-1}-ap_{n-1}=(-1)^{n-1}.$

Адсюль вынікае:

$ap_{n-1}\equiv (-1)^{n}{\pmod {m}}$,  ці:  $\ a(-1)^{n}p_{n-1}\equiv 1{\pmod {m}}.$

Вывад: клас вылікаў $x\equiv (-1)^{n}p_{n-1}b{\pmod {m}}$  ёсць рашэнне зыходнага параўнання.

Іншыя прыкладанні

• Доказ ірацыянальнасці лікаў. Напрыклад, з дапамогаю ланцуговых дробаў была даказана ірацыянальнасць значэння дзэта-функцыі Рымана $\zeta (3)$
• Рашэнне ў цэлых ліках ураўнення Пеля: $\;x^{2}-ny^{2}=1\;$ і іншых дыяфантавых ураўненняў.
• Вызначэнне заведама трансцэндэнтнага ліку (гл. тэарэма Ліувіля)
• Алгарытмы фактарызацыі SQUFOF і CFRAC.
• Характарыстыка артаганальных мнагачленаў
• Характарыстыка ўстойлівых мнагачленаў

Уласцівасці залатога сячэння

Гл. таксама: Залатое сячэнне

У непарыўным дробе залатога сячэння φ няма цэлых лікаў, большых за 1. Адсюль выцякае цікавы вынік: сярод рэчаісных лікаў лік φ — адзін з самых «цяжкіх» для прыбліжэння рацыянальнымі лікамі. Тэарэма Гурвіца сцвярджае, што любы рэчаісны лік x можна прыблізіць дробам m/n так, што

$\left|x-{m \over n}\right|<{1 \over n^{2}{\sqrt {5}}}.$

Хоць практычна ўсе рэчаісныя лікі x маюць бесканечна многа прыбліжэнняў m/n, значна бліжэйшых да x, чым гэта верхняя мяжа, прыбліжэнні для φ (г.зн. лікі 5/3, 8/5, 13/8, 21/13 і г. д.) на граніцы дасягаюць гэтай мяжы, утрымліваючы адлегласць амаль дакладна на ${\scriptstyle {1 \over n^{2}{\sqrt {5}}}}$ ад φ, тым самым ніколі не даючы такога добрага прыбліжэння як, напрыклад, 355/113 для π. Можна паказаць, што любы рэчаісны лік віду (a + bφ)/(c + dφ), дзе a, b, c і d — цэлыя лікі, такія што ad − bc = ±1, мае такую ж уласцівасць, як і залатое сячэнне φ; а таксама, што ўсе астатнія рэчаісныя лікі можна прыблізіць намнога лепш.

Гістарычная даведка

Антычныя матэматыкі ўмелі прадстаўляць адносіны несувымерных велічынь у выглядзе ланцужка падыходных адносін, атрымліваючы гэты ланцужок з дапамогаю алгарытма Еўкліда. Відаць, іменна такім спосабам Архімед атрымаў прыбліжэнне ${\sqrt {3}}\approx {\frac {1351}{780}}$ — гэта 12-ы падыходны дроб для ${\sqrt {3}}$ ці ${\frac {1}{3}}$ ад 4-га падыходнага дробу для ${\sqrt {27}}$.

У V стагоддзі індыйскі матэматык Арыябхата прымяняў падобны «метад здрабнення» для рашэння неазначальных ураўненняў першай і другой ступені. З дапамогаю гэтай жа тэхнікі было, мабыць, атрымана вядомае прыбліжэнне ліку $\pi$ (355/113). У XVI стагоддзі Рафаэль Бамбелі здабываў з дапамогаю ланцуговых дробаў квадратныя карані (гл. яго алгарытм).

Пачатак сучаснай тэорыі непарыўных дробаў даў у 1613 годзе П’етра Антоніа Катальдзі. Ён адзначыў іх асноўную ўласцівасць (гранічнае значэнне ляжыць паміж падыходнымі дробамі) і ўвёў абазначэнне, падобнае на сучаснае. Пазней яго тэорыю пашырыў Джон Валіс, які і прапанаваў тэрмін «непарыўны дроб». Раўназначны тэрмін «ланцуговы дроб» паявіўся ў канцы XVIII стагоддзя.

Прымяняліся гэтыя дробы найперш для рацыянальнага прыбліжэння рэчаісных лікаў; напрыклад, Хрысціян Гюйгенс выкарыстоўваў іх пры праектаванні зубчастых колаў свайго планетарыя. Гюйгенс ужо знаў, што падыходныя дробы заўсёды нескарачальныя і што яны даюць найлепшае рацыянальнае прыбліжэнне.

У XVIII стагоддзі тэорыю ланцуговых дробаў у агульных рысах завяршылі Леанард Эйлер і Жазеф Луі Лагранж.

Гл. таксама

• Алгарытм Еўкліда
• Лікі Фібаначы
• Абагульнены непарыўны дроб
• Перыядычны непарыўны дроб

Літаратура

• В. И. Арнольд. Цепные дроби. — М.: МЦНМО, 2000. — Т. 14. — 40 с. — (Библиотека «Математическое просвещение»).
• Н. М. Бескин Цепные дроби // Квант. — 1970. — Т. 1. — С. 16—26,62.
• Н. М. Бескин Бесконечные цепные дроби // Квант. — 1970. — Т. 8. — С. 10—20.
• Д. И. Боднар. Ветвящиеся цепные дроби. — К.: Наука, 1986. — 174 с.(недаступная спасылка)
• А. А. Бухштаб. Теория чисел. — М.: Просвещение, 1966. — 384 с.
• И. М. Виноградов. Основы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.
• С. Н. Гладковский. Анализ условно-периодических цепных дробей, ч. 1. — Незлобная, 2009. — 138 с.
• И. Я. Депман. История арифметики. Пособие для учителей. — Изд.второе. — М.: Просвещение, 1965. — С. 253—254. Архівавана 14 мая 2017.
• Г. Дэвенпорт. Высшая Арифметика. — М.: Наука, 1965.
• С. В. Сизый. Лекции по теории чисел. — Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999.
• В. Я. Скоробогатько. Теория ветвящихся цепных дробей и ее применение в вычислительной математике. — М.: Наука, 1983. — 312 с.
• А. Я. Хинчин. Цепные дроби. — М.: ГИФМЛ, 1960. Архівавана 2 лістапада 2021.