числа фибоначчи (математическое)
Jan. 19th, 2012 06:36 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЯ не помню, где я впервые увидел формулу для n-го числа Фибоначчи
Думаю, это было в одной из книг Мартина Гарднера. Помню, что она потрясла мое воображение, и я не мог понять, "откуда они знают", что в таких высоких степенях иррациональных чисел вся иррациональность в итоге сбрасывается, и получается натуральное число. Я поверил в это, но доказательство этого казалось совершенно недостижимым, какой-то магией. Я не понимал, что нужно знать, чтобы уметь такое найти.
И как-то получилось, что я этого доказательства так и не видел ни разу, и остался - не задумываясь об этом всерьез - при своем впечатлении, что это "очень сложно".
Поэтому меня совершенно ошеломило увиденное случайно вчера элементарное доказательство этой формулы методами линейной алгебры. Я понимаю, что тем, кто не учил линейную алгебру в университете, это никак не поможет, но поверьте мне тогда на слово - это очень простая математика, самый первый шаг после школьной, самое простое, что можно назвать "высшей математикой". Подробное доказательство (по-английски) есть здесь. Золотое сечение (число φ = (√5+1)/2) возникает в нем при подсчете собственных значений элементарной матрицы 2x2 из единичек и нулей.
Раз уж зашла речь о числах Фибоначчи, поделюсь еще чем-то, что узнал о них пару лет назад - не помню, писал ли тут. Многие знают, что последовательность Фибоначчи, а также число φ, золотое сечение, встречаются в природе в множестве разных процессов, а заодно и в античном искусстве и архитектуре. Так вот, почти все утверждения такого рода неверны - это очень распостраненный миф, который почти всегда оказывается неточной подгонкой под желаемый результат (необязательно осознанной, конечно). Подробная и очень интересная статья об этом, опять-таки по-английски: Fibonacci Flim-Flam. Еще одна статья на ту же тему, менее подробная и в основном о золотом сечении: The Myth That Will Not Go Away.
Думаю, это было в одной из книг Мартина Гарднера. Помню, что она потрясла мое воображение, и я не мог понять, "откуда они знают", что в таких высоких степенях иррациональных чисел вся иррациональность в итоге сбрасывается, и получается натуральное число. Я поверил в это, но доказательство этого казалось совершенно недостижимым, какой-то магией. Я не понимал, что нужно знать, чтобы уметь такое найти.
И как-то получилось, что я этого доказательства так и не видел ни разу, и остался - не задумываясь об этом всерьез - при своем впечатлении, что это "очень сложно".
Поэтому меня совершенно ошеломило увиденное случайно вчера элементарное доказательство этой формулы методами линейной алгебры. Я понимаю, что тем, кто не учил линейную алгебру в университете, это никак не поможет, но поверьте мне тогда на слово - это очень простая математика, самый первый шаг после школьной, самое простое, что можно назвать "высшей математикой". Подробное доказательство (по-английски) есть здесь. Золотое сечение (число φ = (√5+1)/2) возникает в нем при подсчете собственных значений элементарной матрицы 2x2 из единичек и нулей.
Раз уж зашла речь о числах Фибоначчи, поделюсь еще чем-то, что узнал о них пару лет назад - не помню, писал ли тут. Многие знают, что последовательность Фибоначчи, а также число φ, золотое сечение, встречаются в природе в множестве разных процессов, а заодно и в античном искусстве и архитектуре. Так вот, почти все утверждения такого рода неверны - это очень распостраненный миф, который почти всегда оказывается неточной подгонкой под желаемый результат (необязательно осознанной, конечно). Подробная и очень интересная статья об этом, опять-таки по-английски: Fibonacci Flim-Flam. Еще одна статья на ту же тему, менее подробная и в основном о золотом сечении: The Myth That Will Not Go Away.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-01-19 04:40 pm (UTC)http://groups.google.com/group/comp.graphics.algorithms/browse_thread/thread/3608b317d83eddb0?tvc=2
Fibonacci connection between Huffman codes and Wythoff array
http://arxiv.org/abs/cs/0410013
no subject
Date: 2012-01-19 04:43 pm (UTC)no subject
Date: 2012-01-19 04:46 pm (UTC)даже
Date: 2012-01-19 04:48 pm (UTC)no subject
Date: 2012-01-19 04:54 pm (UTC)no subject
Date: 2012-01-19 04:54 pm (UTC)Re: даже
Date: 2012-01-19 04:56 pm (UTC)no subject
Date: 2012-01-19 05:00 pm (UTC)no subject
Date: 2012-01-19 05:03 pm (UTC)Всё-таки не вниз, не вверх, а к ближайшему.
no subject
Date: 2012-01-19 05:05 pm (UTC)no subject
Date: 2012-01-19 05:06 pm (UTC)no subject
Date: 2012-01-19 05:08 pm (UTC)no subject
Date: 2012-01-19 05:23 pm (UTC)no subject
Date: 2012-01-19 05:31 pm (UTC)no subject
Date: 2012-01-19 05:33 pm (UTC)Если у нас есть рекуррентная последовательность вида x_n = a_1 * x_(n-1) + a_2 * x_(n-2) + ... + a_k * x_(n-k), то x_n представляется как линейная комбинация n-ых степеней корней многочлена t^n - a_1 * t^(n-1) - a_2 * t^(n-2) - ... - a_(k-1) * t - a_k.
И даже если не знать этого, то понять что результат в формуле для числа Фибоначчи будет целым очень легко: достаточно заметить, что если раскрыть скобки по биному Ньютона, то все иррациональные члены сократятся, а целые -- наоборот сложатся.
no subject
Date: 2012-01-19 05:39 pm (UTC)no subject
Date: 2012-01-19 05:39 pm (UTC)Именно так.
no subject
Date: 2012-01-19 05:41 pm (UTC)no subject
Date: 2012-01-19 05:48 pm (UTC)А при работе методами ЛА замечать не надо - к результату приходишь тупо по алгоритму.
no subject
Date: 2012-01-19 05:55 pm (UTC)no subject
Date: 2012-01-19 06:00 pm (UTC)то явная формула такая:
Разрешим использовать дроби. Пусть F(0)=3, F(1)=-1/2 и
Казалось бы, ну дроби и дроби, чего тут ждать удивительного? А вылезает ... тригонометрия. Явная формула:
no subject
Date: 2012-01-19 06:03 pm (UTC)Моё сомнение тут вызвано, в частности, тем, что одна из довольно популярных моделей биржи сегодня - это некая разновидность хаотической среды. Согласно же Мандельброту, в хаотических средах вполне могут существовать простые закономерности (см. фракталы). И вот как раз последовательность Фибоначчи очень хорошо уживается с этой идеей, хотя бы концептуально.
no subject
Date: 2012-01-19 06:03 pm (UTC)Именно, это-то как раз очевидно.
no subject
Date: 2012-01-19 06:05 pm (UTC)no subject
Date: 2012-01-19 06:06 pm (UTC)