递归最小二乘RLS自适应均衡算法
第三章 递归最小二乘(RLS)自适应均衡算法
§3.1 引言
在自适应滤波系统中，最陡梯度(LMS )法由于其简单获得了广泛的应用。但各种LMS 算法均有收敛速度较慢(收敛所需码元数多)，对非平稳信号的适应性差(且其中有些调整延时较大)的缺点。究其原因主要是LMS 算法只是用以各时刻的抽头参量等作该时刻数据块估计时平方误差均最小的准则，而未用现时刻的抽头参量等来对以往各时刻的数据块均作重新估计后的累积平方误差最小的原则(即所谓的最小平方(LS )准则)。
为了克服收敛速度慢，信号非平稳适应性差的缺点，根据上述内容，可采用新的准则，即在每时刻对所有已输入信号而言重估的平方误差和最小的准则(即LS 准则)。从物理概念上可见，这是个在现有的约束条件下利用了最多可利用信息的准则，即在一定意义上最有效，信号非平稳的适应性能也应最好的准则。这样建立起来的迭代方法就是递归最小二乘(RLS ：Recursive Least Square )算法，又称为广义Kalman 自适应算法。
用矩阵的形式表示RLS 算法非常方便，因此我们首先定义一些向量和矩阵。假定在时刻t ，均衡器的输入信号为t r ，线性均衡器对于信息符号的估计可以表示为
∑-=--=K
K
j j t j
r t c
t I
)1()(? 式(3-1)
让)1(-t c j 的下标j 从0=j 到1-=N j ，同时定义K t v t y +=)(，则)(?t I
变为 ∑-=--=1
0)()1()(?N j j
j t y t c t I )()1(t Y t C N N
-'= 式(3-2) 其中)1(-t C N 和)(t Y N 分别为均衡器系数)1(-t c j ，1,,1,0-=N j 和输入信号
)(j t y -，1,,1,0-=N j 的列向量。
类似的，在DFE 均衡器结构中，均衡器系数)(t c j ，1,,1,0-=N j 的前11+K 个系数为前向滤波器系数，剩下的112--=K N K 为反馈滤波器系数。用来预测
)(?t I 的数据为21~,~,,,11K t t t K t I I r r --++ ，其中21,~K j I j t ≤≤-为判决器先前作出判决的数
据。这里，我们忽略判决器判错的情况，因而21,~
K j I I j t j t ≤≤=--。同时为方便起见定义
?????-≤<≤≤=--+-+)
1()
0()(1111N j K I K j v j t y j K t j K t 式(3-3)
因此
])1(,),1(),([)('+--=N t y t y t y t Y N
],,,,,,[2111'=--++K t t t t K t I I r r r 式(3-4)
§3.2 RLS 自适应算法
RLS 算法对于)(?t I
的估计可以从下面的式子得到。假定我们的观测向量为)(n Y N ，t n ,,1,0 =，我们期望得到均衡器的系数向量)(t C N 使得均方误差的加权平方和
∑=-=t
n N n t t n e w n 0
2|),(|)(ε 式(3-5)
最小。其中误差定义为
)()()(),(n Y t C n I t n e N N
N '-= 式(3-6)
w 代表遗忘因子，10< 关于权向量)(t C N 的)(n ε最小化便得到下面的线性方程 )()()(t D t C t R N N N = 式(3-7) 其中)(t R N 为信号的自相关矩阵，定义为 ∑=-'=t n n N n t N n Y n Y w t R 0*)()()( 式(3-8) )(t D N 为互相关向量 ∑=-=t n N n t N n Y n I w t D 0*)()()( 式(3-9) 式(3-7)的解为著名的Wiener －Hopf 方程 )()()(1 t D t R t C N N N ?=- 式(3-10) 为了避免复杂的求逆运算，引入一N N ?矩阵 )()(1 t C t P N N -= 式(3-11) 由式(3-8)有 ∑=-'= t n N N n t N n Y n Y w t R 0* )()()( )()()1(* t Y t Y t wR N N N '+-= 式(3-12) 又由矩阵求逆引理有： ??????-'+-'---=-----)()1()()1()()()1()1(1)(* 11 *11 1 t Y t R t Y w t R t Y t Y t R t R w t R N N N N N N N N N 式(3-13) 在上式中定义)()(1 t R t P N N -=，令 )()1()()(* n Y t P t Y t N N N N -'=μ 式(3-14) ) () ()1()(*t w t Y t P t K N N N N μ+-= 式(3-15) )(t N μ为一标量，)(t K N 为一N 维矢量，称为Kalman 增益向量。则 [])1()()()1(1 )(-'--= t P t Y t K t P w t P N N N N N 式(3-16) 假定我们在式(3-16)两边右乘以)(* t Y N ， )]()1()()()()1([1)()(* ** t Y t P t Y t K t Y t P w t Y t P N N N N N N N N -'--= )]}()()()]({[1 t t K t K t w w N N N N μμ-+= )(t K N = 式(3-17) 因此，Kalman 增益向量可以被定义为)()(* t Y t P N N 。 由于 )()()(t D t P t C N N N = )()()1()(* t Y t I t wD t D N N N +-= 式(3-18) 我们得到 )]()()1()][1()()()1([1)(* t Y t I t wD t P t Y t K t P w t C N N N N N N N +--'--= )()1()(1)1()1(* t Y t P t I w t D t P N N N N -+--= )1()1()()(' ---t D t P t Y t K N N N N )()1()()()(1* t Y t P t Y t K t I w N N N N -'- )]1()()()[()1(' --+-=t C t Y t I t K t C N N N N 式(3-19) )1()(-'t C t Y N N 为均衡器在t 时刻的输出，也就是 )1()()(?-'=t C t Y t I N N 式(3-20) 而 )()(?)()1,(t e t I t I t t e N N ≡-=- 式(3-21) 为期望信号与估计信号之间的误差。因此，)(t C N 可以根据下式来递推更新 )()()1()(t e t K t C t C N N N N +-= 式(3-22) 式(3-22)表明：t 时刻最佳的)(t C N 值可由1-t 时刻的最佳)1(-t C N 值加一修正量得到。这就是递推最小二乘算法或Kalman 算法。 将上述在推导过程中出现的各式予以整理，可得到正规RLS 算法的计算步骤。由于此算法为迭代型，故应在已得迭代式组外，还注意在计算的初始部分设置合理的初始值组。根据经验设定则一般可得到较快的收敛效果。由于矩阵)(t R N 类似于统计自相关矩阵，而向量)(t D N 近似于互相关向量。应该注意到)(t R N 不是一个Toeplitz 矩阵，对于较小的t ，)(t R N 可能处于病态条件；因而通常初始时需要在 )(t R N 上加上一个N I δ，δ为一个1>>的正常数，N I 为单位阵。由于对于过去的信号引入了指数权，加上N I δ的作用将随着时间增加而减弱。 正规RLS 算法的计算步骤如下： 步骤1：初始化：令0)0()0(==N N Y C ， 式(3-23) N N I t P δ=)((δ一般取>>1的正数)，0=n 式(3-24) 步骤2：更新1+=t t )1()()()(-'-=t C t Y t I t e N N N 式(3-25) )()1()()(* t Y t P t Y t N N N N -'=μ 式(3-26) ) ()()1()(t w n Y t P t K N N N N μ+'-= 式(3-27) )]1()()()1([1)(-'--=t P t Y t K t P w t P N N N N N 式(3-28) )()()1()(t e t K t C t C N N N N +-= 式(3-29) 在一次迭代当中，正规RLS 算法所需的计算量为乘法N N 532+次，除法1次， 加(减)法N N 5.15.22+次。 我们看到均衡器系数随时间的变化量等于预测误差乘以Kalman 增益向量。由于)(t K N 为N 维， )(t K N 的每一个元素有效地控制着均衡器每一个系数，因而能够得到快速的收敛性质。相反，最陡梯度算法(steepest-descent algorithm )均衡器系数的更新可表示为 )()()1()(* t e t Y t C t C N N N N ?+-= 式(3-30) 唯一变化的参数为步长?。 图 3.1给出了这两个算法初始收敛速度的比较，信道选自[3],具有固定参数 26.00=f ，93.01=f ，26.02=f 。信道的特征值为11/min max =λλ。均衡器的所有系数在初始迭代时置为0。最陡梯度算法的步长选为020.0=?。与最陡梯度算法相比RLS 算法具有较快的跟踪性能和收敛性能。这对于时变信道来说极为重要。例如，短波(HF )信道变化非常快，用梯度算法无法对信号进行均衡。而Kalman 算法就能够足够快地跟踪这种变化。 图3.1 Kalman 算法与梯度算法性能比较 §3.3 几种改进型快速跟踪的RLS 算法 §3.3.1 指数遗忘的加窗RLS 算法和Reset-RLS 算法 RLS 算法广泛的应用于自适应滤波，系统辨识与信号预测。该算法只有在方程误差为0均值的高斯白噪声以及系统模型非时变时才能保证渐进趋于真值。该算法的另一个显著特点是，为了减小预测中的噪声影响，当参数慢慢趋向于真值时，增益向量便接近于0。因此，RLS 算法就有可能跟踪不上信道参数的变化。 为了解决这一问题，在实践当中，人们提出了许多改进的RLS 算法。例如指数遗忘的加窗RLS 算法，避免了增益向量变成0。这一算法的优点是它对于信道参数的变化总是能够起到预防的作用；然而也因为非0的增益向量使得该算法对 信道的扰动和噪声都非常敏感。另外一个方法是一旦检测到信道的变化，就重新初始化迭代协方差矩阵)(t P ，如何检测信道参数的变化就成为该算法的关键。在实际操作中，我们可以通过设置适当的门限来检测信道的突跳。一旦迭代误差超过该门限，RLS 算法便被重新初始化。我们称此方法为复位RLS (Reset －RLS )算法。 §3.3.2 SPRLS 算法 在文献[4]中Park 和Jun 提出了SPRLS 算法(Self －Perturbing Least Squares Algorithm )。它是一种基于前向预测误差来调整RLS 算法的迭代矩阵，前向预测误差越大，意味着信道发生变化的可能性越大。我们再次给出正规RLS 算法： )()()1(?)(?t e t k t t +-=θθ 式(3-31) )()1(?)()(t t t y t e T φθ--= 式(3-32) ) ()1()(1) ()1()(t t P t t t P t k T φφφ-+-= 式(3-33) )1()()()1()(---=t P t t k t P t P T φ 式(3-34) δ/)0(I P = 式(3-35) 0)0(?=θ 式(3-36) 其中，t 为离散采样时刻，)(?t θ 要预测的滤波器权向量，)(t y 是期望的输出信号，)()()(*t n t t y T +=φθ，*θ为信道的真值向量，)(t n 为量测噪声，)(t e 为前向预测误差，)(t k 为自适应增益向量。 SPRLS 算法在(3-34))(t P 的迭代式中加入一项与预测误差有关的项，即 I t e N I N T t P t t k t P t P T ?-?+---=)]1([)1()()()1()(2γβφ 式(3-37) 其中β为常数，)(t e 为前向预测误差，定义为 )()(?)()(t t t y t e T φθ -= 式(3-38) NINT 函数为四舍五入取整函数，γ为灵敏增益系数，根据系统量测噪声的大小调 整其大小，I 为单位阵。 在迭代矩阵中加上一项与前向预测误差有关的项，我们称之为自扰动项。当信道发生变化时, 迭代矩阵受到前向预测误差的扰动，变成非0从而跟踪信道的变化。该误差平方在SPRLS 算法中起着关键的作用，当5.0)(2 当信道参数发生突跳时，该算法比其它普通的RLS 算法性能要好。这一算法在信道参数变化很大而噪声很小时确实很有效，然而当噪声电平很高时上述算法几乎不能工作，原因在于信道参数的变化以及噪声的影响都可能导致较大的前向预测误差。针对上述问题，J.Jiang 和R.Cook 在文献［5］中提出了一个新的方案,也就是我们下面将要介绍的MRLS 算法。 §3.3.3 MRLS 算法 在MRLS 算法当中，迭代矩阵的更新基于一个观测向量与预测向量相关矩阵的函数。由于相关性，这种算法不仅在噪声存在的情况下非常稳健，而且能够快速的跟踪信道参数的变化。 正规RLS 算法的迭代公式已经给出。我们可以看出当迭代时间很长时，增益向量)(t k 已经趋于0，即使信道参数已经改变，)(t θ 和)1(-t θ也非常接近，也就是说RLS 算法失去了跟踪能力。因此 J.Jiang 和R.Cook 提出只要信道参数变化就在)(t P 的迭代式中加上一项正的对角阵，即 I t M y y f NINT t P t t k t P t P n ?-?+---=|})1(,,,?,[|{)1()()()1()(σγβφ 式(3-39) 2 1 11 12)(?)(1 )(1 )]1(,,,?,[n t M t i t M t i n i y i y M i y M t M y y f σσ--=-∑∑---=---= 式(3-40) β、γ定义如同SPRLS 算法。M 代表了运行窗口的大小，它取决于噪声的强度。一旦该扰动项被激活，它便一直起作用直到f 函数的返回值接近于0。 从式(3-40)可以看出，f 函数是包括)(t y 的自相关函数，)(t y 与)(?t y 的互相关函数，以及噪声方差的代数和。由于)(t n 是高斯白噪声，与)(t φ不相关，很容易看出，不管噪声强度多大，当预测参数已经收敛到真值时，一个相当大的M 就使得f 函数的返回值为0。当然，M 的选择应当正比于噪声的方差。另一方面，在任何 噪声电平下，当θ?不等于*θ时，f 函数的值非0。也就是说f 函数对于信道参数的变化很敏感而对于噪声不敏感。由于采用了运行窗口M ，该算法对于信道参数变化的检测有一个时延。M 越大，收敛的速度越慢。事实上这一算法也是在检测时延和抗噪声之间的一种折衷。 结果表明，在噪声很大的情况下，这种改进的RLS 算法可以很好的跟踪时变信道。因为该算法要调整M 的大小，为方便起见我们称这种改进算法为MRLS 算法。 §3.3.4 ISPRLS 算法 虽然MRLS 算法的性能要优于SPRLS 算法，但其灵敏参数γ以及M 窗口的大小要根据噪声的强度进行选择，仍然很不方便。于是Kwang －Seop Eom 等在文献 ［6］中提出另一种基于Kalman 滤波的改进型SPRLS 算法。我们称之为ISPRLS 算法(Improved Self-Perturbing Recursive Least Squares Algorithm )。它不需要在不同的噪声条件下改变灵敏参数及窗口大小，能够很好的克服噪声的影响，快速的跟踪信道。 我们同样假定)(t P 为N N ?协方差矩阵，)(t φ为输入向量，)(t y 为系统输出向 量，)(?t θ为滤波器的权向量，)(t e 为前向预测误差，)(t Q 为一自扰动项。ISPRLS 算法如下： ) ()1()(1) ()1()(t t P t t t P t k T φφφ-+-= 式(3-41) )()1(?)()(t t t y t e φθ --= 式(3-42) )()()1(?)(?t e t k t t +-=θθ 式(3-43) )()1()]()([)(t Q t P t t k I t P T +--=φ 式(3-44) )(t Q 对于决定该算法的性能是否良好是一个关键的因素。因此)(t Q 的设计是 主要要解决问题。为了避免根据噪声的大小来确定参数，该算法基于Kalman 滤波的原理设计出一个新的自扰动项。 假定在某一时刻m t =，系统的真值参数从0)0(θθ=变到m t θθ=)(，时变系统可以表示为 )()}({)1()(m t t t t m --+-=δθθθθ 式(3-45) )()()()(t n t t t y T +=φθ 式(3-46) 其中)(m n -δ为ker Kronec delta 函数。)(t n 为方差为2σ的量测噪声。由Kalman 滤波原理可以得到式(3-44)中的)(t Q 为 I t e E N I N T t Q ?-?=|})]([|{ )(2 2 2σσγβ 式(3-47) 其中)]([2t e E 可以由)(2t e 代替， )()1()1()(222t e t e t e ρρ-+-= 式(3-48) ρ为实常数，10<<γ。 在式(3-47)和(3-48)中，ρ和γ不需要根据噪声的大小进行选择。因为分母上的 2σ会自动根据噪声的大小来调整)(t Q 。 前面介绍的四种改进型的RLS 算法应用的背景均为信道估值(辨识)，鉴于自适应辨识与自适应均衡都属于自适应滤波系统，我们也期望这些改进型的RLS 算 法应用于均衡器时可以获得较好的性能。在下面一节，我们将给出各种算法的计算机仿真以及结果分析。 §3.4 计算机模拟及结果分析 本节通过计算机模拟来比较各种RLS算法的跟踪能力和收敛性能。在上述SPRLS、MRLS、ISPRLS三种具有相同思想的改进型RLS算法中，由于SPRLS 对于噪声过于敏感，相比MRLS、ISPRLS算法性能较差，故我们选取正规RLS，Reset-RLS，MRLS，ISPRLS这几种算法分别用在信道估值和信道均衡中，并进行了比较。 §3.4.1 计算机仿真 仿真1，我们选择文献［4］中的例子，在不同的信噪比下比较Reset-RLS和ISPRLS的均方误差性能。假定未知信道的参数在第70次迭代时由[0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ]变为[0.8 0.9 1.3 1.1 -0.7 0.1 0.9 1.5 -0.2 -0.3]，Reset-RLS在信道变化时重新启动迭代，而ISPRLS在不同信噪比情况下参数不用改变。 图3.2 均方误差曲线 图3.3 均方误差曲线 可以看出，Reset-RLS与ISPRLS对于突变信道的跟踪能力大体相当。但这时Reset-RLS需要对于信道参数的变化实时地检测，门限的选取便成为该算法的关键因素。而ISPRLS算法只是在迭代矩阵中加进一项扰动项，该扰动项会对信道参数的变化作出反应，而无需另外进行专门的检测。 仿真2，我们选择正规RLS，MRLS，ISPRLS三种算法进行比较，信道条件同仿真1，仍在第70次迭代时发生突变。 图3.4 参数误差曲线 图3.5 参数误差曲线 图中给出的是信道参数估计的误差曲线，参数预测误差被定义为θ θ?*-，我们取2－范数，即2 2221n x x x x +++= 。可以看出，在第70次迭代信道发生变 化时，MRLS 算法和ISPRLS 算法可以迅速的跟上信道的变化，具有较快的收敛能力。MRLS 和ISPRLS 算法相比正规RLS 对于信道的突跳具有快速的跟踪能力和收敛性能。MRLS 和ISPRLS 相比，由于MRLS 的运行窗口M 的限制，在刚开始迭代时，它对于信道的跟踪有一段时延。而且在信噪比较低时(10dB 、0dB )，由于在MRLS 和ISPRLS 算法中多加的扰动项受到噪声的影响，在信道突跳前的一段时间，两者收敛时的参数误差要大于正规RLS 算法。因而较好的选择应该将正规RLS 与MRLS 或ISPRLS 结合起来，在信道不变时，用正规RLS 就能达到较好的收敛效果，一旦信道发生变化，启动MRLS 或ISPRLS 快速的跟踪上信道的变化，可见MRLS 和ISPRLS 算法对于时变信道快速的跟踪能力。我们将它们用在均衡系统中，下面的仿真给出了算法的模拟结果。 仿真3，将MRLS ，ISPRLS 算法应用于信道均衡，采用线性均衡器，信号为2PSK ，信道采用复值信道，在第70次迭代时信道参数从[1+0j 0+0j 0.5*(0.996+0.087j) 0+0j 0.3*(0.985+0.174j)] 变为[1+0j 0.3*(0.996+0.087j) 0+0j 0.2*(0.985+0.174j) 0+0j]。 图3.6 均方误差曲线 图3.7 均方误差曲线 从曲线可以看出，在高信噪比情况下(30dB、20dB)，ISPRLS这种改进型算法，在信道发生突跳时具有较快的跟踪能力和较好的收敛性能，MRLS算法略优于RLS算法，但二者的跟踪能力明显不如ISPRLS算法。在低信噪比情况下(10dB、0dB),MRLS和ISPRLS算法却显示不出它们对于正规RLS算法性能的改善。信道的变化早已淹没在很强的噪声之中，区分不开。这与在仿真2当中MRLS和ISPRLS 算法的优良性能似乎还有一定的差距。我们期望的改进型RLS算法用与均衡系统时，在低信噪比下仍不具有较好的性能。在下一节中我们将从自适应滤波的角度来分析问题的实质。 §3.5 信道辨识与信道均衡 相同的算法用于信道辨识与信道均衡时，却有着不同的效果。这使得我们不得不探讨一下，同属于自适应滤波系统的信道辨识和信道均衡到底存在着什麽区别？ §3.5.1 自适应模拟系统和自适应逆模拟系统 自适应滤波系统分为自适应模拟系统和自适应逆模拟系统。自适应模拟系统与辨识可以用一个自适应系统模拟一个未知的、可以随时间慢变的系统。自适应逆模拟则可消除信号在器件和煤质中传输所受到的影响。信道辨识属于自适应模 拟系统，而信道均衡属于自适应逆模拟系统。 图3.8 自适应模拟系统 一个单输入单输出的未知系统(或称被控系统)的自适应模拟示于图3.8，被控系统与自适应滤波器有相同的输入激励。自适应滤波器调整自身以得到一个与未知系统相匹配的输出，通常是得到一个未知系统输出最好的最小均方拟合。这种拟合的程度与自适应系统的可调权系数(即“自由度”)有关。 如图中所示，假定未知系统的传输函数为)(z P ，自适应滤波器达到稳态后的传输函数为)(z H ，信号的相关函数和互相关函数定义为 ][)(*n k k xx x x E n +=φ 式(3-49) ][)(*n k k xd d x E n +=φ 式(3-50) 上两式的Z 变换)(z xx Φ及)(z xd Φ分别表示信号的功率谱和互功率谱。 若自适应滤波器是一个横向滤波器结构，则由维纳滤波理论，输出均方误差ξ可表示为 ]R e [2|][|2W P RW W d E T H -+=ξ ∑∑∑∞-∞=∞ -∞ =∞ -∞ =---+ =l m l dx l xx m l xx l w m l w w )(2)()0(* φφ φ 式(3-51) 其中W 为滤波器的权向量， ][*T X X E R = 式(3-52) ][*X d E P = 式(3-53) 令上式对权的导数为零，可得最小均方误差时的权向量opt W ，对每个权分量，则有 {k r )( z P {k r k {k r 0)(2)(2=--=??∑∞ -∞ =k m k w w xd m xx m k φφξ 式(3-54) 于是 ∑∞ -∞ ==-l xd xx opt k l k w ),()(φφ ∞<<∞-k 式(3-55) 上式左边是一个卷积的形式，经Z 变换后成为两部分的乘积，于是，可得到最佳权向量的Z 变换 ) () ()(z z z H xx xd opt ΦΦ= 式(3-56) 因此，最佳权的Z 变换是信号x 和d 之间的互功率谱与自适应模拟器的输入x 的功率谱之比。由于 )()()()(z z z P z xn xx xd Φ+Φ=Φ 式(3-57) 若假定系统噪声k n 与输入k x 相互独立，则上式右边第二项为零，由此知 )()(z P z H opt = 式(3-58) 即自适应模拟器的传输函数就是未知系统的传输函数。 式(3-58)表明，当自适应模拟系统具有足够的“自由度”去匹配未知系统的输出或输入时，不可能同时匹配系统噪声k n 。事实上，内部系统噪声表现在系统输出一般可看成是一个加性噪声，并认为该噪声与系统本身的输出是不相关的。若自适应模型为线性组合器，并且它的权值已调到使均方误差达到最小，则其最小均方误差解将主要由被控系统的冲激响应所决定，而不是受噪声存在的影响。但自适应收敛过程还是会受到噪声的影响。另外，系统模拟和辨识还与输入信号谱或统计特性有关，一般要求输入信号谱足够宽或统计相关性足够小，才能得到好的模拟和辨识结果。 图3.9 自适应逆模拟系统 ) (z P {k r {k r s ) (z P {k r s ) (z P {k r 图3.9是一个自适应系统用作逆模拟的情况。自适应滤波器的输入为未知被控系统的输出，而它的输出将为未知系统输入的最小均方组合。由图可知，逆模型的输入功率谱(z 在单位圆上)为 ),()(|)(|)(2z z z P z nn ss xx Φ+Φ=Φ jw e z = 式(3-59) 同样假定系统噪声k n 和输入信号k s 独立，由于 )()()()()(* *z z z P z z nd ss dx xd Φ+Φ=Φ=Φ )()(*z z P ss Φ= jw e z = 式(3-60) 因此，逆模拟的最佳传输函数 )()(|)(|)()()()()(2 *z z z P z z P z z z H nn ss ss xx xd opt Φ+ΦΦ=ΦΦ= 式(3-61) 若系统内部噪声为零，则上式为 ) (1 )(z P z H o p t = 式(3-62) 即此时逆模型的传输函数为被控系统传输函数的倒数。事实上，也可以证明式(3-61)和式(3-62)对所有的z 都成立。 从式(3-61)看出，自适应逆模拟和自适应模拟不同，系统噪声k n 和被控系统输出信号一起作为自适应滤波器的权输入，因而对权值的最小均方解产生影响，同时也影响自适应收敛的情况。在图3.9的整个逆模拟系统中，若被控系统为一个全零点FIR 滤波器，则自适应滤波器模型将是一个全极点的递归滤波器，由此，存在自适应滤波器的稳定性和收敛性问题。其所有极点均应位于z 平面的单位圆之内。若考虑自适应滤波器的因果可实现性，通常可在期待响应k d 通道中插入一定的时间延迟。 §3.5.2 自适应滤波算法的跟踪性能和收敛性能 对于自适应滤波算法而言，跟踪性能和收敛性能是两个很重要的考察指标。跟踪是一个稳态过程。相比之下，收敛是一个暂态过程。因而要训练一个自适应滤波器的跟踪能力，就必须从暂态阶段过渡到稳态阶段，这就需要不断的调整滤波器的参数。而且，收敛的速度与跟踪能力是算法的两个不同的性质。一个具有好的收敛性质的自适应滤波算法不一定具有快速的跟踪能力，相反具有快速跟踪能力的算法也不一定具有好的收敛性能。 信道辨识和信道均衡都是自适应滤波系统，但跟踪性能却是一个特殊问题。自适应滤波算法用于系统辨识与用于信道均衡或者加性噪声中的信号恢复却有很大的不同。 实际中动态的系统可能来自两种情况。 1． 参考信号可能是时变的。譬如，当自适应横向滤波器用于动态系统的系 统辨识时，这种情况就会出现。此时，自适应横向滤波器的输入向量的自相关矩阵保持不变，而输入向量与参考向量的互相关矩阵却是时变形式。 2． 自适应滤波器的输入随机过程是动态的。这种情况发生在自适应横向滤波器用于均衡一个时变信道时。此时，自适应横向滤波器的输入向量的自相关矩阵以及输入向量与参考向量的互相关矩阵都是时变形式。因而，时变信道均衡的 图3.10 信道辨识 跟踪性能的数学分析比起系统辨识问题而言要复杂得多。 因而，一个时变系统的跟踪性能，不仅取决于所采用的滤波器类型，而且也是个较特殊问题。 §3.5.3 自适应均衡器的均方误差 下面让我们来分析一下无限长度线性均衡器的均方误差。我们知道在信号为 复值的情况下，均方误差函数被定义为22|?|||k k k I I E e E J -==。J 为均衡器系数的二次函数。 在第二章中我们曾经给出，基于最小均方误差准则的均衡器，按照正交性原 理，应有 ,0}]{[*=- --=-∑l j K K j j k j k r r c I E +∞<<∞-l 式(3-63) 即就是 ),()(**l k k j l j j k j r I E r r E c -∞ -∞ =--=∑ +∞<<∞-l 式(3-64) 将 lj L n j l n n l k j k N f f r r E δ00**)(+=∑=-+-- ? ??≤-+=-其它,0||,0L j l N x lj j l δ 式(3-65) ? ??≤≤-=--其它,00 ,)(** l L f r I E l l k k 式(3-66) 将式(3-65)和(3-66)代入(3-64)并对方程两边取z 变换得到 )(])()()[(1*01*--=+z F N z F z F z C 式(3-67) 因而基于MMSE 准则的均衡器传递函数为 1*1*)()() ()(N z F z F z F z C += -- 式(3-68) 当噪声白化滤波器被包含在)(z C 里时，我们可以得到均衡器的传输函数 1 *)()(1 )(N z F z F z C += '- 0 )(1 N z X += 式(3-69) 我们注意到)(z C '与基于最大失真准则的均衡器传递函数式(2-7)仅在于(3-69)表达式中分母上的噪声功率谱密度0N 。当0N 与信号相比非常小的情况下，使得峰值失真)(c D 最小的均衡器系数与使得均方误差J 最小的均衡器系数相当。也就是，当00→N 时，最大失真准则与最小均方误差准则可以得到相同的解。因而，当 00=N 时，最小均方误差准则对码间干扰可以得到完全的抵消。另一方面，当00≠N 时，在均衡器的输出端则存在剩余码间干扰和加性噪声。 我们通过计算均方误差函数的最小值()min J 可以得到剩余码间干扰和加性噪 声。当均衡器的传递函数如式(3-68)定义时，由于)?()(||**2k k k k k I e E I e E e E J -==，由正交化条件可得0)?(*=k k I e E ，由此得出 )(* m i n k k I e E J = ∑∞ -∞ =--=j k j k j k I r E c I E )(||*2 ∑∞ -∞ =-- =j j j f c 1 式(3-69) 我们注意到(3-69)中的求和为}{j c 和}{j f 的卷积在0点的值。因而，如果}{k b 定义这两个序列的卷积，那末(3-69)的求和就等于0b 。序列}{k b 的z 变化等于 )()()(z F z C z B = 01 *1*)()()()(N z F z F z F z F +=-- 0 )() (N z X z X += 式(3-70) 0b 为 ?= dz z z B j b ) (210π ?+= dz N z X z z X j ] )([) (210π 式(3-71) 通过变量代换jwT e z =可以得到 dw N e X e X T b T T jwT jwT ?+= //0 0)() (2ππ π 式(3-72) 将式(3-72)代入式(3-69)最后可以得到最小均方误差的表达式 ?+- =T T j w T j w T dw N e X e X T J //0 min )() (21ππ π ?+= T T j w T dw N e X N T //0 )(2ππ π dw N T n w H T N T T T n ?∑ ∞-∞ =-++= //0 2 1 |)/2(|2ππ ππ 式(3-73) 在存在码间干扰且1)(=jwT e X 的情况下， m i n 1N N J += 式(3-74) 显然10min ≤≤J ，而且输出信噪比∞γ与min J 的关系为 m i n m i n 1J J -= ∞γ 式(3-75) 当存在剩余误差与加性噪声时，该式也成立。 由上面的分析可以看出，均方误差的最小值是受噪声功率谱密度限制的。这也从数学表达式上说明了为什麽自适应均衡系统对噪声非常敏感。 在这一节当中，我们从自适应模拟与逆模拟，自适应滤波算法的跟踪、收敛性能，以及均衡器的最小均方误差三个方面说明了自适应滤波器用在信道辨识与信道均衡中的差异。由此我们从理论上解释了为什麽相同的RLS 算法用在信道辨识与信道均衡中算法的跟踪性能有较大的差异。对于时变信道，普通均衡算法都难以达到很好的收敛性能和跟踪能力，尤其在短波衰落信道中，信号电平在短时间内就会发生数次深度衰落的情况，更是远远无法适应。进一步寻找新的更加行之有效的均衡算法，这无疑要求我们要开辟新的思路。 从前面的仿真结果及分析可以看到，在信号与加性噪声不相关的情况下(一般情况下均可以满足)，信道辨识不受噪声的影响，可以完全的模拟出系统的传输函数，而且对于时变的信道，一些改进型的算法具有很好的收敛能力和快速的跟踪性能，因而我们期望可以在最短的时间内完全的估计出信道参数。然后通过估出的信道参数来完成均衡的任务。在最近的十年当中，国外的一些学者对基于信道估值的均衡算法进行了一些研究，我们也循着这个思路，针对在短波瑞利衰落信道，研究了基于信道估值的均衡技术。这就是我们下一章将要论述问题。 摘要 软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。然而，软件测试是一个复杂的过程，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的40%～50%。因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发成本非常重要。而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。 本文在分析软件测试和算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。论文提出了基于算法的测试用例生成的内含是应用算法来求解一组优化的测试用例，其框架包括了测试环境构造、算法及测试运行环境三部分，论文给出了基于算法的测试用例生成的模型。最后以三角形分类程序为例应用算法进行测试用例生成的模拟，结果显示，应用算法进行测试用例生成可行。 关键词：软件测试测试用例算法 ABSTRACT Software test is the important means that guarantee software quality and reliability，and in this respect，it plays the role that other method cannot replace. However software test is a complex process , it needs to consume huge manpower，material resources and time，which takes the 40%~50% of entire software development cost approximately . Therefore，raising the automation level of software test tool is very important for ensure software development quality and reduction software development cost . And then，the most important is raising the automation level of the test case generation for raising the automation level of test tool and even entire test process，so this paper study and design mainly according to this problem. Based on the analysis of basic concepts of software testing and genetic algorithm, this article proposes that software test case design is one of the difficulties of software testing. Paper presents the inherent in software test case designing based on genetic algorithm is using genetic algorithm to solve a set of optimization test cases, and the framework includes three parts which are test environment construction, genetic algorithm and the environment for test . Paper presents the model of software test case generation based on genetic algorithm. Finally, we take the triangle categorizer as an example, simulate software test case generation based on genetic algorithm. The results display that software test case generation basing on genetic algorithm is possible. KEY WORDS: software test , test case , genetic algorithm 《系统辨识与建模》（MATLAB编程） 信研0701 孙娅萍2007000694 编程第四次作业 仿真模型参数为：a=[-1.5 0.7];b=[1.0 0.5]，由下式递推产生502组数据，并形成如下矩阵： z(k)=1.5z(k–1)-0.7z(k–2)+1.0u(k–1)+0.5u(k–2)+v(k) 试用一次完成最小二乘法辨识系统模型。 程序部分： %************************************************************% % ***** 二阶系统的最小二乘一次完成算法辨识程序*****% % 系统辨识的输入信号u是6阶的M序列，长度是500； L = 500; u = load('u.txt'); u2 = load('u2.txt'); u1 = load('u1.txt'); z = zeros(1,L+1); for k = 3 : (L+1) % 理想输出作为系统观测值 z(k) = 1.5 * z(k-1) - 0.7 * z(k-2) + u(k-1) + 0.5 * u(k-2); end % 绘制输入信号和输出观测值的图形 figure(1) i = 1 : 1 : L; subplot(2,1,1) plot(i,u) k = 1 : 1 : (L+1); subplot(2,1,2) plot(k,z) z = z' z1 = load('z1.txt'); z2 = load('z2.txt'); z3 = load('z3.txt'); Na = 2; Nb = 2; % 定义Na、Nb； for i = 1 : (Na+Nb) if ((i == 1)) H = -1 * z2; end if (i == 2) H = -1 * z1; end if (i == (Na+1)) H = u2; end 题目： （递推最小二乘法） 考虑如下系统： )()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. 根据输入输出序列列出最小二乘法估计的观测矩阵?： ] )(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。 可以看出，基本的最小二乘法不适用于有色噪声的场合。 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; ○1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 舍伍德算法设计的基本思想: 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为 这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。 设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有： 解此方程可得： 蒙特卡罗(Monte Carlo)算法的基本思想: 设p是一个实数，且1/2 递归算法的优缺点： ○ 1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T ，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T 。 舍伍德算法设计的基本思想: 设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。设Xn 是算法A 的输入规模为n 的实例的全体，则当问题的输入规模为n 时，算法A 所需的平均时间为 这显然不能排除存在x ∈Xn B ，使得对问题的输入规模为n 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x) 是对输入x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有p(x)>0。 设t(x)是算法obstinate 找到具体实例x 的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x 蒙特卡罗(Monte Carlo)算法的基本思想: 设p 是一个实数，且1/2 普通最小二乘法（OLS ） 普通最小二乘法（Ordinary Least Square ，简称OLS ），是应用最多的参数估计方法，也是从最小二乘原理出发的其他估计方法的基础，是必须熟练掌握的一种方法。 在已经获得样本观测值i i x y ,（i=1,2,…,n ）的情况下 （见图中的散点），假如模型（）的参数估计量已经求得到， 为^0β和^ 1β，并且是最合理的参数估计量，那么直线方程（见 图中的直线） i i x y ^ 1^0^ββ+= i=1,2,…,n 应该能够最 好地拟合样本数据。其中^i y 为被解释变量的估计值，它是由参数估计量和解释变量的观测值计算得到的。那么，被解释变量的估计值与观测值应该在总体上最为接近，判断的标准是二者之差的平方和最小。 ),()(1022101ββββQ u x y Q i i n i i ==--=∑∑= ()()),(min ????1021 10212?,?1100ββββββββQ x y y y u Q n i i n i i i =--=-==∑∑∑== 为什么用平方和因为二者之差可正可负，简单求和可能将很大的误差抵消掉，只有平方和才能反映二者在总体上的接近程度。这就是最小二乘原则。那么，就可以从最小二乘原则和样本观测值出发，求得参数估计量。 由于 2 1 ^1^012 ^ ))(()(∑∑+--=n i i n i i x y y y Q ββ＝ 是^0β、^1β的二次函数并且非负，所以其极小值总是存在的。根据罗彼塔法则，当Q 对^0β、^ 1β的一阶偏导数为0时，Q 达到最小。即 0011001100?,?1 ?,?0 =??=??====ββββββββββQ Q 容易推得特征方程： ()0)??(0?)??(1011 10==--==-=--∑∑∑∑∑==i i i i n i i i i i i n i i e x x y x e y y x y ββββ 解得： ∑∑∑∑∑+=+=2^ 1^0^1^0i i i i i i x x x y x n y ββββ （） 所以有：???? ?????-=---=--=∑∑∑∑∑∑∑=======x y x x y y x x x x n y x y x n n i i n i i i n i i n i i n i i n i i n i i i 10121 21121111??)())(()()()(?βββ （） 于是得到了符合最小二乘原则的参数估计量。 为减少计算工作量，许多教科书介绍了采用样本值的离差形式的参数估计量的计算公式。由于现在计量经济学计算机软件被普遍采用，计算工作量已经不是什么问题。但离差形式的计算公式在其他方面也有应用，故在此写出有关公式，不作详细说明。记 ∑=-i x n x 1 ∑=-i y n y 1 y y y x x x i i i i -=-= （）的参数估计量可以写成 ---------------------------------------------------------------最新资料推荐------------------------------------------------------ 基于最小二乘法的系统辨识的设计与开发（整理版）课程（论文）题目： 基于最小二乘法的系统辨识摘要： 最小二乘法是一种经典的数据处理方法。 最小二乘的一次性完成辨识算法（也称批处理算法），他的特点是直接利用已经获得的所有（一批）观测数据进行运算处理。 在系统辨识领域中, 最小二乘法是一种得到广泛应用的估计方法, 可用于动态系统, 静态系统, 线性系统, 非线性系统。 在随机的环境下，利用最小二乘法时，并不要求观测数据提供其概率统计方面的信息，而其估计结果，却有相当好的统计特性。 关键词： 最小二乘法；系统辨识；参数估计 1 引言最小二乘理论是有高斯（ K.F.Gauss）在 1795 年提出： 未知量的最大可能值是这样一个数值，它使各次实际观测值和计算值之间的差值的平方乘以度量其精度的数值以后的和最小。 这就是最小二乘法的最早思想。 最小二乘辨识方法提供一个估算方法，使之能得到一个在最小方差意义上与实验数据最好拟合的数学模型。 递推最小二乘法是在最小二乘法得到的观测数据的基础上，用新引入的数据对上一次估计的结果进行修正递推出下一个参数估计值，直到估计值达到满意的精确度为止。 1 / 10 对工程实践中测得的数据进行理论分析，用恰当的函数去模拟数据原型是一类十分重要的问题，最常用的逼近原则是让实测数据和估计数据之间的距离平方和最小，这即是最小二乘法。 最小二乘法是一种经典的数据处理方法。 在随机的环境下，利用最小二乘法时，并不要求观测数据提供其概率统计方面的信息，而其估计结果，却有相当好的统计特性。 2 最小二乘法的系统辨识设单输入单输出线性定常系统的差分方程为： 1),()()() 1()(01knkubkubnkxakxakxnn （ 1）上式中： )(ku为输入信号；)(kx为理论上的输出值。 )(kx只有通过观测才能得到，在观测过程中往往附加有随机干扰。 )(kx的观测值)(ky可表示为 （ 2）将式（ 2）代入式（ 1）得 1()()() 1()(101kubkubnkyakyakyn (3) 我们可能不知道)(kn的统计特性，在这种情况下，往往把)(kn看做均值为 0 的白噪声。 设 （ 4）则式（ 3）可以写成 (5) 在测量)(ku时也有测量误差，系统内部也可能有噪声，应当 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点". 自动化专业综合设计报告 设计题目：最小二乘递推算法辨识系统参数所在实验室：自动化系统仿真实验室 指导教师： 学生姓名 班级计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)); 第一部分：程序设计思路、辨识结果分析和算法特点总结 (2) 一：RLS遗忘因子法 (2) RLS遗忘因子法仿真思路和辨识结果 (2) 遗忘因子法的特点： (3) 二：RFF遗忘因子递推算法 (4) 仿真思路和辨识结果 (4) 遗忘因子递推算法的特点： (5) 三：RFM限定记忆法 (5) 仿真思路和辨识结果 (5) RFM限定记忆法的特点： (7) 四：RCLS偏差补偿最小二乘法 (7) 仿真思路和辨识结果 (7) RCLS偏差补偿最小二乘递推算法的特点： (9) 五：增广最小二乘法 (9) 仿真思路和辨识结果 (9) RELS增广最小二乘递推算法的特点： (11) 六：RGLS广义最小二乘法 (12) 仿真思路和辨识结果 (12) RGLS广义最小二乘法的特点： (14) 七：RIV辅助变量法 (14) 仿真思路和辨识结果 (14) RIV辅助变量法的特点： (16) 八：Cor-ls相关最小二乘法（二步法） (17) 仿真思路和辨识结果 (17) Cor-ls相关最小二乘法（二步法）特点： (18) 九：MLS多级最小二乘法 (19) 仿真思路和辨识结果 (19) MLS多级最小二乘法的特点： (22) 十：yule_walker辨识算法 (23) 仿真思路和辨识结果 (23) yule_walker辨识算法的特点： (24) 第二部分：matlab程序 (24) 一：RLS遗忘因子算法程序 (24) 二：RFF遗忘因子递推算法 (26) 三：RFM限定记忆法 (28) 四：RCLS偏差补偿最小二乘递推算法 (31) 五：RELS增广最小二乘的递推算法 (33) 六;RGLS 广义最小二乘的递推算法 (36) 七：Tally辅助变量最小二乘的递推算法 (39) 八：Cor-ls相关最小二乘法（二步法） (42) 九：MLS多级最小二乘法 (45) 十yule_walker辨识算法 (49) 基于正交最小二乘算法的RBF神经网络 一、实验环境 硬件平台Win10 64位操作系统，1.5GHZ，4G内存，软件版本MA TLAB2015b 二、实验数据 训练数据集： T F W M Y Q 1000.00130010000 20.00740.03350.00150.00320.010610000 30.00430.022300.00470.005310000 40.5520.30170.25810.30940.231601000 50.54520.27930.26110.29880.203601000 60.55020.24580.27170.31150.234701000 70.24620.15080.09470.09640.099900100 80.25350.10610.09680.09710.08100100 90.26650.08940.09370.09940.090800100 100.66150.52510.51950.471100010 110.67380.44130.52250.47320.966700010 120.66650.47490.52550.47690.975800010 13110.981210.820600001 140.97970.977710.9960.775900001 150.98460.97270.98470.98570.7600001 测试数据集： T F W M Y Q 10.00310.02350.00050.0030.004510000 20.54930.26260.26590.30880.222101000 30.25720.10060.09580.09810.08900100 40.67040.49720.52350.47410.979100010 50.9920.98990.99790.99370.797900001 三、算法介绍 RBF函数网络从结构上看是一个3层前馈网络，包括一个输入层、一个输出层和一个隐含层。输入层节点的作用是将输入数据传递到隐含层节点。隐含层节点称为RBF节点，其激活函数为辐射状函数的神经元构成，通常采用高斯型函数：Array 图1 RBF结构 RBF网络中所用的非线性函数的形式对网络性能的影响并不是至关重要的，关键因素是基函数中心的选取，中心选取不当构造出来的RBF网络的性能一般不能令人满意。例如，如果某些中心靠的太近，会产生近似线形相关，从而带来数值上的病变条件。基本的RBF 神经网络采用随机抽取固定中心的方法，在输入样本数据的分布具有某种特性的情况下，采用这种方法解决给定问题就显得简单可行了。而针对其缺陷，已经有许多改进的方法，其中 之一就是利用最小二乘法选取中心，训练网络权重。 第三章 递归最小二乘(RLS)自适应均衡算法 §3.1 引言 在自适应滤波系统中，最陡梯度(LMS )法由于其简单获得了广泛的应用。但各种LMS 算法均有收敛速度较慢(收敛所需码元数多)，对非平稳信号的适应性差(且其中有些调整延时较大)的缺点。究其原因主要是LMS 算法只是用以各时刻的抽头参量等作该时刻数据块估计时平方误差均最小的准则，而未用现时刻的抽头参量等来对以往各时刻的数据块均作重新估计后的累积平方误差最小的原则(即所谓的最小平方(LS )准则)。 为了克服收敛速度慢，信号非平稳适应性差的缺点，根据上述内容，可采用新的准则，即在每时刻对所有已输入信号而言重估的平方误差和最小的准则(即LS 准则)。从物理概念上可见，这是个在现有的约束条件下利用了最多可利用信息的准则，即在一定意义上最有效，信号非平稳的适应性能也应最好的准则。这样建立起来的迭代方法就是递归最小二乘(RLS ：Recursive Least Square )算法，又称为广义Kalman 自适应算法。 用矩阵的形式表示RLS 算法非常方便，因此我们首先定义一些向量和矩阵。假定在时刻t ，均衡器的输入信号为t r ，线性均衡器对于信息符号的估计可以表示为 ∑-=--=K K j j t j r t c t I )1()(? 式(3-1) 让)1(-t c j 的下标j 从0=j 到1-=N j ，同时定义K t v t y +=)(，则)(?t I 变为 ∑-=--=1 )()1()(?N j j j t y t c t I )()1(t Y t C N N -'= 式(3-2) 其中)1(-t C N 和)(t Y N 分别为均衡器系数)1(-t c j ，1,,1,0-=N j Λ和输入信号 )(j t y -，1,,1,0-=N j Λ的列向量。 类似的，在DFE 均衡器结构中，均衡器系数)(t c j ，1,,1,0-=N j Λ的前11+K 个系数为前向滤波器系数，剩下的112--=K N K 为反馈滤波器系数。用来预测 )(?t I 的数据为21~,~,,,11K t t t K t I I r r --++Λ，其中21,~K j I j t ≤≤-为判决器先前作出判决的数 据。这里，我们忽略判决器判错的情况，因而21,~ K j I I j t j t ≤≤=--。同时为方便起见定义 最小二乘法参数辨识 201403027 摘要:系统辨识在工程中的应用非常广泛,系统辨识的方法有很多种,最小 二乘法是一种应用极其广泛的系统辨识方法.阐述了动态系统模型的建立及其最小二乘法在系统辨识中的应用,并通过实例分析说明了最小二乘法应用于系统辨识中的重要意义. 关键词:最小二乘法;系统辨识;动态系统 Abstract: System identification in engineering is widely used, system identification methods there are many ways， least squares method is a very wide range of application of system identification method and the least squares method elaborated establish a dynamic system models in System Identification applications and examples analyzed by the least squares method is applied to illustrate the importance of system identification. Keywords: Least Squares; system identification; dynamic system 引言 随着科学技术的不断发展,人们认识自然、利用自然的能力越来越强,对于未知对象的探索也越来越深入.我们所研究的对象,可以依据对其了解的程度分为三种类型:白箱、灰箱和黑箱.如果我们对于研究对象的内部结构、内部机制了解很深入的话,这样的研究对象通常称之为“白箱”;而有的研究对象,我们对于其内部结构、机制只了解一部分,对于其内部运行规律并不十分清楚,这样的研究对象通常称之为“灰箱”;如果我们对于研究对象的内部结构、内部机制及运行规律均一无所知的话,则把这样的研究对象称之为“黑箱”.研究灰箱和黑箱时,将研究的对象看作是一个系统,通过建立该系统的模型,对模型参数进行辨识来确定该系统的运行规律.对于动态系统辨识的方法有很多,但其中应用最广泛,辨识 效果良好的就是最小二乘辨识方法,研究最小二乘法在系统辨识中的应用具有现实的、广泛的意义. 1．1 系统辨识简介 系统辨识是根据系统的输入输出时间函数来确定描述系统行为的数学模型。现代控制理论中的一个分支。通过辨识建立数学模型的目的是估计表征系统行为的重要参数，建立一个能模仿真实系统行为的模型，用当前可测量的系统的输入和输出预测系统输出的未来演变，以及设计控制器。对系统进行分析的主要问题是根据输入时间函数和系统的特性来确定输出信号。对系统进行控制的主要问题是根据系统的特性设计控制输入，使输出满足预先规定的要求。而系统辨识所研究的问题恰好是这些问题的逆问题。通常，预先给定一个模型类μ={M}（即给定一类已知结构的模型），一类输入信号u和等价准则J=L(y，yM)(一般情况下，J是误差函数，是过程输出y和模型输出yM的一个泛函)；然后选择使误差函数J达到最小的模型，作为辨识所要求的结果。系统辨识包括两个方面：结构辨识和参数估计。在实际的辨识过程中，随着使用的方法不同，结构辨识和参数估计这两个方面并不是截然分开的，而是可以交织在一起进行的。 1.2系统辨识的目的 在提出和解决一个辨识问题时，明确最终使用模型的目的是至关重要的。它对模型类（模型结构）、输入信号和等价准则的选择都有很大的影响。通过辨识建立数学模型通常有四个目的。 ①估计具有特定物理意义的参数有些表征系统行为的重要参数是难以直接测量的，例如在生理、生态、环境、经济等系统中就常有这种情况。这就需要通过能观测到的输入输出数据，用辨识的方法去估计那些参数。 ②仿真仿真的核心是要建立一个能模仿真实系统行为的模型。用于系统分析的仿真模型要求能真实反映系统的特性。用于系统设计的仿真，则强调设计参数能正确地符合它本身的物理意义。 ③预测这是辨识的一个重要应用方面，其目的是用迄今为止系统的可测量的输入和输出去预测系统输出的未来的演变。例如最常见的气象预报，洪水预报，其他如太阳黑子预报，市场价格的预测，河流污染物含量的预测等。预测模型辨识的等价准则主要是使预测误差平方和最小。只要预测误差小就是好的预测 偏最小二乘法 1.1 基本原理 偏最小二乘法（PLS ）是基于因子分析的多变量校正方法，其数学基础为主成分分析。但它相对于主成分回归（PCR ）更进了一步，两者的区别在于PLS 法将浓度矩阵Y 和相应的量测响应矩阵X 同时进行主成分分解： X=TP+E Y=UQ+F 式中T 和U 分别为X 和Y 的得分矩阵，而P 和Q 分别为X 和Y 的载荷矩阵，E 和F 分别为运用偏最小二乘法去拟合矩阵X 和Y 时所引进的误差。 偏最小二乘法和主成分回归很相似，其差别在于用于描述变量Y 中因子的同时也用于描述变量X 。为了实现这一点，数学中是以矩阵Y 的列去计算矩阵X 的因子。同时，矩阵Y 的因子则由矩阵X 的列去预测。分解得到的T 和U 矩阵分别是除去了大部分测量误差的响应和浓度的信息。偏最小二乘法就是利用各列向量相互正交的特征响应矩阵T 和特征浓度矩阵U 进行回归： U=TB 得到回归系数矩阵，又称关联矩阵B ： B=(T T T -1)T T U 因此，偏最小二乘法的校正步骤包括对矩阵Y 和矩阵X 的主成分分解以及对关联矩阵B 的计算。 1.2主成分分析 主成分分析的中心目的是将数据降维，以排除众多化学信息共存中相互重叠的信息。他是将原变量进行转换，即把原变量的线性组合成几个新变量。同时这些新变量要尽可能多的表征原变量的数据结构特征而不丢失信息。新变量是一组正交的，即互不相关的变量。这种新变量又称为主成分。 如何寻找主成分，在数学上讲，求数据矩阵的主成分就是求解该矩阵的特征值和特征矢量问题。下面以多组分混合物的量测光谱来加以说明。假设有n 个样本包含p 个组分，在m 个波长下测定其光谱数据，根据比尔定律和加和定理有： A n×m =C n×p B p×m 如果混合物只有一种组分，则该光谱矢量与纯光谱矢量应该是方向一致，而大小不同。换句话说，光谱A 表示在由p 个波长构成的p 维变量空间的一组点（n 个），而这一组点一定在一条通过坐标原点的直线上。这条直线其实就是纯光谱b 。因此由m 个波长描述的原始数据可以用一条直线，即一个新坐标或新变量来表示。如果一个混合物由2个组分组成，各组分的纯光谱用b1，b2表示，则有： 1122 T T T i i i a c b c b =+ 有上式看出，不管混合物如何变化，其光谱总可以用两个新坐标轴b1,b2来表示。因此可以 推出，如果混合物由p 个组分组成，那么混合物的光谱就可由p 个主成分轴的线性组合表示。基于FPGA的递归最小二乘算法的研究与实现
最小二乘一次完成算法(程序)
递推最小二乘法算法
几种最小二乘法递推算法的小结
算法设计及分析递归算法典型例题
递归算法的优缺点
递归算法的优缺点
普通最小二乘法(OLS)
基于最小二乘法的系统辨识的设计与开发(整理版)
递归算法工作栈的变化详解
用matlab实现最小二乘递推算法辨识系统参数
(完整word版)多种最小二乘算法分析+算法特点总结
基于最小二乘算法的RBF
递归最小二(RLS)自适应均衡算法
系统辨识—最小二乘法汇总
偏最小二乘法算法