矩阵乘法(加快速幂)

参考文献:《算法导论》、dalao的blog

我真的觉得本篇良心,大大干货

引言:

题目:

斐波那契数列很喜欢被研究,其前几项为:1 1 2 3 5 8 13 ……

则,求斐波那契数列的第n项是?

解法:

1.朴素求解:

由斐波那契数列的定义,可以由递推求解

f(1)=1,f(2)=1

f(n)=f(n-1)+f(n-2)    (n>=3)

f[1]=f[2]=1;
for(int i=1;i<=n;i++)
    f[n]=f[n-1]+f[n-2];
out(f[n]);

2.矩阵快速幂优化递推式:

学习这个首先要了解一下几个东西:

1.矩阵

2.矩阵的运算

3.快速幂

4.矩阵快速幂优化

 

 

矩阵乘法快速幂

1.矩阵

矩阵是二维的一个由n*m构成的”数列“(我想不到其他解释的名词了)

大概长这样:

《矩阵乘法(加快速幂)》

其数学上的定义方式为:

矩阵名=一对括号里面为矩阵的内容

 

矩阵的向量简单来说就是矩阵的一行或者是一列 

我们把矩阵的行和列交换记作(以矩阵A举例)《矩阵乘法(加快速幂)》

零矩阵为所有元素都是0的矩阵

单位向量是第i个元素是1而其他皆为0 的向量

那么,矩阵有以下特殊的几种

1.1对角矩阵

当i!=j时,有aij=0

大概长这样:(盗用一下G_congratulationdalao单位矩阵的图2333,这里的1可以换成其他任意数,但下面的单位矩阵就不可以了)

 

《矩阵乘法(加快速幂)》

 

1.2单位矩阵

矩阵里的元素为0,1,且

当i=j的时候,有aij=1

大概长这样(卑鄙如我2333)

《矩阵乘法(加快速幂)》

 

1.3三对角矩阵

当 | i – j |>1 时,aij=0    <=>  非零出现在主对角线上,且仅靠上下两侧

大概长这样:

《矩阵乘法(加快速幂)》

 

1.4上三角矩阵

当i>j的时候,aij=0

大概长这样:

《矩阵乘法(加快速幂)》

 

1.5下三角矩阵

当i<j的时候,aij=0

大概长这样:

《矩阵乘法(加快速幂)》

 

1.6置换矩阵

每一行每一列有且仅有1个1

大概长这样:

《矩阵乘法(加快速幂)》

 

1.7对称矩阵

《矩阵乘法(加快速幂)》  :行与列互换的结果

大概长这样:

 《矩阵乘法(加快速幂)》

 

2.矩阵的运算

2.1加法

2.1.(1)

设A=(aij).B=(bij),为《矩阵乘法(加快速幂)》矩阵,则矩阵和记为C=(cij)=A+B

定义为cij=aij+bij    (i | 1<=i<=m) (j | 1<=j<=n)

2.1(2)

零矩阵式矩阵加法运算的单位元:A+0=A=0+A

2.1(3)

《矩阵乘法(加快速幂)》为常数,则有:《矩阵乘法(加快速幂)》A=《矩阵乘法(加快速幂)》(aij)  => 当《矩阵乘法(加快速幂)》=-1时,A+《矩阵乘法(加快速幂)》A=0=《矩阵乘法(加快速幂)》A+A

2.2减法

由2.1(3)可得A-B=A+(-B)

 

2.3.乘法

2.3.(1)要求:可以相乘的2个矩阵必须满足两个矩阵相容(一个矩阵行数=另一个矩阵列数)

2.3.(2)设:A=(aij)是《矩阵乘法(加快速幂)》矩阵,B=(bij)是《矩阵乘法(加快速幂)》矩阵

那么《矩阵乘法(加快速幂)》=C=(cij)是一个《矩阵乘法(加快速幂)》

《矩阵乘法(加快速幂)》

分析这个公式,可以发现做了《矩阵乘法(加快速幂)》次的乘法与《矩阵乘法(加快速幂)》次的加法

由很多blog说自己推一遍就理解了

但这里给出一个很直观的计算方法:得出来的矩阵第i行第j列=第一个矩阵的第i行m个数与第二个矩阵第j列的m个数的分别乘积的和

《矩阵乘法(加快速幂)》

2.3.(3)性质:

a.不满足交换率,AB!=BA

b.满足分配率,A(B+C)=AB+AC    (B+C)D=BD+CD

c.满足结合律,A(BC)=(AB)C

 

3.快速幂

(blog施工中,请绕行至其他dalao的blog)

 

4.矩阵乘法快速幂

用于优化递推的话,就要写出递推式。

下面给出本题的写法:

斐波那契的递推式是:《矩阵乘法(加快速幂)》

那么可以改写成这个形式:《矩阵乘法(加快速幂)》

以及将f(n-1)写成这个形式《矩阵乘法(加快速幂)》

然后由于矩阵乘法的定义,可以得到这个公式:《矩阵乘法(加快速幂)》

然后将后面的那个矩阵由结合律又可以得出:《矩阵乘法(加快速幂)》

(blog未完成然后就点了发布了!!!???点个收藏尽请期待)

代码

下面是我的学习手记(逃)

《矩阵乘法(加快速幂)》

 

    原文作者:中原睚眦
    原文地址: https://blog.csdn.net/qq_36976937/article/details/102993661
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞