第一篇：多种最小二乘算法分析+算法特点总结
第一部分：程序设计思路、辨识结果分析和算法特点总结................................................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
第一部分：程序设计思路、辨识结果分析和算法特点总结
一：RLS遗忘因子法
RLS遗忘因子法仿真思路和辨识结果
仿真对象如下：
其中，v(k)为服从N(0,1)分布的白噪声。输入信号u(k)采用M 序列，幅度为 1。M 序列由 9 级移位寄存器产生，x(i)=x(i-4)⊕x(i-9)。选择如下辨识模型：
加权阵取Λ = I。
衰减因子β = 0.98，数据长度 L = 402。辨识结果与理论值比较，基本相同。辨识结果可信： Estimate =-1.4666 0.6503 0.9736 0.3035 遗忘因子法的特点：
对老数据加上遗忘因子，以降低老数据对辨识的影响，相对增加新数据对辨识的影响，不会出现“数据饱和”现象。如模型噪声是有色噪声，则Ø是有偏估计量。常用作其他辨识方式的起步，以获得其他方式的初始值。
二：RFF遗忘因子递推算法 仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同。
其中，0 ≤µ≤1为遗忘因子，此处取0.98。始条件：
参数a1 a2 b1 b2的估计值: ans =-1.4977 0.6863 1.1903 0.4769 待估参数变化过程如图所示：
数据长度L=402，初
遗忘因子递推算法的特点：
从上面两个例子可以看出对于相同的仿真对象，一次算法和递推算法结果基本一致，但递推算法可以实现在线实时辨识，而且可以减少计算量和存储量。
三：RFM限定记忆法 仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同。
辨识结果与理论值比较，基本相同。辨识结果可信： 参数 a1 a2 b1 b2 的估计值为： Theta_a =-1.5128 0.7099 0.8393 0.4416 待估参数的过渡过程如下：
RFM限定记忆法的特点：
辨识所使用的数据长度保持不变，每增加一个新数据就抛掉一个老数据，使参数估计值始终只依赖于有限个新数据所提供的新消息，克服了遗忘因子法不管多老的数据都在起作用的缺点，因此该算法更能有效的克服数据饱和现象。
四：RCLS偏差补偿最小二乘法 仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同。
辨识结果与理论值比较，基本相同。辨识结果可信： 参数a1 a2 b1 b2的估计值为： ans =-1.4916
0.7005 1.0365 0.4271
RCLS偏差补偿最小二乘递推算法的特点：
算法思想：：在最小二乘参数估计值的基础上，引进补偿项σW2C-1D Ø0，则获得了参数的无偏估计。针对模型噪声来说，RCLS算法的适应能力比RLS更好。
五：增广最小二乘法 仿真思路和辨识结果
考虑如下仿真对象：
其中，为服从N(0,1)分布的白噪声。输入信号采用 M 序列，幅度为 1。M 序列由 9 级移位寄存器产生，x(i)=x(i-4)⊕x(i-9)。
选择如下的辨识模型：
观测数据长度取L =402。加权阵取Λ=I。
辨识结果与理论值比较，基本相同，同时又能获得噪声模型的参数估计。辨识结果可信：
参数a1、a2、b1、b2、d1、d2估计结果：
ans =-1.5000 0.7000 1.0001 0.5002-0.9999 0.2000
RELS增广最小二乘递推算法的特点：
增广最小二乘的递推算法对应的噪声模型为滑动平均噪声，扩充了参数向量和数据向量H（k）的维数，把噪声模型的辨识同时考虑进去。最小二乘法只能获得过程模型的参数估计，而增广最小二乘法
同时又能获得噪声模型的参数估计，若噪声模型为平均滑动模型，则只能用RELS算法才能获得无偏估计。当数据长度较大时，辨识精度低于极大似然法。
六：RGLS广义最小二乘法 仿真思路和辨识结果
模型结构选择：
模型结构选用：
其中，各个参数的真值为：
广义最小二乘算法为：
辨识结果与理论值比较，基本相同，同时又能获得噪声传递系数的参数估计。辨识结果可信： 参数a1 a2 b1 b2的估计结果： ans =-1.5058 0.6972 0.9316 0.4833
噪声传递系数c1 c2的估计结果： ans = 0.6203 0.2210
RGLS广义最小二乘法的特点：
该算法用于自回归输入模型，是一种迭代的算法。其基本思想是基于对数据先进行一次滤波处理，后利用普通最小二乘法对滤波后的数据进行辨识，进而获得无偏一致估计。但是当过程的输出信噪比比较大或模型参数较多时，这种数据白色化处理的可靠性就会下降，辨识结果往往会是有偏估计。数据要充分多，否则辨识精度下降。模型阶次不宜过高。初始值对辨识结果有较大影响。
七：RIV辅助变量法 仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同,只不过此处噪声为有色噪声，产生过程为：e(k)=v(k)+0.5v(k-1)+0.2v(k-2),v(k)为0均值的不相关随机噪声。
按照Tally法选取辅助变量x(k)=z(k-nd), nd为误差传递函数的阶数，此处为2.则有
辅助变量法的递推公式可写成：
辨识结果与理论值比较，基本相同。辨识结果可信： 参数a1 a2 b1 b2的估计结果： ans =-1.5314 0.7461 0.9999 0.4597
RIV辅助变量法的特点：
适当选择辅助变量，使之满足相应条件，参数估计值就可以是无偏一致。估计辅助变量法的计算量与最小二乘法相当，但辨识效果却比最小二乘法好的多。尤其当噪声是有色的，而噪声的模型结构又不好确定时，增广最小二乘法和广义最小二乘法一般都不好直接应用，因为他们需要选用特定的模型结构，而辅助变量法不需要确定噪声的模型结构，因此辅助变量法就显得更为灵活，但辅助变量法不能同时获得噪声模型的参数估计。
八：Cor-ls相关最小二乘法（二步法）仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同：，e(k)=v(k)+0.5v(k-1)+0.2v(k-2),v(k)为0均值的不相关随机噪声。Cor-ls的递推公式可写成:
其中：M（k）为输入M序列。初始条件：，辨识结果与理论值比较，基本相同，辨识结果可信： 参数a1 a2 b1 b2的估计结果： ans =-1.4896
0.6858 1.0168 0.4362
Cor-ls相关最小二乘法（二步法）特点：
把辨识分成两步进行：第一步：利用相关分析法获得对象的非参数模型（脉冲响应或相关函数）；第二步：利用最小二乘法、辅助变量法或增广最小二乘法等，进一步求的对象的参数模型。如果模型噪声与输入无关，则Cor-ls相关最小二乘法（二步法）可以得到较好的辨识结果。Cor-ls相关最小二乘法（二步法）实质上是先对数据进行一次相关分析，滤除了有色噪声的影响，再利用最小二乘法必然就会改善辨识结果。能适应较宽广的噪声范围，计算量不大，初始值
对辨识结果影响较小。但要求输入信号与噪声不相关。
九：MLS多级最小二乘法 仿真思路和辨识结果
仿真对象如下:
其中，u(k)是输入变量，此处为 M 序列；v(k)是零均值、方差为 1 的不相关随机噪声，通过控制λ的大小来控制信噪比。辨识模型结构选用:
其中，辨识过程如下：
第一级，辅助模型参数辨识 原模型可写为:
利用最小二乘法可获得辅助模型的参数无偏一致估计值:
数据长度 L=400，第二级，过程模型参数辨识:
根据最小二乘算法可以获得过程模型的参数估计值为:
第三级，噪声模型参数辨识:
根据最小二乘算法可以获得过程模型的参数估计值为
辨识结果与理论值比较，基本相同。辨识结果可信：
第一级 辅助模型参数 e1 e2 e3 e3 e4 f1 f2 f3 f4 辨识结果： E = 1.9062 1.4454 0.5279 0.0613-0.0026 0.7988-0.8694-1.3037-0.6318
第二级 过程模型参数 a1 a2 a3 b1 b2 辨识结果： E2 = 0.9304 0.1596 0.0113 0.7998-1.6502 第三级 噪声模型参数 c1 c2 辨识结果： E3 = 0.9750 0.3824 MLS多级最小二乘法的特点：
当信噪比较大时，采用广义最小二乘法可能会出现多个局部收敛点，解决这个问题的方法可用多级最小二乘法，一般来说多级最小二乘法包含三级辨识过程。利用输入输出数据，通过多级最小二乘法，可分别求的辅助模型，过程模型和噪声模型的参数估计值。在高噪声的情况下，多级最小二乘法明显优于广义最小二乘法，其收敛点唯一。
十：yule_walker辨识算法 仿真思路和辨识结果
仿真对象如下：，z(k)是可观测变量；v(k)是均值为零，方差为 1 的不相关随机噪声；数据长度取 L=1024。相关函数按下式计算 ：
参数的估计算法按下式计算：
辨识结果与理论值比较，基本相同，同时又能获得噪声模型的参数估计。辨识结果可信： 辨识结果为： Theta = 0.8597 0.2955
-0.0034 d = 1.0025 yule_walker辨识算法的特点：
yule_walker辨识算法可以方便的辨识形如估计值。的参数第二部分：matlab程序
一：RLS遗忘因子算法程序
clear clc %========================================== %最小二乘法辨识对象
% Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+v(k)%==========产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%初始值 n=403;%n为脉冲数目 M=[];%存放M序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);
for j=9:-1:2 x(j)=x(j-1);end x(1)=temp;end;%产生高斯白噪声 v=randn(1,400);z=[];z(1)=-1;z(2)=0;u=0.98;% 遗忘因子 L=400;for i=3:402 z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)+v(i-2);zstar(i)=z(i)*u^(L-i+2);end H=zeros(400,4);for i=1:400 H(i,1)=-z(i+1)*u^(L-i);H(i,2)=-z(i)*u^(L-i);H(i,3)=M(i+1)*u^(L-i);H(i,4)=M(i)*u^(L-i);
end Estimate=inv(H'*H)*H'*(zstar(3:402))' 二：RFF遗忘因子递推算法
%最小二乘遗忘因子的递推算法仿真对象
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+v(k)%======================================== clear clc %==========400 个产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n为脉冲数目 M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2 x(j)=x(j-1);end x(1)=temp;end %===========产生均值为0，方差为1 的高斯白噪声=========
v=randn(1,400);%==============产生观测序列z================= z=zeros(402,1);z(1)=-1;z(2)=0;for i=3:402 z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)+v(i-2);end %==============递推求解================= P=10*eye(4);%估计方差
Theta=zeros(4,401);%参数的估计值，存放中间过程估值 Theta(:,1)=[0.001;0.001;0.001;0.001];K=zeros(4,400);%增益矩阵 K=[10;10;10;10];u=0.98;%遗忘因子 for i=3:402 h=[-z(i-1);-z(i-2);M(i-1);M(i-2)];K=P*h*inv(h'*P*h+u);Theta(:,i-1)=Theta(:,i-2)+K*(z(i)-h'*Theta(:,i-2));P=(eye(4)-K*h')*P/u;end %==========================输出结果及作图
============================= disp('参数a1 a2 b1 b2的估计值:')Theta(:,401)i=1:401;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估参数过渡过程')三：RFM限定记忆法
%限定记忆最小二乘的递推算法辨识对象
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+v(k)%======================================== clear clc %==========产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n为脉冲数目 M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2
x(j)=x(j-1);end x(1)=temp;end %===========产生均值为0，方差为1 的高斯白噪声========= v=randn(1,402);%==============产生观测序列z================= z=zeros(402,1);z(1)=-1;z(2)=0;for i=3:402 z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)+v(i);end %递推求解
P_a=100*eye(4);%估计方差 Theta_a=[3;3;3;3];L=20;%记忆长度
for i=3:L-1 %利用最小二乘递推算法获得初步参数估计值和P阵
h=[-z(i-1);-z(i-2);M(i-1);M(i-2)];K=P_a*h*inv(h'*P_a*h+1);Theta_a=Theta_a+K*(z(i)-h'*Theta_a);
P_a=(eye(4)-K*h')*P_a;end for k=0:380 hL=[-z(k+L-1);-z(k+L-2);M(k+L-1);M(k+L-2)];%增加新数据的信息
K_b=P_a*hL*inv(1+hL'*P_a*hL);Theta_b=Theta_a+K_b*(z(k+L)-hL'*Theta_a);P_b=(eye(4)-K_b*hL')*P_a;
hk=[-z(k+L);-z(k+L-1);M(k+L);M(k+L-1);];%去掉老数据的信息 K_a=P_b*hk*inv(1+hk'*P_b*hk);Theta_a=Theta_b-K_a*(z(k+L+1)-hk'*Theta_b);P_a=(eye(4)+K_a*hk')*P_b;Theta_Store(:,k+1)=Theta_a;end
%========================输出结果及作图=========================== disp('参数 a1 a2 b1 b2 的估计值为：')Theta_a i=1:381;figure(1)
plot(i,Theta_Store(1,:),i,Theta_Store(2,:),i,Theta_Store(3,:),i,Theta_Store(4,:))title('待估参数过渡过程')四：RCLS偏差补偿最小二乘递推算法
%偏差补偿最小二乘的递推算法辨识对象
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+v(k)%======================================== clear clc %==========产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n为脉冲数目 M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2 x(j)=x(j-1);end x(1)=temp;end
%===========产生均值为0，方差为1 的正态分布噪声========= v=random('Normal',0,1,1,400);%==============产生观测序列z================= z=zeros(402,1);z(1)=-1;z(2)=0;for i=3:402 z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)+v(i-2);end %===================递推求解================== %赋初值
P=100*eye(4);%估计方差
Theta=zeros(4,401);%参数的估计值，存放中间过程估值 Theta(:,1)=[3;3;3;3];K=[10;10;10;10];%增益 J=0;ThetaC=zeros(4,401);%偏差补偿后的估计值 ThetaC(:,1)=[2;3;1;3.5];D=[1 0 0 0;0 1 0 0;0 0 0 0;0 0 0 0];for i=3:402 h=[-z(i-1);-z(i-2);M(i-1);M(i-2)];J=J+(z(i-1)-h'*Theta(:,i-1))^2/(1+h'*P*h);
K=P*h*inv(h'*P*h+1);Theta(:,i-1)=Theta(:,i-2)+K*(z(i)-h'*Theta(:,i-2));P=(eye(4)-K*h')*P;end es=J/((i-1)*(1+(ThetaC(:,i-2))'*D*Theta(:,i-1)));ThetaC(:,i-1)=Theta(:,i-1)+(i-1)*es*P*D*ThetaC(:,i-2);%==============输出参数估计结果及作图================ disp('参数a1 a2 b1 b2的估计值为：')Theta(:,401)i=1:401;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估参数过渡过程')
五：RELS增广最小二乘的递推算法
%增广最小二乘的递推算法辨识对象
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)-v(k+1)+0.2*v(k)%======================================== clear clc
%==========产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n为脉冲数目 M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2 x(j)=x(j-1);end x(1)=temp;end %===========产生均值为0，方差为1 的高斯白噪声========= v=randn(1,402);%==============产生观测序列z================= z=zeros(402,1);z(1)=-1;z(2)=0;for i=3:402 z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)-v(i-1)+0.2*v(i-2);end
%递推求解
P=100*eye(6);%估计方差
Theta=zeros(6,401);%参数的估计值，存放中间过程估值 Theta(:,1)=[3;3;3;3;3;3];% K=zeros(4,400);%增益矩阵 K=[10;10;10;10;10;10];for i=3:402 h=[-z(i-1);-z(i-2);M(i-1);M(i-2);v(i-1);v(i-2)];K=P*h*inv(h'*P*h+1);Theta(:,i-1)=Theta(:,i-2)+K*(z(i)-h'*Theta(:,i-2));P=(eye(6)-K*h')*P;end %========================= disp('参数a1、a2、b1、b2、d1、d2估计结果：')Theta(:,401)i=1:401;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:),i,Theta(5,:),i,Theta(6,:))title('待估参数过渡过程')
六;RGLS 广义最小二乘的递推算法
%广义最小二乘的递推算法仿真模型
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+e(k)%e(k+2)+2.1*e(k+1)-2.5*e(k)=v(k+2)%======================================== clear clc %==========400 个产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n为脉冲数目 M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2 x(j)=x(j-1);end x(1)=temp;end %===========产生均值为0，方差为1 的高斯白噪声========= v=randn(1,400);e=[];e(1)=v(1);e(2)=v(2);
for i=3:400 e(i)=0*e(i-1)+0*e(i-2)+v(i);end %==============产生观测序列z================= z=zeros(400,1);z(1)=-1;z(2)=0;for i=3:400 z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)+e(i);end %变换后的观测序列 zf=[];zf(1)=-1;zf(2)=0;for i=3:400 zf(i)=z(i)-0*z(i-1)-0*z(i-2);end %变换后的输入序列
uf=[];uf(1)=M(1);uf(2)=M(2);for i=3:400 uf(i)=M(i)-0*M(i-1)-0*M(i-2);end
%赋初值
P=100*eye(4);%估计方差
Theta=zeros(4,400);%参数的估计值，存放中间过程估值 Theta(:,2)=[3;3;3;3];K=[10;10;10;10];%增益 PE=10*eye(2);ThetaE=zeros(2,400);ThetaE(:,2)=[0.5;0.3];KE=[10;10];%递推Theta for i=3:400 h=[-zf(i-1);-zf(i-2);uf(i-1);uf(i-2)];K=P*h*inv(h'*P*h+1);Theta(:,i)=Theta(:,i-1)+K*(z(i)-h'*Theta(:,i-1));P=(eye(4)-K*h')*P;end he=[-e(i-1);-e(i-2)];%递推ThetaE KE=PE*he*inv(1+he'*PE*he);ThetaE(:,i)=ThetaE(:,i-1)+KE*(e(i)-he'*ThetaE(:,i-1));PE=(eye(2)-KE*he')*PE;%=====================输出结果及作图
========================= disp('参数a1 a2 b1 b2的估计结果：')Theta(:,400)disp('噪声传递系数c1 c2的估计结果：')ThetaE(:,400)i=1:400;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估参数过渡过程')七：Tally辅助变量最小二乘的递推算法
%Tally辅助变量最小二乘的递推算法
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+e(k)，e(k)为有色噪声
%e(k)=v(k)+0.5*v(k-1)+0.2*v(k-2),v(k)为零均值的不相关随机噪声
%======================================== clear clc %==========产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n为脉冲数目
M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2 x(j)=x(j-1);end x(1)=temp;end %===========产生均值为0，方差为1 的高斯白噪声========= v=randn(1,400);e=[];e(1)=0.3;e(2)=0.5;for i=3:400 e(i)=v(i)+0.5*v(i-1)+0.2*v(i-2);end %==============产生观测序列z================= z=zeros(402,1);z(1)=-1;z(2)=0;for i=3:400
z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)+e(i);end %递推求解
P=100*eye(4);%估计方差
Theta=zeros(4,400);%参数的估计值，存放中间过程估值 Theta(:,1)=[3;3;3;3];Theta(:,2)=[3;3;3;3];Theta(:,3)=[3;3;3;3];Theta(:,4)=[3;3;3;3];% K=zeros(4,400);%增益矩阵 K=[10;10;10;10];for i=5:400 h=[-z(i-1);-z(i-2);M(i-1);M(i-2)];hstar=[-z(i-2-1);-z(i-2-2);M(i-1);M(i-2)];%辅助变量 %递推算法
K=P*hstar*inv(h'*P*hstar+1);Theta(:,i)=Theta(:,i-1)+K*(z(i)-h'*Theta(:,i-1));P=(eye(4)-K*h')*P;end %==================结果输出及作图=================== disp('参数a1 a2 b1 b2的估计结果：')Theta(:,400)
i=1:400;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估参数过渡过程')八：Cor-ls相关最小二乘法（二步法）
%两步法的递推算法
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+e(k)，e(k)为零均值的不相关随机噪声
%e(k)=v(k)+0.5*v(k-1)+0.2*v(k-2)%======================================== clear clc %==========产生M序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n为脉冲数目 M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2 x(j)=x(j-1);
end x(1)=temp;end %===========产生均值为0，方差为1 的高斯白噪声========= v=randn(1,400);e=[];e(1)=0.3;e(2)=0.5;for i=3:400 e(i)=v(i)+0.5*v(i-1)+0.2*v(i-2);end %==============产生观测序列z=========== z=zeros(402,1);z(1)=-1;z(2)=0;for i=3:400 z(i)=1.5*z(i-1)-0.7*z(i-2)+M(i-1)+0.5*M(i-2)+e(i);end %递推求解
P=100*eye(4);%估计方差
Theta=zeros(4,400);%参数的估计值，存放中间过程估值 Theta(:,1)=[3;3;3;3];
Theta(:,2)=[3;3;3;3];Theta(:,3)=[3;3;3;3];Theta(:,4)=[3;3;3;3];K=zeros(4,400);%增益矩阵 K=[10;10;10;10];for i=5:400 h=[-z(i-1);-z(i-2);M(i-1);M(i-2)];hstar=[M(i-1);M(i-2);M(i-3);M(i-4)];%辅助变量 %递推
K=P*hstar*inv(h'*P*hstar+1);Theta(:,i)=Theta(:,i-1)+K*(z(i)-h'*Theta(:,i-1));P=(eye(4)-K*h')*P;end %==================结果输出及作图=================== disp('参数a1 a2 b1 b2的估计结果：')Theta(:,400)i=1:400;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估参数过渡过程')
九：MLS多级最小二乘法
clear clc %========================================== % Z(k+3)=-0.9*Z(k+2)-0.15*Z(k+1)-0.02*z(k)+0.7*u(k+2)-1.5*u(k+1)+e(k)%e(k+2)+1.0*e(k+1)+0.41*e(k)=r*v(k+2)%==========产生M 序列作为输入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=405;%n为脉冲数目 M=[];%存放M 序列 for i=1:n temp=xor(x(4),x(9));M(i)=x(9);for j=9:-1:2 x(j)=x(j-1);end x(1)=temp;end %===========产生均值为0，方差为1 的高斯白噪声============= v=randn(1,405);
e=[];e(1)=0.3;e(2)=0.7;r=0.9;%控制信噪比 for i=3:405 e(i)=-1.0*e(i-1)-0.41*e(i-2)+r*v(i);end %=================产生观测序列=================== z=[];z(1)=-1;z(2)=0;z(3)=1.5;for i=4:405 z(i)=-0.9*z(i-1)-0.15*z(i-2)-0.02*z(i-3)+0.7*M(i-1)-1.5*M(i-2)+e(i);end %================第一级辨识 辅助模型参数辨识================== H=zeros(400,9);for i=1:400 H(i,1)=-z(i+4);H(i,2)=-z(i+3);
H(i,3)=-z(i+2);H(i,4)=-z(i+1);H(i,5)=-z(i);H(i,6)=M(i+4);H(i,7)=M(i+3);H(i,8)=M(i+2);H(i,9)=M(i+1);end disp('第一级 辅助模型参数 e1 e2 e3 e3 e4 f1 f2 f3 f4 辨识结果：')E=inv(H'*H)*H'*(z(6:405))' e1=E(1);e2=E(2);e3=E(3);e4=E(4);e5=E(5);f1=E(6);f2=E(7);f3=E(8);f4=E(9);%=================第二级辨识 过程模型参数辨识====================
z2=[f1;f2;f3;f4;0;0;0];H2=[ 0 0 0 1 0;
-f1 0 0 e1 1;
-f2-f1 0 e2 e1;
-f3-f2-f1 e3 e2;
-f4-f3-f2 e4 e3;
0-f4-f3 e5 e4;
0 0-f4 0 e5;];
disp('第二级 过程模型参数 a1 a2 a3 b1 b2 辨识结果：')E2=inv(H2'*H2)*H2'*z2 a1=E2(1);a2=E2(2);a3=E2(3);b1=E2(4);
b2=E2(5);%================第三级辨识 噪声模型参数辨识======================= z3=[e1-a1;e2-a2;e3-a3;e4;e5;f2-b2;f3;f4];H3=[1 0;a1 1;a2 a1;a3 a2;0 a3;b1 0;b2 b1;0 b2;];disp('第三级 噪声模型参数 c1 c2 辨识结果：')E3=inv(H3'*H3)*H3'*z3 十yule_walker辨识算法
%Yule-Walker 辨识算法
%辨识模型：z(k)=-0.9*z(k-1)-0.36*z(k-2)-0.054*z(k-3)+v(k)%============== %产生随机噪声
v=random('Normal',0,1,1,1024);%均值为零，方差为 1
%产生观测序列 z=[];z(1)=0;z(2)=1;z(3)=1.5;for i=4:1024 z(i)=-0.9*z(i-1)-0.36*z(i-2)-0.054*z(i-3)+v(i);end %计算 z(k)的自相关函数 Rz0=0;Rz1=0;Rz2=0;Rz3=0;for i=1:1024 Rz0=Rz0+z(i)^2;end Rz0=Rz0/1024;for i=1:1023 Rz1=Rz1+z(i+1)*z(i);end Rz1=Rz1/1024;for i=1:1022
第二篇：算法总结
算法分析与设计总结报告
71110415 钱玉明
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
下面我将谈谈我对这门课程的心得与体会。
一、数学是算法的基础
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。
这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、算法与应用紧密相关
我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。
这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。
四、对计算模型和NP问题的理解
由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。
首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。
NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。
最后谈谈对这门课程的建议
①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。
②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。
③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。
第三篇：算法总结
算法分块总结
为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。
图论模型的应用
分层图思想的应用：
用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。
这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：
最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：
容量有上下界的最大流的应用：
欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：
求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：
抽象成数学模型就是：
设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k 首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。 假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树； 2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。 加边和去边过程，利用动态规划优化特别值得注意。 次小生成树： 加边和去边很值得注意。 每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法： 首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。 最短路径的应用： Dijkstra 算法应用： Folyed 算法应用： Bellman-Ford 算法的应用： 差分约束系统的应用： 搜索算法 搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用： IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索： 可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。 动态规划 动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。 状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP： 状态划分比较困难的题目： 树形DP： 四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2) 高档数据结构的应用 并查集的应用： 巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用： 总结用线段树解题的方法 根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等 树的每个节点根据题目所需，设置变量记录要求的值 用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。 在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。 Trie的应用：； Trie图的应用探索： 后缀数组的应用研究： 在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。 树状数组的应用探索：； 计算几何 掌握基本算法的实现。凸包的应用：； 半平面交算法的应用：； 几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：； 转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：； 经典算法：找平面上的最近点对。 贪心 矩形切割 二分思想应用 活用经典算法 利用归并排序算法思想求数列的逆序对数： 利用快速排序算法思想，查询N个数中的第K小数： 博弈问题 博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。 第一类：推结论。典型题目： 第二类：递推。典型题目： 比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质： 1． 所有的结束位置都是P位置。 2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。 这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。 与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为： 1． 将所有的结束位置标为P位置。 2． 将所有能一步到达P位置的点标为N位置。 3． 找出所有只能到达N位置的点，将它们标为P位置。 4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。 关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为 g(x)min{n0,ng(y)对于所有yF(x)} 1． 对于所有的结束位置x，g(x)= 0。 2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。 3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四类：极大极小法。 典型题目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩阵妙用 矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目： 数学模型举例 向量思想的应用： UVA 10089：注意降维和向量的规范化 ； 利用复数思想进行向量旋转。 UVA 10253： 递推 数代集合 数代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。 组合数学 Polya定理则是解决同构染色计数问题的有力工具。 补集转化思想 ZOJ 单色三角形： 字符串相关 扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀； 填充问题 高精度运算 三维空间问题专题 无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。 其它问题的心得 解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广 源程序代码： } 一、自然数拆分（递归） } #include 二、快速排序（递归）int a[100];void spilt(int t)#include spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i; int value=a[from];printf(“please enter the number:”); while(from a[from]=a[to]; while(from ++from; a[to]=a[from]; } a[from]=value; return from; } void qsort(int a[],int from,int to){ int pivottag;if(from {pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to); } scanf(“%d”,&n); for(i=1;i<=n/2;i++){ a[1]=i;a[2]=n-i;spilt(2); 三、删数字（贪心） #include int a[11]={3,0,0,0,9,8,1,4,7,5,1}; int k=0,i=0,j; int m; while(i<11) { printf(“%d ”,a[i]); i++;} printf(“n please input delete number:”); 四、全排列（递归）#include int i;char temp;if(k==n) for(i=0;i<=3;i++) {printf(“%c ”,a[i]);} else { for(i=k;i<=n;i++) { temp=a[i]; a[i]=a[k]; a[k]=temp; A(a,k+1,n); } } } main(){ int n; char a[4]={'a','b','c','d'},temp; A(a,0,3); getch(); return 0;} 五、多段图（动态规划）#include “stdio.h” #define n 12 //图的顶点数 { while(from scanf(“%d”,&m);for(k=0;k { for(i=0;i<=11-k;i++) { if(a[i]>a[i+1]) { for(j=i;j<10;j++) {a[j]=a[j+1];} break;//满足条件就跳转 } } } int quicksort(int a[],int n){ qsort(a,0,n);} } printf(“the change numbers:”); for(i=0;i<11-m;i++) { if(a[i]!=0) { printf(“%d ”,a[i]);} } } #define k 4 //图的段数 #define MAX 23767 int cost[n][n];//成本值数组 int path[k];//存储最短路径的数组 void creatgraph()//创建图的(成本)邻接矩阵 { int i,j; for(i=0;i for(j=0;j scanf(“%d”,&cost[i][j]);//获取成本矩阵数据 } void printgraph()//输出图的成本矩阵 { int i,j; printf(“成本矩阵:n”); for(i=0;i { for(j=0;j printf(“%d ”,cost[i][j]); printf(“n”); } } //使用向前递推算法求多段图的最短路径 void FrontPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j<=n-1;j++) if(cost[i][j]>0 &&(cost[i][j])+v[j] {length=cost[i][j]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0;//起点 path[k-1]=n-1;//最后的目标 for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//将最短路径存入数组中 } //使用向后递推算法求多段图的最短路径 void BackPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i for(i=1;i<=n-1;i++) { for(length=MAX,j=i-1;j>=0;j--) if(cost[j][i]>0 &&(cost[j][i])+v[j] {length=cost[j][i]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0; path[k-1]=n-1; for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];} //输出最短路径序列 void printpath(){ int i; for(i=0;i printf(“%d ”,path[i]);} main(){ freopen(“E:1input.txt”,“r”,stdin); creatgraph(); printgraph(); FrontPath(); printf(“输出使用向前递推算法所得的最短路径:n”); printpath(); printf(“n输出使用向后递推算法所得的最短路径:n”); BackPath(); printpath();printf(“n”);} 六、背包问题（递归）int knap(int m, int n){ int x; x=m-mn; if x>0 sign=1; else if x==0 sign=0; else sign=-1; switch(sign){ case 0: knap=1;break; case 1: if(n>1) if knap(m-mn,n-1) knap=1; else knap= knap(m,n-1); else knap=0; case-1: if(n>1) knap= knap(m,n-1); else knap=0; } } 七、8皇后（回溯）#include int i; i=1; while(i if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k))) return 0; i++; } return 1;} void Nqueens(int X[N+1]){ int k, i; X[1]=0;k=1; while(k>0){ X[k]=X[k]+1; while((X[k]<=N)&&(!place(k,X))) X[k]=X[k]+1; if(X[k]<=N) if(k==N){ for(i=1;i<=N;i++) printf(“%3d”,X[i]);printf(“n”); } else{ k=k+1; X[k]=0; } else k=k-1; } } void main(){ int n, i; int X[N+1]={0}; clrscr(); Nqueens(X); printf(“The end!”);} 八、图着色（回溯）#include int j,t; while(1){ nextValue(k); if(X[k]==0) return 0; if(k==(N-1)){ for(t=0;t printf(“%3d”,X[t]); printf(“n”); count++; } else mcoloring(k+1); } } int nextValue(int k){ int j; while(1){ X[k]=(X[k]+1)%(M+1); if(X[k]==0) return 0; for(j=0;j if((GRAPH[k][j]==1)&&(X[k]==X[j])) break; } if(j==N){ return 0; } } } void main(){ int k; clrscr(); k=0; mcoloring(k); printf(“ncount=%dn”,count);} 矩阵链乘法（动态规划） 符号S[i, j]的意义： 符号S(i, j)表示，使得下列公式右边取最小值的那个k值 public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s) { int n=p.length-1; for(int i = 1;i <= n;i++)m[i][i] = 0; for(int r = 2;r <= n;r++) for(int i = 1;i <= n-r+1;i++){ int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for(int k = i+1;k < j;k++){ int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(t < m[i][j]){ m[i][j] = t; s[i][j] = k;} } } } O的定义： 如果存在两个正常数c和n0，对于所有的n≥n0时，有： |f(n)|≤c|g(n)|，称函数f(n)当n充分大时的阶比g(n)低，记为 f(n)=O(g(n))。计算时间f(n)的一个上界函数 Ω的定义： 如果存在正常数c和n0，对于所有n≥n0时，有： |f(n)|≥c|g(n)|，则称函数f(n)当n充分大时下有界，且g(n)是它的一个下界，即f(n)的阶不低于g(n)的阶。记为： f(n)=Ω(g(n))。Θ的定义： 如果存在正常数c1，c2和n0，对于所有的n>n0，有： c1|g(n)|≤f(n)≤c2|g(n)|，则记f(n)=Θ(g(n))意味着该算法在最好和最坏的情况下计算时间就一个常因子范围内而言是相同的。(1)多项式时间算法： O(1) (2)指数时间算法： O(2n) Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 贪心方法基本思想： 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 多段图： COST[j]=c(j,r)+COST[r]; 回溯法： (假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi)，看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。约束条件： (1)显式约束：限定每一个xi只能从给定的集合Si上取值。 (2)解 空 间：对于问题的一个实例，解向量满足显式 约束条件的所有多元组，构成了该实例 的一个解空间。 (3)隐式约束：规定解空间中实际上满足规范函数的元 组，描述了xi必须彼此相关的情况。基本做法： 在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 8皇后问题 约束条件 限界函数： 子集和数问题： 约束条件 限界函数： 回溯法－－术语： 活结点：已生成一个结点而它的所有儿子结点还没有 全部生成的结点称为活结点。 E-结点：当前正在生成其儿子结点的活结点叫E-结点。 死结点：不再进一步扩展或其儿子结点已全部生成的结点称为死结点。 使用限界函数的深度优先节点生成的方法成为回溯法；E-结点一直保持到死为止的状态生成的方法 称之为分支限界方法 且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。区别： 分支限界法本质上就是含有剪枝的回溯法，根据递归的条件不同，是有不同的时间复杂度的。 回溯法深度优先搜索堆栈或节点的所有子节点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件下的一个解或特定意义下的最优解 一般如果只考虑时间复杂度二者都是指数级别的 可是因为分支限界法存在着各种剪枝，用起来时间还是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){ int j; X[k]=1; if(s+W[k]==M){ for(j=1;j<=k;j++) printf(“%d ”,X[j]); printf(“n”); } else if((s+W[k]+W[k+1])<=M){ sumofsub(s+W[k],k+1,r-W[k]); } if((s+r-W[k]>=M)&&(s+W[k+1]<=M)){ X[k]=0; sumofsub(s,k+1,r-W[k]); } } void main(){ M=30; W[1]=15; W[2]=9; W[3]=8; W[4]=7; W[5]=6; W[6]=5; W[7]=4; W[8]=3; W[9]=2; W[10]=1; sumofsub(0,1,60);} P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 如果可满足星月化为一个问题L，则此问题L是NP-难度的。如果L是NP难度的且L NP，则此问题是NP-完全的 数学与统计学学院 中期报告 学院: 专业: 年级: 题目: 行列式的算法归纳 学生姓名: 学号: 指导教师姓名 职称: 2012年6月20日 目录 引言..................................................................................................................................................2 1 行列式性质...................................................................................................................................2 2 行列式计算方法...........................................................................................................................5 2.1定义法.................................................................................................................................5 2.2递推法.................................................................................................................................6 2.3化三角法.............................................................................................................................9 2.4拆元法...............................................................................................................................11.4加边法..............................................................................................................................12 2.6数学归结法.......................................................................................................................14 2.7降价法...............................................................................................................................15 2.8利用普拉斯定理...............................................................................................................16 2.9利用范德蒙行列式...........................................................................................................17 结论................................................................................................................................................18 参考文献.........................................................................................................................................18 行列式的概念及应用 摘要：本文先列举行列式计算相关性质，然后归纳总结出了行列式的计算方法，包括：定义法，化三角法，递推法，拆元法，加边法，数学归结法，降价法，利用拉普拉斯定理和利用范德蒙行列式的方法。 关键词：行列式；线性方程组；范德蒙行列式 The concept and application of determinant In this article, it first lists some calculated properties of determinants, and then characterizes some methods to calculate determinant, including: definition, triangulation, recursive method, remove method, bordered，Mathematical induction，reduction，the method using Laplace theorem or the van demon determinant.Keywords: determinant;system of linear equations;Van demon determinant 引言 行列式的概念最初是伴随着方程组的求解而发展起来的。行列式的提出可以追溯到十七世纪，最初的雏形由日本数学家关孝和与德国数学家戈特弗里德·莱布尼茨各自独立得出，时间大致相同。日本数学家关孝和提出来的，他在1683年写了一部名为解伏题之法的著作，意思是“解行列式问题的方法”，书中对行列式的概念和它的展开已经有了清楚的叙述。欧洲第一个提出行列式概念的是德国数学家，微积分学奠基人之一莱布尼茨。十八世纪开始，行列式开始作为独立的数学概念被研究。十九世纪以后，行列式理论进一步得到发展和完善。矩阵概念的引入使得更多有关行列式的性质被发现，行列式在许多领域都逐渐显现出重要的意义和作用，出现了线性自同态和向量组的行列式的定义。行列式的性质 性质1 行列互换，行列式值不变，即 a11a12a1na21a22a2nan1an2anna11[1] a21a22a2nan1an2 anna12a1n其实，元素aij在上式的右端位于第j行第i列，即此时i是列指标，j为行指标。 在行列式中，行与列的地位是对称的，所以有关行的性质，对列也成立。 性质2 如果行列式中一行为零，那么行列式为零。 的元都是二项式，那么这个行列式等于把这些性质3 如果行列式的某一行或一列二项式各取一项作成相应行或列而其余行或列不变的两个行列式的和。 即 a11b1jc1ja21b2jc2jan1bnjcnja1na11b1ja2na21b2jannan1bnja1na11c1ja2na21c2jannan1cnja1na2n ann这就是说，如果某一行是两组数的和，那么这个行列式就等于两个行列式的和，而这两个行列式除这一行以外全与原来行列式的对应的行一样。 性质4 如果行列式中有两行相同，那么行列式为零，所谓两行相同就是说两行的对应元素都相等。 性质5 如果行列式中两行成比例，那么行列式为零。性质6 把一行的倍数加到另一行，行列式不变。性质7 对换行列式中两行的位置，行列式反号。 2.行列式的计算方法 2.1 定义法 n阶行列式计算的定义[3]： a11Dna21an1其中，j1j2jna12a1na22a2nan2ann(1)(j1j2jn)a1j1a2j2anjn j1j2jn表示对所有n级排列求和。j1j2jn是1,2,,n的一个排列，当j1j2jn是(j1j2jn)偶排列时，(1)是正号；当j1j2jn是奇排列时，(1)(j1j2jn)是负的。a1j1a2j2anjn是D中取自不同行不同列的n个元素的乘积。 a11a21例2.1：证明Da31a12a22a32a42a52a13a23000a14a24000a15a2500.00a41a51分析 观察行列式我们会发现有许多零,故直接用定义法.证明： 由行列式的定义知除去符号差别外行列式一般项可表示为a1j1a2j2anjn 则 Dnj1j2j5(1)(j1j2j5)a1j1a2j2anjn.（3） 其中j1,j1,,j5为1,2,3,4,5的任意排列,在D中位于后三行后三列的元素为零,而在前两行前两列中,取不同行不同列的元素只有四个,就是说（3）式中每一项至少有一个来自后三行后三列.故D=0.注意 此方法适用于阶数较低的行列式或行列式中零的个数较多.2.3 递推法 应用行列式的性质，把一个较高阶行列式表示为具有相同结构的较低阶行列式（比如，n-1阶或n-1阶与n-2阶等）的线性关系式，这种关系式称为递推关系式。根据递推关系式及某个低阶初始行列式（比如二阶或一阶行列式）的值，便可递推求得所给n阶行列式的值，这种计算行列式的方法称为递推法。 注意：用此方法一定要看行列式是否具有较低阶的相同结构如果没有的话，即很难 找出递推关系式，从而不能使用此方.[4] 例2.2证如下行列式等式 Dn1001000000 0001n1n1,其中（虽然这是一道证明题，但我们可以直接求 证明： Dn出其值，从而证之）。 分析：此行列式的特点是：除主对角线及其上下两条对角线的元素外，其余的元素 都为零，这种行列式称“三对角”行列式。从行列式的左上方往右下方看，即知Dn1与Dn具有相同的结构。因此可考虑利用递推关系式计算。 证明：Dn按第1列展开，再将展开后的第二项中n-1阶行列式按第一行展开有： Dn（＋）Dn－1－Dn－2，这是由Dn1 和Dn2表示Dn的递推关系式。若由上面的递推关系式从n阶逐阶往低 阶递推，计算较繁，注意到上面的递推关系式是由n-1阶和n-2阶行列式表示n阶行列式，因此，可考虑将其变形为： Dn－Dn－1＝Dn－1－Dn－2＝（Dn－1－Dn－2）或 Dn－Dn－1＝Dn－1－Dn－2＝（。Dn－1－Dn－2）现可反复用低阶代替高阶，有： 23Dn－Dn－1＝（Dn－1－Dn－2）＝（Dn－2－Dn－3）＝（Dn－3－Dn－4）＝＝（D2－D1）=同样有 n2n－2[()()](1)2n 23Dn－Dn－1＝（Dn－1－Dn－2）＝（Dn－2－Dn－3）＝（Dn－3－Dn－4）[()()](2)n1n1因此当 时，由（1）（2）式可解得：Dn。 ＝＝（D2－D1）=n2n－22n 小结：虽然我们从一个行列式中可以看出有低阶的相同的结构，然后得到一递推关系式，但我们不要盲目乱代，一定要看清这个递推关系式是否可以简化我们的计算，如果不行的话，就要适当地换递 推关系式，如本题。 2.3化三角形法 运用行列式的性质是计算行列式的一个重要途径,大多数行列式的计算都依赖于行列式的性 [7]质,将行列式化成上三角(下三角或反三角)的形式,再根据行列式的定义来计算行列式.行列式的性质告诉了我们该如何求行列式,而一切的行列式都可以根据以上性质来进行初等行变换(列变换),变成阶梯形(上三角)的行列式,再根据定义计算即可.其计算步骤可归纳如下: (ⅰ)看行列式的行和(列和),如果行列和相等,则均加到某一列(行)（直观上加到第一列(行)）.(ⅱ)有公因子的提出公因子.(ⅲ)进行初等行变换(列变换)化成上三角(下三角或反三角)的行列式.(ⅳ)由行列式的定义进行计算.由以上四步,计算一般行列式都简洁多了.123n1234[6]例2.3 计算行列式Dn345n1n12.n12n2n1分析 直接用化三角形法化简很烦,观察发现对于任意相邻两列中的元素,位于同一行的元素中,后面元素与前面元素相差1,因此先从第n1列乘-1加到第n列,第n2列乘-1加到第n1列, 这样做下去直到第1列乘-1加到第2列,然后再计算就显得容易.123n1234解：Dn345n1n12123111111111n11n1 10001000n12n2n1 n1n112n12n111210011100n10n0nn1n0000000n0 000n0n0 00n0000n1n(n1)000n2n00(n1)(n2)1n(n1)(1)2 n2n(n1)(n1)n1n(1)2.2问题推广 在例2.3中1,2,,n,这n个数我们可以看成有限个等差数列在循环,那么对于一般的等差数列也应该适应.计算行列式 [1] a1Da1da12da1(n1)da1a1da12da1(n1)da1d2d(n1)da1a1da12da13da1ddda12da1(n1)da13da14da1ddda1nda1a1(n3)dda1nda1a1da1(n2)d ddd(1n)ddddnd d(1n)dd d(1n)dddndnd0000000nd0 d(n1)dnnd2d(n1)dndnd00(n1)(n2)d(n1)dn1(a1)(nd)(1)2 nn(n1)(n2)1n(a1a1(n1)d)n1()(nd)(1)2.n2 (n1)(n2)1n(a1a1(n1)dn1)(nd)(1)2结论如果将例2.3中的数a11，d1代入(n2显然成立.2.4．拆元法 由行列式拆项性质知，将已知行列式拆成若干个行列式之积，计算其值，再得原行 列式值，此法称为拆行（列）法。 由行列式的性质知道，若行列式的某行（列）的元素都是两个数之和，则该行列式可拆成两个行列式的和，这两个行列式的某行（列）分别以这两数之一为该行（列）的元素，而其他各行（列）的元素与原行列式的对应行（列）相同，利用行列式的这一性质，有时较容易求得行列式[2]的值。 例2.4求下列行列式的值 设n阶行列式： a11a21an1a12a1na22a2n1 an2ann且满足aijaji,i,j1,2,,n,对任意数b，求n阶行列式 a11ba12ba1nba21ba22ba2nb? an1ban2bannb 分析:该行列式的每个元素都是由两个数的和组成，且其中有一个数是b，显然 用拆行（列）法。 解： a11ba12ba1nba11a12ba1nbba12bDa21ba22ba2nba21a22ba2nbba22bnan1ban2bannban1an2bannbban2ba11a12a1nba11ba1nb1a12a1na21a22a2nb1a22a2na21ba2nbb an1an2annban1bannb1an2anna11a12a1na111a1n1a12a1na21a22a2nba211a2n1a22a2nb an1an2annan11ann1an2annnnn1bA2ibA1i1bi1iAij。 i1,j1又令 a11a12a1nA=a21a22a2n,且aijaji,i,j1,2,,n。 an1an2ann 所以 有A1,且A'A。 由A－1＝A＊A得：AA－1A＊即A＊A＝E 所以 A＊＝A－1。7 a1nba2nbannb 又（A＊）(A1)'(A')1(A)1A＊，所以 A*也为反对称矩阵。 *又 Aij(i,j1,2,,n)为A的元素，所以有i1,j1'nAij0。 从而知：Dn1bi1,j1nAij1。 2.5．加边法 计算行列式往往采用降阶的办法，但在一些特殊的行列式的计算上却要采用加边法。行列式的加边法是为了将行列式降阶作准备的。更有利于将行列式化成上三角的形式，其加边的元素，也可根据计算的难易程度来确定。具有随意性。利用行列式按行（列）展开的性质把n阶行列式通过 [3]加行（列）变成与之相等的n1阶行列式,然后计算.添加行列式的四种方法[18]:设Dna11a21an1a12a1na22a2nan2ann.（1）首行首列Dna11a21an1a11a21an1a11a21an1a11a21an1a12a1na22a2nan2anna12a1na22a2nan2anna12a1na22a2nan2anna12a1na22a2nan2ann1a1a2an0a110a210a11a21an1a1a2a31a11a21a3100a12a22an2a11a21a310a12a22a320a12a1na22a2n.an2ann01a13a1a23a2.an3ana12a1na22a2na32a3n.00a13a1a23a2a33a3.010an1（2）首行末列Dn（3）末行首列Dn（4）末行末列Dn例2.5 计算n 阶行列式： [4] x121Dnx1x2x1x2x1x2x221x1x2x1x2x1x2xn21 分析 我们先把主对角线的数都减1，这样我们就可明显地看出第一行为x1与x1,x2,,xn相乘，第二行为x2与x1,x2,,xn相乘，„„，第n行为xn与x1,x2,,xn相乘。这样就知道了该行列式每行有相同的因子x1,x2,,xn，从而就可考虑此法。解： 1x1x20x121x1x22Dn0x2x1x210xnx1nxn1x1x2x1(i1,,n)x2xnx2ri1xir1x1100x2xn001001xnx22i12xn1x1100xnn1 1xic1xici1(i1,,n)x2xn0100011xi2。i1n000n1注意:加边法最在的特点就是要找出每行或每列相同的因子，那么升阶之后，就可利用行列式的性质把绝大部分元素化为零，然后再化为三角形行列式，这样就达到了简化计算的效果。 2.6数学归结法 数学归纳法有两种一种是不完全归纳法,另一种是完全归纳法,通常用不完全归纳法寻找行列式 [5]的猜想,再用数学归纳法证明猜想的正确性.基本方法 1)先计算n1,2,3时行列式的值.2)观察D1,D2,D3的值猜想出Dn的值.3)用数学归纳法证明.例2.6 证明： [6]2cos1 Dn12cos100010000000012cossin(n1)sin(sin0)0002cos2cos1证：当n1,2时，有 sin(11)sin 2cos1sin(21)D24cos2112cossinD12cos结论显然成立。 现假定结论对小于等于n1时成立。即有 Dn2将Dn按第1列展开，得 sin(n21),sinDn1 sin(n11)。 sin2cos1Dn0012cos00000012cos2cos10002cos00000012cos2cos1(n1)2cos1(n1)2cosDn1Dn2sin(n11)sin(n21)sinsin2cossinnsin(n1)sin2cossinnsinncoscosnsinsinsinncoscosnsinsinsin(n1)sin2cos 故当对n时，等式也成立。得证。 2.7降阶法 n阶行列式等于它的任意一行(列)各元素与其对应的代数余子式乘积的和.即 DaijAij(i1,2,,n)或DaijAij(j1,2,,n).j1i1nn行列式按一行（列）展开将高阶转化为若干低阶行列式计算方法称为降阶法.这是一种计算[9]行列式的常用方法.1301例2.7 计算D30141121011001.1解 D30911022001109111220110214.21注意 对于一般的n阶行列式若直接用降阶法计算量会大大加重.因此必须先利用行列式的性质将行列式的某一行（列）化为只含有一个非零元素,然后再按此行（列）展开,如此进行下去,直到二阶.2.8 利用拉普拉斯定理 在利用行列式的一行(列)展开式时,我们可以发现计算行列式可以按某一行(列)展开,进行计算行列式.试想,我们可以根据行列式的某一个K级字式展开吗? 拉普拉斯经过对行列式的研究.终于发现此种方法可行,并给出了严密的证明,为了使行列式的计算更为简洁,现引入拉普拉斯定理.拉普拉斯定理[12]:设在行列式D中任意取定了k1kn1个行,由这k行元素所组成的一切K级字式与它们的代数余子式的乘积的和等于行列式D.拉普拉斯定理的四种特殊情形： 1）AnnCmn00BmmAnnCmnAnnBmm Ann2） 0CnmAnnBmm Bmm3）Bmm(1)mnAnnBmm 4） CnmBmmAnn0(1)mnAnnBmm 例2.8计算n阶行列式 aaaabDnbb 解 Dn(i2，n1)aaaabi1200(n1)a000000aa0a 0C2Ci0b(n2)(i3,n)00000000利用拉普拉斯定理(n1)ab(n2)2200n20000(n2)(n2)[(n2)ab(n1)]()2.9 利用范德蒙行列式 范德蒙行列式[14] ： 1x1x12x1n11x2x22n1x21x3x32n1x31xn2xn1jinn1xn(xixj) (an1)n1(an1)n2例2.9[16] (an2)n1(a1)n1(an2)n2(a1)n2an21a11an1an2 a1：计算n阶行列式 Dnan11解 ： 显然该题与范德蒙行列式很相似，但还是有所不同，所以先利用行列式的性质把它化为范德蒙行列式的类型。 先将的第n行依次与第n-1行，n-2行，„,2行，1行对换，再将得到到的新的行列式的第n行与第n-1行，n-2行，„,2行对换，继续仿此作法，直到最后将第n行与第n-1行对换，这样，共经过（n-1）+（n-2）+„+2+1=n（n-1）/2次行对换后，得到 1Dn(1)n(n1)21an21a11a an2an1an1(an1)n2(an1)n1(an2)n2(a1)n2(an2)n1(a1)n1上式右端的行列式已是范德蒙行列式，故利用范德蒙行列式的结果得 EnABnmEmBA Dn(1)n(n1)21jin[(ani)(anj)](1)n(n1)21jin(ij) 结论： 综上所述，针对行列式结构特点而采用与之相适应的计算技巧，从而总结出了多种类型题目所适用的计算方法，因此，对于计算行列式的方法，我们首先要熟练掌握并懂得如何选择、运用，不管是哪一种行列式的计算，选取恰当的方法，才能较快地解出其值。 参考文献 ［1］李师正等.高等代数复习解题方法与技巧.高等教育出版社, 2005 ［2］张贤科 许甫华.高等代数学.清华大学出版社, 2000 ［3］刘学鹏等.高等代数复习与研究.南海出版公司, 1995 ［4］许甫华 张贤科.高等代数解题方法.清华大学出版社, 2001 ［5］李永乐.研究生入学考试线性代数.北京大学出版社, 2000 ［6］王萼芳 石生明.高等代数学.高等教育出版社, 2003 ［7］吕林根.许子道.解析几何.高等教育出版社 2006 ［8］贾冠军.菏泽师专学报, Journal of Heze Teachers College, 1999年 02期 ［9］吴晓庆，关丰宇.行列式的相关性质与应用.数学学习与研究 2011年第3期 [10] 张子杰.行列式计算中的一些方法.河北工程技术高等专科学院学报.[11] 北京大学数学系几何与代数教研室代数小组，高等代数（第二版）.北京：高等教育出版社，1994 [12] 王品超著，高等代数新方法.济南：山东教育出版社，1989 [13] 李师正,高等代数复习解题方法与技巧.高等教育出版社,2005 [14] 刘洪星,高等代数选讲.机械工业出版社,2009 [15] 姚慕生,高等代数.上海：复旦大学出版社，2002 [16] 许甫华，张贤科.高等代数解题方法.北京：清华大学出版社，2001 [17] 期刊论文 ,一个n阶行列式的若干种计算方法.科技信息，2009，（3）：18-23 [18] 张禾瑞 郝鈵新 《高等代数》 高等教育出版社 1999 [19] 徐仲 陆全 张凯院 吕全义 安晓虹 《高等代数》 西北工业大学出版社 2006第四篇：算法总结材料
第五篇：行列式算法归纳总结
点击咨询 