Мои впечатления о книге "Золотое сечение" Марио Ливио. Часть IV

См. также
Мои впечатления о книге "Золотое сечение" Марио Ливио. Часть I
Часть II. Алгебраические свойства золотого сечения.
Часть III. Числа Фибоначчи и золоте сечение.
Часть IV. Цепные дроби и золоте сечение.
Часть V. Фрактальная геометрия и золоте сечение.
Часть VI. Закон Бенфорда, или закон первой цифры.
Часть VII. Золотое сечение в природе.


Цепные дроби и золоте сечение.
Те, кому эта часть неинтересна могут спокойно её пропустить.

Т.к. тема цепных дробей находится глубоко в теории чисел, я буду цитировать многие утверждения с Википедии на русском без доказательства.

Итак, вкратце повторю известные нам уже факты.

Ниже есть продолжение.

Вспомним определение, золотого сечения. Меньшая часть так относится к большей, как большая ко всей величине. Это в свою очередь приводит нас к уравнению

$\phi^2-\phi-1=0$ (*)

Положительный корень которого и есть число $\phi$, золотое сечение. Численное значение

$\phi=\frac{1+ \sqrt{5} }{2} \approx 1,6180339887$

Сопряжённое с ${\phi}$ число равняется $-\frac{1}{\phi}$ и оно равняется $\frac{1-\sqrt{5}}{2}$.

Далее, мы доказали, что $\phi=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}}$ (**). При этом я обещал привести ещё один способ доказательства используя числа Фибоначчи. Также мы доказали, что $\phi$ иррационально, при этом я обещал привести ещё один способ доказательства этого факта используя цепные дроби.

Начнём с того, зачем нужны цепные дроби, они же непрерывные дроби.

Непрерывные дроби являются самыми "математически естественными" представлениями вещественных чисел.

Большинство людей знакомы с десятичным представлением вещественных чисел, которое может быть определено как

$r = \sum_{i=0}^\infty a_i 10^{-i}$

где a₀ может быть любым целым числом а последующие a_i являются одним из элементом {0,1,2,…,9}. В этом представление, число π, к примеру, может быть представлено как последовательность целых чисел (ai) = (3,1,4,1,5,9,2,…).

Это десятичное представление имеет несколько проблем. Одна из них, многие рациональные числа не имеет конечного представления в этой системе. Например, число 1/3 представимо бесконечной последовательностью (0,3,3,3,3,…). Другая проблема заключается в том, что константа 10 является по-сути произвольным выбором, которая оказывает предрасположение числам, которые как-либо относятся к целому числу 10. Например, 137/1600 имеет конечное десятичное представление, тогда как 1/3 не имеет, не потому что 137/1600 проще чем 1/3, а всего лишь потому что 1600 делить степень 10 (10⁶ = 1600 × 625). Запись как цепная дробь является представлением вещественных чисел, которая не имеет этих проблем.

Давайте рассмотрим как мы можем описать число, такое как 415/93, которое примерно равняется 4,4624. Это примерно 4.Вообще-то это чуть больше чем 4, около 4 + 1/2. Но 2 в знаменателе не совсем точно; там должно быть число чуть больше чем 2, примерно 2 + 1/6. Таким образом, 415/93 примерно равняется 4 + 1/(2 + 1/6). Но 6 в знаменателе не верно; настоящее значение чуть больше 6, 6+1/7. Таким образом, 415/93 является 4+1/(2+1/(6+1/7). Это точное значение.

Опуская некоторые обязательные части в выражении 4 + 1 / (2 + 1 / (6 + 1 / 7)) мы получим краткую нотацию [4;2,6,7]. (Заметьте, что общепринято заменять только первую запятую точной с запятой).

Это была мотивация введения этого понятия. Перед тем, как я перечислю (без доказательств) свойства цепных дробей я дам формальное определение и несколько примеров для вычисления цепной дроби.

Определение. Цепная дробь (или непрерывная дробь) — это математическое выражение вида

$[a_0; a_1, a_2, a_3,\cdots] = a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\ldots}}}\;$

где a₀ есть целое число и все остальные a_n натуральные числа (то есть неотрицательные целые).

Продемонстрирую как любое действительное число может быть представлено в виде цепной дроби $[a_0; a_1, a_2, a_3,\cdots]$ на примере разложения числа π.

$a_0 = \lfloor π \rfloor = 3, x_0 = π - a_0 = π - 3$

$a_1 = \left\lfloor \frac{1}{x_0} \right\rfloor = \left\lfloor \frac{1}{π - 3} \right\rfloor = 7, x_1 = \frac{1}{x_0} - a_1 = \frac{1}{π - 3} - 7 $

$a_2 = \left\lfloor \frac{1}{x_1} \right\rfloor = \left\lfloor \frac{1}{\frac{1}{π - 3} - 7} \right\rfloor = 15, x_2 = \frac{1}{x_1} - a_2 = \frac{1}{ \frac{1}{π - 3} - 7} - 15 $
...
$a_n = \left\lfloor \frac{1}{x_{n-1}} \right\rfloor, x_n = \frac{1}{x_{n-1}} - a_n$
...
где $\lfloor x \rfloor$ обозначает целую часть числа x.

Продолжаю процедуру таким образом, получим
$\pi=[3;7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,...]$

или

$\pi=3+\frac{1}{7+\frac{1}{15+\frac{1}{1+\frac{1}{292+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{2+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{14+\frac{1}{2+\frac{1}{1+\frac{1}{1+...}}}}}}}}}}}}}}}$

Словесное описание превращения 415/93 в цепную дробь приведённое выше по сути следует этому рецепту.

Перед тем как продолжить, я, очевидно, должен объяснить как это всё связано с золотым сечением. Помните, равенство (**) $\phi=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}}$? По определению цепной дроби, из (**) следует, что $\phi=[1;1,1,1,1,1,1,...]$. Т.е. сами того не ведая мы разложили $\phi$ в цепную дробь (я помню, что я обещал привести ещё один способ доказательства используя числа Фибоначчи).

Давайте, для тренировки, разложим число $\phi$ в цепную дробь используя вышеприведённый алгоритм. Напомню, что
(*) $\phi^2-\phi-1=0$, откуда $\phi^2-\phi=1$, откуда $\phi(\phi-1)=1$ или

$\frac{1}{\phi - 1} = \phi$ (***)

Итак,

$a_0 = \lfloor \phi \rfloor = 1, x_0 = \phi - a_0 = \phi-1

$a_1 = \left\lfloor \frac{1}{x_0} \right\rfloor = \left\lfloor \frac{1}{\phi - 1} \right\rfloor = $
используя (***)
$=\left\lfloor \phi \right\rfloor=a_0=1, x_1= \frac{1}{x_0} - a_1 = \frac{1}{\phi-1} - 1 = $
используя (***)
$=\phi-1=a_0$
т.е. $1=a_1=a_0$, $\phi-1=a_1=a_0$

Отсюда не трудно показать, что для любого n верно
$1=a_n=a_0$, $\phi-1=a_n=a_0$

Таким образом, $a_0=a_1=a_2=...=a_n=...=1$, т.е. $\phi=[1;1,1,1,...]$


Вернёмся к цепным дробям. Для рациональных чисел, существует более простой и намного более простой алгоритм разложения в цепную дробь. Он основан на алгоритме Евклида. Приведу пример его использования на примере превращения 415/93 в цепную дробь. Найдём gcd(415, 93) с помощью алгоритме Евклида.

(1) $415=4*93+43$
(2) $93=2*43+7$
(3) $43=6*7+1$
(4) $7=7*1+0$

Отсюда gcd(415, 93)=1, т.е. это взаимно-простые числа. Но нас интересует не это. Мы можем переписать эти равенства в следующей форме.

Равенство (1) разделим на 93, тогда получим

(1') $\frac{415}{93}=4+\frac{43}{93}$.

Равенство (2) разделим на 43, тогда получим

(2') $\frac{93}{43}=2+\frac{7}{43}$

Теперь необходимо заметить, что крайне правая дробь в равенстве (1') является обратной дробью крайне левой дроби в равенство (2'), т.е. $\frac{43}{93}=\frac{1}{\frac{43}{93}}$. Это не случайность, это верно по построению. В двух словах отмечу, это следствие того, что gcd(415, 93)=gcd(93, 43) и gcd(0,1) = 1. Подробности см. http://ru.wikipedia.org/wiki/Алгоритм Евклида#Алгоритм Евклида для целых чисел а также подраздел "Связь с цепными дробями" там же.

Таким образом из (1') следует $\frac{415}{93}=4+\frac{43}{93}=4+\frac{1}{\frac{93}{43}}=$
используя (2') получаем
$=4+\frac{1}{2+\frac{7}{43}}$
т.е.
(2'') $\frac{415}{93}=4+\frac{1}{2+\frac{7}{43}}$

Равенство (3) разделим на 7, тогда получим
(3') $\frac{43}{7}=6+\frac{1}{7}$
Комбинируя (2'') и (3') получим

$\frac{415}{93}=4+\frac{1}{2+\frac{7}{43}}=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}$
или
(3'') $\frac{415}{93}=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}$

Равенство (4) разделим на 1 (привожу этот шаг, для тех случаев, когда $gcd \neq 1$, т.е. здесь не стоит 1), тогда получим

(4') $\frac{7}{1}=7$

Комбинируя (3'') и (4') получим

$\frac{415}{93}=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}=4+\frac{1}{2+\frac{1}{6+\frac{1}{\frac{1}{7}}}}$=
$=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}$
т.е.

$\frac{415}{93}=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}$ или

$\frac{415}{93}=[4;2,6,7].

Продолжим рассматривать общие свойства цепных дробей.

Определение. n-ой подходящей дробью для цепной дроби $x=[a_0; a_1, a_2, a_3,\cdots]$, называется конечная цепная дробь $[a_0; a_1, \cdots, a_n]$ значение которой равно некоторому рациональному числу $\frac{p_n}{q_n}$.

В самом деле если написать конечную цепную дробь, достаточно конечное количество раз привести к общему знаменателю, постепенно сокращая количество "этажей", чтобы в итоге получить обычную дробь, которая и будет записью некоторого рационального числа.

В чём логика введение такого определения? Интуитивно, точно так же как в десятичном представление действительного числа, любое конечное представление числа является некоторым приближение действительного числа.

Давайте сначала я поясню, что я имею в виду для десятичных чисел. Рассмотрим число $\frac{1}{3}$. Оно в точности равняется $0,(3)=0,33333...$ Однако, это бесконечная запись числа. Можно использовать приближение этого числа, допустим взяв два знака после запятой. Число $0,33$ является приближением числа $\frac{1}{3}$. Во сколько улучшиться наше приближение, если мы вместо 2 возьмём 3 знака после запятой, т.е. возьмём $0,333$? Ответ, в 10 раз. Однако, какое бы конечное количество знаков после запятой мы не брали, мы получим лишь приближение.

Можно найти посмотреть и по-другому. $1/3=0,(3)=0,33333...$. Если мы "обрубим" наше число на 2 знаке после запятой, мы получим погрешность в $0,01=10^{-2}$. Если мы "обрубим" наше число на 3 знаке после запятой, погрешность будет $0,001=10^{-3}$, т.е. уменьшиться в 10 раз.

Определение n-ой подходящей дробью дана выше, это такое же "огрубление" бесконечного представления нашего числа. Что будет происходит при этом с погрешностью?

Опуская подробности может быть доказано следующее. Если действительное число x разложить в цепную дробь, то её подходящие дроби будут удовлетворять неравенству

$\left|x - \frac{p_n}{q_n}\right| < \frac{1}{q_n^2}$

Отсюда, в частности, следует:

подходящая дробь $\frac{p_n}{q_n}$ является наилучшим приближением для x среди всех дробей, знаменатель которых не превосходит $q_n$;

Более того, при помощи подходящих дробей могут быть получены все лучшие рациональные приближения числа x. Cм. http://en.wikipedia.org/wiki/Continued_fraction#Best%20rational%20approximations

Таким образом, цепная дробь сходится к число x самым быстрым возможным способом, используя рациональные числа, т.е. погрешность представления уменьшается само быстро из всех таких представлений. Чуть ниже я вернусь к этому моменту.

Какие ещё желательные свойства есть у цепной дроби?

* Представление как непрерывная дробь конечно тогда и только тогда когда число является рациональным.

* Каждое рациональное число имеет по-существу единственное представление как непрерывная дробь. Каждое рациональное число можно представить в точности двумя способами, т.к. [a₀; a₁, … a_n − 1, a_n] = [a₀; a₁, … a_n − 1, a_n − 1, 1]. Математики предпочитают иметь взаимно-однозначное соответствие между рациональными числами и цепными дробями; первая, более короткая нотация выбрана в качество каноническое представления.

* Представление как непрерывная дробь иррационального числа единственно.

* Цепная дробь является периодической тогда и только тогда, когда число является квадратичной иррациональностью, т.е. имеет форму

$\frac{a+b\sqrt{c}}{d}$

для целых a, b, c, d; где b и d не ноль и c>1 и ''c'' не является точным квадратом.

К примеру, периодическая непрерывная дробь [1; 1, 1, 1, ...] является золотым сечением, а периодическая непрерывная дробь [1; 2, 2, 2, ...] является квадратным корнем из 2.

* Раннее усечение представления числа x в виде цепной дроби приводит к рациональному приближению x, которая в определенном смысле является "наилучшим" рациональным приближением.

Последнее свойство чрезвычайно важно. У десятичного представления числа его нет. Усечение десятичного представления числа приводит к рациональному приближению числа, но обычно к не очень хорошему приближению. К примеру, усечение 1/7 = 0.142857... в разных местах приводит к приближениям таким как 142/1000, 14/100 и 1/10. Но очевидно лучшим рациональным приближением будет само число "1/7". Обрывая десятичное представление π мы получаем приближения такие как 31415/10000 и 314/100. Цепная дробь π начинается [3; 7, 15, 1, 292, ...]. Усекая это представление мы получаем отличные рациональные приближение 3, 22/7, 333/106, 355/113, 103993/33102, .... Знаменатели 314/100 и 333/106 почти одинаковые, но ошибка в приближении 314/100 в девятнадцать раз больше ошибки, чем в приближении 333/106. Как приближении π, [3; 7, 15, 1] более чем в сто раз точнее приближения 3,1416.

Вернёмся к золотому сечению. Как было доказано, $\phi=[1;1, 1, 1,...]$. Мы имеем бесконечную (чисто)периодическую дробь. Из того, что это представление бесконечно, следует, что $\phi$ иррационально (это обещанное доказательство иррациональности $\phi$). Из периодичности следует, что это число является квадратичной иррациональностью (см. также выше), но это мы итак знаем, т.к. $\phi=\frac{1+ \sqrt{5}}{2}.

Мне осталось показать связь золотого сечения, цепных дробей, точнее n-ой подходящей дробью, и чисел Фибоначчи.

Итак, $\phi=[1;1, 1, 1,...]$. Давайте посчитаем его подходящие дроби.

Непосредственно из определения следует,

$[1,1,..,1]$={всего n единиц}=$1+\frac{1}{[1,...1]}$={всего (n-1) единиц} (10)

где в левой части есть n единиц в записи цепной дроби, а в правой (n-1) единиц в записи цепной дроби (формально доказывается при помощи индукции по n).


1-ая подходящая дробь $[1]=1$.
2-ая подходящая дробь $[1, 1]=1+\frac{1}{[1]}=1+1=2=\frac{2}{1}$
3-ая подходящая дробь $[1, 1, 1]=1+\frac{1}{[1, 1]}=1+\frac{1}{2}=\frac{2+1}{2}=\frac{3}{2}$
4-ая подходящая дробь $[1, 1, 1, 1]=1+[1,1]=$
$=1+\frac{1}{\frac{3}{2}}=1+\frac{2}{3}=\frac{2+3}{3}=\frac{5}{3}$
...

Никакой связи с числами Фибоначчи не заметили?

Хорошо, тогда небольшая немного обрезанная цитата с прошлой части:

Достаём из шляпы число $\phi$. Давайте, найдём отношения числа Фибоначчи $F_(n+1)$ к предыдущему числу и посмотрим, что получится (это было проделано в книге).

$\frac{F_2}{F_1}=\frac{1}{1}=1$

$\frac{F_3}{F_2}=\frac{2}{1}=2$

$\frac{F_4}{F_3}=\frac{3}{2}$

$\frac{F_5}{F_4}=\frac{5}{3}$

...

$\lim_{n\to\infty}\frac{F(n+1)}{F(n)}=\phi$ (*****)

http://alexsmail.blogspot.com/2010/12/iii.html

Легко видеть, что:

1-ая подходящая дробь $[1]=1=\frac{F_2}{F_1}$.
2-ая подходящая дробь $[1, 1]=1+1=\frac{2}{1}=\frac{F_3}{F_2}$
3-ая подходящая дробь $[1, 1, 1]=\frac{2+1}{2}=\frac{3}{2}=\frac{F_4}{F_3}$
4-ая подходящая дробь $[1, 1, 1, 1]=\frac{2+3}{3}=\frac{5}{3}=\frac{F_5}{F_4}$
...

Обратите внимание на сложение, которое происходит после первого знака равенства. Т.к. 1-ая подходящая равняется 1, 2-ая подходящая дробь равняется 2, а затем для того чтобы получить n-ую подходящую дробь определяется так, её знаменатель есть числитель (n-1) подходящей дроби, а числитель равняется сумме числителя и знаменателя (n-1) подходящей дроби. Используя индукцию и равенство (10) нетрудно убедиться, что n-ая подходящая дробь является в точности $\frac{F_{n+1}}{F_n}$. Так как подходящие дроби стремятся к цепной дроби, из это следует, что
$\lim_{n\to\infty}\frac{F(n+1)}{F(n)}=\phi$. Это и есть последнее обещанное доказательство.

Однако, теперь мы знаем, что этот предел $\lim_{n\to\infty}\frac{F(n+1)}{F(n)}=\phi$ сходится чрезвычайно быстро, ведь каждый его член задаёт соответствующую подходящею дробь.

Таким образом, числа Фибоначчи задают лучшее, в описанном выше смысле, приближение для $\phi$. Этого мы раньше не видели.

UPDATE:
Верно, что все подходящие дробь задаёт лучшее, в описанном выше смысле, приближение для $\phi$. В общем случае, чтобы получить все такие лучшие приближения, нужно добавлять, по определённому алгоритму ещё (конечные) цепные дроби, т.е. в общем случае, это не все лучшие, в описанном выше смысле, приближения. Однако, из-за того в разложении $\phi$ есть исключительно единицы, такой добавки не происходит. Таким обраpом, числа Фибоначчи задают все лучшее, в описанном выше смысле, приближение для $\phi$.
END OF UPDATE


Напоследок, ещё одна цитата:

Интересный результат, которые следует из того факта, что выражение непрерывной дроби для φ не использует целых чисел больше чем 1, состоит в том, что φ является одним из самых "трудных" действительных чисел для приближения с помощью рациональных чисел. Одна теорема утверждает, что любое действительное число k может быть приближено дробью m/n при помощи

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

Тогда когда практически все действительные числа k имеют в конечно счёте бесконечно много приближений m/n, которые находятся на значительно меньшем расстояние от k, чем этот предел, приближения для φ (т.е. числа 5/3, 8/5, 13/8, 21/13, и т.д.) последовательно "касаются границы", удерживая расстояние на почти точно $\frac{1}{n^2 \sqrt{5}$ расстоянии от φ, тем самым никогда не создавая приближения столь же внушительные как, к примеру, 55/113 для φ. Может быть показано что любое действительное число формы (a + bφ)/(c + dφ) – где a, b, c и d являются целыми числами, такими как ad − bc = ±1 – имеют такое же свойство как и золотое сечение φ; а также, что все остальные действительные числа могут быть приближены намного лучше.

В описанном выше смысле, число φ является "самым иррациональным из всех иррациональных". Интуитивно это можно понять следующим образом. Любое действительное число можно представить в виде $[a_0; a_1, a_2, a_3,\cdots]$. При этом $a_1=a_2=...a_n=...\ge 1$. Эта запись сходится чрезвычайно быстро. Очевидно, если два числа, скажем, $[a_0; a_1, a_2, a_3,\cdots]$ и $[b_0; b_1, b_2, b_3,\cdots]$ отличаются только в одном месте, скажем i,i>0, то число у которого в том месте число больше будет сходится "быстрее". Т.е. если $a_i>b_i$, то первое число будет сходится быстрее, если же $b_i>a_i$, то второе число будет сходится быстрее. Т.к. $a_i \ge 1$ натуральное число, то если для всех i, будет стоят 1, это будет число которое будет сходится "медленнее" всех.



Текстовое содержимое доступно в соответствии с лицензией Creative Commons Attributions-ShareAlike (CC-BY-SA), http://creativecommons.org/licenses/by-sa/3.0/. Источники: Википедия http://ru.wikipedia.org/wiki/Непрерывная дробь. Авторы: http://ru.wikipedia.org/w/index.php?title=Непрерывная дробь&action=history, http://ru.wikipedia.org/wiki/Алгоритм Евклида. Авторы: http://ru.wikipedia.org/w/index.php?title=Алгоритм Евклида&action=history

Продолжение следует.