[tju]矩阵的应用.pptVIP

矩阵的应用 Name: ftfish (周伟) School: TJU Major: CS Grade: 2007 Mail: ftfish@acm.org QQ: 155 175 157 2008.7.14 线性递推关系 令h0,h1,h2,…,hn,…表示一个数列 如果存在a1,a2,…,ak,和bn，使得 hn=a1hn-1 + a2hn-2 + … + akhn-k +bn (n≥k) 则称该序列满足k阶线性递推关系 例如： 错位排列数Dn = (n-1)(Dn-1+Dn-2) = nDn-1+(-1)n Fibonacci数Fn= Fn-1+Fn-2 常系数线性齐次递推关系 若数列a1,a2,…,ak均为常数，bn=0 则称{hn}满足常系数线性齐次递推关系 竞赛中经常遇到求解常系数线性齐次递推关系的问题 下面不加证明地给出一般常系数线性齐次递推关系的解法 下面以求解Fibonacci数列Fn为例说明此解法 求解常系数线性齐次递推关系 将递推关系写成： hn + a1hn-1 + a2hn-2 + … + akhn-k =0 的形式 得到方程（称为特征方程）： xk + a1xk-1 + a2xk-2 +…+ak =0 求上述方程的k个根（特征根），得： r1,r2,…,rk（可能有虚数） 若没有重根( ri ≠ rj , i ≠ j )，则递推关系的解为： 求解常系数线性非齐次递推关系 若递推关系非齐次，即 hn=a1hn-1 + a2hn-2 + … + akhn-k +bn (n≥k， bn ≠0) 则问题要稍微复杂些 一般地，线性非齐次递推关系的解，等于其对应的齐次递推关系的通解，加上非齐次递推关系的一个特解 通解可以用前面的方法求得，特解一般需要猜测得到。 非齐次递推关系的特解 经验性的特解列表 bn hn c（常数） r（常数） c*n + d r*n + s c*n2 + d*n + e r*n2+s * n + t n的k次多项式 n的k次多项式 cn r*cn 特征根方法的局限性 首先，必须肯定特征根方法的理论与实践上的价值 但是对于我们来说，它的价值却不像数学中那样大 它有如下局限性： 1、需要求解k阶方程 2、求出的k个根不一定都是实根 3、精度误差 4、…… 矩阵的乘法 设 A=(aij)是一个m×s的矩阵，B=(bij)是一个s×n的矩阵，即A的列数等于B的行数，规定A与B的乘积C=AB是一个m×n的矩阵，且有： 其第i行第j列的元素Cij等于A的第i行各元素与B的第j列对应元素的乘积的和 Fibonacci序列的矩阵求法 考虑1×2的矩阵[Fn-1,Fn-2] 能否找到一个2×2的矩阵A，使得 [Fn-1,Fn-2]×A＝ [Fn,Fn-1]?? Fibonacci序列的矩阵求法 [F2,F1] ×A＝ [F3,F2] [F3,F2] ×A＝ [F4,F3] [F4,F3] ×A＝ [F5,F4] …… [Fn-1,Fn-2]×A＝ [Fn,Fn-1] 矩阵乘法满足结合律 [F2,F1] ×An-2＝ [Fn,Fn-1] 常系数线性齐次递推关系——矩阵乘方解法 上述方法具有一般性 对于一般的k阶常系数线性齐次递推关系， 1、写出一个1×k的矩阵[Fn-1,Fn-2,…,Fn-k] 2、根据递推关系，求出k×k的矩阵A 3、利用分治法求A的幂 4、用初始条件[Fk,Fk-1,…,F1]左乘A的幂 5、输出所得矩阵相应位置的元素 常系数线性齐次递推关系——前n项和求法 如果我们想要求Sn=F1+F2+…+Fn 设有1×3的矩阵[Fn-1,Fn-2,Sn-2] 能否找到矩阵A，使得 [Fn-1,Fn-2,Sn-2]×A＝ [Fn,Fn-1,Sn-1]？ 常系数线性非齐次递推关系 如果Fn=Fn-1+Fn-2+1，如何求得Fn？ 考虑1×3的矩阵[Fn-1,Fn-2,1] 寻找矩阵A，使得 [Fn-1,Fn-2,1]×A＝ [Fn,Fn-1,1] 常系数线性非齐次递推关系——综合例题 Fn = Fn-1 + 2Fn-2 + 3n + 4 F1 = F2 = 1 n 231 矩阵乘方例题 给出一个k×k的矩阵A，求矩阵S： S = A + A2 + A3 + … + An 考虑矩阵[An-1,Sn-2] 求出矩阵M，使得 [An-1,Sn-2]×M＝ [An,Sn-1] Magic Bean 有种诡异的豆，把它放在一张有向图的结点1上。每一时刻，它可以跳到图中相邻的结点上，或者原地不动，或者爆炸 求在T时间内，这个豆子可能有多少种路径 T≤106，N≤20 TOJ 2871.