求遞歸方程漸近界的常用方法-資料下載頁(yè)
2025-08-04 16:53本頁(yè)面
【正文】 形式f(n)的形式 條 件 方程()的特解的形式 an C(a)≠0 a是C(t)的m重根 ns C(1)≠0 1是C(t)的m重根 nsan C(a)≠0 a是C(t)的m重根 第三步，寫(xiě)出()即()的通解()其中{Ti(n)，i=0,1,2,…,n}是()的基礎(chǔ)解系，g(n)是()的一個(gè)特解。然后由()的初始條件T(i)=Ti ，i=1,2,…,k1來(lái)確定()中的待定的組合常數(shù){ai}，即依靠線性方程組或解出{ai}，并代回()。其中βj=Tjg(j)，j=0,1,2,…,k1。第四步，估計(jì)()的漸近階，即為所要求。下面用兩個(gè)例子加以說(shuō)明。例l 考慮遞歸方程它的相應(yīng)特征方程為：C(t)=t2t1=0解之得兩個(gè)單根和。相應(yīng)的()的基礎(chǔ)解系為{r0n，r1n}。相應(yīng)的()的一個(gè)特解為F*(n)=8，因而相應(yīng)的()的通解為：F(n)=a0r0n +a1r1n 8令其滿足初始條件，得二階線性方程組：或或解之得，從而于是。例2 考慮遞歸方程 T(n)=4T(n1)4T(n2)+2nn ()和初始條件T(0)=0，T(1)=4/3。它對(duì)應(yīng)的特征方程()為C(t)=t24t+4=0有一個(gè)兩重根r =2。故相應(yīng)的()的基礎(chǔ)解系為{2n，2nn}。由于f(n)=2nn，利用表61，相應(yīng)的()的一個(gè)特解為T*(n)=n2(p0+p1n)2n，代人()，定出p0=1/2，p1=1/6。因此相應(yīng)的()的通解為：T(n)=a02n+a1n2n+n2(1/2+n/6)2n，令其滿足初始條件得a0=a1=0，從而T(n)=n2(1/2+n/6)2n于是T(n)=θ(n32n)。遞歸方程組解的漸進(jìn)階的求法——母函數(shù)法關(guān)于T(n)的遞歸方程的解的母函數(shù)通常設(shè)為：()當(dāng)()右端由于T(n)增長(zhǎng)太快而僅在x=0處收斂時(shí)可另設(shè)()如果我們可以利用遞歸方程建立A(x)的一個(gè)定解方程并將其解出，那么，把A(x)展開(kāi)成冪級(jí)數(shù)，則xn或xn/n!項(xiàng)的系數(shù)便是所求的遞歸方程的解。其漸近階可接著進(jìn)行估計(jì)。下面舉兩個(gè)例子加以說(shuō)明。例1 考慮線性變系數(shù)二階齊次遞歸方程(n1)T(n)=(n2)T(n1)+2T(n2) ，n≥2 ()和初始條件T(0)=0，T(1)=1。根據(jù)初始條件及()，可計(jì)算T(2)=0，T(3)=T(1)=1。設(shè){T(n)}的母函數(shù)為：由于T (0)=T (2)=0，T(1)= 1，有 ：令 B(x)= A (x)/x，即：那么：利用()并代入T (3)= 1，得即兩邊同時(shí)沿[0,x]積分，并注意到B(0)=1，有：把B(x)展開(kāi)成冪級(jí)數(shù)，得從而最后得例2 考慮線性變系數(shù)一階非齊次遞歸方程D(n)=nD(n1)+(1)n n≥1 ()及初始條件D (0)= 1很明顯D(n)隨n的增大而急劇增長(zhǎng)。如果仍采用()形式的函數(shù)，則()的右端可能僅在x=0處收斂，所以這里的母函數(shù)設(shè)為：用xn/n!乘以()的兩端，然后從1到∞求和得：化簡(jiǎn)并用母函數(shù)表達(dá)，有：A(x) 1= xA(x)+ex1或(1x)A(x)=ex從而A(x)=ex/(1x)展成冪級(jí)數(shù)，則：故
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1