计算机算法：递推法

递推法

递推是计算机数值算法中的重要算法。递推的思路是通过数学推导将复杂的运算化解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。

递推法通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

递推法的解题步骤：

⑴按次序研究集合中最初最原始的若干问题。

⑵按次序寻求集合中问题间的转换规律即递推关系，使问题逐次转化成较低层级或简

单的且能解决问题的或已解决的问题。

递推法在解题中的应用：递推法在解题中的应用十分广泛，递推法的特征是化难为易、化繁为简。使用递推法时，先考虑与题目有关系的另一个较为简单的问题，并加以解决。然后以此为基础，寻求规律，一步一步递推出原题的解答。按照推导问题的方向递推分为逆推法和顺推法两种。

所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。

所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

示例1：逆推法示例。猴子第1天摘下若干个桃子，当即吃了一半又一个。第2天又把剩下的桃吃了一半有一个，以后每天都吃前一天剩下的桃子的一半又一个，到第10天猴子想吃的时候，只剩下一个桃子。问猴子第1天一共摘了多少桃子？

【分析】

已知条件第10天剩下1个桃子，隐含条件每一次前一天的桃子个数等于后一天桃子的个数加1的2倍。采用逆向思维的方法，从后往前推，可用逆推法求解。

【算法】算法描述如下：

#include

Main()

{ int a=1,I;

For (i=9;i>=1;i--)

a=(a+1)*2

Printf(“%d”,a);

}

示例2：顺推法示例。有一段楼梯有10段台阶，规定每一步只能跨一级或两级，问：要登上第10级台阶有多少种不同的走法？

【分析】

跨到第二级台阶，可以每次跨一级，也可以一次跨二级，共有2种不同的走法。

第三级台阶，可以由第一级台阶跨二级台阶到达，也可以由第二级台阶跨一级到达。而到达第一级和第二级台阶各有1、2种不同的走法，所以到达第三级台阶共有1+2=3种不同的走法。以下类推。所以，登上第三阶、第四阶、…的不同走法次数依次为登上它的前两个台阶走法数的和。即依次为1，2，3，5，8，13，21，34，55，89，…

所以登上第十级台阶共有89种不同的走法。这列数为斐波纳次数列。

【算法】算法用伪代码描述如下：

f1=1;

f2=2;

For n=3 to 10 do

{f n=f n-1+f n-2;

writeln(f n);

}

由此可见递推关系是一种简洁高效的常见数学模型。在递推问题中，每个数据项都和它前面的若干个数据项（或后面的如干个数据项）有一定的关联，这种关联一般通过“递推关系式”表示。问题求解一般从初始的一个或如干个数据项出发，通过递推关系逐步推出，从而得到最终结果，这种求解问题的方法叫“递推法”。其中初始的如干数据项成为“边界”。

。

(完整版)已知数列递推公式求通项公式的几种方法

求数列通项公式的方法 一、公式法 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则113222n n n n a a ++-=，故数列{}2 n n a 是以1222 a 1 1==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31()222 n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 11 3 222 n n n n a a ++-=，说明数列{}2n n a 是等差数列，再直接利用等差数列的通项公式求出31(1)22 n n a n =+-，进而求出数列{}n a 的通项公式。 二、累加法 例2 已知数列{}n a 满足1121 1n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 11232211 2 ()()()()[2(1)1][2(2)1](221)(211)1 2[(1)(2)21](1)1 (1)2(1)1 2 (1)(1)1n n n n n a a a a a a a a a a n n n n n n n n n n n ---=-+-++-+-+=-++-+++?++?++=-+-++++-+-=+-+=-++=L L L 所以数列{}n a 的通项公式为2 n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-++-+-+L ，即得数列{}n a 的通项公式。

九类常见递推数列求通项公式方法

递推数列通项求解方法举隅 类型一：1n n a pa q +=+（1p ≠） 思路1（递推法）：()123()n n n n a pa q p pa q q p p pa q q q ---??=+=++=+++=?? ……121(1n p a q p p -=++++…211)11n n q q p a p p p --??+=+ ?+ ? --??。 思路2（构造法）：设()1n n a p a μμ++=+，即()1p q μ-=得1 q p μ= -，数列{}n a μ+是以1a μ+为首项、p 为公比的等比数列，则1 111n n q q a a p p p -??+ =+ ?--?? ，即1111n n q q a a p p p -??=++ ? --?? 。 例1 已知数列{}n a 满足123n n a a -=+且11a =，求数列{}n a 的通项公式。 解：方法1（递推法）： ()123232(23)3222333n n n n a a a a ---??=+=++=+++=??…… 1223(122n -=++++ (211) 332)12232112n n n --+??+=+?+=- ? --?? 。 方法2（构造法）：设()12n n a a μμ++=+，即3μ=，∴数列{}3n a +是以134a +=为首项、2为公比的等比数列，则1 1342 2n n n a -++=?=，即123n n a +=-。 类型二：1()n n a a f n +=+ 思路1（递推法）： 123(1)(2)(1)(3)(2)(1)n n n n a a f n a f n f n a f n f n f n ---=+-=+-+-=+-+-+-= …1 11 ()n i a f n -==+ ∑。

由递推公式求通项公式的方法

由递推公式求通项公式的方法 已知数列的递推公式，求取其通项公式是数列中一类常见的题型，这类题型如果单纯的看某一个具体的题目，它的求解方法灵活是灵活多变的，构造的技巧性也很强，但是此类题目也有很强的规律性，存在着解决问题的通法，本文就高中数学中常见的几类题型从解决通法上做一总结，方便于学生学习和老师的教学，不涉及具体某一题目的独特解法与技巧。 一、1()n n a a f n +=+型数列，（其中()f n 不是常值函数) 此类数列解决的办法是累加法，具体做法是将通项变形为1()n n a a f n +-=，从而就有 21321(1),(2),,(1).n n a a f a a f a a f n --=-=-=- 将上述1n -个式子累加，变成1(1)(2)(1)n a a f f f n -=+++- ，进而求解。 例1. 在数列{}n a 中,112,21,.n n n a a a n a +==+-求 解：依题意有 213211,3,,23n n a a a a a a n --=-=-=- 逐项累加有221(123)(1)1323(1)212n n n a a n n n n +---=+++-= =-=-+ ，从而223n a n n =-+。 注：在运用累加法时,要特别注意项数,计算时项数容易出错. 变式练习：已知{}n a 满足11=a ,) 1(11+=-+n n a a n n ,求}{n a 的通项公式。 二、)(1n f a a n n ?=+型数列，（其中()f n 不是常值函数) 此类数列解决的办法是累积法，具体做法是将通项变形为1()n n a f n a +=，从而就有 32121 (1),(2),,(1)n n a a a f f f n a a a -===- 将上述1n -个式子累乘，变成1 (1)(2)(1)n a f f f n a =???- ，进而求解。 例2. 已知数列{}n a 中11123,(2)321 n n n a a a n n --==?≥+，求数列{}n a 的通项公式。

用matlab实现最小二乘递推算法辨识系统参数

用matlab实现最小二乘递推算法辨识系统参 数 自动化系统仿真实验室指导教师： 学生姓名班级计082-2 班学号撰写时间： 全文结束》》-3-1 成绩评定： 一．设计目的 1、学会用Matlab实现最小二乘法辨识系统参数。 2、进一步熟悉Matlab的界面及基本操作； 3、了解并掌握Matlab中一些函数的作用与使用；二．设计要求最小二乘递推算法辨识系统参数，利用matlab编程实现，设初始参数为零。z(k)-1、5*z(k-1)+0、7*z(k-2)=1*u(k-1)+0、5*u(k-2)+v(k); 选择如下形式的辨识模型：z(k)+a1*z(k- 1)+a2*z(k-2)=b1*u(k-1)+b2*u(k-2)+v(k);三．实验程序 m=3;N=100;uk=rand(1,N);for i=1:Nuk(i)=uk(i)*(-1)^(i-1);endyk=zeros(1,N); for k=3:N yk(k)=1、5*yk(k-1)-0、 7*yk(k-2)+uk(k-1)+0、5*uk(k-2); end%j=100;kn=0;%y=yk(m:j);%psi=[yk(m-1:j-1);yk(m-2:j-2);uk(m-1:j-1);uk(m-2:j- 2)];%pn=inv(psi*psi);%theta=(inv(psi*psi)*psi*y);theta=[0 ;0;0;0];pn=10^6*eye(4);for t=3:Nps=([yk(t-1);yk(t-

2);uk(t-1);uk(t-2)]);pn=pn- pn*ps*ps*pn*(inv(1+ps*pn*ps));theta=theta+pn*ps*(yk(t)-ps*theta);thet=theta;a1=thet(1);a2=thet(2);b1=thet(3);b2= thet(4); a1t(t)=a1;a2t(t)=a2;b1t(t)=b1;b2t(t)=b2;endt=1:N;plot(t,a 1t(t),t,a2t(t),t,b1t(t),t,b2t(t));text(20,1、 47,a1);text(20,-0、67,a2);text(20,0、97,b1);text(20,0、47,b2);四．设计实验结果及分析实验结果图：仿真结果表明，大约递推到第步时，参数辨识的结果基本到稳态状态，即a1=1、5999，b1=1，c1=0、5，d1=-0、7。五、设计感受这周的课程设计告一段落了，时间短暂，意义重大。通过这次次练习的机会，重新把matlab课本看了一遍，另外学习了系统辨识的有关内容，收获颇丰。对matlab的使用更加纯熟，也锻炼了自己在课本中搜索信息和知识的能力。在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。同时我也进一步认识了matlab软件强大的功能。在以后的学习和工作中必定有很大的用处。

递推最小二乘法推导(RLS)——全网最简单易懂的推导过程

递推最小二乘法推导（RLS）——全网最简单易懂的推导过程 作者：阿Q在江湖 先从一般最小二乘法开始说起 已知x和y的一系列数据，求解参数theta的估计。用矩阵的形式来表达更方便一些： 其中k代表有k组观测到的数据， 表示第i组数据的输入观测量，yi表示第i组数据的输出观测量。令： ，则最小二乘的解很简单， 等价于即参数解为：如果数据是在线的不断的过来，不停的采用最小二乘的解法来解是相当消耗资源与内存的，所

以要有一种递推的形式来保证对的在线更新。 进一步推导出递推最小二乘法（RLS） 我们的目的是从一般最小二乘法的解 推导出 的递推形式。一定要理解这里的下标k代表的意思，是说在有k组数据情况下的预测，所以k比k-1多了一组数据，所以可以用这多来的一组数据来对原本的估计进行修正，这是一个很直观的理解。下面是推导过程： 先看一般最小二乘法的解 下面分别对 和 这两部分进行推导变换，令

得到下面公式（1） 下面来变换得到公式（2） 下面再来，根据一般最小二乘法的解，我们知道下式成立，得到公式（3）（注：后续公式推导用到） 好了，有了上面最主要的三步推导，下面就简单了,将上面推导的结果依次代入公式即可：

至此，终于变成 的形式了。 通过以上推导，我们来总结一下上面RLS方程： 注：以上公式7中，左边其实是根据公式1，右边I为单位矩阵

公式（5）和（7）中，有些文献资料是用右边的方程描述，实际上是等效的，只需稍微变换即可。例如（5）式右边表达式是将公式（1）代入计算的。为简化描述，我们下面还是只讨论左边表达式为例。 上面第7个公式要计算矩阵的逆，求逆过程还是比较复杂，需要用矩阵引逆定理进一步简化。 矩阵引逆定理： 最终RLS的方程解为：

几种最小二乘法递推算法的小结

一、 递推最小二乘法 递推最小二乘法的一般步骤： 1. 根据输入输出序列列出最小二乘法估计的观测矩阵?： ] )(u ... )1( )( ... )1([)(T b q n k k u n k y k y k ------=? 没有给出输出序列的还要先算出输出序列。 本例中， 2)]-u(k 1),-u(k 2),-1),-y(k -[-y(k )(T =k ?。 2. 给辨识参数θ和协方差阵P 赋初值。一般取0θ=0或者极小的数，取σσ,20I P =特别大，本例中取σ=100。 3. 按照下式计算增益矩阵G ： ) ()1()(1)()1()(k k P k k k P k G T ???-+-= 4. 按照下式计算要辨识的参数θ： )]1(?)()()[()1(?)(?--+-=k k k y k G k k T θ?θθ 5. 按照下式计算新的协方差阵P ： )1()()()1()(---=k P k k G k P k P T ? 6. 计算辨识参数的相对变化量，看是否满足停机准则。如满足，则不再递推；如不满足， 则从第三步开始进行下一次地推，直至满足要求为止。 停机准则：ε???<--) (?)1(?)(?max k k k i i i i 本例中由于递推次数只有三十次，故不需要停机准则。 7. 分离参数：将a 1….a na b 1….b nb 从辨识参数θ中分离出来。 8. 画出被辨识参数θ的各次递推估计值图形。 为了说明噪声对递推最小二乘法结果的影响，程序5-7-2在计算模拟观测值时不加噪 声， 辨识结果为a1 =1.6417，a2 = 0.7148，b1 = 0.3900，b2 =0.3499，与真实值a1 =1.642， a2 = 0.715， b1 = 0.3900，b2 =0.35相差无几。 程序5-7-2-1在计算模拟观测值时加入了均值为0，方差为0.1的白噪声序列，由于噪 声的影响，此时的结果为变值，但变化范围较小，现任取一组结果作为辨识结果。辨识结果为a1 =1.5371， a2 = 0.6874， b1 = 0.3756，b2 =0.3378。 程序5-7-2-2在计算模拟观测值时加入了有色噪声，有色噪声为 E(k)+1.642E(k-1)+0.715E(k-2)，E(k)是均值为0，方差为0.1的白噪声序列，由于有色噪声的影响，此时的辨识结果变动范围远比白噪声时大，任取一组结果作为辨识结果。辨识结果为a1 =1.6676， a2 = 0.7479， b1 = 0.4254，b2 =0.3965。 可以看出，基本的最小二乘法不适用于有色噪声的场合。

递推最小二乘法算法

题目： （递推最小二乘法） 考虑如下系统： )()4(5.0)3()2(7.0)1(5.1)(k k u k u k y k y k y ξ+-+-=-+-- 式中，)(k ξ为方差为0.1的白噪声。 取初值I P 610)0(=、00=∧ ）（θ。选择方差为1的白噪声作为输入信号)(k u ，采用PLS 法进行参数估计。 Matlab 代码如下： clear all close all L=400; %仿真长度 uk=zeros(4,1); %输入初值：uk(i)表示u(k-i) yk=zeros(2,1); %输出初值 u=randn(L,1); %输入采用白噪声序列 xi=sqrt(0.1)*randn(L,1); %方差为0.1的白噪声序列 theta=[-1.5;0.7;1.0;0.5]; %对象参数真值 thetae_1=zeros(4,1); %（）θ初值 P=10^6*eye(4); %题目要求的初值 for k=1:L phi=[-yk;uk(3:4)]; %400×4矩阵phi 第k 行对应的y(k-1),y(k-2),u(k-3), u(k-4) y(k)=phi'*theta+xi(k); %采集输出数据 %递推最小二乘法的递推公式 K=P*phi/(1+phi'*P*phi); thetae(:,k)=thetae_1+K*(y(k)-phi'*thetae_1); P=(eye(4)-K*phi')*P; %更新数据 thetae_1=thetae(:,k); for i=4:-1:2 uk(i)=uk(i-1); end uk(1)=u(k); for i=2:-1:2 yk(i)=yk(i-1);

由递推公式求通项公式的三种方法

由递推公式求通项公式的三种方法 递推公式和通项公式是数列的两种表示方法，它们都可以确定数列中的任意一项，只是由递推公式确定数列中的项时，不如通项公式直接，下面介绍由递推公式求通项公式的几种方法． 1．累加法 [典例1] 数列{a n }的首项为3，{b n }为等差数列且b n ＝a n ＋1－a n (n ∈N * )．若b 3＝－2，b 10＝12，则a 8＝( ) A ．0 B ．3 C ．8 D ．11 [解析] 由已知得b n ＝2n －8，a n ＋1－a n ＝2n －8，所以a 2－a 1＝－6，a 3－a 2＝－4，…，a 8－a 7＝6，由累加法得a 8－a 1＝－6＋(－4)＋(－2)＋0＋2＋4＋6＝0，所以a 8＝a 1＝3. [答案] B [题后悟道] 对形如a n ＋1＝a n ＋f (n )(f (n )是可以求和的)的递推公式求通项公式时，常用累加法，巧妙求出a n －a 1与n 的关系式． 2．累乘法 [典例2] 已知数列{a n }中，a 1＝1，前n 项和S n ＝ n ＋23a n . (1)求a 2，a 3； (2)求{a n }的通项公式． [解] (1)由S 2＝43 a 2得3(a 1＋a 2)＝4a 2， 解得a 2＝3a 1＝3. 由S 3＝53 a 3得3(a 1＋a 2＋a 3)＝5a 3， 解得a 3＝32 (a 1＋a 2)＝6. (2)由题设知a 1＝1. 当n >1时，有a n ＝S n －S n －1＝n ＋23a n －n ＋13 a n －1，

整理得a n ＝n ＋1n －1 a n －1. 于是a 2＝31a 1，a 3＝42a 2，…，a n －1＝n n －2a n －2，a n ＝n ＋1n －1 a n －1. 将以上n －1个等式中等号两端分别相乘，整理得a n ＝ n n ＋1 2. 综上可知，{a n }的通项公式a n ＝ n n ＋1 2. [题后悟道] 对形如a n ＋1＝a n f (n )(f (n )是可以求积的)的递推公式求通项公式时，常用累乘法，巧妙求出a n a 1与n 的关系式． 3．构造新数列 [典例3] 已知数列{a n }满足a 1＝1，a n ＋1＝3a n ＋2；则a n ＝________. [解析] ∵a n ＋1＝3a n ＋2，∴a n ＋1＋1＝3(a n ＋1)， ∴a n ＋1＋1a n ＋1 ＝3，∴数列{a n ＋1}为等比数列，公比q ＝3， 又a 1＋1＝2，∴a n ＋1＝2·3 n －1， ∴a n ＝2·3n －1－1. [答案] 2×3 n －1－1 [题后悟道] 对于形如“a n ＋1＝Aa n ＋B (A ≠0且A ≠1)”的递推公式求通项公式，可用迭代法或构造等比数列法． 上面是三种常见的由递推公式求通项公式的题型和对应解法，从这些题型及解法中可以发现，很多题型及方法都是相通的，如果能够真正理解其内在的联系及区别，也就真正做到了举一反三、触类旁通，使自己的学习游刃有余，真正成为学习的主人．

九类常见递推数列求通项公式方法

递推数列通项求解方法 类型一：1n n a pa q += +（1p ≠） 思路1（递推法）：()123()n n n n a pa q p pa q q p p pa q q q ---??=+=++=+++=?? ......121(1n p a q p p -=++++ (2) 1 1)11n n q q p a p p p --??+=+?+ ? --?? 。 思路2（构造法）：设()1n n a p a μμ++=+，即()1p q μ-=得1 q p μ= -，数列 {}n a μ+是以1a μ+为首项、p 为公比的等比数列，则1 111n n q q a a p p p -??+ =+ ?--??，即1111n n q q a a p p p -??=++ ? --?? 。 例1 已知数列{}n a 满足123n n a a -=+且11a =，求数列{}n a 的通项公式。 解：方法1（递推法）： ()123232(23)3222333n n n n a a a a ---??=+=++=+++=?? (1) 22 3(122n -=++++ (2) 11 332 )12232112n n n --+??+=+?+=- ? --? ?。 方法2（构造法）：设()12n n a a μμ++=+，即3μ=，∴数列{}3n a +是以134 a +=为首项、2为公比的等比数列，则113422n n n a -++=?=，即1 23n n a +=-。

1n n +思路1（递推法）： 123(1)(2)(1)(3)(2)(1)n n n n a a f n a f n f n a f n f n f n ---=+-=+-+-=+-+-+-= …1 11 ()n i a f n -==+∑。 思路2（叠加法）：1(1)n n a a f n --=-，依次类推有：12(2)n n a a f n ---=-、 23(3)n n a a f n ---=-、…、21(1)a a f -=，将各式叠加并整理得1 11 ()n n i a a f n -=-= ∑ ，即 1 11 ()n n i a a f n -==+ ∑ 。 例2 已知11a =，1n n a a n -=+，求n a 。 解：方法1（递推法）：123(1)(2)(1)n n n n a a n a n n a n n n ---=+=+-+=+-+-+= ......1[23a =+++ (1) (1)(2)(1)]2 n i n n n n n n =++-+-+= = ∑ 。 方法2（叠加法）：1n n a a n --=，依次类推有：121n n a a n ---=-、232n n a a n ---=-、…、 212a a -=，将各式叠加并整理得12 n n i a a n =-= ∑ ，12 1 (1)2 n n n i i n n a a n n ==+=+ = = ∑ ∑ 。

递推公式求通项公式的几种方

由递推公式求通项公式的常用方法 由数列的递推公式求通项公式是高中数学的重点问题，也是难点问题，它是历年高考命题的热点题。对于递推公式确定的数列的求解，通常可以通过递推公式的变换，转化为等差数列或等比数列问题，有时也用到一些特殊的转化方法与特殊数列。 方法一：累加法 形如a n +1－a n ＝f (n )（n ＝2,3,4,…）,且f (1)＋f (2)＋…＋f (n -1)可求，则用累加法求a n 。有时若不能直接用，可变形成这种形式，然后利用这种方法求解。 例1：（07年北京理工农医类）已知数列{a n }中，a 1＝2,a n ＋1＝a n ＋cn (c 是常数，n ＝1,2,3,…)且a 1,a 2,a 3成公比不为1的等比数列 （1）求c 的值 （2）求{a n }的通项公式 解：（1）a1,a2,a3成公比不为1的等比数列 2 022)2(2)() ,3,2,1(111113 12 2===++?=+∴=+=?=∴+c c a c c a a c a n cn a a a a a n n 因此（舍去）或解得又 （2）由（1）知n a a n a a n n n n 2,211=-+=++即，将n ＝1,2, …,n －1,分别代入 ) 1(2322 2121342312-=-?=-?=-?=--n a a a a a a a a n n 将上面n －1个式子相加得a n －a 1＝2(1＋2＋3＋…＋n －1)＝n 2 －n 又a 1＝2,a n ＝n 2 －n ＋2 方法二：累乘法 形如 a n +1 a n ＝g (n )（n ＝2,3,4…），且f (1)f(2)…f (n －1)可求，则用累乘法求a n .有时若不能直接用，可变形成这种形式，然后用这种方法求解。

递推关系求通项公式教案

教 案 课题：递推关系求通项公式 课型： 习题课 授课人：呼延敏 要点自主整合：累加法、累乘法两种基本的由递推公式求通项 教学目标: 【知识目标】 累加法、累乘法的应用 【能力目标】 培养学生的发散思维能力，进而提高转化与化归能力的培养. 【情感目标】培养学生的创新意识与创新思维，培养学生的合作探究意识 。 学生能够通过等差、等比数列的通项公式推导得到累加法、累乘法两种基 本的由递推公式求通项公式的方法，并进一步拓展到“构造法”，在此过程中使学生的思维空间得以拓展，养成善于观察，勇于创新的学习精神。 教学重点：已知数列递推关系求通项关系的几种基本类型。 教学难点：累加法、累乘法的应用 教学过程： 引 例： 11=a n n a a +=+21 求n a 提问：等差数列的通项公式的推导方法是什么? 学生答：…………… 类型<一> 形如a 1=a, a n+1=a n +f ()n 型 其中f ()n 为可求和数列采用累 加法求通项 例1：数列{}n a 中a 1=1 a n+1=2n+a n 求a n 解析： a n+1—a n =2n ∴当n 2≥时a n —a n-1=2()1-n a 2—a 1=2 a 3—a 2=4

a 4—a 3=6 ..…… a n —a n-1=2()1-n 对上面的n-1个式子相加得到：a n =n 2—n+1 变式训练1：数列中{}n a a 1=1 a n+1=a n +2n 求a n 类型<二> 形如a 1=a, a n+1=a n *f ()n 型 采用累乘法 在引例1中将加号+变为乘号*即得到一个等比数列11=a n n a a *=+21 让学生回顾：等比数列中通项公式的推导方法是什么？ 学生答：………… 将变式训练1中的加号+变为乘号*得到如下例题 例2：数列中{}n a 11=a n n n a a 21*=+ 求n a 解析： 1+n a = n n a 2* ∴当2≥n 时 11 2--=n n n a a 21 2=a a 22 32=a a 3342=a a ……….. 11 2--=n n n a a

系统辨识及其matlab仿真(一些噪声和辨识算法)

【1】随机序列产生程序 【2】白噪声产生程序 【3】M序列产生程序 【4】二阶系统一次性完成最小二乘辨识程序 【5】实际压力系统的最小二乘辨识程序 【6】递推的最小二乘辨识程序 【7】增广的最小二乘辨识程序 【8】梯度校正的最小二乘辨识程序 【9】递推的极大似然辨识程序 【10】Bayes辨识程序 【11】改进的神经网络MBP算法对噪声系统辨识程序【12】多维非线性函数辨识程序的Matlab程序【13】模糊神经网络解耦Matlab程序 【14】F-检验法部分程序 【1】随机序列产生程序 A=6; x0=1;M=255; for k=1:100 x2=A*x0; x1=mod (x2,M); v1=x1/256; v(:,k)=v1; x0=x1; v0=v1; end v2=v k1=k; %grapher k=1:k1; plot(k,v,k,v,'r'); xlabel('k'), ylabel('v');title('(0,1)均匀分布的随机序列') 【2】白噪声产生程序 A=6; x0=1; M=255; f=2; N=100; for k=1:N x2=A*x0; x1=mod (x2,M); v1=x1/256; v(:,k)=(v1-0.5)*f; x0=x1;

v0=v1; end v2=v k1=k; %grapher k=1:k1; plot(k,v,k,v,'r'); xlabel('k'), ylabel('v');title('(-1,+1)均匀分布的白噪声') 【3】M序列产生程序 X1=1;X2=0;X3=1;X4=0; %移位寄存器输入Xi初T态（0101），Yi为移位寄存器各级输出m=60; %置M序列总长度 for i=1:m %1# Y4=X4; Y3=X3; Y2=X2; Y1=X1; X4=Y3; X3=Y2; X2=Y1; X1=xor(Y3,Y4); %异或运算 if Y4==0 U(i)=-1; else U(i)=Y4; end end M=U %绘图 i1=i k=1:1:i1; plot(k,U,k,U,'rx') xlabel('k') ylabel('M序列') title('移位寄存器产生的M序列') 【4】二阶系统一次性完成最小二乘辨识程序 %FLch3LSeg1 u=[-1,1,-1,1,1,1,1,-1,-1,-1,1,-1,-1,1,1]; %系统辨识的输入信号为一个周期的M序列 z=zeros(1,16); %定义输出观测值的长度 for k=3:16 z(k)=1.5*z(k-1)-0.7*z(k-2)+u(k-1)+0.5*u(k-2); %用理想输出值作为观测值 end subplot(3,1,1) %画三行一列图形窗口中的第一个图形 stem(u) %画出输入信号u的经线图形 subplot(3,1,2) %画三行一列图形窗口中的第二个图形 i=1:1:16; %横坐标范围是1到16，步长为1 plot(i,z) %图形的横坐标是采样时刻i, 纵坐标是输出观测值z, 图形格式为连续曲线

用matlab实现最小二乘递推算法辨识系统参数

自动化专业综合设计报告 设计题目：最小二乘递推算法辨识系统参数所在实验室：自动化系统仿真实验室 指导教师： 学生姓名 班级计082-2 班 学号 撰写时间：2012-3-1 成绩评定：

一．设计目的 1、学会用Matlab实现最小二乘法辨识系统参数。 2、进一步熟悉Matlab的界面及基本操作； 3、了解并掌握Matlab中一些函数的作用与使用； 二．设计要求 最小二乘递推算法辨识系统参数，利用matlab编程实现，设初始参数为零。z(k)-1.5*z(k-1)+0.7*z(k-2)=1*u(k-1)+0.5*u(k-2)+v(k); 选择如下形式的辨识模型： z(k)+a1*z(k-1)+a2*z(k-2)=b1*u(k-1)+b2*u(k-2)+v(k); 三．实验程序 m= 3; N=100; uk=rand(1,N); for i=1:N uk(i)=uk(i)*(-1)^(i-1); end yk=zeros(1,N); for k=3:N yk(k)=1.5*yk(k-1)-0.7*yk(k-2)+uk(k-1)+0.5*uk(k-2); end %j=100;kn=0; %y=yk(m:j)'; %psi=[yk(m-1:j-1);yk(m-2:j-2);uk(m-1:j-1);uk(m-2:j-2)]'; %pn=inv(psi'*psi); %theta=(inv(psi'*psi)*psi'*y); theta=[0;0;0;0]; pn=10^6*eye(4); for t=3:N ps=([yk(t-1);yk(t-2);uk(t-1);uk(t-2)]); pn=pn-pn*ps*ps'*pn*(inv(1+ps'*pn*ps)); theta=theta+pn*ps*(yk(t)-ps'*theta); thet=theta'; a1=thet(1); a2=thet(2); b1=thet(3); b2=thet(4); a1t(t)=a1; a2t(t)=a2;b1t(t)=b1;b2t(t)=b2; end t=1:N; plot(t,a1t(t),t,a2t(t),t,b1t(t),t,b2t(t));

递推阻尼最小二乘法辨识算法公式的详细推导与说明

控制理论与控制工程 学位课程《系统辨识》考试报告 递推阻尼最小二乘法公式详细 推导 专业：控制理论与控制工程 班级：2011双控（研） 学生姓名：江南 学号：20110201016 任课教师：蔡启仲老师 2012年06月29 日

摘要 在参数辨识中，递推最小二乘法是用得最多的一种算法。但是，最小二乘法存在一些缺点，如随着协方差矩阵的减小，易产生参数爆发现象；参数向量和协方差矩阵的处置选择不当会使得辨识过程在参数收敛之前结束；在存在随机噪声的情况下，参数易产生漂移，出现不稳定等。为了防止参数爆发现象，Levenberg 提出在参数优化算法中增加一个阻尼项，以增加算法的稳定性。本文在一般的最小二乘法中增加了阻尼因子，构成了阻尼最小二乘法。又根据实时控制的要求，详细推到了递推阻尼最小二乘公式，实现在线辨识。 关键字：系统辨识，最小二乘法，递推算法 正文 1.题目的基本要求 已知单入单出系统的差分方程以及噪声，在应用最小二乘法进行辨识的时候，在性能指标中加入阻尼因子，详细推导阻尼最小二乘法的递推公式。 2.输入辨识信号和系统噪声的产生方法和理论依据 2.1系统辩识信号输入选择准则 （1）输入信号的功率或副度不宜过大，以免使系统工作在非线性区，但也不应过小，以致信噪比太小，直接影响辩识精度； （2）输入信号对系统的“净扰动”要小，即应使正负向扰动机会几乎均等； （3）工程上要便于实现，成本低。 2.2白噪声及其产生方法 （1） 白噪声过程 （2）白噪声是一种均值为0、谱密度为非0常数的平稳随机过程。 （3）白噪声过程定义：如果随机过程 () t ω的均值为0，自相关函数为 ()()2 R t t ωσδ= （2.2.1） 式中()t δ 为狄拉克（Dirac) 分布函数，即 (){ (),00,0 1t t t dt δδ∞ ∞=≠∞ ==? -且t （2.2.2） 则称该随机过程为白燥声过程。 2.3白噪声序列 (1) 定义 如果随机序列{() }w t 均值为0，并且是两两不相关的，对应的自相关函数为 ()2 ,0,1,2w l R l l σδ==±± 式中{1,0 0,0 l l l δ=≠=则称这种随机序列{()}w t 为白噪声序列。 2.4白噪声序列的产生方法 (1) （0，1）均匀分布随机数的产生 在计算机上产生（0，1）均匀分布随机数的方法很多，其中最简单、最方便的是数学方法。产生伪随机数的数学方法很多，其中最常用的是乘同余法和混合同余法。 ①乘同余法。

数列递推公式的九种方法

求递推数列的通项公式的九种方法 利用递推数列求通项公式，在理论上和实践中均有较高的价值.自从二十世纪八十年代以来，这一直是全国高考和高中数学联赛的热点之一. 一、作差求和法 例1 在数列{}中，31 =a , ) 1(11++ =+n n a a n n ，求通项公式. 解：原递推式可化为：1 111 +- + =+n n a a n n 则, 2 11112 -+=a a 3 12123-+ =a a 4 13134-+ =a a ，……，n n a a n n 1111--+ =-逐项相加得：n a a n 111- +=. 故n a n 14- =. 二、作商求和法 例 2 设数列{}是首项为1的正项数列，且 0)1(12 2 1 =+-+++n n n n a a na a n （n=1,2,3…） ，则它的通项公式是=▁▁▁（2000年高考15题） 解：原递推式可化为： ) ]()1[(11n n n n a a na a n +-+++=0 ∵ n n a a ++1＞0， 1 1+=+n n a a n n 则 ,4 3,32,21342312===a a a a a a ……，n n a a n n 11 -= - 逐项相乘得： n a a n 1 1=，即=n 1. 三、换元法 例3 已知数列{}，其中9 13,3421 == a a ，且当n ≥3时， ) (3 1 211----=-n n n n a a a a ，求通项公式（1986年高考文科第八

题改编）. 解：设1 1 ---=n n n a a b ，原递推式可化为： } {,3 1 21n n n b b b --=是一个等比数列，9 1 3491312 1 =-= -=a a b ，公比为3 1.故n n n n b b )3 1 ()31(91)31(2211 ==?=---.故n n n a a )3 1 (1=--.由逐差法可得： n n a )3 1(2123-= . 例4已知数列{}，其中2,12 1 ==a a ，且当n ≥3时，122 1 =+---n n n a a a ，求通项公式。解 由122 1 =+---n n n a a a 得：1)()(2 1 1 =------n n n n a a a a ，令1 1 ---=n n n a a b ，则上式为12 1 =---n n b b ，因此是一个等差数列，1121=-=a a b ，公差为1.故n b n =.。 由于112312121-=-++-+-=+++--n n n n a a a a a a a b b b ΛΛ 又2 )1(12 1 -= +++-n n b b b n Λ 所以)1(2 1 1-= -n n a n ，即)2(2 12 +-= n n a n 四、积差相消法 例5设正数列，，…，，…满足2 -n n a a 2 1---n n a a = ) 2(≥n 且11 ==a a ，求的通项公式. 解 将递推式两边同除以2 1--n n a a 整理得：122 1 1=----n n n n a a a a 设= 1 -n n a a ，则0 11 a a b = =1，1 21=--n n b b ，故有 1 212=-b b ⑴122 3 =-b b ⑵ … … … …

常见递推数列通项公式的求法典型例题及习题

.. . 常见递推数列通项公式的求法典型例题及习题 【典型例题】 [例1] b ka a n n +=+1型。 （1）1=k 时，}{1n n n a b a a ?=-+是等差数列，)(1b a n b a n -+?= （2）1≠k 时，设)(1m a k m a n n +=++ ∴ m km ka a n n -+=+1 比较系数：b m km =- ∴ 1-= k b m ∴ }1{-+ k b a n 是等比数列，公比为k ，首项为11-+k b a ∴ 11)1(1-?-+=-+ n n k k b a k b a ∴ 1)1(11--?-+=-k b k k b a a n n [例2] )(1n f ka a n n +=+型。 （1）1=k 时，)(1n f a a n n =-+，若)(n f 可求和，则可用累加消项的方法。 例：已知}{n a 满足11=a ，)1(1 1+= -+n n a a n n 求}{n a 的通项公式。 解： ∵ 11 1)1(11+- =+= -+n n n n a a n n ∴ n n a a n n 1111--= -- 112121---=---n n a a n n 21 3132-- -= ---n n a a n n ……

.. . 312123-= -a a 21112-=-a a 对这（1-n ）个式子求和得： n a a n 111- =- ∴ n a n 1 2- = （2）1≠k 时，当b an n f +=)(则可设)()1(1B An a k B n A a n n ++=++++ ∴ A B k An k ka a n n --+-+=+)1()1(1 ∴ ???=--=-b A B k a A k )1()1( 解得： 1-= k a A ，2)1(1-+-=k a k b B ∴ }{B An a n ++是以B A a ++1为首项，k 为公比的等比数列 ∴ 1 1)(-?++=++n n k B A a B An a ∴ B An k B A a a n n --?++=-1 1)( 将A 、B 代入即可 （3）n q n f =)(（≠q 0，1） 等式两边同时除以1 +n q 得q q a q k q a n n n n 1 11+?=++ 令 n n n q a C = 则q C q k C n n 1 1+ =+ ∴ }{n C 可归为b ka a n n +=+1型 [例3] n n a n f a ?=+)(1型。 （1）若)(n f 是常数时，可归为等比数列。 （2）若)(n f 可求积，可用累积约项的方法化简求通项。 例：已知： 311= a ，1121 2-+-=n n a n n a （2≥n ）求数列}{n a 的通项。 解：123537532521232121212233 2211+= ?--?--?+-=???-----n n n n n n n a a a a a a a a a a n n n n n n

由递推公式求通项的9种方法经典汇总

由递推公式求通项的9种方法经典汇总

————————————————————————————————作者：————————————————————————————————日期：

精析由递推公式求通项的9种方法 1．a n ＋1＝a n ＋f (n )型 把原递推公式转化为a n ＋1－a n ＝f (n )，再利用累加法(逐差相加法)求解，即a n ＝a 1＋(a 2－a 1)＋(a 3－a 2)＋…＋(a n －a n －1)＝a 1＋f (1)＋f (2)＋f (3)＋…＋f (n －1)． [例1] 已知数列{a n }满足a 1＝12，a n ＋1＝a n ＋1n 2＋n ，求a n . [解] 由条件，知a n ＋1－a n ＝1n 2＋n ＝1n (n ＋1)＝1n －1n ＋1 ，则(a 2－a 1)＋(a 3－a 2)＋(a 4－a 3)＋…＋(a n －a n －1)＝????1－12＋????12－13＋????13－14＋…＋? ?? ??1n －1－1n ， 所以a n －a 1＝1－1n . 因为a 1＝12，所以a n ＝12＋1－1n ＝32－1n . 2．a n ＋1＝f (n )a n 型 把原递推公式转化为a n ＋1a n ＝f (n )，再利用累乘法(逐商相乘法)求解，即由a 2a 1＝f (1)，a 3a 2＝f (2)，…，a n a n －1 ＝f (n －1)，累乘可得a n a 1＝f (1)f (2)…f (n －1)． [例2] 已知数列{a n }满足a 1＝23，a n ＋1＝n n ＋1·a n ，求a n . [解] 由a n ＋1＝n n ＋1 ·a n ，得a n ＋1a n ＝n n ＋1， 故a n ＝a n a n －1·a n －1a n －2·…·a 2a 1·a 1＝n －1n ×n －2n －1 ×…×12×23＝23n .即a n ＝23n . 3．a n ＋1＝pa n ＋q (其中p ，q 均为常数，pq (p －1)≠0)型 对于此类问题，通常采用换元法进行转化，假设将递推公式改写为a n ＋1＋t ＝p (a n ＋t )，比较系数可知t ＝ q p －1 ，可令a n ＋1＋t

已知数列递推公式求通项公式的几种方法

已知数列递推公式求通项公式的几种方法 Revised on November 25, 2020

求数列通项公式的方法 一、公式法 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则11 3 222 n n n n a a ++-=，故数列{}2n n a 是以1222 a 1 1==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31()222n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 11 3 222 n n n n a a ++-=，说明数列{}2 n n a 是等差数列，再直接利用等差数列的通项公式求出3 1(1) 22n n a n =+-，进而求出数列{}n a 的通项公式。 二、累加法 例2 已知数列{}n a 满足11211n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 所以数列{}n a 的通项公式为2n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为 121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-+ +-+-+， 即得数列{}n a 的通项公式。 例3 已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。 解：由1231n n n a a +=+?+得1231n n n a a +-=?+则 所以3 1.n n a n =+-