首页 > 其他分享 >矩阵快速幂加速递推

矩阵快速幂加速递推

时间:2023-06-02 13:11:36浏览次数:41  
标签:dots begin end cdot 矩阵 bmatrix 递推 加速

矩阵优化递推的思想在于把递推的层数化为矩阵的幂数,也就是说设计一个矩阵 \(A\),使得 \(A^n\) 中的某个元素就是递推的第 \(n\) 项,即 \(f_n\)。这么做就可以将 \(O(n)\) 的递推优化为 \(O(\log_2 n)\)的矩阵快速幂(矩阵 \(A\) 的行列数为常数,因此快速幂中的矩阵乘法复杂度为常数),本质上是一种倍增做法

具体的讲,假如是我们现在有如下线性递推关系

\[f_n,f_{n-1},f_{n-2},\dots,f_2,f_1 \\ f_n=\{f_{n-1},f_{n-2},\dots,f_{n-k-1}\} \]

其中第二行的 \(\{\}\) 代表一种运算,意味着 \(f_n\) 可以由 \(f_{n-1}\) 到 \(f_{n-k}\) 的这些数做某种运算得出

那我们将这种递推关系转化为矩阵乘法形式(\(A\) 为 \((k+1)\times(k+1)\) 的方阵),得:

\[\begin{bmatrix} f_n & f_{n-1} \dots f_{n-k} \end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n-2} \dots f_{n-k-1} \end{bmatrix} A = \begin{bmatrix} f_{n-2} & f_{n-3} \dots f_{n-k-2} \end{bmatrix} A^2 = \dots = \begin{bmatrix} f_{k} & f_{k-1} \dots f_0 \end{bmatrix} A^{n-k} \]

这样,我们只需要计算到 \(f_k\) ,剩下就交给矩阵快速幂 \(O(\log_2 n)\) 计算 \(A^{n-k}\) 即可


那么,如何设计矩阵 \(A\) 呢?

我们以计算斐波拉契数列为例,首先我们可以很快得出形如上式的矩乘形式

\[\begin{bmatrix} f_n & f_{n-1} \end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n-2} \end{bmatrix} A = \dots = \begin{bmatrix} f_1 & f_0 \end{bmatrix} A^{n-1} \]

那么 \(A\) 一定为一个 \(2\times2\) 的矩阵,我们令其为 \(\begin{bmatrix}a&b\\c&d\end{bmatrix}\) 代入上式 \(\begin{bmatrix}f_n & f_{n-1}\end{bmatrix}=\begin{bmatrix}f_{n-1} & f_{n-2}\end{bmatrix}A\) 得到如下:

\[\begin{bmatrix} f_n & f_{n-1} \end{bmatrix} = \begin{bmatrix} (a\cdot f_{n-1}+c\cdot f_{n-2}) & (b\cdot f_{n-1}+d\cdot f_{n-2}) \end{bmatrix} \]

因此可以得到

\[f_n=a\cdot f_{n-1}+c\cdot f_{n-2}\\f_{n-1}=b\cdot f_{n-1}+d\cdot f_{n-2} \]

代入 \(n\) 较小的值,手工计算出 \(f_n\),\(f_{n-1}\) 和 \(f_{n-2}\),最后得解 \(\begin{cases}a=b=c=1\\d=0\end{cases}\)

因此,\(A=\begin{bmatrix}1&1\\1&0\end{bmatrix}\)

标签:dots,begin,end,cdot,矩阵,bmatrix,递推,加速
From: https://www.cnblogs.com/SkyNet-PKN/p/17451485.html

相关文章

  • 2022-2023 春学期 矩阵与数值分析 C5 插值与逼近
    2022-2023春学期矩阵与数值分析C5插值与逼近C5插值与逼近原文5.1引言有n个插值节点,就有n插值条件,可以构造至多n-1次的插值函数需要考虑简单函数类的选取问题:如代数多项式,三角多项式,分段多项式,有理函数,样条函数等;存在唯一性问题;余项估计问题;收敛性问题等思......
  • HDU4382(特殊的矩阵连乘)
    题目:HarryPotterandCyberSequenceGenerator题意,有两个容器C1,C2,初始的时候C1中有一个数的值为V,给你K个操作,每次都重复这K个操作N遍,最后问你C2中的数是   多少。N<=10^100。1:循环操作的次数巨大,敏感的想到这是矩阵连乘的题目。2:K个操作可以得出一个矩阵,N个K操作就是这个......
  • 系数矩阵为Hessian矩阵时的使用Pearlmutter trick的共轭梯度解法
    共轭梯度法已经在前文中给出介绍:python版本的“共轭梯度法”算法代码  =======================================  使用共轭梯度法时,如果系数矩阵为Hessian矩阵,那么我们可以使用Pearlmuttertrick技术来减少计算过程中的内存消耗,加速计算。 使用Pearlmuttertrick的......
  • 协方差与协方差矩阵
    本文讲的主要内容是协方差以及协方差矩阵。在统计学中,我们见过的最基本的三个概念是均值,方差,标准差。假定给定了n个样本的集合,那么公式如下     均值是描述样本的平均值,标准差描述的是样本集合的各个点到均值距离的平均,体现了样本的散步程度。而方差仅仅是标准差的平方。实际......
  • 1439. 有序矩阵中的第 k 个最小数组和
    给你一个m *n的矩阵mat,以及一个整数k,矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出1个元素形成一个数组。返回所有可能数组中的第k个最小数组和。来源:力扣(LeetCode)链接:https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-so......
  • 在树莓派上实现numpy的conv2d卷积神经网络做图像分类,加载pytorch的模型参数,推理mnist
    这几天又在玩树莓派,先是搞了个物联网,又在尝试在树莓派上搞一些简单的神经网络,这次搞得是卷积识别mnist手写数字识别训练代码在电脑上,cpu就能训练,很快的:importtorchimporttorch.nnasnnimporttorch.optimasoptimfromtorchvisionimportdatasets,transformsimportn......
  • 矩阵
    #define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ inti,j,p; floatarr1[3][3],arr2[3][3],arr[3][3],arr0[3][3]={0}; printf("请输入两个三行三列的矩阵:\n"); for(i=0;i<3;i++) {  for(j=0;j<3;j++)  scanf......
  • python推荐系统实现(矩阵分解来协同过滤)|附代码数据
    原文链接:http://tecdat.cn/?p=10911最近我们被客户要求撰写关于推荐系统的研究报告,包括一些图形和统计输出。用户和产品的潜在特征编写推荐系统矩阵分解工作原理使用潜在表征来找到类似的产品 1.用户和产品的潜在特征我们可以通过为每个用户和每部电影分配属性,然后将它们相......
  • hdu 5171(矩阵快速幂)
    GTY'sbirthdaygiftTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)ProblemDescriptiona,b∈S),andadda+b Input2≤n≤100000,1≤k≤1000000000).Thesecondlinecontainsnelementsai......
  • 前缀和 (Acwing_796 子矩阵的和)
    题目1.S[i,j]即为图1红框中所有数的的和为:S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]2.(x1,y1),(x2,y2)这一子矩阵中的所有数之和为:S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]#include<iostream>usingnamespacestd;constintN=1e3+10;int......