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

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

${\displaystyle [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 — натуральныя лікі (дадатныя цэлыя).

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

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

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

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

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

${\displaystyle \dots }$

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

${\displaystyle \dots }$

дзе ${\displaystyle \lfloor x\rfloor }$ абазначае цэлую частку  (руск.) ліку ${\displaystyle x}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прыклады

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

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

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

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

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

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

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

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

Напрыклад:

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

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

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

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

для ліку

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

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

${\displaystyle \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 ]}$

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

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

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

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

${\displaystyle {\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), аднак вялікай цікавасці ён не выклікаў.

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

Разгледзім параўнанне  (руск.):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Гл. таксама

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