第一篇：多種最小二乘算法分析+算法特點(diǎn)總結(jié)
第一部分：程序設(shè)計(jì)思路、辨識(shí)結(jié)果分析和算法特點(diǎn)總結(jié)................................................2 一：RLS遺忘因子法.................................................................................................2 RLS遺忘因子法仿真思路和辨識(shí)結(jié)果.................................................................2 遺忘因子法的特點(diǎn)：..........................................................................................3 二：RFF遺忘因子遞推算法.......................................................................................4 仿真思路和辨識(shí)結(jié)果..........................................................................................4 遺忘因子遞推算法的特點(diǎn)：................................................................................5 三：RFM限定記憶法..................................................................................................5 仿真思路和辨識(shí)結(jié)果..........................................................................................5 RFM限定記憶法的特點(diǎn)：....................................................................................7 四：RCLS偏差補(bǔ)償最小二乘法..................................................................................7 仿真思路和辨識(shí)結(jié)果..........................................................................................7 RCLS偏差補(bǔ)償最小二乘遞推算法的特點(diǎn)：..........................................................9 五：增廣最小二乘法.................................................................................................9 仿真思路和辨識(shí)結(jié)果..........................................................................................9 RELS增廣最小二乘遞推算法的特點(diǎn)：................................................................11 六：RGLS廣義最小二乘法.......................................................................................12 仿真思路和辨識(shí)結(jié)果........................................................................................12 RGLS廣義最小二乘法的特點(diǎn)：.........................................................................14 七：RIV輔助變量法................................................................................................14 仿真思路和辨識(shí)結(jié)果........................................................................................14 RIV輔助變量法的特點(diǎn)：..................................................................................16 八：Cor-ls相關(guān)最小二乘法（二步法）..................................................................17 仿真思路和辨識(shí)結(jié)果........................................................................................17 Cor-ls相關(guān)最小二乘法（二步法）特點(diǎn)：........................................................18 九：MLS多級(jí)最小二乘法.........................................................................................19 仿真思路和辨識(shí)結(jié)果........................................................................................19 MLS多級(jí)最小二乘法的特點(diǎn)：...........................................................................22 十：yule_walker辨識(shí)算法.....................................................................................23 仿真思路和辨識(shí)結(jié)果........................................................................................23 yule_walker辨識(shí)算法的特點(diǎn)：.......................................................................24 第二部分：matlab程序..................................................................................................24 一：RLS遺忘因子算法程序.....................................................................................24 二：RFF遺忘因子遞推算法.....................................................................................26 三：RFM限定記憶法................................................................................................28 四：RCLS偏差補(bǔ)償最小二乘遞推算法......................................................................31 五：RELS增廣最小二乘的遞推算法.........................................................................33 六;RGLS 廣義最小二乘的遞推算法..........................................................................36 七：Tally輔助變量最小二乘的遞推算法................................................................39 八：Cor-ls相關(guān)最小二乘法（二步法）..................................................................42 九：MLS多級(jí)最小二乘法.........................................................................................45 十yule_walker辨識(shí)算法........................................................................................49
第一部分：程序設(shè)計(jì)思路、辨識(shí)結(jié)果分析和算法特點(diǎn)總結(jié)
一：RLS遺忘因子法
RLS遺忘因子法仿真思路和辨識(shí)結(jié)果
仿真對象如下：
其中，v(k)為服從N(0,1)分布的白噪聲。輸入信號(hào)u(k)采用M 序列，幅度為 1。M 序列由 9 級(jí)移位寄存器產(chǎn)生，x(i)=x(i-4)⊕x(i-9)。選擇如下辨識(shí)模型：
加權(quán)陣取Λ = I。
衰減因子β = 0.98，數(shù)據(jù)長度 L = 402。辨識(shí)結(jié)果與理論值比較，基本相同。辨識(shí)結(jié)果可信： Estimate =-1.4666 0.6503 0.9736 0.3035 遺忘因子法的特點(diǎn)：
對老數(shù)據(jù)加上遺忘因子，以降低老數(shù)據(jù)對辨識(shí)的影響，相對增加新數(shù)據(jù)對辨識(shí)的影響，不會(huì)出現(xiàn)“數(shù)據(jù)飽和”現(xiàn)象。如模型噪聲是有色噪聲，則?是有偏估計(jì)量。常用作其他辨識(shí)方式的起步，以獲得其他方式的初始值。
二：RFF遺忘因子遞推算法 仿真思路和辨識(shí)結(jié)果
辨識(shí)模型與遺忘因子法所用模型相同。
其中，0 ≤μ≤1為遺忘因子，此處取0.98。始條件：
參數(shù)a1 a2 b1 b2的估計(jì)值: ans =-1.4977 0.6863 1.1903 0.4769 待估參數(shù)變化過程如圖所示：
數(shù)據(jù)長度L=402，初
遺忘因子遞推算法的特點(diǎn)：
從上面兩個(gè)例子可以看出對于相同的仿真對象，一次算法和遞推算法結(jié)果基本一致，但遞推算法可以實(shí)現(xiàn)在線實(shí)時(shí)辨識(shí)，而且可以減少計(jì)算量和存儲(chǔ)量。
三：RFM限定記憶法 仿真思路和辨識(shí)結(jié)果
辨識(shí)模型與遺忘因子法所用模型相同。
辨識(shí)結(jié)果與理論值比較，基本相同。辨識(shí)結(jié)果可信： 參數(shù) a1 a2 b1 b2 的估計(jì)值為： Theta_a =-1.5128 0.7099 0.8393 0.4416 待估參數(shù)的過渡過程如下：
RFM限定記憶法的特點(diǎn)：
辨識(shí)所使用的數(shù)據(jù)長度保持不變，每增加一個(gè)新數(shù)據(jù)就拋掉一個(gè)老數(shù)據(jù)，使參數(shù)估計(jì)值始終只依賴于有限個(gè)新數(shù)據(jù)所提供的新消息，克服了遺忘因子法不管多老的數(shù)據(jù)都在起作用的缺點(diǎn)，因此該算法更能有效的克服數(shù)據(jù)飽和現(xiàn)象。
四：RCLS偏差補(bǔ)償最小二乘法 仿真思路和辨識(shí)結(jié)果
辨識(shí)模型與遺忘因子法所用模型相同。
辨識(shí)結(jié)果與理論值比較，基本相同。辨識(shí)結(jié)果可信： 參數(shù)a1 a2 b1 b2的估計(jì)值為： ans =-1.4916
0.7005 1.0365 0.4271
RCLS偏差補(bǔ)償最小二乘遞推算法的特點(diǎn)：
算法思想：：在最小二乘參數(shù)估計(jì)值的基礎(chǔ)上，引進(jìn)補(bǔ)償項(xiàng)σW2C-1D ?0，則獲得了參數(shù)的無偏估計(jì)。針對模型噪聲來說，RCLS算法的適應(yīng)能力比RLS更好。
五：增廣最小二乘法 仿真思路和辨識(shí)結(jié)果
考慮如下仿真對象：
其中，為服從N(0,1)分布的白噪聲。輸入信號(hào)采用 M 序列，幅度為 1。M 序列由 9 級(jí)移位寄存器產(chǎn)生，x(i)=x(i-4)⊕x(i-9)。
選擇如下的辨識(shí)模型：
觀測數(shù)據(jù)長度取L =402。加權(quán)陣取Λ=I。
辨識(shí)結(jié)果與理論值比較，基本相同，同時(shí)又能獲得噪聲模型的參數(shù)估計(jì)。辨識(shí)結(jié)果可信：
參數(shù)a1、a2、b1、b2、d1、d2估計(jì)結(jié)果：
ans =-1.5000 0.7000 1.0001 0.5002-0.9999 0.2000
RELS增廣最小二乘遞推算法的特點(diǎn)：
增廣最小二乘的遞推算法對應(yīng)的噪聲模型為滑動(dòng)平均噪聲，擴(kuò)充了參數(shù)向量和數(shù)據(jù)向量H（k）的維數(shù)，把噪聲模型的辨識(shí)同時(shí)考慮進(jìn)去。最小二乘法只能獲得過程模型的參數(shù)估計(jì)，而增廣最小二乘法
同時(shí)又能獲得噪聲模型的參數(shù)估計(jì)，若噪聲模型為平均滑動(dòng)模型，則只能用RELS算法才能獲得無偏估計(jì)。當(dāng)數(shù)據(jù)長度較大時(shí)，辨識(shí)精度低于極大似然法。
六：RGLS廣義最小二乘法 仿真思路和辨識(shí)結(jié)果
模型結(jié)構(gòu)選擇：
模型結(jié)構(gòu)選用：
其中，各個(gè)參數(shù)的真值為：
廣義最小二乘算法為：
辨識(shí)結(jié)果與理論值比較，基本相同，同時(shí)又能獲得噪聲傳遞系數(shù)的參數(shù)估計(jì)。辨識(shí)結(jié)果可信： 參數(shù)a1 a2 b1 b2的估計(jì)結(jié)果： ans =-1.5058 0.6972 0.9316 0.4833
噪聲傳遞系數(shù)c1 c2的估計(jì)結(jié)果： ans = 0.6203 0.2210
RGLS廣義最小二乘法的特點(diǎn)：
該算法用于自回歸輸入模型，是一種迭代的算法。其基本思想是基于對數(shù)據(jù)先進(jìn)行一次濾波處理，后利用普通最小二乘法對濾波后的數(shù)據(jù)進(jìn)行辨識(shí)，進(jìn)而獲得無偏一致估計(jì)。但是當(dāng)過程的輸出信噪比比較大或模型參數(shù)較多時(shí)，這種數(shù)據(jù)白色化處理的可靠性就會(huì)下降，辨識(shí)結(jié)果往往會(huì)是有偏估計(jì)。數(shù)據(jù)要充分多，否則辨識(shí)精度下降。模型階次不宜過高。初始值對辨識(shí)結(jié)果有較大影響。
七：RIV輔助變量法 仿真思路和辨識(shí)結(jié)果
辨識(shí)模型與遺忘因子法所用模型相同,只不過此處噪聲為有色噪聲，產(chǎn)生過程為：e(k)=v(k)+0.5v(k-1)+0.2v(k-2),v(k)為0均值的不相關(guān)隨機(jī)噪聲。
按照Tally法選取輔助變量x(k)=z(k-nd), nd為誤差傳遞函數(shù)的階數(shù)，此處為2.則有
輔助變量法的遞推公式可寫成：
辨識(shí)結(jié)果與理論值比較，基本相同。辨識(shí)結(jié)果可信： 參數(shù)a1 a2 b1 b2的估計(jì)結(jié)果： ans =-1.5314 0.7461 0.9999 0.4597
RIV輔助變量法的特點(diǎn)：
適當(dāng)選擇輔助變量，使之滿足相應(yīng)條件，參數(shù)估計(jì)值就可以是無偏一致。估計(jì)輔助變量法的計(jì)算量與最小二乘法相當(dāng)，但辨識(shí)效果卻比最小二乘法好的多。尤其當(dāng)噪聲是有色的，而噪聲的模型結(jié)構(gòu)又不好確定時(shí)，增廣最小二乘法和廣義最小二乘法一般都不好直接應(yīng)用，因?yàn)樗麄冃枰x用特定的模型結(jié)構(gòu)，而輔助變量法不需要確定噪聲的模型結(jié)構(gòu)，因此輔助變量法就顯得更為靈活，但輔助變量法不能同時(shí)獲得噪聲模型的參數(shù)估計(jì)。
八：Cor-ls相關(guān)最小二乘法（二步法）仿真思路和辨識(shí)結(jié)果
辨識(shí)模型與遺忘因子法所用模型相同：，e(k)=v(k)+0.5v(k-1)+0.2v(k-2),v(k)為0均值的不相關(guān)隨機(jī)噪聲。Cor-ls的遞推公式可寫成:
其中：M（k）為輸入M序列。初始條件：，辨識(shí)結(jié)果與理論值比較，基本相同，辨識(shí)結(jié)果可信： 參數(shù)a1 a2 b1 b2的估計(jì)結(jié)果： ans =-1.4896
0.6858 1.0168 0.4362
Cor-ls相關(guān)最小二乘法（二步法）特點(diǎn)：
把辨識(shí)分成兩步進(jìn)行：第一步：利用相關(guān)分析法獲得對象的非參數(shù)模型（脈沖響應(yīng)或相關(guān)函數(shù)）；第二步：利用最小二乘法、輔助變量法或增廣最小二乘法等，進(jìn)一步求的對象的參數(shù)模型。如果模型噪聲與輸入無關(guān)，則Cor-ls相關(guān)最小二乘法（二步法）可以得到較好的辨識(shí)結(jié)果。Cor-ls相關(guān)最小二乘法（二步法）實(shí)質(zhì)上是先對數(shù)據(jù)進(jìn)行一次相關(guān)分析，濾除了有色噪聲的影響，再利用最小二乘法必然就會(huì)改善辨識(shí)結(jié)果。能適應(yīng)較寬廣的噪聲范圍，計(jì)算量不大，初始值
對辨識(shí)結(jié)果影響較小。但要求輸入信號(hào)與噪聲不相關(guān)。
九：MLS多級(jí)最小二乘法 仿真思路和辨識(shí)結(jié)果
仿真對象如下:
其中，u(k)是輸入變量，此處為 M 序列；v(k)是零均值、方差為 1 的不相關(guān)隨機(jī)噪聲，通過控制λ的大小來控制信噪比。辨識(shí)模型結(jié)構(gòu)選用:
其中，辨識(shí)過程如下：
第一級(jí)，輔助模型參數(shù)辨識(shí) 原模型可寫為:
利用最小二乘法可獲得輔助模型的參數(shù)無偏一致估計(jì)值:
數(shù)據(jù)長度 L=400，第二級(jí)，過程模型參數(shù)辨識(shí):
根據(jù)最小二乘算法可以獲得過程模型的參數(shù)估計(jì)值為:
第三級(jí)，噪聲模型參數(shù)辨識(shí):
根據(jù)最小二乘算法可以獲得過程模型的參數(shù)估計(jì)值為
辨識(shí)結(jié)果與理論值比較，基本相同。辨識(shí)結(jié)果可信：
第一級(jí) 輔助模型參數(shù) e1 e2 e3 e3 e4 f1 f2 f3 f4 辨識(shí)結(jié)果： E = 1.9062 1.4454 0.5279 0.0613-0.0026 0.7988-0.8694-1.3037-0.6318
第二級(jí) 過程模型參數(shù) a1 a2 a3 b1 b2 辨識(shí)結(jié)果： E2 = 0.9304 0.1596 0.0113 0.7998-1.6502 第三級(jí) 噪聲模型參數(shù) c1 c2 辨識(shí)結(jié)果： E3 = 0.9750 0.3824 MLS多級(jí)最小二乘法的特點(diǎn)：
當(dāng)信噪比較大時(shí)，采用廣義最小二乘法可能會(huì)出現(xiàn)多個(gè)局部收斂點(diǎn)，解決這個(gè)問題的方法可用多級(jí)最小二乘法，一般來說多級(jí)最小二乘法包含三級(jí)辨識(shí)過程。利用輸入輸出數(shù)據(jù)，通過多級(jí)最小二乘法，可分別求的輔助模型，過程模型和噪聲模型的參數(shù)估計(jì)值。在高噪聲的情況下，多級(jí)最小二乘法明顯優(yōu)于廣義最小二乘法，其收斂點(diǎn)唯一。
十：yule_walker辨識(shí)算法 仿真思路和辨識(shí)結(jié)果
仿真對象如下：，z(k)是可觀測變量；v(k)是均值為零，方差為 1 的不相關(guān)隨機(jī)噪聲；數(shù)據(jù)長度取 L=1024。相關(guān)函數(shù)按下式計(jì)算 ：
參數(shù)的估計(jì)算法按下式計(jì)算：
辨識(shí)結(jié)果與理論值比較，基本相同，同時(shí)又能獲得噪聲模型的參數(shù)估計(jì)。辨識(shí)結(jié)果可信： 辨識(shí)結(jié)果為： Theta = 0.8597 0.2955
-0.0034 d = 1.0025 yule_walker辨識(shí)算法的特點(diǎn)：
yule_walker辨識(shí)算法可以方便的辨識(shí)形如估計(jì)值。的參數(shù)第二部分：matlab程序
一：RLS遺忘因子算法程序
clear clc %========================================== %最小二乘法辨識(shí)對象
% Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+v(k)%==========產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%初始值 n=403;%n為脈沖數(shù)目 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;%產(chǎn)生高斯白噪聲 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 個(gè)產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n為脈沖數(shù)目 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 %===========產(chǎn)生均值為0，方差為1 的高斯白噪聲=========
v=randn(1,400);%==============產(chǎn)生觀測序列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);%估計(jì)方差
Theta=zeros(4,401);%參數(shù)的估計(jì)值，存放中間過程估值 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 %==========================輸出結(jié)果及作圖
============================= disp('參數(shù)a1 a2 b1 b2的估計(jì)值:')Theta(:,401)i=1:401;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估參數(shù)過渡過程')三：RFM限定記憶法
%限定記憶最小二乘的遞推算法辨識(shí)對象
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+v(k)%======================================== clear clc %==========產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n為脈沖數(shù)目 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 %===========產(chǎn)生均值為0，方差為1 的高斯白噪聲========= v=randn(1,402);%==============產(chǎn)生觀測序列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);%估計(jì)方差 Theta_a=[3;3;3;3];L=20;%記憶長度
for i=3:L-1 %利用最小二乘遞推算法獲得初步參數(shù)估計(jì)值和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)];%增加新數(shù)據(jù)的信息
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);];%去掉老數(shù)據(jù)的信息 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
%========================輸出結(jié)果及作圖=========================== disp('參數(shù) a1 a2 b1 b2 的估計(jì)值為：')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('待估參數(shù)過渡過程')四：RCLS偏差補(bǔ)償最小二乘遞推算法
%偏差補(bǔ)償最小二乘的遞推算法辨識(shí)對象
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+v(k)%======================================== clear clc %==========產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n為脈沖數(shù)目 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
%===========產(chǎn)生均值為0，方差為1 的正態(tài)分布噪聲========= v=random('Normal',0,1,1,400);%==============產(chǎn)生觀測序列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);%估計(jì)方差
Theta=zeros(4,401);%參數(shù)的估計(jì)值，存放中間過程估值 Theta(:,1)=[3;3;3;3];K=[10;10;10;10];%增益 J=0;ThetaC=zeros(4,401);%偏差補(bǔ)償后的估計(jì)值 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);%==============輸出參數(shù)估計(jì)結(jié)果及作圖================ disp('參數(shù)a1 a2 b1 b2的估計(jì)值為：')Theta(:,401)i=1:401;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估參數(shù)過渡過程')
五：RELS增廣最小二乘的遞推算法
%增廣最小二乘的遞推算法辨識(shí)對象
%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
%==========產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n為脈沖數(shù)目 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 %===========產(chǎn)生均值為0，方差為1 的高斯白噪聲========= v=randn(1,402);%==============產(chǎn)生觀測序列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);%估計(jì)方差
Theta=zeros(6,401);%參數(shù)的估計(jì)值，存放中間過程估值 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('參數(shù)a1、a2、b1、b2、d1、d2估計(jì)結(jié)果：')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('待估參數(shù)過渡過程')
六;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 個(gè)產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n為脈沖數(shù)目 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 %===========產(chǎn)生均值為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 %==============產(chǎn)生觀測序列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);%估計(jì)方差
Theta=zeros(4,400);%參數(shù)的估計(jì)值，存放中間過程估值 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;%=====================輸出結(jié)果及作圖
========================= disp('參數(shù)a1 a2 b1 b2的估計(jì)結(jié)果：')Theta(:,400)disp('噪聲傳遞系數(shù)c1 c2的估計(jì)結(jié)果：')ThetaE(:,400)i=1:400;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估參數(shù)過渡過程')七：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)為零均值的不相關(guān)隨機(jī)噪聲
%======================================== clear clc %==========產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n為脈沖數(shù)目
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 %===========產(chǎn)生均值為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 %==============產(chǎn)生觀測序列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);%估計(jì)方差
Theta=zeros(4,400);%參數(shù)的估計(jì)值，存放中間過程估值 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 %==================結(jié)果輸出及作圖=================== disp('參數(shù)a1 a2 b1 b2的估計(jì)結(jié)果：')Theta(:,400)
i=1:400;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估參數(shù)過渡過程')八：Cor-ls相關(guān)最小二乘法（二步法）
%兩步法的遞推算法
%Z(k+2)=1.5*Z(k+1)-0.7*Z(k)+u(k+1)+0.5*u(k)+e(k)，e(k)為零均值的不相關(guān)隨機(jī)噪聲
%e(k)=v(k)+0.5*v(k-1)+0.2*v(k-2)%======================================== clear clc %==========產(chǎn)生M序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=403;%n為脈沖數(shù)目 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 %===========產(chǎn)生均值為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 %==============產(chǎn)生觀測序列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);%估計(jì)方差
Theta=zeros(4,400);%參數(shù)的估計(jì)值，存放中間過程估值 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 %==================結(jié)果輸出及作圖=================== disp('參數(shù)a1 a2 b1 b2的估計(jì)結(jié)果：')Theta(:,400)i=1:400;figure(1)plot(i,Theta(1,:),i,Theta(2,:),i,Theta(3,:),i,Theta(4,:))title('待估參數(shù)過渡過程')
九：MLS多級(jí)最小二乘法
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)%==========產(chǎn)生M 序列作為輸入=============== x=[0 1 0 1 1 0 1 1 1];%initial value n=405;%n為脈沖數(shù)目 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 %===========產(chǎn)生均值為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 %=================產(chǎn)生觀測序列=================== 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 %================第一級(jí)辨識(shí) 輔助模型參數(shù)辨識(shí)================== 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('第一級(jí) 輔助模型參數(shù) e1 e2 e3 e3 e4 f1 f2 f3 f4 辨識(shí)結(jié)果：')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);%=================第二級(jí)辨識(shí) 過程模型參數(shù)辨識(shí)====================
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('第二級(jí) 過程模型參數(shù) a1 a2 a3 b1 b2 辨識(shí)結(jié)果：')E2=inv(H2'*H2)*H2'*z2 a1=E2(1);a2=E2(2);a3=E2(3);b1=E2(4);
b2=E2(5);%================第三級(jí)辨識(shí) 噪聲模型參數(shù)辨識(shí)======================= 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('第三級(jí) 噪聲模型參數(shù) c1 c2 辨識(shí)結(jié)果：')E3=inv(H3'*H3)*H3'*z3 十yule_walker辨識(shí)算法
%Yule-Walker 辨識(shí)算法
%辨識(shí)模型：z(k)=-0.9*z(k-1)-0.36*z(k-2)-0.054*z(k-3)+v(k)%============== %產(chǎn)生隨機(jī)噪聲
v=random('Normal',0,1,1,1024);%均值為零，方差為 1
%產(chǎn)生觀測序列 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 %計(jì)算 z(k)的自相關(guān)函數(shù) 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
第二篇：算法總結(jié)
算法分析與設(shè)計(jì)總結(jié)報(bào)告
71110415 錢玉明
在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學(xué)生，學(xué)習(xí)算法無疑會(huì)增強(qiáng)自己的競爭力，修煉自己的“內(nèi)功”。
下面我將談?wù)勎覍@門課程的心得與體會(huì)。
一、數(shù)學(xué)是算法的基礎(chǔ)
經(jīng)過這門課的學(xué)習(xí)，我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。
①主定理
本門課中它主要應(yīng)用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個(gè)大問題分解為a個(gè)子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級(jí)高于nlogba時(shí)，我們可以設(shè)法降低子問題組合時(shí)的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴(kuò)大問題的規(guī)模或者減小子問題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。
②隨機(jī)算法中的許多定理的運(yùn)用
在這門課中，我學(xué)到了以前從未遇見過的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過多次的嘗試來降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素?cái)?shù)判定的定理。尤其是對尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯(cuò)率的計(jì)算，算法性能的評(píng)價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。
這些算法都給予了我很大啟發(fā)，要想學(xué)好算法，學(xué)好數(shù)學(xué)是必不可少的。沒有深厚的數(shù)學(xué)功力作為地基，即使再漂亮的算法框架，代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。
二、算法的核心是思想
我們學(xué)習(xí)這門課不是僅僅掌握那幾個(gè)經(jīng)典算法例子，更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢？舉個(gè)例子。有同學(xué)曾問我這樣一個(gè)問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個(gè)星期。現(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個(gè)瓶子的水，每個(gè)瓶子可以只喝一點(diǎn)。問如何解決？其實(shí)一開始我也一頭霧水，但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān)，我就立馬有了思路，運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說，我們不僅要學(xué)習(xí)算法，更得學(xué)習(xí)思想方法。
①算法最基本的設(shè)計(jì)方法包括分治法，動(dòng)態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個(gè)元素中最大元和最小元的量級(jí)，降低n位二進(jìn)制x和y相乘的量級(jí)，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨(dú)立的子問題，關(guān)鍵是子問題要與原問題同類，可以采取平衡法來提高性能。
動(dòng)態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復(fù)的，后面的問題可以利用前面解決過的問題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹，解決矩陣連乘時(shí)最小計(jì)算次數(shù)問題，尋找最長公共子序列等等。
貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。
周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點(diǎn)，典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。
回溯法就是就是在滿足一定的條件后就往前走，當(dāng)走到某步時(shí)，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問題，平面點(diǎn)集的凸包問題和0-1背包問題。
分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問題。
②評(píng)價(jià)算法性能的方法如平攤分析中的聚集法，會(huì)計(jì)法和勢能法。聚集法就是把指令分為幾類，計(jì)算每一類的消耗，再全部疊加起來。會(huì)計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去，以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢能法計(jì)算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計(jì)。
這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間，盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會(huì)計(jì)法中用什么指令提前計(jì)算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學(xué)會(huì)去應(yīng)用，在具體的問題中去判斷分析。
三、算法與應(yīng)用緊密相關(guān)
我認(rèn)為學(xué)習(xí)算法不能局限于書本上的理論運(yùn)算，局限于如何提高性能以降低復(fù)雜度，我們要將它與實(shí)際生活聯(lián)系起來。其實(shí)算法問題的產(chǎn)生就來自于生活，設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長公共子序列算法可以應(yīng)用在生物信息學(xué)中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個(gè)字符串的相近性，這可應(yīng)用在數(shù)據(jù)挖掘中。快速傅立葉變換（FFT）可應(yīng)用在計(jì)算多項(xiàng)式相乘上來降低復(fù)雜度，脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法，它對于解決網(wǎng)絡(luò)流量分配問題起了很大的幫助，等等。
這些應(yīng)用給了我很大的啟發(fā)：因?yàn)閱渭冎v一個(gè)Union-Find算法，即使了解了它的實(shí)現(xiàn)原理，遇到具體的實(shí)際問題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問題結(jié)合起來，不能停留在思想方法階段，要學(xué)以致用，做到具體問題具體分析。
四、對計(jì)算模型和NP問題的理解
由于對這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。
首先談到計(jì)算模型，就不得不提到圖靈計(jì)算，他將基本的計(jì)算抽象化，造出一個(gè)圖靈機(jī)，得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問題都是可以計(jì)算的，否則就是不可計(jì)算的。由此引申出一個(gè)著名論題：任何合理的計(jì)算模型都是相互等價(jià)的。它說明了可計(jì)算性本身不依賴于任何具體的模型而客觀存在。
NP問題比較復(fù)雜，我認(rèn)為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個(gè)特殊的性質(zhì)，如果存在一個(gè)NP-C問題找到一個(gè)多項(xiàng)式時(shí)間的解法，則所有的NP-C問題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時(shí)可以找出精確解，但是規(guī)模大時(shí)，就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會(huì)采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法，如漢諾塔問題。
最后談?wù)剬@門課程的建議
①對于這門算法課，我認(rèn)為應(yīng)該加強(qiáng)對算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會(huì)兒，或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制，誰能解決這個(gè)問題，平時(shí)成績加分。這在一定程度上會(huì)將強(qiáng)我們思考分析問題的能力。因?yàn)槲腋杏X到，一個(gè)問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點(diǎn)名回答問題可以一定程度上有效的防止不認(rèn)真聽課的現(xiàn)象。
②作業(yè)安排的不是很恰當(dāng)。本門課主要安排了三次作業(yè)，個(gè)人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼，沒有太多的技術(shù)含量。而且對于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因?yàn)檫@間接成為了程序設(shè)計(jì)題，不是算法設(shè)計(jì)題。
③本門課的時(shí)間安排的不太恰當(dāng)，因?yàn)楸緦W(xué)期的課程太多，壓力太大。沒有太多的時(shí)間去學(xué)習(xí)這門課程。因?yàn)槲蚁嘈糯蠹叶紝λ信d趣，比較重視，想花功夫，但苦于沒時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期，那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過，且課程的壓力也不是很大。錯(cuò)開時(shí)間的話，我覺得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。
第三篇：算法總結(jié)
算法分塊總結(jié)
為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過的題目按算法分塊做一個(gè)全面詳細(xì)的總結(jié)，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設(shè)計(jì)中，時(shí)刻都要牢記要減少冗余，要以簡潔高效為追求目標(biāo)。另外當(dāng)遇到陌生的問題時(shí)，要想方設(shè)法進(jìn)行模型簡化，轉(zhuǎn)化，轉(zhuǎn)化成我們熟悉的東西。
圖論模型的應(yīng)用
分層圖思想的應(yīng)用：
用此思想可以建立起更簡潔、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型，進(jìn)而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質(zhì)： 由于層是由復(fù)制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進(jìn)行新層的存儲(chǔ)，甚至幾乎不需要花時(shí)間去處理。由于層之間的相似性，很多計(jì)算結(jié)果都是相同的。所以我們只需對這些計(jì)算進(jìn)行一次，把結(jié)果存起來，而不需要反復(fù)計(jì)算。如此看來，雖然看起來圖變大了，但實(shí)際上問題的規(guī)模并沒有變大。層之間是拓?fù)溆行虻摹＿@也就意味著在層之間可以很容易實(shí)現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。
這些特點(diǎn)說明這個(gè)分層圖思想還是很有潛力的，尤其是各層有很多公共計(jì)算結(jié)果這一點(diǎn)，有可能大大消除冗余計(jì)算，進(jìn)而降低算法時(shí)間復(fù)雜度。二分圖最大及完備匹配的應(yīng)用： ZOJ place the robots: 二分圖最優(yōu)匹配的應(yīng)用：
最大網(wǎng)絡(luò)流算法的應(yīng)用：典型應(yīng)用就求圖的最小割。最小費(fèi)用最大流的應(yīng)用：
容量有上下界的最大流的應(yīng)用：
歐拉路以及歐拉回路的應(yīng)用：主要利用求歐拉路的套圈算法。最小生成樹：
求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復(fù)雜度降為O(Vlog2V+E)，后者一般應(yīng)用于稀疏圖，其時(shí)間復(fù)雜度為O(Elog2V)。最小K度限制生成樹：
抽象成數(shù)學(xué)模型就是：
設(shè)G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個(gè)頂點(diǎn),k為給定的一個(gè)正整數(shù)。首先考慮邊界情況。先求出問題有解時(shí)k 的最小值：把v0點(diǎn)從圖中刪去后，圖中可能會(huì)出 現(xiàn)m 個(gè)連通分量，而這m 個(gè)連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當(dāng)k 首先，將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去，此時(shí)的圖可能不再連通，對各個(gè)連通分量，分別求最小生成樹。接著，對于每個(gè)連通分量V’，求一點(diǎn)v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個(gè)m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時(shí)間復(fù)雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉(zhuǎn)化成以v0為根的有根樹。 假設(shè)已經(jīng)得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關(guān)聯(lián)的邊后，必定形成一個(gè)環(huán)。若想得到一棵p+1 度限制生成樹，需刪去一條在環(huán)上的且與v0無關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大，則所得到的生成樹的權(quán)值和就越小。動(dòng)態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點(diǎn)，動(dòng)態(tài)轉(zhuǎn)移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 狀態(tài)共|V|個(gè)，狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度O(1)，所以總的時(shí)間復(fù)雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時(shí)間復(fù)雜度為O(V)。1 先求出最小m度限制生成樹； 2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當(dāng)dT(v0)=k時(shí)停止。 加邊和去邊過程，利用動(dòng)態(tài)規(guī)劃優(yōu)化特別值得注意。 次小生成樹： 加邊和去邊很值得注意。 每加入一條不在樹上的邊，總能形成一個(gè)環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權(quán)值越大，新得到的生成樹的權(quán)值和越小。具體做法： 首先做一步預(yù)處理，求出樹上每兩個(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預(yù)處理，我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。如何預(yù)處理呢？因?yàn)檫@是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。 最短路徑的應(yīng)用： Dijkstra 算法應(yīng)用： Folyed 算法應(yīng)用： Bellman-Ford 算法的應(yīng)用： 差分約束系統(tǒng)的應(yīng)用： 搜索算法 搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個(gè)較優(yōu)的搜索出發(fā)點(diǎn)，凡是能用高效算法的地方盡量爭取用高效算法。基本的遞歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應(yīng)用： 枚舉思想的應(yīng)用： ZOJ 1252 island of logic A*算法的應(yīng)用： IDA*算法的應(yīng)用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，動(dòng)態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索： 可行性剪枝，最優(yōu)性剪枝，調(diào)整搜索順序是常用的優(yōu)化手段。 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉(zhuǎn)移方程，另外還要考慮高效的預(yù)處理（以便更好更快的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移）。最常用的思想就是用枚舉最后一次操作。 狀態(tài)壓縮DP，又叫帶集合的動(dòng)態(tài)規(guī)劃：題目特點(diǎn)是有一維的維數(shù)特別小。類似TSP問題的DP： 狀態(tài)劃分比較困難的題目： 樹形DP： 四邊形不等式的應(yīng)用探索：四邊形不等式通常應(yīng)用是把O(n^3)復(fù)雜度O(n^2) 高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用 并查集的應(yīng)用： 巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應(yīng)用： 總結(jié)用線段樹解題的方法 根據(jù)題目要求將一個(gè)區(qū)間建成線段樹，一般的題目都需要對坐標(biāo)離散。建樹時(shí)，不要拘泥于線段樹這個(gè)名字而只將線段建樹，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個(gè)點(diǎn)、線段、或數(shù)組中一個(gè)值)組成的，都可以建線段樹；不要拘泥于一維，根據(jù)題目要求可以建立面積樹、體積樹等等 樹的每個(gè)節(jié)點(diǎn)根據(jù)題目所需，設(shè)置變量記錄要求的值 用樹形結(jié)構(gòu)來維護(hù)這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點(diǎn)的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時(shí)，都只對O(logL)個(gè)節(jié)點(diǎn)修改這個(gè)特點(diǎn)，在O(logL)的時(shí)間內(nèi)維護(hù)修改后相關(guān)節(jié)點(diǎn)的變量。 在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運(yùn)用子樹的收縮與葉子節(jié)點(diǎn)的釋放，避免重復(fù)操作。 Trie的應(yīng)用：； Trie圖的應(yīng)用探索： 后綴數(shù)組的應(yīng)用研究： 在字符串處理當(dāng)中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹了解得比較多，關(guān)于后綴數(shù)組則很少見于國內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹的一個(gè)非常精巧的替代品，它比后綴樹容易編程實(shí)現(xiàn)，能夠?qū)崿F(xiàn)后綴樹的很多功能而時(shí)間復(fù)雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。 樹狀數(shù)組的應(yīng)用探索：； 計(jì)算幾何 掌握基本算法的實(shí)現(xiàn)。凸包的應(yīng)用：； 半平面交算法的應(yīng)用：； 幾何+模擬類題目：幾何設(shè)計(jì)好算法，模擬控制好精度。掃描法：； 轉(zhuǎn)化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應(yīng)用：； 經(jīng)典算法：找平面上的最近點(diǎn)對。 貪心 矩形切割 二分思想應(yīng)用 活用經(jīng)典算法 利用歸并排序算法思想求數(shù)列的逆序?qū)?shù)： 利用快速排序算法思想，查詢N個(gè)數(shù)中的第K小數(shù)： 博弈問題 博弈類題目通常用三類解法：第一類推結(jié)論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應(yīng)用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。 第一類：推結(jié)論。典型題目： 第二類：遞推。典型題目： 比如有向無環(huán)圖類型的博弈。在一個(gè)有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應(yīng)該具有如下性質(zhì)： 1． 所有的結(jié)束位置都是P位置。 2． 對于每一個(gè)N位置，至少存在一種移動(dòng)可以將棋子移動(dòng)到一個(gè)P位置。3． 對于每一個(gè)P位置，它的每一種移動(dòng)都會(huì)將棋子移到一個(gè)N位置。 這樣，獲勝的策略就是每次都把棋子移動(dòng)到一個(gè)P位置，因?yàn)樵谝粋€(gè)P位置，你的對手只能將棋子移動(dòng)到一個(gè)N位置，然后你總有一種方法再把棋子移動(dòng)到一個(gè)P位置。一直這樣移動(dòng)，最后你一定會(huì)將棋子移動(dòng)到一個(gè)結(jié)束位置（結(jié)束位置是P位置），這時(shí)你的對手將無法在移動(dòng)棋子，你便贏得了勝利。 與此同時(shí)，得到了這些性質(zhì)，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為： 1． 將所有的結(jié)束位置標(biāo)為P位置。 2． 將所有能一步到達(dá)P位置的點(diǎn)標(biāo)為N位置。 3． 找出所有只能到達(dá)N位置的點(diǎn)，將它們標(biāo)為P位置。 4． 如果在第三步中沒有找到新的被標(biāo)為P位置的點(diǎn)，則算法結(jié)束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應(yīng)用。 關(guān)于SG函數(shù)的基本知識(shí)：對于一個(gè)有向圖(X, F)來說，SG函數(shù)g是一個(gè)在X上的函數(shù)，并且它返回一個(gè)非負(fù)整數(shù)值，具體定義為 g(x)?min{n?0,n?g(y)對于所有y?F(x)} 1． 對于所有的結(jié)束位置x，g(x)= 0。 2． 對于每一個(gè)g(x)≠ 0的位置x，在它可以一步到達(dá)的位置中至少存在一個(gè)位置y使得g(y)= 0。 3．對于每一個(gè)g(x)＝ 0的位置x，所有可以由它一步到達(dá)的位置y都有g(shù)(y)≠ 0。 定理 如果g(xi)是第i個(gè)有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個(gè)有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類：極大極小法。 典型題目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關(guān)系（最基本的就是求Fibonacci數(shù)列的某項(xiàng)）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目： 數(shù)學(xué)模型舉例 向量思想的應(yīng)用： UVA 10089：注意降維和向量的規(guī)范化 ； 利用復(fù)數(shù)思想進(jìn)行向量旋轉(zhuǎn)。 UVA 10253： 遞推 數(shù)代集合 數(shù)代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個(gè)數(shù)不會(huì)超過100，因此可以考慮用一個(gè)數(shù)代替一個(gè)集合，首先把所有的運(yùn)算結(jié)果都用預(yù)處理算出來，到計(jì)算的時(shí)候只要用O(1)的復(fù)雜度就可以完成一次運(yùn)算。 組合數(shù)學(xué) Polya定理則是解決同構(gòu)染色計(jì)數(shù)問題的有力工具。 補(bǔ)集轉(zhuǎn)化思想 ZOJ 單色三角形： 字符串相關(guān) 擴(kuò)展的KMP算法應(yīng)用：；最長回文串； 最長公共子串； 最長公共前綴； 填充問題 高精度運(yùn)算 三維空間問題專題 無論什么問題，一旦擴(kuò)展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實(shí)現(xiàn)能力。 其它問題的心得 解決一些判斷同構(gòu)問題的方法：同構(gòu)的關(guān)鍵在于一一對應(yīng)，而如果枚舉一一對應(yīng)的關(guān)系，時(shí)間復(fù)雜度相當(dāng)?shù)母撸米钚”硎荆湍馨岩粋€(gè)事物的本質(zhì)表示出來。求最小表示時(shí)，我們一定要仔細(xì)分析，將一切能區(qū)分兩個(gè)元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當(dāng)?shù)摹⒏咝У钠ヅ渌惴ǎɡ鏚MP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進(jìn)行推廣 源程序代碼： } 一、自然數(shù)拆分（遞歸） } #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); 三、刪數(shù)字（貪心） #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;} 五、多段圖（動(dòng)態(tài)規(guī)劃）#include “stdio.h” #define n 12 //圖的頂點(diǎn)數(shù) { 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;//滿足條件就跳轉(zhuǎn) } } } 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 //圖的段數(shù) #define MAX 23767 int cost[n][n];//成本值數(shù)組 int path[k];//存儲(chǔ)最短路徑的數(shù)組 void creatgraph()//創(chuàng)建圖的(成本)鄰接矩陣 { int i,j; for(i=0;i for(j=0;j scanf(“%d”,&cost[i][j]);//獲取成本矩陣數(shù)據(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;//起點(diǎn) path[k-1]=n-1;//最后的目標(biāo) for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//將最短路徑存入數(shù)組中 } //使用向后遞推算法求多段圖的最短路徑 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);} 矩陣鏈乘法（動(dòng)態(tài)規(guī)劃）? 符號(hào)S[i, j]的意義： 符號(hào)S(i, j)表示，使得下列公式右邊取最小值的那個(gè)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的定義： 如果存在兩個(gè)正常數(shù)c和n0，對于所有的n≥n0時(shí)，有： |f(n)|≤c|g(n)|，稱函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)低，記為 f(n)=O(g(n))。計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù) Ω的定義： 如果存在正常數(shù)c和n0，對于所有n≥n0時(shí)，有： |f(n)|≥c|g(n)|，則稱函數(shù)f(n)當(dāng)n充分大時(shí)下有界，且g(n)是它的一個(gè)下界，即f(n)的階不低于g(n)的階。記為： f(n)=Ω(g(n))。Θ的定義： 如果存在正常數(shù)c1，c2和n0，對于所有的n>n0，有： c1|g(n)|≤f(n)≤c2|g(n)|，則記f(n)=Θ(g(n))意味著該算法在最好和最壞的情況下計(jì)算時(shí)間就一個(gè)常因子范圍內(nèi)而言是相同的。(1)多項(xiàng)式時(shí)間算法： O(1) (2)指數(shù)時(shí)間算法： O(2n) Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 貪心方法基本思想： 貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 多段圖： COST[j]=c(j,r)+COST[r]; 回溯法： (假定集合Si的大小是mi)不斷地用修改過的規(guī)范函數(shù)Pi(x1,…,xi)去測試正在構(gòu)造中的n-元組的部分向量(x1,…,xi)，看其是否可能導(dǎo)致最優(yōu)解。如果判定(x1,…,xi)不可能導(dǎo)致最優(yōu)解，那么就將可能要測試的mi+1…mn個(gè)向量略去。約束條件： (1)顯式約束：限定每一個(gè)xi只能從給定的集合Si上取值。 (2)解 空 間：對于問題的一個(gè)實(shí)例，解向量滿足顯式 約束條件的所有多元組，構(gòu)成了該實(shí)例 的一個(gè)解空間。 (3)隱式約束：規(guī)定解空間中實(shí)際上滿足規(guī)范函數(shù)的元 組，描述了xi必須彼此相關(guān)的情況。基本做法： 在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解：如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 8皇后問題 約束條件 限界函數(shù)： 子集和數(shù)問題： 約束條件 限界函數(shù)： 回溯法－－術(shù)語： 活結(jié)點(diǎn)：已生成一個(gè)結(jié)點(diǎn)而它的所有兒子結(jié)點(diǎn)還沒有 全部生成的結(jié)點(diǎn)稱為活結(jié)點(diǎn)。 E-結(jié)點(diǎn)：當(dāng)前正在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)叫E-結(jié)點(diǎn)。 死結(jié)點(diǎn)：不再進(jìn)一步擴(kuò)展或其兒子結(jié)點(diǎn)已全部生成的結(jié)點(diǎn)稱為死結(jié)點(diǎn)。 使用限界函數(shù)的深度優(yōu)先節(jié)點(diǎn)生成的方法成為回溯法；E-結(jié)點(diǎn)一直保持到死為止的狀態(tài)生成的方法 稱之為分支限界方法 且用限界函數(shù)幫助避免生成不包含答案結(jié)點(diǎn)子樹的狀態(tài)空間的檢索方法。區(qū)別： 分支限界法本質(zhì)上就是含有剪枝的回溯法，根據(jù)遞歸的條件不同，是有不同的時(shí)間復(fù)雜度的。 回溯法深度優(yōu)先搜索堆棧或節(jié)點(diǎn)的所有子節(jié)點(diǎn)被遍歷后才被從棧中彈出找出滿足約束條件的所有解 分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列，優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)找出滿足約束條件下的一個(gè)解或特定意義下的最優(yōu)解 一般如果只考慮時(shí)間復(fù)雜度二者都是指數(shù)級(jí)別的 可是因?yàn)榉种藿绶ù嬖谥鞣N剪枝，用起來時(shí)間還是很快的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是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問題的集合 如果可滿足星月化為一個(gè)問題L，則此問題L是NP-難度的。如果L是NP難度的且L NP，則此問題是NP-完全的 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 中期報(bào)告 學(xué)院: 專業(yè): 年級(jí): 題目: 行列式的算法歸納 學(xué)生姓名: 學(xué)號(hào): 指導(dǎo)教師姓名 職稱: 2012年6月20日 目錄 引言..................................................................................................................................................2 1 行列式性質(zhì)...................................................................................................................................2 2 行列式計(jì)算方法...........................................................................................................................5 2.1定義法.................................................................................................................................5 2.2遞推法.................................................................................................................................6 2.3化三角法.............................................................................................................................9 2.4拆元法...............................................................................................................................11.4加邊法..............................................................................................................................12 2.6數(shù)學(xué)歸結(jié)法.......................................................................................................................14 2.7降價(jià)法...............................................................................................................................15 2.8利用普拉斯定理...............................................................................................................16 2.9利用范德蒙行列式...........................................................................................................17 結(jié)論................................................................................................................................................18 參考文獻(xiàn).........................................................................................................................................18 行列式的概念及應(yīng)用 摘要：本文先列舉行列式計(jì)算相關(guān)性質(zhì)，然后歸納總結(jié)出了行列式的計(jì)算方法，包括：定義法，化三角法，遞推法，拆元法，加邊法，數(shù)學(xué)歸結(jié)法，降價(jià)法，利用拉普拉斯定理和利用范德蒙行列式的方法。 關(guān)鍵詞：行列式；線性方程組；范德蒙行列式 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 引言 行列式的概念最初是伴隨著方程組的求解而發(fā)展起來的。行列式的提出可以追溯到十七世紀(jì)，最初的雛形由日本數(shù)學(xué)家關(guān)孝和與德國數(shù)學(xué)家戈特弗里德·萊布尼茨各自獨(dú)立得出，時(shí)間大致相同。日本數(shù)學(xué)家關(guān)孝和提出來的，他在1683年寫了一部名為解伏題之法的著作，意思是“解行列式問題的方法”，書中對行列式的概念和它的展開已經(jīng)有了清楚的敘述。歐洲第一個(gè)提出行列式概念的是德國數(shù)學(xué)家，微積分學(xué)奠基人之一萊布尼茨。十八世紀(jì)開始，行列式開始作為獨(dú)立的數(shù)學(xué)概念被研究。十九世紀(jì)以后，行列式理論進(jìn)一步得到發(fā)展和完善。矩陣概念的引入使得更多有關(guān)行列式的性質(zhì)被發(fā)現(xiàn)，行列式在許多領(lǐng)域都逐漸顯現(xiàn)出重要的意義和作用，出現(xiàn)了線性自同態(tài)和向量組的行列式的定義。行列式的性質(zhì) 性質(zhì)1 行列互換，行列式值不變，即 a11a12?a1na21a22?a2n????an1an2?anna11[1] a21a22?a2n?an1?an2 ??anna12?a1n其實(shí)，元素aij在上式的右端位于第j行第i列，即此時(shí)i是列指標(biāo)，j為行指標(biāo)。 在行列式中，行與列的地位是對稱的，所以有關(guān)行的性質(zhì)，對列也成立。 性質(zhì)2 如果行列式中一行為零，那么行列式為零。 ?的元都是二項(xiàng)式，那么這個(gè)行列式等于把這些性質(zhì)3 如果行列式的某一行?或一列二項(xiàng)式各取一項(xiàng)作成相應(yīng)行?或列?而其余行?或列?不變的兩個(gè)行列式的和。 即 a11?b1j?c1ja21?b2j?c2j??an1?bnj?cnj?a1na11?b1j?a2na21?b2j?????annan1?bnj?a1na11?c1j?a2na21?c2j?????annan1?cnj?a1n?a2n ??ann這就是說，如果某一行是兩組數(shù)的和，那么這個(gè)行列式就等于兩個(gè)行列式的和，而這兩個(gè)行列式除這一行以外全與原來行列式的對應(yīng)的行一樣。 性質(zhì)4 如果行列式中有兩行相同，那么行列式為零，所謂兩行相同就是說兩行的對應(yīng)元素都相等。 性質(zhì)5 如果行列式中兩行成比例，那么行列式為零。性質(zhì)6 把一行的倍數(shù)加到另一行，行列式不變。性質(zhì)7 對換行列式中兩行的位置，行列式反號(hào)。 2.行列式的計(jì)算方法 2.1 定義法 n階行列式計(jì)算的定義[3]： a11Dn?a21?an1?其中，j1j2?jna12?a1na22?a2n??an2?ann(?1)?(j1j2?jn)a1j1a2j2?anjn ?j1j2?jn?表示對所有n級(jí)排列求和。j1j2?jn是1,2,?,n的一個(gè)排列，當(dāng)j1j2?jn是?(j1j2?jn)偶排列時(shí)，(?1)是正號(hào)；當(dāng)j1j2?jn是奇排列時(shí)，(?1)?(j1j2?jn)是負(fù)的。a1j1a2j2?anjn是D中取自不同行不同列的n個(gè)元素的乘積。 a11a21例2.1：證明D?a31a12a22a32a42a52a13a23000a14a24000a15a250?0.00a41a51分析 觀察行列式我們會(huì)發(fā)現(xiàn)有許多零,故直接用定義法.證明： 由行列式的定義知除去符號(hào)差別外行列式一般項(xiàng)可表示為a1j1a2j2?anjn 則 Dn?j1j2?j5?(?1)?(j1j2?j5)a1j1a2j2?anjn.（3） 其中j1,j1,?,j5為1,2,3,4,5的任意排列,在D中位于后三行后三列的元素為零,而在前兩行前兩列中,取不同行不同列的元素只有四個(gè),就是說（3）式中每一項(xiàng)至少有一個(gè)來自后三行后三列.故D=0.注意 此方法適用于階數(shù)較低的行列式或行列式中零的個(gè)數(shù)較多.2.3 遞推法 應(yīng)用行列式的性質(zhì)，把一個(gè)較高階行列式表示為具有相同結(jié)構(gòu)的較低階行列式（比如，n-1階或n-1階與n-2階等）的線性關(guān)系式，這種關(guān)系式稱為遞推關(guān)系式。根據(jù)遞推關(guān)系式及某個(gè)低階初始行列式（比如二階或一階行列式）的值，便可遞推求得所給n階行列式的值，這種計(jì)算行列式的方法稱為遞推法。 注意：用此方法一定要看行列式是否具有較低階的相同結(jié)構(gòu)如果沒有的話，即很難 找出遞推關(guān)系式，從而不能使用此方.[4] 例2.2證如下行列式等式 ???Dn?10?0?????1?00?0000 ???0????0?0???1???n?1??n?1?,其中???（雖然這是一道證明題，但我們可以直接求 證明： Dn????出其值，從而證之）。 分析：此行列式的特點(diǎn)是：除主對角線及其上下兩條對角線的元素外，其余的元素 都為零，這種行列式稱“三對角”行列式。從行列式的左上方往右下方看，即知Dn?1與Dn具有相同的結(jié)構(gòu)。因此可考慮利用遞推關(guān)系式計(jì)算。 證明：Dn按第1列展開，再將展開后的第二項(xiàng)中n-1階行列式按第一行展開有： Dn?（?＋?）Dn－1－??Dn－2，這是由Dn?1 和Dn?2表示Dn的遞推關(guān)系式。若由上面的遞推關(guān)系式從n階逐階往低 階遞推，計(jì)算較繁，注意到上面的遞推關(guā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）現(xiàn)可反復(fù)用低階代替高階，有： 23Dn－?Dn－1＝（?Dn－1－?Dn－2）＝?（Dn－2－?Dn－3）＝?（Dn－3－?Dn－4）＝?＝?（D2－?D1）=?同樣有 n?2n－2[(???)?????(???)]????(1)2n 23Dn－?Dn－1＝?（Dn－1－?Dn－2）＝?（Dn－2－?Dn－3）＝?（Dn－3－?Dn－4）[(???)?????(???)]????(2)?n?1??n?1因此當(dāng) ???時(shí)，由（1）（2）式可解得：Dn?。 ???＝?＝?（D2－?D1）=?n?2n－22n 小結(jié)：雖然我們從一個(gè)行列式中可以看出有低階的相同的結(jié)構(gòu)，然后得到一遞推關(guān)系式，但我們不要盲目亂代，一定要看清這個(gè)遞推關(guān)系式是否可以簡化我們的計(jì)算，如果不行的話，就要適當(dāng)?shù)負(fù)Q遞 推關(guān)系式，如本題。 2.3化三角形法 運(yùn)用行列式的性質(zhì)是計(jì)算行列式的一個(gè)重要途徑,大多數(shù)行列式的計(jì)算都依賴于行列式的性 [7]質(zhì),將行列式化成上三角(下三角或反三角)的形式,再根據(jù)行列式的定義來計(jì)算行列式.行列式的性質(zhì)告訴了我們該如何求行列式,而一切的行列式都可以根據(jù)以上性質(zhì)來進(jìn)行初等行變換(列變換),變成階梯形(上三角)的行列式,再根據(jù)定義計(jì)算即可.其計(jì)算步驟可歸納如下: (ⅰ)看行列式的行和(列和),如果行列和相等,則均加到某一列(行)（直觀上加到第一列(行)）.(ⅱ)有公因子的提出公因子.(ⅲ)進(jìn)行初等行變換(列變換)化成上三角(下三角或反三角)的行列式.(ⅳ)由行列式的定義進(jìn)行計(jì)算.由以上四步,計(jì)算一般行列式都簡潔多了.123?n?1234?[6]例2.3 計(jì)算行列式Dn?345?n1n12.?????n12?n?2n?1分析 直接用化三角形法化簡很煩,觀察發(fā)現(xiàn)對于任意相鄰兩列中的元素,位于同一行的元素中,后面元素與前面元素相差1,因此先從第n?1列乘-1加到第n列,第n?2列乘-1加到第n?1列, 這樣做下去直到第1列乘-1加到第2列,然后再計(jì)算就顯得容易.123?n?1234?解：Dn?345?n1n1212?31111?111?11?n1?1?n1 ?1000?10?00?????n12?n?2n?1 ???n1?n1?1?2???n12?n?111?21001?110?0?n10??n0?n?????n?1?n0?00000?0?n0 ?00?0?n0??n0 ?0?0???n0?000??n1n(n?1)?000?n2?????n0?0(n?1)(n?2)1n(n?1)?(?1)2 n2n(n?1)(n?1)n?1?n(?1)2.2問題推廣 在例2.3中1,2,?,n,這n個(gè)數(shù)我們可以看成有限個(gè)等差數(shù)列在循環(huán),那么對于一般的等差數(shù)列也應(yīng)該適應(yīng).計(jì)算行列式 [1] a1D?a1?da1?2d?a1?(n?1)da1?a1?da1?2d?a1?(n?1)da1?d2d?(n?1)da1??a1?da1?2da1?3d?a1ddd?a1?2d?a1?(n?1)da1?3d?a1?4d??a1?dd?da1?nda1??a1?(n?3)dda1?nda1a1?d?a1?(n?2)d d?dd?(1?n)d?d?dd?nd ?d(1?n)dd ?d(1?n)dd?d???nd??nd?0?0?0?00??00?nd?0 d(n?1)d???nnd2d?(n?1)d??nd??nd??0?0(n?1)(n?2)d(n?1)dn?1?(a1????)(?nd)(?1)2 nn(n?1)(n?2)1n(a1?a1?(n?1)d)n?1?()(?nd)(?1)2.n2 (n?1)(n?2)1n(a1?a1?(n?1)dn?1)(?nd)(?1)2結(jié)論如果將例2.3中的數(shù)a1?1，d?1代入?(n2顯然成立.2.4．拆元法 由行列式拆項(xiàng)性質(zhì)知，將已知行列式拆成若干個(gè)行列式之積，計(jì)算其值，再得原行 列式值，此法稱為拆行（列）法。 由行列式的性質(zhì)知道，若行列式的某行（列）的元素都是兩個(gè)數(shù)之和，則該行列式可拆成兩個(gè)行列式的和，這兩個(gè)行列式的某行（列）分別以這兩數(shù)之一為該行（列）的元素，而其他各行（列）的元素與原行列式的對應(yīng)行（列）相同，利用行列式的這一性質(zhì)，有時(shí)較容易求得行列式[2]的值。 例2.4求下列行列式的值 設(shè)n階行列式： a11a21?an1a12?a1na22?a2n?1 ??an2?ann且滿足aij??aji,i,j?1,2,?,n,對任意數(shù)b，求n階行列式 a11?ba12?b?a1n?ba21?ba22?b?a2n?b????? an1?ban2?b?ann?b 分析:該行列式的每個(gè)元素都是由兩個(gè)數(shù)的和組成，且其中有一個(gè)數(shù)是b，顯然 用拆行（列）法。 解： a11?ba12?b?a1n?ba11a12?b?a1n?bba12?b?Da21?ba22?b?a2n?ba21a22?b?a2n?bba22?b?n???????????an1?ban2?b?ann?ban1an2?b?ann?bban2?b?a11a12?a1n?ba11b?a1n?b1a12?a1n?a21a22?a2n?b1a22?a2n????a21b?a2n?b????b??? an1an2?ann?ban1b?ann?b1an2?anna11a12?a1na111?a1n1a12?a1n?a21a22?a2n???ba211?a2n1a22?a2n???????b??? an1an2?annan11?ann1an2?annnnn?1?b?A2i???b?A1i?1?bi?1i?Aij。 i?1,j?1又令 a11a12?a1nA=a21a22?a2n???,且aij??aji,i,j?1,2,?,n。 an1an2?ann 所以 有A?1,且A'??A。 由A－1＝A＊A得：A?A－1?A＊即A＊?A＝E 所以 A＊＝A－1。7 a1n?ba2n?b?ann?b 又（A＊）?(A?1)'?(A')?1??(A)?1??A＊，所以 A*也為反對稱矩陣。 *又 Aij(i,j?1,2,?,n)為A的元素，所以有i?1,j?1'?nAij?0。 從而知：Dn?1?bi?1,j?1?nAij?1。 2.5．加邊法 計(jì)算行列式往往采用降階的辦法，但在一些特殊的行列式的計(jì)算上卻要采用加邊法。行列式的加邊法是為了將行列式降階作準(zhǔn)備的。更有利于將行列式化成上三角的形式，其加邊的元素，也可根據(jù)計(jì)算的難易程度來確定。具有隨意性。利用行列式按行（列）展開的性質(zhì)把n階行列式通過 [3]加行（列）變成與之相等的n?1階行列式,然后計(jì)算.添加行列式的四種方法[18]:設(shè)Dn?a11a21?an1a12?a1na22?a2n??an2?ann.（1）首行首列Dn?a11a21?an1a11a21?an1a11a21?an1a11a21?an1a12?a1na22?a2n??an2?anna12?a1na22?a2n??an2?anna12?a1na22?a2n??an2?anna12?a1na22?a2n??an2?ann1a1a2?an0a11?0a21?0a11?a21?an1a1a2?a3?1a11a21?a31?0?0a12a22?an2a11a21a31?0a12a22a32?0a12?a1na22?a2n.??an2?ann0?1a13?a1a23?a2.??an3?ana12?a1na22?a2na32?a3n.??0?0a13?a1a23?a2a33?a3.??0?10an1（2）首行末列Dn?（3）末行首列Dn?（4）末行末列Dn?例2.5 計(jì)算n 階行列式： [4] x12?1Dn?x1x2x1x2x1x2x22?1x1x2x1x2x1x2xn2?1 分析 我們先把主對角線的數(shù)都減1，這樣我們就可明顯地看出第一行為x1與x1,x2,?,xn相乘，第二行為x2與x1,x2,?,xn相乘，??，第n行為xn與x1,x2,?,xn相乘。這樣就知道了該行列式每行有相同的因子x1,x2,?,xn，從而就可考慮此法。解： 1x1x2?0x12?1x1x2?2Dn?0x2x1x2?1??0?xnx1nxn1x1x2?x1(i?1,?,n)x2xn?x2ri?1?xir1x110?0x2?xn0?01?0?0??1?xnx22i?1?2?xn?1x110?0??xnn?1 1??xic1?xici?1(i?1,?,n)x2?xn01?0???00?1?1??xi2。i?1n00?0n?1注意:加邊法最在的特點(diǎn)就是要找出每行或每列相同的因子，那么升階之后，就可利用行列式的性質(zhì)把絕大部分元素化為零，然后再化為三角形行列式，這樣就達(dá)到了簡化計(jì)算的效果。 2.6數(shù)學(xué)歸結(jié)法 數(shù)學(xué)歸納法有兩種一種是不完全歸納法,另一種是完全歸納法,通常用不完全歸納法尋找行列式 [5]的猜想,再用數(shù)學(xué)歸納法證明猜想的正確性.基本方法 1)先計(jì)算n?1,2,3時(shí)行列式的值.2)觀察D1,D2,D3的值猜想出Dn的值.3)用數(shù)學(xué)歸納法證明.例2.6 證明： [6]2cos?1 Dn?12cos?1?0001?00??000?000?12cos??sin(n?1)?sin?(sin??0)0?002cos???2cos??1證：當(dāng)n?1,2時(shí)，有 sin(1?1)?sin? 2cos?1sin(2?1)?D2??4cos2??1?12cos?sin?D1?2cos??結(jié)論顯然成立。 現(xiàn)假定結(jié)論對小于等于n?1時(shí)成立。即有 Dn?2?將Dn按第1列展開，得 sin(n?2?1)?,sin?Dn?1? sin(n?1?1)?。 sin?2cos?1Dn??001?2cos???0000?00?12cos?2cos?1??000?2cos???0000?00?12cos??2cos??1(n?1)?2cos??1(n?1)?2cos??Dn?1?Dn?2sin(n?1?1)?sin(n?2?1)??sin?sin?2cos??sinn??sin(n?1)??sin?2cos??sinn??sinn??cos??cosn??sin??sin?sinn??cos??cosn??sin??sin?sin(n?1)??sin??2cos?? 故當(dāng)對n時(shí)，等式也成立。得證。 2.7降階法 n階行列式等于它的任意一行(列)各元素與其對應(yīng)的代數(shù)余子式乘積的和.即 D??aijAij(i?1,2,?,n)或D??aijAij(j?1,2,?,n).j?1i?1nn行列式按一行（列）展開將高階轉(zhuǎn)化為若干低階行列式計(jì)算方法稱為降階法.這是一種計(jì)算[9]行列式的常用方法.1301例2.7 計(jì)算D?30141121011001.1解 D?30?9110?2200110?911?1??220?110?21??4.21注意 對于一般的n階行列式若直接用降階法計(jì)算量會(huì)大大加重.因此必須先利用行列式的性質(zhì)將行列式的某一行（列）化為只含有一個(gè)非零元素,然后再按此行（列）展開,如此進(jìn)行下去,直到二階.2.8 利用拉普拉斯定理 在利用行列式的一行(列)展開式時(shí),我們可以發(fā)現(xiàn)計(jì)算行列式可以按某一行(列)展開,進(jìn)行計(jì)算行列式.試想,我們可以根據(jù)行列式的某一個(gè)K級(jí)字式展開嗎? 拉普拉斯經(jīng)過對行列式的研究.終于發(fā)現(xiàn)此種方法可行,并給出了嚴(yán)密的證明,為了使行列式的計(jì)算更為簡潔,現(xiàn)引入拉普拉斯定理.拉普拉斯定理[12]:設(shè)在行列式D中任意取定了k?1?k?n?1?個(gè)行,由這k行元素所組成的一切K級(jí)字式與它們的代數(shù)余子式的乘積的和等于行列式D.拉普拉斯定理的四種特殊情形： 1）AnnCmn00BmmAnnCmn?Ann?Bmm Ann2） 0Cnm?Ann?Bmm Bmm3）Bmm?(?1)mnAnn?Bmm 4） CnmBmmAnn0?(?1)mnAnn?Bmm 例2.8計(jì)算n階行列式 ?aaa?ab?Dn?b??b???????????? ????? 解 ?Dn(i?2，n?1)aaa?ab??i?1??2???0?????0(n?1)a00?0?00???0??aa?0????a 0?????C2?Ci0b??(n?2)?(i?3,?n)0?0????0?0?0?0?00????????????利用拉普拉斯定理?(n?1)ab??(n?2)??2?20?0n?20?0????0??0????(n?2)?(n?2)?[????(n?2)??ab(n?1)]?(???)2.9 利用范德蒙行列式 范德蒙行列式[14] ： 1x1x12x1n?11x2x22n?1x21x3x32n?1x31xn2xn?1?j?i?nn?1xn?(xi?xj) (a?n?1)n?1(a?n?1)n?2例2.9[16] (a?n?2)n?1?(a?1)n?1(a?n?2)n?2?(a?1)n?2?a?n?21???a?11an?1an?2? a1：計(jì)算n階行列式 Dn??a?n?11解 ： 顯然該題與范德蒙行列式很相似，但還是有所不同，所以先利用行列式的性質(zhì)把它化為范德蒙行列式的類型。 先將的第n行依次與第n-1行，n-2行，?,2行，1行對換，再將得到到的新的行列式的第n行與第n-1行，n-2行，?,2行對換，繼續(xù)仿此作法，直到最后將第n行與第n-1行對換，這樣，共經(jīng)過（n-1）+（n-2）+?+2+1=n（n-1）/2次行對換后，得到 1Dn?(?1)n(n?1)21a?n?2???1a?1?1a? an?2an?1a?n?1?(a?n?1)n?2(a?n?1)n?1(a?n?2)n?2?(a?1)n?2(a?n?2)n?1?(a?1)n?1上式右端的行列式已是范德蒙行列式，故利用范德蒙行列式的結(jié)果得 ?En?AB??n?m?Em?BA Dn?(?1)n(n?1)21?j?i?n?[(a?n?i)?(a?n?j)]?(?1)n(n?1)21?j?i?n?(i?j) 結(jié)論： 綜上所述，針對行列式結(jié)構(gòu)特點(diǎn)而采用與之相適應(yīng)的計(jì)算技巧，從而總結(jié)出了多種類型題目所適用的計(jì)算方法，因此，對于計(jì)算行列式的方法，我們首先要熟練掌握并懂得如何選擇、運(yùn)用，不管是哪一種行列式的計(jì)算，選取恰當(dāng)?shù)姆椒ǎ拍茌^快地解出其值。 參考文獻(xiàn) ［1］李師正等.高等代數(shù)復(fù)習(xí)解題方法與技巧.高等教育出版社, 2005 ［2］張賢科 許甫華.高等代數(shù)學(xué).清華大學(xué)出版社, 2000 ［3］劉學(xué)鵬等.高等代數(shù)復(fù)習(xí)與研究.南海出版公司, 1995 ［4］許甫華 張賢科.高等代數(shù)解題方法.清華大學(xué)出版社, 2001 ［5］李永樂.研究生入學(xué)考試線性代數(shù).北京大學(xué)出版社, 2000 ［6］王萼芳 石生明.高等代數(shù)學(xué).高等教育出版社, 2003 ［7］呂林根.許子道.解析幾何.高等教育出版社 2006 ［8］賈冠軍.菏澤師專學(xué)報(bào), Journal of Heze Teachers College, 1999年 02期 ［9］吳曉慶，關(guān)豐宇.行列式的相關(guān)性質(zhì)與應(yīng)用.數(shù)學(xué)學(xué)習(xí)與研究 2011年第3期 [10] 張子杰.行列式計(jì)算中的一些方法.河北工程技術(shù)高等專科學(xué)院學(xué)報(bào).[11] 北京大學(xué)數(shù)學(xué)系幾何與代數(shù)教研室代數(shù)小組，高等代數(shù)（第二版）.北京：高等教育出版社，1994 [12] 王品超著，高等代數(shù)新方法.濟(jì)南：山東教育出版社，1989 [13] 李師正,高等代數(shù)復(fù)習(xí)解題方法與技巧.高等教育出版社,2005 [14] 劉洪星,高等代數(shù)選講.機(jī)械工業(yè)出版社,2009 [15] 姚慕生,高等代數(shù).上海：復(fù)旦大學(xué)出版社，2002 [16] 許甫華，張賢科.高等代數(shù)解題方法.北京：清華大學(xué)出版社，2001 [17] 期刊論文 ,一個(gè)n階行列式的若干種計(jì)算方法.科技信息，2009，（3）：18-23 [18] 張禾瑞 郝鈵新 《高等代數(shù)》 高等教育出版社 1999 [19] 徐仲 陸全 張凱院 呂全義 安曉虹 《高等代數(shù)》 西北工業(yè)大學(xué)出版社 2006第四篇：算法總結(jié)材料
第五篇：行列式算法歸納總結(jié)
點(diǎn)擊咨詢 