专栏首页ml齐次方程到矩阵(番外篇)

齐次方程到矩阵(番外篇)

     最近做题,老是遇到了一些公式比如An=An-1+An-2,然后给你一个巨大n的数据,要你求An的值,然后以前做起来,还是比较的顺手的,但是时间抹去了记得的记忆,说明没有学会,于是又花掉一些时间,来回顾以及学习快速矩阵算法。

  其实,每一次我们想到快速矩阵的时候,就可能会产生一个问题? 矩阵该怎么构造,在已经知道了公式的情况下。

不妨以一个我们所收悉的列子:(引自一位 http://www.cnblogs.com/frog112111/archive/2013/05/19/3087648.html )

 求Fibonacci数列第n项的方法是 构造常系数矩阵

(一)   Fibonacci数列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的第n项快速求法(不考虑高精度)

解法:

考虑1×2的矩阵|f[n-2],f[n-1]|。根据Fibonacci数列的递推关系,我们可以通过乘以一个2×2的矩阵A,得到矩阵:|f[n-1],f[n]|。

即:|f[n-2],f[n-1]|*A = 【f[n-1],f[n]】=【f[n-1],f[n-1]+f[n-2]】

很容易构造出这个2×2矩阵A,即: 0 1 1 1

所以,有【f[1],f[2]】×A=【f[2],f[3]】 又因为矩阵乘法满足结合律,故有: 【f[1],f[2]】×A ^(n-1) =【f[n],f[n+1]】 这个矩阵的第一个元素f[n]即为所求。

(二)   数列f[n]=f[n-1]+f[n-2]+1,f[1]=f[2]=1的第n项的快速求法(不考虑高精度)

解法: 仿照前例,考虑1×3的矩阵【f[n-2],f[n-1],1】,希望求得某3×3的矩阵A,使得此1×3的矩阵乘以A得到矩阵:【f[n-1],f[n],1】

即:【f[n-2],f[n-1],1】* A =【f[n-1],f[n],1】=【f[n-1],f[n-1]+f[n-2]+1,1】

容易构造出这个3×3的矩阵A,即: 0 1 0 1 1 0 0 1 1

故:【f[1],f[2],1】* A^(n-1) = 【f[n],f[n+1],1】

(三)数列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的第n项的快速求法(不考虑高精度). 解法: 仿照前例,考虑1×4的矩阵【f[n-2],f[n-1],n,1】,希望求得某4×4的矩阵A,使得此1×4的矩阵乘以A得到矩阵:【f[n-1],f[n],n+1,1】 即:【f[n-2],f[n-1],n,1】* A  = 【f[n-1],f[n],n+1,1】=【f[n-1],f[n-1]+f[n-2]+n+1,n+1,1】 容易构造出这个4×4的矩阵A,即: 0 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1

故:【f[1],f[2],3,1】* A^(n-1) = 【f[n],f[n+1],n+2,1】

(四)   数列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的前n项和s[n]=f[1]+f[2]+……+f[n]的快速求法(不考虑高精度).

解法:

仿照之前的思路,考虑1×3的矩阵【f[n-2],f[n-1],s[n-2]】,我们希望通过乘以一个3×3的矩阵A,得到1×3的矩阵:【f[n-1],f[n],s[n-1]】 即:【f[n-2],f[n-1],s[n-2]】 * A  = 【f[n-1],f[n],s[n-1]】=【f[n-1],f[n-1]+f[n-2],s[n-2]+f[n-1]】 容易得到这个3×3的矩阵A是: 0 1 0 1 1 1 0 0 1

这种方法的矩阵规模是(r+1)*(r+1)

f(1)=f(2)=s(1)=1 ,所以,有

【f(1),f(2),s(1)】* A  = 【f(2),f(3),s(2)】

故:【f(1),f(2),s(1)】* A^(n-1)  = 【f(n),f(n+1),s(n)】

(五)   数列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的前n项和s[n]=f[1]+f[2]+……+f[n]的快速求法(不考虑高精度).

解法:

考虑1×5的矩阵【f[n-2],f[n-1],s[n-2],n,1】, 我们需要找到一个5×5的矩阵A,使得它乘以A得到如下1×5的矩阵【f[n-1],f[n],s[n-1],n+1,1】 即:【f[n-2],f[n-1],s[n-2],n,1】* A  =【f[n-1],f[n],s[n-1],n+1,1】

=【f[n-1], f[n-1]+f[n-2]+n+1,s[n-2]+f[n-1],n+1,1】 容易构造出A为: 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 1

故:【f(1),f(2),s(1),3,1】* A^(n-1)  = 【f(n),f(n+1),s(n),n+2,1】

一般地,如果有f[n]=p*f[n-1]+q*f[n-2]+r*n+s 可以构造矩阵A为: 0  q  0  0  0 1  p  1  0  0 0  0  1  0  0 0  r  0  1  0 0  s  0  1  1

更一般的,对于f[n]=Sigma(a[n-i]*f[n-i])+Poly(n),其中0<i<=某常数c, Poly (n)表示n的多项式,我们依然可以构造类似的矩阵A来解决问题。 设Degree(Poly(n))=d, 并规定Poly(n)=0时,d=-1,此时对应于常系数线性齐次递推关系。则本方法求前n项和的复杂度为: ((c+1)+(d+1))3*logns

例如:A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2);给定三个值N,X,Y求S(N):S(N) = A(0)2 +A(1)2+……+A(n)2。

解:

考虑1*4 的矩阵【s[n-2],a[n-1]^2,a[n-2]^2,a[n-1]*a[n-2]】

我们需要找到一个4×4的矩阵A,使得它乘以A得到1×4的矩阵

【s[n-1],a[n]^2,a[n-1]^2,a[n]*a[n-1]】

即:【s[n-2],a[n-1]^2,a[n-2]^2,a[n-1]*a[n-2]】* A = 【s[n-1],a[n]^2,a[n-1]^2,a[n]*a[n-1]】

= 【s[n-2]+a[n-1]^2 , x^2 * a[n-1]^2 + y^2 * a[n-2]^2 + 2*x*y*a[n-1]*a[n-2] ,

a[n-1]^2 , x*a[n-1]^2 + y*a[n-2]a[n-1]】

可以构造矩阵A为:

1     0    0    0

1    x^2   1    x

0    y^2   0    0

0    2xy   0    y

故:【S[0],a[1]^2,a[0]^2,a[1]*a[0]】 * A^(n-1) = 【s[n-1],a[n]^2,a[n-1]^2,a[n]*a[n-1]】

所以:【S[0],a[1]^2,a[0]^2,a[1]*a[0]】 * A^(n) = 【s[n],a[n+1]^2,a[n]^2,a[n+1]*a[n]】

若A = (B * C ) 则AT = ( B * C )T = CT * BT

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 雅克比迭代算法(Jacobi Iterative Methods) -- [ mpi , c++]

    雅克比迭代,一般用来对线性方程组,进行求解。形如: \(a_{11}*x_{1} + a_{12}*x_{2} + a_{13}*x_{3} = b_{1}\...

    Gxjun
  • nyoj-----127星际之门(一)

    星际之门(一) 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 公元3000年,子虚帝国统领着N个星系,原先它们是靠近光束飞船来进...

    Gxjun
  • hdu------(4300)Clairewd’s message(kmp)

    Clairewd’s message Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768...

    Gxjun
  • 通俗易懂的讲解奇异值分解(SVD)和主成分分析(PCA)

    奇异值分解(The Singular Value Decomposition,SVD)

    deephub
  • 另一个角度看矩阵分析

    这个问题很好解释,矩阵使得公式表达更加的方便。就这一便利性而言就值得引入矩阵这一概念,譬如:

    sea-wind
  • 数据分析与数据挖掘 - 06线性代数

    导数是高等数学中非常重要的知识点,也是人工智能的算法应用中比较常用的一个知识,这一章我们的重点就是讲解一下导数和其求导法则。首先我们来看一下导数的基本概念:函数...

    马一特
  • 数学实验(预习)

    也可以用初等变换求逆矩阵,构造一个n行2n列的矩阵(A E),并进行初等变换,A编程单位矩阵的时候,E就变成了A的逆矩阵.

    云深无际
  • 吹弹牛皮之Unity 引擎基础 - 矩阵(三)

    上图中展示了p,q两个基向量(单位向量)绕原点旋转后得到的新基向量p'和q'。根据勾股定理有:

    用户7698595
  • 吹弹牛皮之Unity 引擎基础 - 矩阵(一)

    沉迷于硬笔的练习偷懒了很长时间。过去的7月份仅仅更新了一篇文章,实在是深表遗憾。接着之前的向量篇小菜继续向下探索。谢谢大家长久来的鼓励和支持。

    用户7698595
  • 一起来学matlab-matlab学习笔记10 10_1一般运算符

    本文为matlab自学笔记的一部分,之所以学习matlab是因为其真的是人工智能无论是神经网络还是智能计算中日常使用的,非常重要的软件。也许最近其带来的一...

    DrawSky

扫码关注云+社区

领取腾讯云代金券