لئوناردو بوناچی ، که به عنوان فیبوناچی شناخته می شود ، عمیقاً بر زندگی ما تأثیر گذاشته است. در ابتدای قرن 13 $^$ ، وی سیستم عددی هندو-عربی را به اروپا معرفی کرد. به جای اعداد رومی ، جایی که من یکی از آنها را برای پنج ، x برای ده و غیره می ایستم ، سیستم عددی هندو-عربی از موقعیتی برای شاخص بودن بزرگی استفاده می کند. این منجر به عبارات بسیار کوتاه تر برای تعداد زیادی می شود. 1

در حالی که تاریخچه سیستم عددی جذاب است ، این پست وبلاگ به این موضوع می پردازد که فیبوناچی به چه معادل مشهورترین شناخته شده است: دنباله فیبوناچی. به طور خاص ، ما از ایده های جبر خطی استفاده خواهیم کرد تا با بیان بسته ای از $ n^$ fibonacci شماره 2 به دست بیاوریم. در سفر ما برای رسیدن به آنجا ، ما همچنین در مورد بازگشت در R. 3 بینش هایی کسب خواهیم کرد

معمای خرگوش

در Liber Abaci ، فیبوناچی سؤال زیر را مطرح می کند (پاراگراف):

فرض کنید ما دو خرگوش تازه متولد شده ، یک زن و یک مرد داریم. فرض کنید این خرگوش ها بعد از یک ماه جفت دیگری از خرگوش های زن و مرد تولید می کنند. این خرگوش های تازه متولد شده ، به نوبه خود ، پس از یک ماه نیز جفت می شوند و یک جفت دیگر تولید می کنند و غیره. خرگوش ها هرگز نمی میرند. چند جفت خرگوش بعد از یک سال وجود دارد؟

شکل زیر این روند را نشان می دهد. هر امتیاز به مرور زمان یک جفت خرگوش را نشان می دهد. برای نشان دادن اینکه هر جفت خرگوش تازه متولد شده باید یک ماه قبل از تولید خرگوش های جدید صبر کند ، خرگوش هایی که هنوز بارور نیستند به رنگ خاکستری رنگی هستند ، در حالی که خرگوش های آماده برای تولید به رنگ قرمز رنگ هستند.

ما می توانیم یک رابطه عود خطی را که توالی فیبوناچی را توصیف می کند ، استخراج کنیم. به ویژه ، توجه داشته باشید که خرگوش ها هرگز نمی میرند. بنابراین ، در زمان $ n $ ، تمام خرگوش ها از زمان $ n - 1 $ حمل می کنند. علاوه بر این ، ما می دانیم که هر جفت خرگوش حاصلخیز یک جفت خرگوش جدید تولید می کند. با این حال ، آنها باید یک ماه صبر کنند ، به طوری که مقدار خرگوش های حاصلخیز برابر با مقدار خرگوش در زمان زمان $ n - 2 $ است. در نتیجه ، دنباله فیبوناچی $ _^<infty>$ است:

برای $ n geq 3 $ و $ f_1 = f_2 = 1 $. قبل از اینکه یک عبارت بسته را به دست آوریم که شماره $ n^$ fibonacci را مستقیماً محاسبه می کند ، در بخش بعدی ، ما با راه حل های جایگزین و ساده تر در R. بازی می کنیم.

اجرای در r

ما می توانیم یک برنامه کاملاً ناکارآمد اما زیبا برای محاسبه شماره $ n^$ fibonacci بنویسیم:

R takes roughly 5 seconds to compute the $30^>$ Fibonacci number; computing the $40^>شماره $ صبر من را خسته می کند. این راه حل بازگشتی به ویژه کارآمد نیست زیرا R عملکرد را یک بار غیر ضروری انجام می دهد. به عنوان مثال ، درخت تماس برای FIB (5):

که نشان می دهد فیبر (2) سه بار خوانده می شد. این لازم نیست ، زیرا می توانیم به جای اینکه هر بار دوباره آن را بازیابی کنیم ، نتیجه این تماس عملکرد را ذخیره کنیم. این روش Memoization نامیده می شود (همچنین به یادآوری بسته R مراجعه کنید). اجرای این امر منجر به:

این فیبوناچی 1000 $^$ را در یک دهم ثانیه محاسبه می کند. البته می توانیم این را به صورت متوالی بنویسیم ، و همچنین همه شماره های فیبوناچی میانی را ذخیره کنیم. این همچنین از مسائل حافظه ناشی از اجرای بازگشتی جلوگیری می کند. جالب اینجاست که اگرچه این الگوریتم به نظر می رسد که باید $ O (n) $ باشد ، اما در واقع $ o (n^2) $ است زیرا ما تعداد فزاینده ای را اضافه می کنیم (برای اطلاعات بیشتر در این مورد ، اینجا را ببینید).

30 شماره فیبوناچی اول عبارتند از: 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ، 144 ، 233 ، 377 ، 610 ، 987 ، 1597 ، 2584 ، 4181 ، 6765 ، 10946 ، 17711، 28657 ، 46368 ، 75025 ، 121393 ، 196418 ، 317811 ، 514229 ، 832040.

این یک افزایش سریع است ، همانطور که در شکل سمت چپ زیر آشکار می شود. شکل در سمت راست نشان می دهد که در نحوه رشد توالی ساختاری وجود دارد.

ما در پایان پست وبلاگ به ساختار رشد خواهیم پرداخت. اول ، ما باید یک بیان بسته از شماره فیبوناچی $ n^$ را بدست آوریم. در بخش بعدی ، ما با درک اینکه ماتریس های مورب محاسبات ساده تر را انجام می دهند ، گامی به سمت آن برداشته ایم.

ماتریس های مورب خوب هستند

هدف ما این است که یک فرم بسته از شماره Fibonacci $ n^$ را بدست آوریم. اولین نکته ای که باید به آن توجه داشته باشید این است که ، به دلیل بازگشت خطی ، می توانیم شماره های فیبوناچی را به عنوان استفاده از نقشه خطی مشاهده کنیم. به طور خاص ، $ t in mathcal ( mathbb^2) $ توسط:

[t (x ، y) = (y ، x + y) enspace. ]

[t^n (0 ، 1) = (f_n ، f_) enspace ، ]

که ما با القاء اثبات خواهیم کرد. به طور خاص ، توجه داشته باشید که مورد پایه $ n = 1 $:

[t^1 (0 ، 1) = (1 ، 0 + 1) = (1 ، 1) = (f_1 ، f_2) enspace ، ]

در واقع دو شماره فیبوناچی اول را ارائه می دهد. اکنون برای مرحله القایی: ما فرض می کنیم که این یک $ n خودسرانه را در خود جای داده است ، و ما نشان می دهیم که با استفاده از موارد زیر با قیمت N + 1 $ نگه داشته می شود:

آخرین برابری از تعریف توالی فیبوناچی ، یعنی این واقعیت که هر عدد برابر با مجموع دو عدد قبلی است ، دنبال می شود. ماتریس این نقشه خطی با توجه به مبنای استاندارد توسط:

[A Equiv Mathcal (t) = شروع 0 & 1 \ 1 & 1 end enspace ، ]

از آنجا که $ t (1 ، 0) = (0 ، 1) $ و $ t (0 ، 1) = (1 ، 1) $. مشاهده کنید که:

در کد R متوالی برای محاسبه شماره های فیبوناچی ، ما نقشه خطی $ n $ را بارها اعمال کرده ایم ، که شماره فیبوناچی را که به آن علاقه مند بودیم به ما داد. ما می توانیم این را به صورت ماتریس بنویسیم:

اگر می خواهید با استفاده از این معادله ، شماره فیبوناچی 3^$ $ $ را محاسبه کنید ، باید سه بار با خود یک دلار دلار ضرب کنید. حالا فرض کنید که چیزی شبیه به آن داشته اید:

[ شروع lambda_1 & 0 \ 0 & lambda_2 end^n شروع 0 \ 1 end = شروع f_n \ f_ end enspace. ]

با استفاده از معادله فوق ، قدرت ماتریس بی اهمیت می شود:

[ شروع lambda_1 & 0 \ 0 & lambda_2 end^n = lambda_1^n & 0 \ 0 & lambda_2^n end enspace. ]

دیگر نیازی به انجام مکرر در ضرب ماتریس نخواهد بود. در عوض ، ما با استفاده از تنها ضرب مقیاس به شماره N^$ fibonacci می رسیدیم! بنابراین وظیفه ما به شرح زیر است: یک ماتریس جدید برای نقشه خطی که مورب است پیدا کنید. برای حل این مسئله ، ما به مقادیر ویژه و ویژه ای نیاز خواهیم داشت.

یافتن مقادیر ویژه و ویژه

یک جفت eigenveector-eigenvalue $ (v ، lambda) $ برای $ v neq 0 $ که:

[tv = lambda v enspace ، ]

این بدان معناست که برای یک بردار خاص $ v $ ، نقشه خطی فقط بردار را با یک $ lambda $ ثابت می کند. در اینجا کلید وجود دارد: با استفاده از eigenvectors به عنوان مبنای ، ماتریس نقشه خطی مورب است. این امر به این دلیل است که ماتریس نقشه خطی ما ، $ A $ ، توسط:

[ شروع tv_1 & = a_ v_1 + a_ v_2 \ tv_2 & = a_ v_1 + a_ v_2 enspace.پایان]

اکنون از آنجا که این پایه فقط شامل Eigenvectors است ، می دانیم که $ tv_1 = lambda v_1 $ و $ tv_2 = lambda v_2 $ ، که دلالت بر این دارد که $ a_ = lambda_1 $ و $ a_ = 0 $ و همچنین $ a_ =0 $ و $ a_ = lambda_2 $. برای توضیح فوق العاده ای در مورد مقادیر ویژه و ویژه های ویژه ، این فیلم را توسط 3Blue1Brown ببینید. 4

به منظور یافتن مقادیر ویژه و ویژه های ویژه ، توجه داشته باشید که نقشه خطی دو معادله زیر را برآورده می کند:

[ شروع t (x ، y) & = lambda (x ، y) \ [1em] t (x ، y) & = (y ، x + y) enspace.پایان]

[ شروع lambda x & = y \ [1em] lambda y & = x + y enspace.پایان]

ما عبارت اول را در حالت دوم جایگزین می کنیم و بازده می دهیم:

[ شروع lambda^2 x & = x + y \ [1em] ( lambda^2 - 1) x & = y enspace ، end ]

که اکنون ما در اولین معادله جایگزین می شویم ، که نتیجه آن است:

[ شروع lambda x & = ( lambda^2 - 1) x \ [1em] 0 & = lambda^2 - lambda - 1 enspace.پایان]

اکنون می توانیم فرمول درجه دوم یا "mitteachtsformel" را اعمال کنیم ، همانطور که در بخش هایی از آلمان خوانده می شود زیرا دانش آموزان باید در هنگام غرق شدن از خواب در نیمه شب ، فرمول را بدانند. ما نه در آلمان هستیم و نه نیمه شب ، و نه می توانم فرمول را به خاطر بسپارم ، بنابراین بیایید به سرعت آن را برای مشکل خود استخراج کنیم:

[x08egin lambda^2 - lambda - 1 &= 0 \[1em] lambda^2 - lambda &= 1 \[1em] 4lambda^2 - 4lambda &= 4 \[1em] 4lambda^2 - 4lambda + 1&= 4 + 1 \[1em] (2lambda - 1)^2&= 4 + 1 \[1em] 2lambda - 1 &= pm sqrt \[1em] lambda &= frac> Enspace.پایان]

اکنون که هر دو مقادیر ویژه را پیدا کرده ایم ، به شکارچی های ویژه می رویم! ما مقادیر ویژه را از بالا در معادلات قرار می دهیم:

If we set $x = 1$, then $y = frac>$بنابراین ، دو بخش ویژه عبارتند از:

به عنوان یک بررسی عقل برای دیدن اینکه آیا این واقعاً صحیح است ، ما بررسی می کنیم که آیا $ tv_1 = lambda_1 v_1 $:

که نشان می دهد این دو عبارت برابر هستند. علاوه بر این ، محصول نقطه ای از دو دستگاه ویژه صفر است ، به این معنی که دو eigenvector به صورت خطی مستقل هستند (همانطور که باید باشد). در بخش بعدی متوجه خواهیم شد که همان قلمرو را می توان با نقشه های مختلف توصیف کرد.

تغییر پایه

اکنون که مقادیر ویژه و ویژه ای را پیدا کرده ایم ، می توانیم ماتریس $ d $ نقشه خطی $ t $ را که با توجه به اساس eigenvectors مورب است ، ایجاد کنیم:

با این حال ما هنوز تمام نشده ایم. توجه داشته باشید که $ d $ ماتریس نقشه خطی $ t $ با توجه به مبنایی است که شامل هر دو eigenvectors $ v_1 $ و $ v_2 $ است ، نه با توجه به مبنای استاندارد. ما سیستم مختصات خود را تغییر داده ایم - نقشه ما - همانطور که در شکل زیر نشان داده شده است. بردارهای رنگی سیاه بردارهای پایه استاندارد هستند در حالی که بردارهای رنگی به رنگ قرمز بردارهای پایه جدید ما هستند.

برای ایجاد برخی از شهود ، بیایید با نمایندگی $ omega $ در هر دو پایه استاندارد و نمایشگاه جدید ما بازی کنیم. هر بردار ترکیبی خطی از بردارهای پایه است. بگذارید $ a_1 $ و $ a_2 $ ضرایب مبنای استاندارد باشد به گونه ای:

[ omega = a_1 شروع 1 \ 0 پایان + a_2 شروع 0 \ 1 end enspace. ]

اکنون به دلیل اینکه من آن را زودتر ترسیم کرده ام ، می دانم که $ A_1 = -1 $ و $ A_2 = 0. 3 $. این نمایندگی $ omega $ در مبنای استاندارد است. چگونه می توانیم آن را در eigenbasis خود نمایندگی کنیم؟خوب ، با استفاده از Eigenbasis ، بردار $ omega $ هنوز ترکیبی خطی از بردارهای پایه است ، اما با ضرایب مختلف. آنها را به عنوان $ b_1 $ و $ b_2 $ مشخص کنید. ما چنین داریم:

اگر این را به صورت ماتریس بنویسیم ، داریم:

بنابراین ، ما می توانیم با محاسبات یک بردار $ $ با مبنای $ $ $ $ e $ را نمایندگی کنیم:

[b = e^ s ، a enspace. ]

در Eigenbasis ما ، بردار $ omega $ مختصات را دارد:

این بدان معنی است که ما نمایندگی داریم:

که وقتی به شکل بالا نگاه می کنید ، حس بصری می کند. برای یک فیلم جبر خطی زیبا دیگر توسط 3Blue1Brown ، این بار در مورد تغییر پایگاه ها ، به اینجا مراجعه کنید. در بخش بعدی ، ما از آنچه در بالا آموخته ایم برای بیان شماره n^$ fibonacci $ به صورت بسته استفاده خواهیم کرد.

فیبوناچی با فرم بسته

از بالا به یاد بیاورید که راه حل ما برای یافتن شماره $ n^$ fibonacci در فرم ماتریس:

اکنون ، ما با تغییر مبنای از مبنای استاندارد به Eigenbasis ، ماتریس غیر مورب $ A $ را با ماتریس مورب $ D $ تعویض کرده ایم. با این حال ، بردار $ (0 ، 1)^t $ هنوز به صورت استاندارد است! به منظور تغییر نمایندگی خود به Eigenbasis ، همانطور که در بالا گفته شد ، آن را با $ e^$ ضرب می کنیم. ما نوشتیم:

بیایید از این برای محاسبه ، مثلاً شماره فیبوناچی 10^$ $ (که 55 است) در R استفاده کنیم:

هاهاین کار کاملاً کار نکرد ، این کار را کرد؟ما در هنگام گرد شدن ، جواب F_ $ را تقریباً دریافت کردیم ، اما $ f_ $ کاملاً خاموش است. چه چیزی را از دست دادیم؟خوب ، این در واقع پاسخ صحیح است - این فقط به صورت اشتباه است! ما باید این را از Eigenbasis به مبنای استاندارد تبدیل کنیم. برای انجام این کار ، مشاهده کنید که:

[ شروع b & = e^ s ، a \ e b & = s ، a \ e b & = a enspace ، end ]

از آنجا که $ S $ ماتریس هویت است. بنابراین ، تنها کاری که باید انجام دهیم این است که با E $ $ ضرب کنیم:

که راه حل صحیح است. برای به دست آوردن راه حل بسته به صورت جبری ، ابتدا ماتریس $ e $ را معکوس می کنیم:

بیان فرم بسته شماره $ n^$ fibonacci بنابراین توسط:

ما این را در R تأیید می کنیم:

نسبت طلایی

در بخش فوق ، ما یک بیان بسته از شماره N^$ fibonacci $ را به دست آورده ایم. در این بخش ، ما به مشاهده ای که در ابتدا انجام داده ایم باز می گردیم: ساختاری در نحوه رشد اعداد فیبوناچی وجود دارد. یوهانس کپلر ، که پس از آن دانشگاه در شهر من نامگذاری شده است ، (دوباره) کشف کرد که:

which is the golden ratio. The golden ratio $phi$ denotes that the ratio of two parts is equal to the ratio of the sum of the parts to the larger part, i.e., for $a> b>0 $:

ما این را به صورت تجربی در شکل اول مشاهده کرده ایم ، که تفاوت های موجود در ورود به سیستم دو شماره فیبوناچی متوالی را نشان می دهد ، و قبلاً برای $ N $ کوچک به دست آمده است:

[ ext , F_ - ext , F_n = ext , frac> تقریبا 0. 4812 Enspace ، ]

which exponentiated yields the golden ratio. Observe that $left(frac> RIGHT)^n $ خیلی سریع به صفر می رود زیرا $ n $ رشد می کند تا بتوانیم شماره $ n^$ fibonacci را توسط:

[F_n = left lfloor frac> phi^n راست rceil enspace ، ]

جایی که ما به سادگی به نزدیکترین عدد صحیح دور می شویم. در نهایت پاسخ به معمای فیبوناچی:

پس از گذشت دوازده ماه از محارم ، 144 جفت خرگوش وجود دارد! 5

تعمیم های مختلفی از دنباله فیبوناچی وجود دارد. یکی از این تعمیمها اجازه دادن به سفارشات بالاتر $ k $ در دنباله است که برای $ k = 3 $ به عنوان دنباله Tribonacci شناخته می شود. رویکرد ما برای $ k = 2 $ می تواند به طور مستقیم تعمیم داده شود تا هر سفارش $ k $ را حساب کند (اگر می خواهید یک سوراخ خرگوش پایین بروید ، به عنوان مثال این را ببینید).

نتیجه

در این پست وبلاگ ، ما نگاهی دقیق به دنباله فیبوناچی انداخته ایم. به طور خاص ، ما دیدیم که این پاسخ به یک معما در مورد پیش بینی خرگوش ها ، و چگونگی سرعت بخشیدن به الگوریتم بازگشتی برای یافتن شماره $ n^$ fibonacci است. سپس از ایده های جبر خطی استفاده کردیم تا به یک بیان بسته از شماره $ n^$ fibonacci برسیم. به طور خاص ، ما متذکر شدیم که توالی فیبوناچی یک رابطه عود خطی است - می توان آن را به طور مکرر با استفاده از نقشه خطی مشاهده کرد. با این بینش ، ما مشاهده کردیم که ماتریس نقشه خطی غیر مورب است ، که اجرای مکرر را خسته کننده می کند. از طرف دیگر ماتریس های مورب به راحتی تکثیر می شوند. ما با تغییر مبنای پایه از پایه استاندارد به مبنای eigenvectors ، به یک ماتریس مورب رسیدیم ، که منجر به یک ماتریس مورب از مقادیر ویژه برای نقشه خطی شد. با این نمایندگی ، شماره n^$ $ fibonacci به صورت بسته در دسترس است. برای اینکه آن را به صورت استاندارد بدست آوریم ، مجبور شدیم پایه و اساس را از Eigenbasis تغییر دهیم. ما همچنین دیدیم که چگونه شماره های فیبوناچی با نسبت طلایی $ phi $ ارتباط دارد.

من می خواهم از دون ون دن برغ ، جوناس هاسلبک و سوفیا کروول بخاطر نظرات مفید در این پست وبلاگ تشکر کنم.

پانویسها و منابع

این دلیل اصلی این است که سیستم اعدام Hinu-Arabic را به دست گرفت. این اعتقاد که تکثیر و تقسیم با استفاده از اعداد هندو-عربی ساده تر است ، نادرست است.↩

این پست وبلاگ از تمرین 16 در صفحه الهام گرفته شده است. 161 در جبر خطی درست انجام شد.↩

من آموخته ام که در حال حاضر جوهر (بسیار خوب) در این موضوع ریخته شده است ، به عنوان مثال در اینجا و اینجا ببینید. یک مقاله خوب نیز این قطعه توسط استیو استروگاتز است که به هر حال ، کتاب فوق العاده ای به نام Sync نوشت. او همچنین در پادکست Mindscape شان کارول بوده است ، به اینجا گوش دهید.↩

اگر همه چیزهایی را که در این پست وبلاگ نوشته شده است فراموش کنید ، اما از طریق آن از فیلم های 3Blue1brown (یا گرانت ساندرسون ، همانطور که در دنیای واقعی شناخته شده است) آگاه شد ، پس من این پست وبلاگ را موفقیت آمیز می دانم.↩

The downside of the closed-form solution is that it is difficult to calculate the power of the square root with high accuracy. In fact, fib_golden is incorrect for $n> 70$. Our fib_mem implementation is also incorrect, but only for $n>93 $(من آن را با شماره های فیبوناچی که از اینجا محاسبه شده است مقایسه کرده ام).↩