线性代数 --- 计算斐波那契数列第n项的快速算法(矩阵的n次幂)

 计算斐波那契数列第n项的快速算法(矩阵的n次幂)

The n-th term of Fibonacci Numbers:

        斐波那契数列的是一个古老而又经典的数学数列,距今已经有800多年了。关于斐波那契数列的计算方法不难,只是当我们希望快速求出其数列中的第100,乃至第1000项时,有没有又准又快的方法,一直是一个值得探讨和研究的问题。笔者(松下J27)在这篇文章中,就介绍了一种基于线性代数的快速算法,即,基于矩阵的n次幂找到斐波那契数列的第n项。这是我在MIT线性代数的公开课中看到的,并以此文记录下来。

(意大利数学家斐波那契,图片来源于参考文献【1】) 

已知斐波那契数列的数学表示方式如下:

Fibonacci:0,1,1,2,3,5,8,13,21,34......

他始于数列的前两个初始值0,1,后面所有的项都是前两项的和,依此类推得到:

0+1=11+1=21+2=32+3=53+5=8。。。

        基于上面的计算规律,假设我用F_{i}来表示该数列的第i个数的话,那斐波那契数列用代数的方式可写成两个初值和一个递归公式的组合,即:

F_{0}=0,F_{1}=1

F_{i+2}=F_{i}+F_{i+1},\: i=0,1,2...

        现在把上面的公式用矩阵和向量的方式来表示,以便于用线性代数来分析:

1,先把初值用向量u0来表示

u_{0}=\begin{bmatrix} F_{0}\\ F_{1} \end{bmatrix}=\begin{bmatrix} 0\\ 1\end{bmatrix}

2,用向量u_{i}表示数列中的第n项。

 u_{i}=\begin{bmatrix} F_{i}\\ F_{i+1} \end{bmatrix}

3,如此一来根据递归公式就能写出第i+1项u_{i+1}

u_{i+1}=\begin{bmatrix} F_{i+1}\\ F_{i+2} \end{bmatrix}=\begin{bmatrix} F_{i+1}\\ F_{i}+F_{i+1} \end{bmatrix}

4,用矩阵来表示从第i项u_{i}到第i+1项u_{i+1}的过程

u_{i+1}=\begin{bmatrix} F_{i+1}\\ F_{i+2} \end{bmatrix}=\begin{bmatrix} F_{i+1}\\ F_{i}+F_{i+1} \end{bmatrix}=\begin{bmatrix} 0 &1 \\ 1& 1\end{bmatrix}\begin{bmatrix} F_{i}\\ F_{i+1} \end{bmatrix}=\begin{bmatrix} 0 &1 \\ 1& 1\end{bmatrix}u_{i}

其中,参与计算的矩阵A为:

A=\begin{bmatrix} 0& 1\\ 1&1 \end{bmatrix}

         现在,我们知道了初始向量u_{0},也知道如果计算u_{i+1},我们就能通过线性代数中矩阵与向量的计算来计算斐波那契数列中的任意一项:

        可以看到,如果你要计算第100项,不出意外,只要把上述步骤继续下去一定能够找到。另外,如果把上述计算中的三次计算合成一部,就是三个矩阵A连续相乘后,再乘以u0。

        这就是说,斐波那契数列中第n项的计算公式应该是:

u_{n}=A\cdot A\cdot A\cdot A...\cdot Au0=A^{n}u0

u_{n}=A^{n}u0 (式1) 

这里要注意的是,根据这种方法算出来的是一个向量,而我们需要的结果,即,第n项是该向量中的第一个元素。


引入矩阵的对角化:

        熟悉线性代数的朋友看到A的n次幂时,马上就会想到是否可以通过特征向量矩阵X特征值矩阵\Lambda对A进行对角化。

线性代数 --- 矩阵的对角化以及矩阵的n次幂-CSDN博客文章浏览阅读1k次,点赞15次,收藏9次。本文从矩阵A的对角化开始,一直聊到了对角化的应用,并以一个A的n次幂为例子结尾。https://blog.csdn.net/daduzimama/article/details/138088128

因为,如果方阵A可以被对角化为:

A=X\Lambda X^{-1}

那么上面推导出来的斐波那契数列的第n项的计算公式就能简化为:

u_{n}=A\cdot A\cdot A\cdot A...\cdot Au0=A^{n}u0\Rightarrow

u_{n}=(X\Lambda X^{-1})\cdot (X\Lambda X^{-1})\cdot (X\Lambda X^{-1})...\cdot (X\Lambda X^{-1})u0=X\Lambda ^{n}X^{-1}u0

u_{n}=X\Lambda ^{n}X^{-1}u0 , (式2) 

 

现在我们试着用(式2)去计算斐波那契数列的第100项:

第一步,计算矩阵A的特征向量与特征值:

\lambda _{1}=-0.61803399,x_{1}=\begin{bmatrix}-0.85065081 \\ 0.52573111\end{bmatrix}

\lambda _{2}=1.61803399,x_{2}=\begin{bmatrix}-0.52573111\\ -0.85065081\end{bmatrix}

 通过计算得出了两个不同的特征值,说明矩阵A可以对角化。

第二步,构建特征向量矩阵X,特征值矩阵\Lambda和特征向量矩阵的逆:

X=\begin{bmatrix} -0.85065081&-0.52573111 \\ 0.52573111&-0.85065081 \end{bmatrix}

\Lambda =\begin{bmatrix} -0.61803399 &0 \\ 0 & 1.61803399 \end{bmatrix}

 X^{-1}=\begin{bmatrix} -0.85065081&0.52573111 \\ -0.52573111&-0.85065081 \end{bmatrix}

第三步,计算特征值矩阵\Lambda的100次幂:

 \Lambda ^{100}=\begin{bmatrix} -0.61803399^{100} &0 \\ 0 & 1.61803399^{100} \end{bmatrix}

=\begin{bmatrix}1.26251334E-21 &0 \\ 0 & 7.92070840E+20 \end{bmatrix}

第四步,基于(式2)去计算第100项的值:

 u_{100}=\begin{bmatrix} 3.54224848E+20\\ 5.73147844E+20 \end{bmatrix}

其中,第100项的值为:

F_{100}=3.54224848E+20

进一步简化:

如果我能把u0表示成所有特征向量的线性组合的话,就能更进一步简化计算:

u_{0}=c_{1}x_{1}+c_{2}x_{2}...+c_{n}x_{n}=Xc (式3) 

其中,权重系数向量c等于:

c=X^{-1}u_{0} (式4) 

如此一来,斐波那契的第n项的计算公式(式1)就变成了:

u_{n}=A^{n}(c_{1}x_{1}+c_{2}x_{2}...+c_{n}x_{n})=c_{1}A^{n}x_{1}+c_{2}A^{n}x_{2}...+c_{n}A^{n}x_{n} (式5) 

 又因为这里的x都是特征向量,根据特征向量的性质,我们有Key Equation:

Ax=\lambda x

对于上式中的第一项c_{1}A^{n}x_{1}有:

c_{1}A^{n}x_{1}=c_{1}A\cdot A...\cdot A\cdot Ax_{1}=c_{1}A\cdot A...\cdot A\cdot \lambda _{1}x_{1}

因为\lambda _{1}是一个系数,所以我们把他提到前面去:

c_{1}A^{n}x_{1}=c_{1}\lambda _{1}A\cdot A...\cdot Ax_{1}

这样一来又出现了一个\lambda _{1},继续:

c_{1}A^{n}x_{1}=c_{1}\lambda _{1}A\cdot A...\cdot \lambda _{1}x_{1}

如此反复,一直到第n个乘法:

c_{1}A^{n}x_{1}=c_{1}\lambda _{1}^{n}A

依此类推,(式5)可改写成:

u_{n}=c_{1}\lambda _{1}^{n}x_{1}+c_{2}\lambda _{2}^{n}x_{2}...+c_{n}\lambda _{n}^{n}x_{n} (式6) 

 (式6) 也可以写成:

u_{n}=c_{1}\lambda ^{n}x_{1}+c_{2}\lambda ^{n}x_{2}...+c_{n}\lambda ^{n}x_{n}=X\Lambda ^{n}c (式7) 

这一点也可以通过把 (式3)代入(式2)得到(式7)

u_{n}=X\Lambda ^{n}X^{-1}u0=X\Lambda ^{n}X^{-1}(Xc)=X\Lambda ^{n}c

这里面最重要的是(式6),因为他把计算分离开了,分成了一个个常数与向量的乘积之和。

现在针对这一简化算法做一个小结,并以求斐波那契的第100项为例:

第一步,优先使用(式4)算出权重向量c

c=X^{-1}u_{0}=\begin{bmatrix} 0.52573111\\ -0.85065081 \end{bmatrix} 

\Rightarrow c_{1}=0.52573111, c_{2}=-0.85065081 

 

第二步,分别计算c_{1}\lambda _{1}^{100}x_{1}c_{2}\lambda_{2} ^{100}x_{2},其中c和\lambda都是常数。

 

第三步,求和。把第二步的结果加在一起,求出最终的结果。在本例中,因为c_{1}\lambda _{1}^{100}x_{1}中的元素几乎为0,所以他们二者的和几乎约等于c_{2}\lambda_{2} ^{100}x_{2}

u_{100}=c_{1}\lambda _{1}^{100}x_{1}+c_{2}\lambda _{2}^{100}x_{2}=\begin{bmatrix} F_{100}\\ F_{101} \end{bmatrix}

最终,得到了同样正确的结果:

F_{100}=3.54224848E+20


 (全文完) 

--- 作者,松下J27

参考文献(鸣谢):

1,https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91

2, Lec22_对角化和矩阵乘幂_哔哩哔哩_bilibili

(配图与本文无关) 

版权声明:所有的笔记,可能来自很多不同的网站和说明,在此没法一一列出,如有侵权,请告知,立即删除。欢迎大家转载,但是,如果有人引用或者COPY我的文章,必须在你的文章中注明你所使用的图片或者文字来自于我的文章,否则,侵权必究。 ----松下J27

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/577227.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

关于SSL加密,您应该知道什么?

SSL加密,全称为安全套接字层加密,是一种网络安全协议,主要用于在网络通信中提供隐私和数据完整性。它通过在客户端和服务器之间建立一个加密的通道,确保数据在传输过程中不被窃取或篡改。随着互联网的普及和电子商务的快速发展&am…

边OTG边充电芯片LDR6500

随着科技的飞速发展,智能移动设备已成为我们生活中不可或缺的一部分。而在这些设备的连接与数据传输中,Type-C接口以其高效、便捷的特性逐渐占据了主导地位。OTG(On-The-Go)技术则进一步扩展了Type-C接口的功能,使得设…

uniapp 微信小程序 获取openid,手机号进行登录,配合后端

流程&#xff1a;登录注册功能,通过uni.getUserProfile获取wxcode,通过wxcode传给后端获取openid,sessionkey,unionid。 通过<u-button type"success" open-type"getPhoneNumber" getphonenumber"decryptPhoneNumber">一键登录</u-butt…

Spark-机器学习(5)分类学习之朴素贝叶斯算法

在之前的文章中&#xff0c;我们学习了回归中的逻辑回归&#xff0c;并带来简单案例&#xff0c;学习用法&#xff0c;并带来了简单案例。想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你宝贵…

合合信息引领AI场景化革新,供应链金融智能化审核全面升级!

官.网地址&#xff1a;合合TextIn - 合合信息旗下OCR云服务产品 随着供给侧结构性改革的深入推进和产业结构的不断升级&#xff0c;金融机构在监管部门的指导下&#xff0c;积极拓展供应链金融业务&#xff0c;取得了显著成效。这一举措有效缓解了上下游中小企业的融资困难&a…

你的网站还在使用HTTP? 免费升级至HTTPS吧

如果您的网站还在使用老的http协议&#xff0c;可以申请一个免费的SSL证书升级至https&#xff01; 具体步骤如下&#xff1a; 1 申请免费SSL证书 根据你的需求选择合适的SSL证书类型&#xff0c;如单域名证书&#xff0c;多域名证书、通配符证书 登录免费供应商JoySSL官网&…

中电金信:深度解析|数字化营销运营体系搭建

如何更好更快地梳理好体系搭建思路&#xff0c;稳步实现落地&#xff1f;下文将为大家明确搭建的推进步骤、执行要点&#xff0c;帮助商业银行理顺数字化营销运营体系的“点”“线”“面”~ 与所有转型的曲折、阵痛等特征一样&#xff0c;商业银行构建数字化营销运营体系过程中…

数据结构与算法解题-20240426

这里写目录标题 面试题 08.04. 幂集367. 有效的完全平方数192. 统计词频747. 至少是其他数字两倍的最大数718. 最长重复子数组 面试题 08.04. 幂集 中等 幂集。编写一种方法&#xff0c;返回某集合的所有子集。集合中不包含重复的元素。 说明&#xff1a;解集不能包含重复的子…

DSP开发实战教程--EPWM模块的影子寄存器详细讲解原理和代码实例

EPWM模块影子寄存器的原理 在TI&#xff08;Texas Instruments&#xff09;的DSP28335中&#xff0c;EPWM&#xff08;Enhanced Pulse Width Modulator&#xff09;模块提供了高精度、高灵活性的PWM信号生成功能。为了能在不影响当前PWM波形输出的情况下预装载新的PWM参数&…

电源小白入门学习6——锂离子电池特性及充电电路

锂离子电池特性及充电电路 锂离子电池18650电池锂聚合物电池锂电池的放电曲线 锂离子电池充电方法常见的充电方案 锂离子电池 锂离子电池是一种常见的可充电电池类型&#xff0c;主要依靠锂离子在正极和负极之间的移动来工作。在充放电过程中&#xff0c;锂离子在两个电极之间…

表情识别 | LBP+SVM实现脸部动态特征的人脸表情识别程序(Matlab)

表情识别 | LBPSVM实现脸部动态特征的人脸表情识别程序&#xff08;Matlab&#xff09; 目录 表情识别 | LBPSVM实现脸部动态特征的人脸表情识别程序&#xff08;Matlab&#xff09;预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1 运行环境 程序运行在Windows系统下&am…

不同技术实现鼠标滚动图片的放大缩小

摘要&#xff1a; 最近弄PC端的需求时&#xff0c;要求在layui技术下实现鼠标滚动图片的放大缩小的功能&#xff01;下面来总结一下不同框架剩下这功能&#xff01; layui: 看了一下layui文档&#xff0c;其实这有自带的组件的&#xff01;但是又版本要求的!并且layui的官方文档…

让ThreadPoolExecutor无所遁形:Java线程池运行原理详解

ThreadPoolExecutor的核心工作原理 当我们在Java中讨论并发和多线程时&#xff0c;ThreadPoolExecutor 是不可或缺的一个类。在 java.util.concurrent 包下&#xff0c;该类负责管理线程池内的线程&#xff0c;包括线程的创建、执行、管理以及线程池的监控等。理解 ThreadPool…

玩转手机在AidLux上安装宝塔面板

AidLux&#xff0c;手机不用刷机、不用root&#xff0c;直接在手机应用市场就能下载使用。 1.4G的应用包&#xff0c;看起来挺大的&#xff0c;那是因为内嵌了一套完整的AIoT应用开发和部署平台。 不仅Android手机可以玩&#xff0c;华为的Harmony系统也可以使用。 使用它最主…

websocket爬虫

人群看板需求分析 先找到策略中心具体的数据。对应数据库中的数据 看看接口是否需要被逆向 点开消费者细分&#xff0c;可以找到人群包&#xff08;人群名称&#xff09; 点击查看透视 label字段分类: 在这里插入图片描述 预测年龄&#xff1a;tagTitle 苹果id&#x…

【Unity基础】TextMeshPro组件学习过程记录

目录 1.TextMeshPro组件渲染创建文本RTL Editor字体Font Asset字体加粗&#xff0c;下划线等字体大小控制字体颜色控制字体渐变控制字符间隔、单词间隔、行间距、段落间距控制WrappingUV映射控制代码 2.TextMeshPro组件AssetFace InfoGeneration Setting 3.使用Dynamic SDF Sys…

从C语言到C++过渡篇(快速入门C++)

目录 引言 命名空间 C 的输入输出&#xff08;cout & cin&#xff09; 输出 cout 输入 cin 缺省参数 函数重载 知识要点讲解 函数重载底层 引用& 内联函数 auto & nullptr 结语 引言 很多同学从C语言到C的转变不知从何下手&#xff0c;今天这篇文章主…

【MRI重建】Cartesian采样中data consistency 常规数据一致性实现(pytorch)

关于 在MRI重建中,data consistency 可以帮助加快MRI图像重建和减少模型重建带来的重建误差。 工具 方法实现 x_rec: 重建图像, (batch_size,2,H,W) mask: 欠采样模版,(batch_size,2,H,W) k_un: 真实欠采样采集数据, (batch_size,2,H,W) torch.view_as_complex: 将实数数据…

【Linux】HTTP协议2

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;题目解析 &#x1f30e;推荐文章&#xff1a;承接上文【Linux】HTTP协议1 目录 &#x1f449;&#x1f3fb;HTTP方法&#x1f449;&#x1f3fb;HTTP状态码&…

Swift - 流程控制

文章目录 Swift - 流程控制if-else2. while3. for3.1 闭区间运算符3.2 半开区间运算符3.3 for - 区间运算符用在数组上3.3.1 单侧区间 3.4 区间类型3.5 带间隔的区间值 4. switch4.1 fallthrough4.2 switch注意点 5. 复合条件6. 区间匹配、元组匹配7. 值绑定8. where9. 标签语句…