Преглед на кода на Верижна дроб

'''Верижна дроб''' или '''продължаваща дроб''' в [[математика]]та в общия случай означава израз от вида
:<math>x = a_0 + \cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{a_3 + \cfrac{b_3}{\ddots\,}}}},</math> или в обикновения случай при <math>b_i=1</math> <math>x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots\,}}}},</math>

където <math>a_0</math> е [[цяло число]] <math>a_0 \in \Z</math>, а останалите <math>a_i</math> и <math>b_i</math> са положителни цели числа <math>a_i, b_i \in \N</math> за <math>i \in \N</math>. Числата <math>a_0, a_1, a_2, a_3,\cdots</math> и <math>b_0, b_1, b_2, b_3,\cdots</math> се наричат елементи на верижната дроб.<ref name="wolfram">[http://mathworld.wolfram.com/ContinuedFraction.html Regular Continued Fraction], Wolfram Mathematics.</ref> Дробите <math>\tfrac{b_i}{a_i}</math> и <math>\tfrac{1}{a_i}</math> се наричат частични дроби, <math>b_{i}</math> се нарича <math>i</math>-ти частичен числител и <math>a_{i}</math> се нарича <math>i</math>-ти частичен знаменател.<ref>В част от литературата <math>a_i</math> и <math>b_i</math> често се разменят, така че частичните знаменатели са <math>b_i</math>.</ref> Частичните числители и частичните знаменатели също се наричат елементи на продължаващата дроб (след [[Оскар Перон]], [[1975]]).<ref>{{Literatur |Autor=Oskar Perron |Titel=Die Lehre von den Kettenbrüchen. Band I: Elementare Kettenbrüche |Verlag=Wissenschaftliche Buchgesellschaft |Ort=Darmstadt |Datum=1977 |Seiten=1}}</ref>

Всяко [[реално число]] може да бъде представено във вид на верижна дроб (крайна или безкрайна). Числото представлява крайна верижна дроб [[тогава и само тогава, когато]] то е [[Рационално число|рационално]]. Безкрайната верижна дроб се нарича още '''непрекъсната дроб'''. 

Главната (но не единствена) полза от верижните дроби се състои в това, че те позволяват да се намерят добри приближения на реални числа във вид на обикновени [[Дроб (математика)|дроби]].<ref name="wolfram" /> Верижните дроби се използват широко в [[Теория на числата|теорията на числата]] и [[изчислителна математика|изчислителната математика]]. Използват се също така във [[физика]]та, [[Небесна механика|небесната механика]], техниката и други сфери.
нотация

== Обозначаване ==
=== Нотации ===
Използват се различни нотации за обозначаване на верижни дроби.

Съкратеното обозначаване на обща верижна дроб е
:<math>a_{0}+{\frac {b_{1}|}{|a_{1}}}+{\frac {b_{2}|}{|a_{2}}}+ {\frac {b_{3}|}{|a_{3}}}+\cdots</math>

Въз основа на символите за сума <math>\sum</math> и произведение <math>\textstyle \prod</math>, [[Гаус]] също въвежда следната нотация за това:
:<math>a_{0}+{\underset {i=1}{\overset {\infty }{\mathbf {K} }}}{\frac {b_{i}}{a_{i}}}\, .</math>

Правилната верижна дроб често се записва по следния начин: <ref>Освен посочените тук изписвания има и <math>a_0+\tfrac{1}{a_1+{}} \tfrac{1}{a_2+{}} \tfrac{1}{a_3+{}}\cdots</math> (например в „''John Horton Conway, Richard Kenneth Guy'' – The book of numbers. Springer, 1996“), <math>\langle a_0, a_1, a_2, a_3, \dotsc \rangle</math> (z.&nbsp;B. im Buch von Niven/Zuckerman) както и <math>a_0 + /\!/a_1, a_2, a_3, \dotsc/\!/</math> (z.&nbsp;B. в „''Donald Knuth'' – The Art of Computer Programming. (Band 2), Addison-Wesley, 1997“).</ref>
:<math>[a_{0};a_{1},a_{2},\dotsc ],</math>

тук само <math>a_{0}</math> е посочен отделно, защото е от <math>\mathbb {Z}</math>, но следващите <math>a_{i}</math> са винаги само от <math>\mathbb {N}</math>.

Обозначаването на крайни непрекъснати дроби е съответно

:<math>a_{0}+{\frac {b_{1}|}{|a_{1}}}+{\frac {b_{2}|}{|a_{2}}}+\cdots +{ \frac {b_{n}|}{|a_{n}}}\,,\quad a_{0}+{\underset {i=1}{\overset {n}{\mathbf {K} }}} {\frac {b_{i}}{a_{i}}}\,,\quad [a_{0};a_{1},\dotsc ,a_{n}]\,.</math>

=== Представяне като композиция от образи ===
Продължаващата дроб може също да се представи като композиция от образи <math>T_{i}\colon \mathbb {R} \to \mathbb {R}</math>. Това дава по-формално определение от даденото по-рано.

За да се направи това, задава се <math>T_{i}(x)={\tfrac {b_{i}}{a_{i}+x}}</math> и се взема
:<math>a_{0}+{\underset {i=1}{\overset {n}{\mathbf {K} }}}{\frac {b_{i}}{a_{i}}}: = a_ {0} + T_{1}\circ T_{2}\circ \cdots \circ T_{n-1}\circ T_{n}(0).</math>

Дефиницията на безкрайни последователни дроби се прави чрез разглеждане на [[Граница на редица|граничните стойности]] в раздела [[Верижна дроб#Безкрайни последователни дроби|Безкрайни последователни дроби]].

== Образуване ==
Верижната дроб се образува чрез [[Итерация|итеративен]] процес на представяне на число като сбор от неговата цяла част и [[реципрочна стойност]] на друго число, след което записването на това друго число като сума от неговата цяла част и друга реципрочна стойност, и така нататък.{{sfn|Encyclopaedia Britannica|2013}} В крайна верижна дроб (или прекратена продължителна дроб) [[итерация]]та/[[рекурсия]]та се прекратява след ограничен брой стъпки чрез използване на цяло число вместо друга верижна дроб. При безкрайната верижна дроб този процес продължава и тя е безкраен израз. И в двата случая всички цели числа в редицата, различни от първото, трябва да са положителни.{{sfn|Pettofrezzo|Byrkit|1970|p=150}}

Всяко реално число <math>x</math> може да бъде представено чрез (крайна или безкрайна, периодична или непериодична) верижна дроб <math>[a_0; a_1, a_2, a_3,\ldots]</math>, където
:<math>a_0 = \lfloor x \rfloor,\quad x_0 = x - a_0,</math>
:<math>a_1 = \left\lfloor \frac{1}{x_0} \right\rfloor,\quad x_1 = \frac{1}{x_0} - a_1, </math>
:<math>\dots</math>
:<math>a_n = \left\lfloor \frac{1}{x_{n-1}} \right\rfloor,\quad x_n = \frac{1}{x_{n-1}} - a_n,</math>
:<math>\dots</math>

[[Функция скобка|долните скобки]] <math>\lfloor x \rfloor</math> обозначават цялата част на числото <math>x</math>.

За рационално число <math>x</math> това разширение завършва, когато <math>x_{n}</math> достигне [[нула]] за някои <math>n</math>. В този случай <math>x</math> е представено от крайна продължителна дроб <math>x=[a_{0};a_{1},\ldots ,a_{n}]</math>. Един ефективен алгоритъм за преобразуване на обикновена дроб в непрекъсната дроб е [[Алгоритъм на Евклид|алгоритъмът на Евклид]]. Представянето на рационално число като непрекъсната дроб е двусмислено: ако алгоритъмът, даден тук, дава непрекъснатата дроб <math>[\dots ,a_{n}]</math>, тогава верижната дроб <math>[\dots ,a_{n}-1,1]</math> съответства на същото число.

Като пример се разглежда рационалното число 415/93, което е около 4,4624. Като първо приближение се започва с 4, което е цяло число; 415/93 = 4 + 43/93. Дробната част е реципрочната на 93/43, което е около 2,1628. Използва се цялата част 2 като приближение за реципрочната стойност, за да се получи второ приближение на 4 + 1/2 = 4,5. Сега 93/43 = 2 + 7/43; останалата дробна част 7/43 е реципрочната стойност на 43/7, а 43/7 е около 6,1429. Използва се 6 като приближение за да се получи 2 + 1/6 като приближение за 93/43 и {{nowrap|4 + {{sfrac|1|2 + {{sfrac|1|6}}}}}}, около 4,4615, като трето приближение. Освен това, 43/7 = 6 + 1/7. И накрая, дробната част, 1/7, е реципрочната на 7, така че нейното приближение в тази схема 7 е точно (7/1 = 7 + 0/1) и дава точния израз {{nowrap|4 + {{sfrac|1|2 + {{sfrac|1|6 + {{sfrac|1|7}}}}}}}} за 415/93.

== Подходящи дроби ==
<math>n</math>-та '''подходяща дроб''' за верижната дроб <math>x=[a_{0};a_{1},a_{2},a_{3},\ldots ]</math> се нарича крайна продължителна дроб <math>[a_{0};a_{1},\ldots ,a_{n}]</math>, чиято стойност е някакво рационално число <math>p_{n}/ q_{ n}</math>. Подходящите дроби с четни номера образуват нарастваща последователност, чиято граница е <math>x</math>. По същия начин подходящите дроби с нечетни номера образуват намаляваща последователност, чиято граница също е <math>x</math>. По този начин стойността на верижната дроб винаги е между стойностите на съседни подходящи дроби.

[[Ойлер]] е извел следните рекурентни формули за изчисляване на числителите и знаменателите на подходящи дроби:
:<math>p_{-1}=1,\quad p_{0}=a_{0},\quad p_{n}=a_{n}p_{n-1}+p_{n-2};</math>
:<math>q_{-1}=0,\quad q_{0}=1,\quad q_{n}=a_{n}q_{n-1}+q_{n-2}.</math>

По този начин величините <math>p_{n}</math> и <math>q_{n}</math> са многочлени от <math>a_{0},a_{1},\dots ,a_{n}</math>, наречени '''[[Континуанта|континуанти]]'''<ref>Континуанта е определен многочлен от няколко променливи, свързани с верижни дроби.</ref>:
:<math>p_{n}=K_{n+1}(a_{0},a_{1},\dots ,a_{n}),</math>
:<math>q_n = K_n(a_1, a_2, \dots, a_n).</math>

Последователностите както на числителите <math>\{p_{n}\}</math>, така и на знаменателите <math>\{q_{n}\}</math> на подходящи дроби са строго нарастващи.

Числителите и знаменателите на съседни подходящи дроби са свързани с отношението
[[Файл:Golden ration convergents.svg|300п|мини|Подходящи дроби за [[Златно сечение|златното сечение]]]]
{{NumBlk|:|<math>p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}.</math>|1|LnSty=none}}

От тук се вижда, че подходящите дроби винаги са несъкратими. Разделя се равенство (1) на <math>q_{n-1}q_{n}</math> и то добива вида
:<math>{\frac {p_{n}}{q_{n}}}-{\frac {p_{n-1}}{q_{n-1}}}={\frac {(-1)^ {n-1}}{q_{n-1}q_{n}}}.</math>

От това следва, че {{sfn |Виноградов|1952|с=18}}
:<math>\left|x - \frac{p_{n-1}}{q_{n-1}}\right| < \frac{1}{q_{n-1}q_n} < \frac{1}{q_{n-1}^2}.</math>

Изображението показва как подходящи дроби за златното сечение се доближават до него с увеличаване на номера на дробта. Дробите с нечетни номера се доближават до златното сечение отгоре, дробите с четни номера се доближават до него отдолу.

== Източници и бележки ==
<references />

[[Категория:Дроби]]
[[Категория:Математически анализ]]
[[Категория:Теория на числата]]