四基于線性代數(shù)與差分方程方法的模型

第四章

基于線性代數(shù)方法的數(shù)學(xué)模型基于線性代數(shù)與差分方程方法的模型

在第三章中，我們有多處對不連續(xù)變化的變量采取了連續(xù)化的方法，從而建立了相應(yīng)的微分方程模型。但是由于以下原因：第一，有時(shí)變量事實(shí)上只能取自一個(gè)有限的集合；第二，有時(shí)采取連續(xù)化方法后建立的模型比較復(fù)雜，無法求出問題的解，從而只能求它們的數(shù)值解。也就是說，在建模時(shí)我們對離散變量作了連續(xù)化處理，而在求解時(shí)，又對連續(xù)變量作了離散化處理，使之重新變?yōu)殡x散變量。所以采取連續(xù)化方法的效果有時(shí)并不很好，因而是不可取的。電子計(jì)算機(jī)的廣泛應(yīng)用為我們處理大量信息提供了實(shí)現(xiàn)的可能，這就十分自然地提出了一個(gè)問題，對具有離散變量的實(shí)際問題直接建立一個(gè)離散模型是否更為可?。勘菊陆榻B的幾個(gè)模型就是基于這種想法建立起來的?！?.1狀態(tài)轉(zhuǎn)移問題所謂狀態(tài)轉(zhuǎn)移問題討論的是在一定的條件下，系統(tǒng)由一狀態(tài)逐步轉(zhuǎn)移到另一狀態(tài)是否可能，如果可以轉(zhuǎn)移的話，應(yīng)如何具體實(shí)現(xiàn)？

例4.1

人、狗、雞、米過河問題這是一個(gè)人所共知而又十分簡單的智力游戲。某人要帶狗、雞、米過河，但小船除需要人劃外，最多只能載一物過河，而當(dāng)人不在場時(shí)，狗要咬雞、雞要吃米，問此人應(yīng)如何過河。在本問題中，可采取如下方法：一物在此岸時(shí)相應(yīng)分量為1，而在彼岸時(shí)則取為0，例如（1,0,1,0）表示人和雞在此岸，而狗和米則在對岸。（i）可取狀態(tài)：根據(jù)題意，并非所有狀態(tài)都是允許的，例如（0,1,1,0）就是一個(gè)不可取的狀態(tài)。本題中可取狀態(tài)（即系統(tǒng)允許的狀態(tài)）可以用窮舉法列出來，它們是：人在此岸人在對岸(1，1，1，1)(0，0，0，0)(1，1，1，0)(0，0，0，1)(1，1，0，1)(0，0，1，0)(1，0，1，1)(0，1，0，0)(1，0，1，0)(0，1，0，1)總共有十個(gè)可取狀態(tài)，對一般情況，應(yīng)找出狀態(tài)為可取的充要條件。（ii）可取運(yùn)算：狀態(tài)轉(zhuǎn)移需經(jīng)狀態(tài)運(yùn)算來實(shí)現(xiàn)。在實(shí)際問題中，擺一次渡即可改變現(xiàn)有狀態(tài)。為此也引入一個(gè)四維向量（轉(zhuǎn)移向量），用它來反映擺渡情況。例如（1，1，0，0）表示人帶狗擺渡過河。根據(jù)題意，允許使用的轉(zhuǎn)移向量只能有（1，0，0，0，）、（1，1，0，0）、（1，0，1，0）、（1，0，0，1）四個(gè)。規(guī)定一個(gè)狀態(tài)向量與轉(zhuǎn)移向量之間的運(yùn)算。規(guī)定狀態(tài)向量與轉(zhuǎn)移向量之和為一新的狀態(tài)向量，其運(yùn)算為對應(yīng)分量相加，且規(guī)定0+0=0，1+0=0+1=1，1+1=0。

在具體轉(zhuǎn)移時(shí)，只考慮由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)移。問題化為：由初始狀態(tài)（1，1，1，1）出發(fā)，經(jīng)奇數(shù)次上述運(yùn)算轉(zhuǎn)化為（0，0，0，0）的轉(zhuǎn)移過程。我們可以如下進(jìn)行分析：（第一次渡河）（第二次渡河）＝以下可繼續(xù)進(jìn)行下去，直至轉(zhuǎn)移目的實(shí)現(xiàn)。上述分析實(shí)際上采用的是窮舉法，對于規(guī)模較大的問題是不宜采用的。例4.2夫妻過河問題這是一個(gè)古老的阿拉伯?dāng)?shù)學(xué)問題。有三對夫妻要過河，船最多可載兩人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不場的情況下與其他男子在一起，問此時(shí)這三對夫妻能否過河？這一問題的狀態(tài)和運(yùn)算與前一問題有所不同，根據(jù)題意，狀態(tài)應(yīng)能反映出兩岸的男女人數(shù)，過河也同樣要反映出性別

故可如下定義：（i）可取狀態(tài)：用H和W分別表示此岸的男子和女子數(shù)，狀態(tài)可用矢量（H，W）表示，其中0≤H、W≤3?？扇顟B(tài)為（0,i），(i,i)，(3,i)，0≤i≤3。(i,i)為可取狀態(tài)，這是因?yàn)榭偪梢赃m當(dāng)安排而使他們是i對夫妻。（ii）可取運(yùn)算：過河方式可以是一對夫妻、兩個(gè)男人或兩個(gè)女人，當(dāng)然也可以是一人過河。轉(zhuǎn)移向量可取成((－1)im,(－1)in)，其中m、n可取0、1、2，但必須滿足1≤m+n≤2。當(dāng)j為奇數(shù)時(shí)表示過河。當(dāng)j為偶數(shù)時(shí)表示由對岸回來，運(yùn)算規(guī)則同普通向量的加法。

問題歸結(jié)為由狀態(tài)(3,3)經(jīng)奇數(shù)次可取運(yùn)算，即由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)移，轉(zhuǎn)化為(0,0)的轉(zhuǎn)移問題。和上題一樣，我們既可以用計(jì)算機(jī)求解，也可以分析求解，此外，本題還可用作圖方法來求解。在H~W平面坐標(biāo)中，以“·”表示可取狀態(tài)，從A(3,3)經(jīng)奇數(shù)次轉(zhuǎn)移到達(dá)O(0,0)。奇數(shù)次轉(zhuǎn)移時(shí)向左或下移動(dòng)1-2格而落在一個(gè)可取狀態(tài)上，偶數(shù)次轉(zhuǎn)移時(shí)向右或上移動(dòng)1-2格而落在一個(gè)可取狀態(tài)上。為了區(qū)分起見,用紅箭線表示奇數(shù)次轉(zhuǎn)移，用藍(lán)箭線表示第偶數(shù)次轉(zhuǎn)移,下圖給出了一種可實(shí)現(xiàn)的方案,故A(3,3)O(0,0)HW這三對夫妻是可以過河的。假如按這樣的方案過河,共需經(jīng)過十一次擺渡。不難看出,在上述規(guī)則下,4對夫妻就無法過河了,讀者可以自行證明之.類似可以討論船每次可載三人的情況,其結(jié)果是5對夫妻是可以過河的,而六對以上時(shí)就無法過河了。

§4.2密碼的設(shè)計(jì)，解碼與破譯

密碼的設(shè)計(jì)和使用至少可從追溯到四千多年前的埃及,巴比倫、羅馬和希臘，歷史極為久遠(yuǎn)。古代隱藏信息的方法主要有兩大類：其一為隱藏信息載體，采用隱寫術(shù)等；其二為變換信息載體，使之無法為一般人所理解。

在密碼學(xué)中，信息代碼被稱為密碼，加密前的信息被稱為明文，經(jīng)加密后不為常人所理解的用密碼表示的信息被稱為密文(ciphertext)，將明文轉(zhuǎn)變成密文的過程被稱為加密(enciphering)，其逆過程則被稱為解密(deciphering)，而用以加密、解密的方法或算法則被稱為密碼體制(crytosystem)。記全體明文組成的集合為U，全體密文組成的集合為V，稱U為明文空間，V為密文空間。加密常利用某一被稱為密鑰的東西來實(shí)現(xiàn)，它通常取自于一個(gè)被稱為密鑰空間的含有若干參數(shù)的集合K。按數(shù)學(xué)的觀點(diǎn)來看，加密與解密均可被看成是一種變換：取一k∈K，u∈U，令，v為明文u在密鑰K下的密文，而解碼則要用到K的逆變換K-1，。由此可見，密碼體系雖然可以千姿百態(tài)，但其關(guān)鍵還在于密鑰的選取。隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，大量各具特色的密碼體系不斷涌現(xiàn)。離散數(shù)學(xué)、數(shù)論、計(jì)算復(fù)雜性、混沌、……，許多相當(dāng)高深的數(shù)學(xué)知識(shí)都被用上，逐步形成了（并仍在迅速發(fā)展的）具有廣泛應(yīng)用面的現(xiàn)代密碼學(xué)。

早期密碼

替代密碼

移位密碼

代數(shù)密碼

代替法密碼采用另一個(gè)字母表中的字母來代替明文中的字母，明文字母與密文字母保持一一對應(yīng)關(guān)系，但采用的符號改變了。加密時(shí)，把明文換成密文，即將明文中的字母用密文字母表中對應(yīng)位置上的字母取代。解密時(shí)，則把密文換成明文，即把密文中的字母用明文字母表中對應(yīng)位置上的字母代回，解密過程是加密過程的逆過程。在代替法加密過程中，密文字母表即代替法密鑰，密鑰可以是標(biāo)準(zhǔn)字母表，也可以是任意建立的。

1.代替法密碼明文字母表

ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表

KLMNOPQRSTUVWXYZABCDEFGHIJ密鑰常用一密鑰單詞或密鑰短語生成混淆字母表。密鑰單詞或密鑰短語可以存放在識(shí)別碼、通行字或密鑰的秘密表格中。

混合一個(gè)字母表，常見的有兩種方法，這兩種方法都采用了一個(gè)密鑰單詞或一個(gè)密鑰短語。

方法1：a)選擇一個(gè)密鑰單詞或密鑰短語，例如：constructb)去掉其中重復(fù)的字母，得：construc)在修改后的密鑰后面接上從標(biāo)準(zhǔn)字母表中去掉密鑰中已有的字母后剩下的字母，得：明文字母表

ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表

CONSTRUABDEFGHIJKLMPQVWXYZ在設(shè)計(jì)密鑰時(shí)，也可在明文字母表中選擇一個(gè)特定字母，然后從該特定字母開始寫密鑰單詞將密鑰單詞隱藏于其中。例如，對于上例，選取特定字母k，則可得：

明文字母表

ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表

KLMPQVWXYZCONSTRUABDEFGHIJ

方法2：a)選擇一個(gè)密鑰單詞或密鑰短語，例如：constructb)去掉其中重復(fù)的字母，得：construc)這些字母構(gòu)成矩陣的第一行，矩陣的后續(xù)各行由標(biāo)準(zhǔn)字母表中去掉密鑰單詞的字母后剩下的字母構(gòu)成d)將所得矩陣中的字母按列的順序排出

得：cugmyoahpznbiqsdjvrtekwrflx按照此方法產(chǎn)生的字母表稱為混淆字母表。還可以使用混淆數(shù)?；煜龜?shù)由以下方法產(chǎn)生：a)選一密鑰單詞或密鑰短語，例如：constructb)按照這些字母在標(biāo)準(zhǔn)字母表中出現(xiàn)的相對順序給它們編號，對序列中重復(fù)的字母則自左向右編號，得：construct 143675928c)自左向右選出這些數(shù)字,得到一個(gè)混淆數(shù)字組:143675928，混淆字母表由從小到大的順序取矩陣中相應(yīng)列得出。為增加保密性，在使用代替法時(shí)還可利用一些其他技巧，如單字母表對多字母表、單字母對多字母、多重代替等。

2.移位密碼體制移位密碼采用移位法進(jìn)行加密，明文中的字母重新排列，本身不變，只是位置改變了。早在4000多年前，古希臘人就用一種名叫“天書”的器械來加密消息。該密碼器械是用一條窄長的草紙纏繞在一個(gè)直徑確定的圓筒上，明文逐行橫寫在紙帶上，當(dāng)取下紙帶時(shí)，字母的次序就被打亂了，消息得以隱蔽。收方閱讀消息時(shí)，要將紙帶重新繞在直徑與原來相同的圓筒上，才能看到正確的消息。在這里圓筒的直徑起到了密鑰的作用。

另一種移位法采用將字母表中的字母平移若干位的方法來構(gòu)造密文字母表，傳說這類方法是由古羅馬皇帝凱撒最早使用的，故這種密文字母表被稱為凱撒字母表。例如，如用將字母表向右平移3位的方法來構(gòu)造密文字母表，可得：明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表：DEFGHIJKLMNOPQRTSUVWXYZABC因此“THANKYOU”“WKDQNBRX”

以上兩種移位較易被人破譯，為打破字母表中原有的順序還可采用所謂路線加密法，即把明文字母表按某種既定的順序安排在一個(gè)矩陣中，然后用另一種順序選出矩陣中的字母來產(chǎn)生密文表。例如，對明文：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS.以7列矩陣表示如下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先約定的方式選出密文。例如，如按列選出，得到密文：touthyhrihueeysanahomndrifoorsszrnetjeed使用不同的順序進(jìn)行編寫和選擇，可以得到各種不同的路線加密體制。對于同一明文消息矩陣，采用不同的抄寫方式，得到的密文也是不同的。當(dāng)明文超過規(guī)定矩陣的大小時(shí)，可以另加一矩陣。當(dāng)需要加密的字母數(shù)小于矩陣大小時(shí)，可以在矩陣中留空位或以無用的字母來填滿矩陣。

移位法也可和代替法結(jié)合使用，并使用約定的單詞或短語作密鑰，以進(jìn)一步加強(qiáng)保密性，這就是鑰控列序加密法。

例如，用密鑰單詞construct對明文MATHEMATICALMODELINGISUSEFUL加密：CONSTRUCT143675928MATHEMATICALMODELINGISUSEFUL按混淆數(shù)的順序選出各列，得到密文：

MCNLTLFTLIAAGMDSHMSEOSIIUAEE移位法的使用可重復(fù)多次，只進(jìn)行一次移位加密的稱為一次移位法，經(jīng)多次移位的則稱為多次移位法

代替法與移位法密碼的破譯對竊聽到的密文進(jìn)行分析時(shí)，窮舉法和統(tǒng)計(jì)法是最基本的破譯方法。窮舉分析法

就是對所有可能的密鑰或明文進(jìn)行逐一試探，直至試探到“正確”的為止。此方法需要事先知道密碼體制或加密算法（但不知道密鑰或加密具體辦法）。破譯時(shí)需將猜測到的明文和選定的密鑰輸入給算法，產(chǎn)生密文，再將該密文與竊聽來的密文比較。如果相同，則認(rèn)為該密鑰就是所要求的，否則繼續(xù)試探，直至破譯。以英文字母為例，當(dāng)已知對方在采用代替法加密時(shí)，如果使用窮舉字母表來破譯，那么對于最簡單的一種使用單字母表－單字母－單元代替法加密的密碼，字母表的可能情況有26！種，可見，單純地使用窮舉法，在實(shí)際應(yīng)用中幾乎是行不通的，只能與其它方法結(jié)合使用。統(tǒng)計(jì)法是根據(jù)統(tǒng)計(jì)資料進(jìn)行猜測的。在一段足夠長且非特別專門化的文章中，字母的使用頻率是比較穩(wěn)定的。在某些技術(shù)性或?qū)ｉT化文章中的字母使用頻率可能有微小變化。

在上述兩種加密方法中字母表中的字母是一一對應(yīng)的，因此，在截獲的密文中各字母出現(xiàn)的概率提供了重要的密鑰信息。根據(jù)權(quán)威資料報(bào)道，可以將26個(gè)英文字母按其出現(xiàn)的頻率大小較合理地分為五組：

t,a,o,i,n,s,h,r;

e;

d,l;

c,u,m,w,f,g,y,p,b;

v,k,j,x,q,z;不僅單個(gè)字母以相當(dāng)穩(wěn)定的頻率出現(xiàn)，相鄰字母對和三字母對同樣如此。按頻率大小將雙字母排列如下：th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,er,it,ar,te,se,hi,of使用最多的三字母按頻率大小排列如下：

The,ing,and,her,ere,ent,tha,nth,was,eth,for,dth統(tǒng)計(jì)的章節(jié)越長，統(tǒng)計(jì)結(jié)果就越可靠。對于只有幾個(gè)單詞的密文，統(tǒng)計(jì)是無意義的。下面介紹一下統(tǒng)計(jì)觀察的三個(gè)結(jié)果：a)單詞the在這些統(tǒng)計(jì)中有重要的作用；b)以e，s，d，t為結(jié)尾的英語單詞超過了一半；c)以t，a，s，w為起始字母的英語單詞約為一半。對于a)，如果將the從明文中刪除，那么t的頻率將要降到第二組中其他字母之后，而h將降到第三組中，并且th和he就不再是最眾多的字母了。以上對英語統(tǒng)計(jì)的討論是在僅涉及26個(gè)字母的假設(shè)條件下進(jìn)行的。實(shí)際上消息的構(gòu)成還包括間隔、標(biāo)點(diǎn)、數(shù)字等字符?？傊?，破譯密碼并不是件很容易的事。

2.希爾密碼代替密碼與移位密碼的一個(gè)致命弱點(diǎn)是明文字符和密文字符有相同的使用頻率,破譯者可從統(tǒng)計(jì)出來的字符頻率中找到規(guī)律，進(jìn)而找出破譯的突破口。要克服這一缺陷，提高保密程度就必須改變字符間的一一對應(yīng)。1929年，希爾利用線性代數(shù)中的矩陣運(yùn)算，打破了字符間的對應(yīng)關(guān)系，設(shè)計(jì)了一種被稱為希爾密碼的代數(shù)密碼。為了便于計(jì)算，希爾首先將字符變換成數(shù)，例如，對英文字母，我們可以作如下變換：

ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789101112131415161718192021222324250將密文分成n個(gè)一組，用對應(yīng)的數(shù)字代替，就變成了一個(gè)個(gè)n維向量。如果取定一個(gè)n階的非奇異矩陣A（此矩陣為主要密鑰），用A去乘每一向量，即可起到加密的效果，解密也不麻煩，將密文也分成n個(gè)一組，同樣變換成n維向量，只需用去乘這些向量，即可將他們變回原先的明文。定理1,若使得(mod26)，則必有=1，其中為與26的最大公因子。證任取，令，于是，故，由的任意性可知必有

(mod26)

即

上式說明必有，不然它將整除1，而這是不可能的。在具體實(shí)施時(shí)，我們很快會(huì)發(fā)現(xiàn)一些困難：(1)

為了使數(shù)字與字符間可以互換，必須使用取自0—25之間的整數(shù)(2)由線性代數(shù)知識(shí)，，其中為A的伴隨矩陣。由于使用了除法，在求A的逆矩陣時(shí)可能會(huì)出現(xiàn)分?jǐn)?shù)。不解決這些困難，上述想法仍然無法實(shí)現(xiàn)。解決的辦法是引進(jìn)同余運(yùn)算，并用乘法來代替除法，（如同線性代數(shù)中用逆矩陣代替矩陣除法一樣）。此外，我們還不難證明這樣的還是由唯一確定的。事實(shí)上設(shè)有和

則故必有（也因?yàn)椋?，即由定?，0—26中除13以外的奇數(shù)均可取作這里的，下表為經(jīng)計(jì)算求得的逆元素

1357911151719212325

1921153197231151725例1

取a=3用希爾密碼體系加密語句THANKYOU步1

將THANKYOU轉(zhuǎn)換成（20，8，1，14，11，25，15，21）步2

每一分量乘以3并關(guān)于26取余得（8，24，3，16，7，23，19，11）密文為HXCPGWSK現(xiàn)在我們已不難將方法推廣到n為一般整數(shù)的情況了,只需在乘法運(yùn)算中結(jié)合應(yīng)用取余，求逆矩陣時(shí)用逆元素相乘來代替除法即可。

例2

取A=則(具體求法見后),用A加密THANKYOU,再用對密文解密

用矩陣A左乘各向量加密（關(guān)于26取余）得

得到密文JXCPIWEK解:(希爾密碼加密)用相應(yīng)數(shù)字代替字符，劃分為兩個(gè)元素一組并表示為向量：（希爾密碼解密）用A-1左乘求得的向量，即可還原為原來的向量。(自行驗(yàn)證)希爾密碼是以矩陣法為基礎(chǔ)的，明文與密文的對應(yīng)由n階矩陣A確定。矩陣A的階數(shù)是事先約定的，與明文分組時(shí)每組字母的字母數(shù)量相同，如果明文所含字?jǐn)?shù)與n不匹配，則最后幾個(gè)分量可任意補(bǔ)足。

A-1的求法方法1利用公式，例如，若取，則,,(mod26)，即方法2利用高斯消去法。將矩陣(A,E)中的矩陣A消為E，則原先的E即被消成了A-1，

如

，

(用9乘第二行并取同余)

，

第一行減去第二行的2倍并取同余，得

，

左端矩陣已化為單位陣，故右端矩陣即為

A-1希爾密碼系統(tǒng)的解密依賴于以下幾把鑰匙（key）：Key1矩陣A的階數(shù)n，即明文是按幾個(gè)字母來劃分的。Key2變換矩陣A，只有知道了A才可能推算出Key3明文和密文由字母表轉(zhuǎn)換成n維向量所對應(yīng)的非負(fù)整數(shù)表（上面，為方便起見，我們采用了字母的自然順序）。希爾密碼體系為破譯者設(shè)置了多道關(guān)口，加大了破譯難度。破譯和解密是兩個(gè)不同的概念，雖然兩者同樣是希望對密文加以處理而得到明文的內(nèi)容，但是他們有一個(gè)最大的不同——破譯密碼時(shí)，解密必需用到的鑰匙未能取得，破譯密碼的一方需要依據(jù)密文的長度，文字的本身特征，以及行文習(xí)慣等等各方面的信息進(jìn)行破譯。破譯密碼雖然需要技術(shù)，但更加重要的是“猜測”的藝術(shù)?！安聹y”的成功與否直接決定著破譯的結(jié)果。破譯希爾密碼的關(guān)鍵是猜測文字被轉(zhuǎn)換成成幾維向量所、對應(yīng)的字母表是怎樣的，更為重要的是要設(shè)法獲取加密矩陣A。（希爾密碼的破譯）由線性代數(shù)的知識(shí)可以知道，矩陣完全由一組基的變換決定，對于n階矩陣A，只要猜出密文中n個(gè)線性無關(guān)的向量

(i=1,2,…,n)對應(yīng)的明文(i=1,2,…,n)是什么，即可確定A，并將密碼破譯。

在實(shí)際計(jì)算中，可以利用以下方法：令則，取矩陣[Q|P],經(jīng)過一系列初等行變換，將由密文決定的n維矩陣Q化為n階單位陣I的時(shí)候，由明文決定的矩陣P自動(dòng)化為(A-1)T，即：例5

有密文如下:goqbxcbuglosnfal;根據(jù)英文的行文習(xí)慣以及獲取密碼的途徑和背景，猜測是兩個(gè)字母為一組的希爾密碼，前四個(gè)明文字母是dear，試破譯這段秘文。解：前兩組明文字母de和ar對應(yīng)的二維向量是：按同一對應(yīng)整數(shù)表，密文中對應(yīng)這兩組的二維向量是：，

，

由此可得，對應(yīng)上例則有

,

利用這一逆矩陣，可對截獲密文進(jìn)行解密，破譯出的電文是DearMacGodforbid.

這只是對最簡單情況進(jìn)行的舉例，如果加密矩陣的階數(shù)大于2，需要的密文應(yīng)該有較長長度，所需的計(jì)算量也是很大的。破譯的關(guān)鍵是猜中n及n個(gè)獨(dú)立的n維向量，其后求解加密矩陣的計(jì)算量僅為O(n2)。希爾密碼體制中有兩個(gè)要素非常重要：第一是字母與n維向量進(jìn)行轉(zhuǎn)換所依據(jù)的非負(fù)整數(shù)表，本節(jié)中所舉的是最自然的情況；當(dāng)然如果依據(jù)其它的整數(shù)表也是完全可以進(jìn)行的，其情況將會(huì)更復(fù)雜一些，破譯的難度就會(huì)增大。第二個(gè)要素是加密矩陣，如何定義、求解這個(gè)矩陣對于密碼的加密和破譯更加關(guān)鍵。唯一的要求是加密時(shí)應(yīng)選擇行列式值與26無公因子的矩陣。RSA公開密鑰體制

傳統(tǒng)的密碼通訊只能在事先約定的雙方間進(jìn)行，雙方必須掌握相同的密鑰，而密鑰的傳送必須使用另外的“安全信道”。這樣如果要使n個(gè)用戶都能夠秘密的交換信息，則每個(gè)用戶將需要用個(gè)密鑰，這種巨大的密鑰量給密鑰的分配與管理帶來了極大的困難；此外在有些情況下，事先約定密鑰還是不可能的。公開密鑰體制的提出就是為了從根本上解決上述問題。其基本思想是：把密鑰劃分為公開密鑰和秘密密鑰兩部分,兩者互為逆變換，但幾乎不可能從公開密鑰推出秘密密鑰.每個(gè)使用者均有自己的公開及秘密密鑰。

雖然只要能解密的密文，從理論上講都是可破譯的，但如果破譯所需要的工作量過大，要求花費(fèi)的時(shí)間過長，以致超過了保密期限，則該密碼系統(tǒng)應(yīng)當(dāng)被認(rèn)為是安全可靠的。

定義1設(shè)n為一正整數(shù)，將小于n且與n互素的正整數(shù)個(gè)數(shù)記為Φ(n)，稱之為歐拉（EulerL.）Φ函數(shù)。不難證明：若p，q為兩個(gè)相異素?cái)?shù)，n=p×q，則

φ(n)=(p-1)(q-1)令p,q為隨機(jī)選取的兩個(gè)大素?cái)?shù)（大約為十進(jìn)制100位或更大）,n=pq,n是公開的，而p,q則是保密的。僅知道歐拉函數(shù)φ(n)=(p-1)(q-1)，但如果不知道因式分解就不能用這個(gè)公式計(jì)算。隨機(jī)選取一個(gè)數(shù)e，e為小于φ(n)且與它互素的正整數(shù)。利用輾轉(zhuǎn)相除法，可以找到整數(shù)d和r，使

ed+rφ(n)=1即ed≡1(modφ(n))

數(shù)n,e和d分別稱為模、加密密鑰和解密密鑰。數(shù)n和e組成公開密鑰的加密密鑰，而其余的項(xiàng)p,q,φ(n)和d組成了秘密陷門。很顯然，陷門信息包含了四個(gè)相關(guān)的項(xiàng)。若知道φ(n),則由

pq=np+q=n-φ(n)+1可知p,q是二次方程x2+(φ(n)-n-1)x+n=0的根，可以算出p和q，從而將n因式分解。所以RSA體制的安全性與因式分解密切相關(guān)，若能知道n的因子分解，該密碼就能被破譯。因此，要選用足夠大的n，使得在當(dāng)今的條件下要分解它足夠困難。為加密消息m，首先將它分為小于n（對二進(jìn)制數(shù)據(jù)，選取小于n的2的最大次方冪）的數(shù)據(jù)塊，也就是說，如果p和q都為十進(jìn)制100位的素?cái)?shù)，則n剛好在200位以內(nèi)，因此每個(gè)消息塊的長度也應(yīng)在兩百位以內(nèi)。加密消息c由類似劃分的同樣長度的消息塊組成。加密公式為

(modn)

要解密消息，取每一個(gè)加密塊c(I)并計(jì)算(modn)由公式ed≡1(modφ(n))我們有ed=1-rφ(n),因此≡≡≡(modn)其中r為某一整數(shù)。這里利用了歐拉定理:φ(n)≡1(modn)根據(jù)以上公式從密文恢復(fù)出了明文。那么RSA公開密鑰體制是怎樣使用的

呢？請看下例！設(shè)使用者取定p=47，q=59,則N=pq=2773,φ(n)=(p-1)(q-1)=2668.取素?cái)?shù)e=17，顯然它與φ(n)互素，加密者知道p、q的值，易得出d=157。將(e,n)=(17,2773)作為公開密鑰發(fā)布；嚴(yán)守機(jī)密的秘密密鑰是(157,2773).現(xiàn)在有人要向此使用者傳送一段（英文）明文信息，例如：

Ilovezhejianguniversity將這段文字轉(zhuǎn)換為數(shù)字，不計(jì)大小寫，每兩個(gè)詞之間為一個(gè)空格符號，空格符對應(yīng)數(shù)字00，每個(gè)英文字母對應(yīng)表征其在字母表中位置的兩位數(shù)字，例如：A對應(yīng)01，B對應(yīng)02，…，Z對應(yīng)26，等等。再從頭向后，將每四位數(shù)字劃歸一組，不足時(shí)補(bǔ)充空格。如此得到以下十三組數(shù)字：0900121522050026080510090114070021140922051819092025每一組數(shù)字視為一個(gè)數(shù)，用公開密鑰(17,2773)對其加以變換。以第一個(gè)數(shù)為例，由于n=2773,比這里任何可能出現(xiàn)的四位數(shù)字均大，故只需計(jì)算每一數(shù)字在模2773下的17次冪。我們有

?900≡1510(mod2773).在以上整個(gè)過程中，為減少計(jì)算量應(yīng)隨時(shí)注意取模。這樣900對應(yīng)的密碼是1510。以這一方法得到的密文電碼是：1510041715241445054226921684076116442488178718771672解密過程與此類似，只不過使用密鑰(157,2773)，直接計(jì)算很煩瑣，但用計(jì)算機(jī)處理這一問題卻非常簡單。本例中將四位數(shù)字劃分為一組，是為了使每組的數(shù)字不超過n=2773.當(dāng)使用一個(gè)很大的n時(shí)，每次完全可以處理一個(gè)位數(shù)更多的數(shù)碼組。只要相應(yīng)的整數(shù)小于n即可?！?.3馬氏鏈模型隨著人類的進(jìn)化，為了揭示生命的奧秘，人們越來越注重遺傳學(xué)的研究，特別是遺傳特征的逐代傳播，已引起人們廣泛的注意。無論是人，還是動(dòng)、植物都會(huì)將本身的特征遺傳給下一代，這主要是因?yàn)楹蟠^承了雙親的基因，形成自己的基因?qū)?，由基因又確定了后代所表現(xiàn)的特征。本節(jié)將利用數(shù)學(xué)的馬氏鏈方法來建立相應(yīng)的遺傳模型等，并討論幾個(gè)簡單而又有趣的實(shí)例。馬氏鏈（馬爾柯夫鏈）研究的是一類重要的隨機(jī)過程，研究對象的狀態(tài)s(t)是不確定的，它可能取K種狀態(tài)si(i=1,…,k)之一，有時(shí)甚至可取無窮多種狀態(tài)。在建模時(shí)，時(shí)間變量也被離散化，我們希望通過建立兩個(gè)相鄰時(shí)刻研究對象取各種狀態(tài)的概率之間的聯(lián)系來研究其變化規(guī)律，故馬氏鏈研究的也是一類狀態(tài)轉(zhuǎn)移問題。例4.6設(shè)某商店經(jīng)營情況可能有三種狀態(tài)：好（S1：利潤豐厚）、一般（S2）和不好（S3：虧損）。根據(jù)統(tǒng)計(jì)資料，上月狀態(tài)為Si，下月狀態(tài)為Sj的概率為pij（i=1,2,3;j=1,2,3），0≤pij≤1例4.6中的關(guān)系既可用一轉(zhuǎn)移矩陣表示例4.7研究某一草原生態(tài)系統(tǒng)中物質(zhì)磷的循環(huán)，考慮土壤中含磷、牧草含磷、牛羊體內(nèi)含磷和流失于系統(tǒng)之外四種狀態(tài)，分別以S1，S2，S3和S4表示這四種狀態(tài)。以年為時(shí)間參數(shù)，一年內(nèi)如果土壤中的磷以0.4的概率被牧草生長吸收，水土流失于系統(tǒng)外的概率為0.2；牧草中的含磷以0.6的概率被牛羊吃掉而轉(zhuǎn)換到牛羊體內(nèi)，0.1的概率隨牧草枯死腐敗歸還土壤；牛羊體中的磷以0.7的概率因糞便排泄而還歸土壤，又以自身0.1的比率因屠宰后投放市場而轉(zhuǎn)移到系統(tǒng)外。我們可以建立一個(gè)馬爾柯夫鏈來研究此生態(tài)系統(tǒng)問題，其轉(zhuǎn)移概率列表于下：1000S4流失系統(tǒng)外0.10.200.7S3羊體含磷00.60.30.1S2牧草含磷0.200.40.4S1土壤含磷i時(shí)段狀態(tài)S4S3S2S1i+1時(shí)段狀態(tài)狀態(tài)轉(zhuǎn)移概率相應(yīng)的轉(zhuǎn)移矩陣為：且Sj+1=SjM馬氏鏈模型的性質(zhì)完全由其轉(zhuǎn)移矩陣決定，故研究馬氏鏈的數(shù)學(xué)工具是線性代數(shù)中有關(guān)矩陣的理論。首先，任一轉(zhuǎn)移矩陣的行向量均為概率向量，即有（1）（I,j=1,…,n）（2）（i=1,…,n）這樣的矩陣被稱為隨機(jī)矩陣。常染色體遺傳模型

下面給出雙親體基因型的所有可能的結(jié)合，以及其后代形成每種基因型的概率，如表所示。

在常染色體遺傳中，后代從每個(gè)親體的基因?qū)χ懈骼^承一個(gè)基因，形成自己的基因時(shí)，基因?qū)σ卜Q為基因型。如果我們所考慮的遺傳特征是由兩個(gè)基因A和a控制的，（A、a為表示兩類基因的符號）那么就有三種基因?qū)?，記為AA，Aa，aa。

1000aa010Aa0001AA后代基因型aa－aaAa－aaAa－AaAA－aaAA－AaAA－AA父體——母體的基因型雙親隨機(jī)結(jié)合的較一般模型相對比較復(fù)雜，這些我們僅研究一個(gè)較簡單的特例。例4.8農(nóng)場的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場計(jì)劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過若干年后，這種植物的任一代的三種基因型分布情況如何？（a）假設(shè)：令n=0,1,2,…。（i）設(shè)an,bn和cn分別表示第n代植物中，基因型為AA,Aa和aa的植物占植物總數(shù)的百分比。令x(n)為第n代植物的基因型分布：當(dāng)n=0時(shí)表示植物基因型的初始分布（即培育開始時(shí)的分布）例4.8農(nóng)場的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場計(jì)劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過若干年后，這種植物的任一代的三種基因型分布情況如何？（b）建模根據(jù)假設(shè)(ii)，先考慮第n代中的AA型。由于第n－1代的AA型與AA型結(jié)合。后代全部是AA型；第n－1代的Aa型與AA型結(jié)合，后代是AA型的可能性為1/2，而第n－1代的aa型與AA型結(jié)合，后代不可能是AA型。因此當(dāng)n=1,2…時(shí)即類似可推出cn=0

顯然有（ii）第n代的分布與第n－1代的分布之間的關(guān)系是通過表5.2確定的。(4.2)(4.3)(4.4)將（4.2）、（4.3）、（4.4）式相加，得根據(jù)假設(shè)(I)，可遞推得出：對于(4.2)式.(4.3)式和(4.4)式，我們采用矩陣形式簡記為其中（注：這里M為轉(zhuǎn)移矩陣的位置）

(4.5)由（4.5）式遞推，得(4.6)（4.6）式給出第n代基因型的分布與初始分布的關(guān)系。為了計(jì)算出Mn，我們將M對角化，即求出可逆矩陣P和對角庫D，使M=PDP-1因而有Mn=PDnP-1,n=1,2,…其中這里，，是矩陣M的三個(gè)特征值。對于(4.5)式中的M，易求得它的特征值和特征向量：=1，=1/2，=0因此所以

通過計(jì)算，P-1=P，因此有即所以有當(dāng)時(shí)，，所以從（4.7）式得到即在極限的情況下，培育的植物都是AA型。若在上述問題中，不選用基因AA型的植物與每一植物結(jié)合，而是將具有相同基因型植物相結(jié)合，那么后代具有三種基因型的概率如表所示。11/40aa01/20Aa01/41AA后代基因型aa－aaAa－AaAA－AA父體——母體的基因型并且，其中M的特征值為通過計(jì)算，可以解出與、相對應(yīng)的兩個(gè)線性無關(guān)的特征向量e1和e2，及與相對應(yīng)的特征內(nèi)量e3：因此解得：當(dāng)時(shí)，，所以因此，如果用基因型相同的植物培育后代，在極限情況下，后代僅具有基因AA和aa。例4.9

常染體隱性疾病模型現(xiàn)在世界上已經(jīng)發(fā)現(xiàn)的遺傳病有將近4000種。在一般情況下，遺傳疾病和特殊的種族、部落及群體有關(guān)。例如，遺傳病庫利氏貧血癥的患者以居住在地中海沿岸為多，鐮狀網(wǎng)性貧血癥一般流行在黑人中，家族黑蒙性白癡癥則流行在東歐猶太人中間?；颊呓?jīng)常未到成年就痛苦地死去，而他們的父母則是疾病的病源。假若我們能識(shí)別這些疾病的隱性患者，并且規(guī)定兩個(gè)隱性患者不能結(jié)合（因?yàn)閮蓚€(gè)隱性病患者結(jié)合，他們的后代就可能成為顯性患者），那么未來的兒童，雖然有可能是隱性患者，但絕不會(huì)出現(xiàn)顯性特征，不會(huì)受到疾病的折磨。

現(xiàn)在，我們考慮在控制結(jié)合的情況下，如何確定后代中隱性患者的概率。

（a）假設(shè)（i）常染色體遺傳的正?；蛴洖锳，不正?；蛴洖閍，并以AA，Aa，aa

分別表示正常人，隱性患者，顯性患者的基因型（ii）設(shè)an,bn分別表示第n代中基因型為

AA，Aa的人占總?cè)藬?shù)的百分比，記，n=1,2,…（這里不考慮aa型是因?yàn)檫@些人不可能成年并結(jié)婚）（iii）為使每個(gè)兒童至少有一個(gè)正常的父親或母親，因此隱性患者必須與正常人結(jié)合，其后代的基因型概率由下表給出：1/20Aa1/21AA后代基因型AA－AaAA－AA父母的基因型（b）建模由假設(shè)（iii），從第n－1代到第n代基因型分布的變化取決于方程所以，其中如果初始分布x(0)已知，那么第n代基因型分布為解將M對角化，即求出特征值及其所對應(yīng)的特征向量，得計(jì)算=(4.8)因?yàn)椋援?dāng)時(shí)，，隱性患者逐漸消失。從(4.8)式中可知每代隱性患者的概率是前一代隱性患者概率的1/2。

(4.9)（c）模型討論研究在隨機(jī)結(jié)合的情況下，隱性患者的變化是很有意思的，但隨機(jī)結(jié)合導(dǎo)致了非線性化問題，超出了本章范圍，然而用其它技巧，在隨機(jī)結(jié)合的情況下可以把（4.9）式改寫為(4.10)下面給會(huì)出數(shù)值例子：某地區(qū)有10%的黑人是鐮狀網(wǎng)性盆血癥隱性患者，如果控制結(jié)合，根據(jù)（4.9）式可知下一代（大約27年）的隱性患者將減少到5%；如果隨機(jī)結(jié)合，根據(jù)（4.10）式，可以預(yù)言下一代人中有9.5%是隱性患者，并且可計(jì)算出大約每出生400個(gè)黑人孩子，其中有一個(gè)是顯性患者。（近親繁殖）近親繁殖是指父母雙方有一個(gè)或兩個(gè)共同的祖先，一般追蹤到四代，即至少有相同的曾祖父（母）或外曾祖父（母）。為簡單起見，我們來考察一對表兄妹（或堂兄妹）結(jié)婚的情況，其中□代表男性，○代表女性。設(shè)曾祖父有某基因?qū)1A2，曾祖母有某基因?qū)3A4，容易求得：祖父母取得A1的概率為1/2，故祖父母同有A1基因的概率為1/4；父母同有A1基因的概率為1/16，而子女從父母那里獲得基因?qū)1A1的概率為1/64，而獲得相同基因?qū)ΓǚQ為基因純合子）A1A1，A2A2，A3A3或A4A4之一的概率為1/16,此概率被稱為表兄妹(或堂兄妹)結(jié)婚(表親)的近交系數(shù)。類似可求得半堂親（只有一個(gè)共同祖先）的近交系數(shù)為1/32，從表親（父母為表親）的近交系數(shù)為1/64；非近親結(jié)婚不可能發(fā)生重復(fù)取某祖先的一對基因?qū)χ械哪骋换蜃鳛樽约旱幕驅(qū)Φ那闆r，故近交系數(shù)為0。（群體的近交系數(shù)）設(shè)某群體中存在近親婚配現(xiàn)象，稱各種近交系數(shù)的數(shù)學(xué)期望為該群體的近交系數(shù)。例如，某村鎮(zhèn)共有2000對婚配關(guān)系，其中有59對表親，22對半堂親和28對從表親，則該村鎮(zhèn)的近親系數(shù)為現(xiàn)在，我們來研究近親結(jié)婚會(huì)產(chǎn)生什么結(jié)果。設(shè)某基因?qū)τ葾、a兩種基因組成，出現(xiàn)A的概率為p，出現(xiàn)a的概率為q=1-p。在隨機(jī)交配群體中，其子女為AA、Aa及aa型的概率分別為p2、2pq及q2。對近交系數(shù)為F的群體，根據(jù)條件概率公式，后代出現(xiàn)aa型基因?qū)Φ母怕蕿楸容^存在近親交配的群體與不允許近親交配(F=0)的群體，令若a為某種隱性疾病的基因，易見，在近交群體中，后代產(chǎn)生遺傳病（aa型）的概率增大了，且F越大，后代患遺傳病的概率也越大。同樣，后代出現(xiàn)AA型基因?qū)Φ母怕蕿閜2+Fpq。Aa型不可能是共同祖先同一基因的重復(fù)，故其出現(xiàn)的概率為2pq(1-F)。例如，苯丙酮尿癥是一種隱性基因純合子aa型疾病（a為隱性疾病基因），隱性基因出現(xiàn)的頻率，求表兄妹結(jié)婚及非近親結(jié)婚的子女中患有苯丙酮尿癥的概率。由前，表兄妹結(jié)婚的近交系數(shù)為1/16,故其子女發(fā)生該疾病的概率為而對禁止近親結(jié)婚的群體，子女發(fā)生該疾病的概率為q2=10-4。表兄妹（或堂兄妹）結(jié)婚使子女發(fā)生該疾病的概率增大了大約7.19倍，由此可見，為了提高全民族的身體素質(zhì)，近親結(jié)婚是應(yīng)當(dāng)禁止的。例4.10

X—鏈遺傳模型的一個(gè)實(shí)例X—鏈遺傳是指另一種遺傳方式：雄性具有一個(gè)基因A或a，雌性具有兩個(gè)基因AA，或Aa，或aa。其遺傳規(guī)律是雄性后代以相等概率得到母體兩個(gè)基因中的一個(gè)，雌性后代從父體中得到一個(gè)基因，并從母體的兩個(gè)基因中等可能地得到一個(gè)。下面，研究與X—鏈遺傳有關(guān)的近親繁殖過程。（a）假設(shè)（i）從一對雌雄結(jié)合開始,在它們的后代中,任選雌雄各一個(gè)成配偶,然后在它們產(chǎn)生的后代中任選兩個(gè)結(jié)成配偶,如此繼續(xù)下去,(在家畜、家禽飼養(yǎng)中常見這種現(xiàn)象)（ii）父體與母體的基因型組成同胞對，同胞對的形式有

(A,AA),(A,Aa),(A,aa),(a,AA),(a,Aa),(a,aa)6種。初始一對雌雄的同胞對，是這六種類型中的任一種，其后代的基因型如下表所示。（iii）在每一代中，配偶的同胞對也是六種類型之一，并有確定的概率。為計(jì)算這些概率,設(shè)an,bn,cn,dn,en,fn

分別是第n代中配偶的同胞對為(A,AA)，(A,Aa)，(A,aa),(a,AA),(a,Aa),(a,aa)型的概率，n=0,1,…。令（iv）如果第n－1代配偶的同胞對是（A,Aa）型，那么它們的雄性后代將等可能地得到基因A和a，它們的雌性后代的基因型將等可能地是AA或Aa。又由于第n

代雌雄結(jié)合是隨機(jī)的，那么第n代配偶的同胞對將等可能地為四種類型(A,AA),(A,Aa),(a,AA),(a,Aa)之一，對于其它類型的同胞對，我們可以進(jìn)行同樣分析，因此有11/20000aa01/2111/20Aa00001/21AA11/2011/20a01/2101/21AA后代基因型(a,aa)(a,Aa)(a,AA)(A,aa)(A,Aa)(A,AA)父體——母體的基因型(4.11)其中從（4.11）式中易得經(jīng)過計(jì)算，矩陣M的特征值和特征向量為

，，，，，,M對角化，則有(4.12)其中：當(dāng)時(shí)因此，當(dāng)時(shí)，（4.12）式中即因此，在極限情況下所有同胞對或者是（A,AA）型，或者是（a,aa）型。如果初始的父母體同胞對是（A,Aa）型，即b0=1，而a0=c0=d0=e0=f0=0，于是，當(dāng)時(shí)即同胞對是(A,AA)型的概率是2/3，是(a,aa)型的概率為1/3。（正則鏈與吸收鏈）根據(jù)轉(zhuǎn)移矩陣的不同結(jié)構(gòu)，馬氏鏈可以分為多個(gè)不同的類型，這里，我們只簡單介紹其中常見而又較為重要的兩類：正則鏈與吸收鏈。定義2對于馬氏鏈，若存在一正整數(shù)K，使其轉(zhuǎn)移矩陣的K次冪MK>0（每一分量均大于0），則稱此馬爾鏈為一正則（regular）鏈。定理2若A為正則鏈的轉(zhuǎn)移矩陣，則必有：（1）當(dāng)時(shí)，，其中W為一分量均大于零的隨機(jī)矩陣。（2）W的所有行向量均相同。定理3記定理2中的隨機(jī)矩陣W的行向量為V=(v1,…,vn),則：（1）對任意隨機(jī)向量x，有（2）V是A的不動(dòng)點(diǎn)向量,即VA=V,A的不動(dòng)點(diǎn)向量是唯一的。定義3狀態(tài)Si稱為馬氏鏈的吸收狀態(tài)，若轉(zhuǎn)移矩陣的第i行滿足：Pii=1，Pij=0（j≠i）定義4馬氏鏈被稱為吸收鏈，若其滿足以下兩個(gè)條件：（1）至少存在一個(gè)吸收狀態(tài)。（2）從任一狀態(tài)出發(fā),經(jīng)有限步轉(zhuǎn)移總可到達(dá)某一吸收狀態(tài)根據(jù)定義3，例4.7中狀態(tài)S4即為一吸收鏈具有r個(gè)吸收狀態(tài)，n－r個(gè)非吸收狀態(tài)的吸收鏈，它的n×n轉(zhuǎn)移矩陣的標(biāo)準(zhǔn)形式為（注：非標(biāo)準(zhǔn)形式可經(jīng)對狀態(tài)重新編號）其中Ir為r階單位陣，O為r×s零陣，R為s×r矩陣，S為s×s矩陣。令上式中的子陣Sn表達(dá)了以任何非吸收狀態(tài)作為初始狀態(tài)，經(jīng)過n步轉(zhuǎn)移后，處于s個(gè)非吸收狀態(tài)的概率。在吸收鏈中，令F=(I－S)-1，稱F為基矩陣。定理4吸收鏈的基矩陣F中的每個(gè)元素，表示從一個(gè)非吸收狀態(tài)出發(fā)，過程到達(dá)每個(gè)非吸收狀態(tài)的平均轉(zhuǎn)移次數(shù)。定理5設(shè)N=FC，F(xiàn)為吸收鏈的基矩陣，C=(1,1,…,1)T，則N

的每個(gè)元素表示從非吸收狀態(tài)出發(fā)，到達(dá)某個(gè)吸收狀態(tài)被吸收之前的平均轉(zhuǎn)移次數(shù)。定理6設(shè)B=FR=（bij），其中F為吸收鏈的基矩陣，R為T中的子陣，則bij表示從非吸收狀態(tài)i出發(fā)，被吸收狀態(tài)j

吸收的概率。例4.12（競賽問題）甲乙兩隊(duì)進(jìn)行一場搶答競賽，競賽規(guī)則規(guī)定：開始時(shí)每隊(duì)各記2分，搶答題開始后，如甲取勝則甲加1分而乙減1分，反之則乙加1分甲減1分,(每題必需決出勝負(fù))。規(guī)則還規(guī)定，當(dāng)其中一方的得分達(dá)到4分時(shí)，競賽結(jié)束?，F(xiàn)希望知道：（1）甲隊(duì)獲勝的概率有多大？（2）競賽從開始到結(jié)束，平均轉(zhuǎn)移的次數(shù)為多少？（3）甲獲得1、2、3分的平均次數(shù)是多少？設(shè)甲勝一題的概率為p，（0<p<1），p與兩隊(duì)的實(shí)力有關(guān)。甲隊(duì)得分有5種可能，即0，1，2，3，4。我們分別記為狀態(tài)S0，S1，S2，S3，S4，其中S0和S4是吸收狀態(tài)，a1，a2和a3是非吸收狀態(tài)。過程以S2作為初始狀態(tài)。根據(jù)甲隊(duì)贏得1分的概率為p，建立轉(zhuǎn)移矩陣：S

0S

1

S

2S

3S

4

將上式改記為標(biāo)準(zhǔn)形式T：其中計(jì)算F：令q=1-p，則因?yàn)閍2是初始狀態(tài)，根據(jù)定理4，甲隊(duì)獲分為1，2，3分的平均次數(shù)為，，。又

==根據(jù)定理5，以a2為初始狀態(tài)，甲隊(duì)最終獲勝的平均轉(zhuǎn)移欠數(shù)為。又因?yàn)椋鶕?jù)定理6，甲隊(duì)最后獲勝的概率。§4.4差分方程建模

一、差分方程簡介以t表示時(shí)間，規(guī)定t只取非負(fù)整數(shù)。t=0表示第一周期初，t=1表示第二周期初等。記yt為變量y在時(shí)刻t時(shí)的取值，則稱為yt的一階差分，稱為的二階差分。類似地，可以定義yt的n階差分。由t、yt及yt的差分給出的方程稱為yt差分方程，其中含的最高階差分的階數(shù)稱為該差分方程的階。差分方程也可以寫成不顯含差分的形式。例如，二階差分方程也可改寫成滿足一差分方程的序列yt稱為此差分方程的解。類似于微分方程情況，若解中含有的獨(dú)立常數(shù)的個(gè)數(shù)等于差分方程的階數(shù)時(shí)，稱此解為該差分方程的通解。若解中不含任意常數(shù)，則稱此解為滿足某些初值條件的特解，例如，考察兩階差分方程易見與均是它的特解，而則為它的通解，其中c1，c2為兩個(gè)任意常數(shù)。類似于微分方程，稱差分方程

為n階線性差分方程，當(dāng)≠0時(shí)稱其為n階非齊次線性差分方程，而則被稱為方程對應(yīng)的齊次線性差分方程。若所有的ai(t)均為與t無關(guān)的常數(shù)，則稱其為常系數(shù)差分方程，即n階常系數(shù)線性差分方程可分成（4.15）

的形式，其對應(yīng)的齊次方程為（4.16）

容易證明，若序列與均為方程（4.16）的解，則也是方程（4.16）的解，其中c1、c2為任意常數(shù)，這說明，齊次方程的解構(gòu)成一個(gè)線性空間（解空間）。

此規(guī)律對于（4.15）也成立。方程（4.15）可用如下的代數(shù)方法求其通解：（步一）先求解對應(yīng)的特征方程

（4.17）

（步二）根據(jù)特征根的不同情況，求齊次方程(4.16)的通解

情況1若特征方程（4.17）有n個(gè)互不相同的實(shí)根,…,，則齊次方程（4.16）的通解為(C1,…,Cn為任意常數(shù))，情況2若λ

是特征方程（4.17）的k重根，通解中對應(yīng)于λ的項(xiàng)為為任意常數(shù)，i=1,…,k。情況3若特征方程（4.17）有單重復(fù)根通解中對應(yīng)它們的項(xiàng)為為λ的模，為λ的幅角。

情況4若為特征方程（4.17）的k重復(fù)根，則通解對應(yīng)于它們的項(xiàng)為為任意常數(shù)，i=1,…,2k。

.若yt為方程(4.16)的通解,則非齊次方程(4.15)的通解為（步三）求非齊次方程(4.15)的一個(gè)特解

求非齊次方程（4.15）的特解一般要用到常數(shù)變易法，計(jì)算較繁。對特殊形式的b(t)也可使用待定系數(shù)法。例4.13求解兩階差分方程解對應(yīng)齊次方程的特征方程為，其特征根為，對應(yīng)齊次方程的通解為

原方程有形如的特解。代入原方程求得，，故原方程的通解為在應(yīng)用差分方程研究問題時(shí)，一般不需要求出方程的通解，在給定初值后，通常可用計(jì)算機(jī)迭代求解，但我們常常需要討論解的穩(wěn)定性。對差分方程(4.15),若不論其對應(yīng)齊次方程的通解中任意常數(shù)C1,…,Cn如何取值,在時(shí)總有,則稱方程(7.14)的解是穩(wěn)定的,否則稱其解為不穩(wěn)定的.根據(jù)通解的結(jié)構(gòu)不難看出,非齊次方程(4.15)穩(wěn)定的充要條件為其所有特征根的模均小于1。例4.14（市場經(jīng)濟(jì)的蛛網(wǎng)模型）在自由競爭的市場經(jīng)濟(jì)中，商品的價(jià)格是由市場上該商品的供應(yīng)量決定的，供應(yīng)量越大，價(jià)格就越低。另一方面，生產(chǎn)者提供的商品數(shù)量又是由該商品的價(jià)格決定的，價(jià)格上升將刺激生產(chǎn)者的生產(chǎn)積極性，導(dǎo)致商品生產(chǎn)量的增加。反之，價(jià)格降低會(huì)影響生產(chǎn)者的積極性，導(dǎo)致商品生產(chǎn)量的下降。在市場經(jīng)濟(jì)中，對每一商品事實(shí)上存在著兩個(gè)不同的函數(shù)：（1）供應(yīng)函數(shù)x=f(P)，它是價(jià)格P的單增函數(shù)，其曲線稱為供應(yīng)曲線。（2）需求函數(shù)x=g(P)，它是價(jià)格P的單降函數(shù)，其曲線稱為需求曲線，供應(yīng)曲線與需求曲線的形狀如圖所示。記t時(shí)段初市場上的供應(yīng)量(即上一時(shí)段的生產(chǎn)量)為xt，市場上該商品的價(jià)格為Pt。商品成交的價(jià)格是由需求曲線決定的，即隨著,Mt將趨于平衡點(diǎn)M*,即商品量將趨于平衡量x*,價(jià)格將趨于平衡價(jià)格P*。圖中的箭線反映了在市場經(jīng)濟(jì)下該商品的供應(yīng)量與價(jià)格的發(fā)展趨勢。xoPP0P2P*P1xx1x2x0x*需求曲線供應(yīng)曲線M0M2M1M*①PoM3M2M1②但是，如果供應(yīng)曲線和需求曲線呈圖①中的形狀，則平衡點(diǎn)M*是不穩(wěn)定的，Mt將越來越遠(yuǎn)離平衡點(diǎn)。圖①和圖②的區(qū)別在哪里，如何判定平衡點(diǎn)的穩(wěn)定性呢？但是，如果供應(yīng)曲線和需求曲線呈圖②中的形狀，則平衡點(diǎn)M*是不穩(wěn)定的，Mt將越來越遠(yuǎn)離平衡點(diǎn)。即使初始時(shí)刻的供應(yīng)量和價(jià)格對應(yīng)于平衡點(diǎn)，一點(diǎn)微小的波動(dòng)也會(huì)導(dǎo)致市場供求出現(xiàn)越來越大的混亂。上述用圖示法分析市場經(jīng)濟(jì)穩(wěn)定性的討論在經(jīng)濟(jì)學(xué)中被稱為市場經(jīng)濟(jì)的蛛網(wǎng)模型。不難看出，在圖①中平衡點(diǎn)M*處供應(yīng)曲線的切線斜率大于需求曲線切線斜率的絕對值，而在圖②中情況恰好相反。現(xiàn)在利用差分方程方法來研究蛛網(wǎng)模型，以驗(yàn)證上述猜測是否正確。我們知道，平衡點(diǎn)M*是否穩(wěn)定取決于在M*附近供、需曲線的局部性態(tài)。為此，用M*處供、需曲線的線性近似來代替它們，并討論此線性近似模型中M*的穩(wěn)定性。設(shè)供應(yīng)曲線與需求曲線的線性近似分別為

和式中，a、b分別為供應(yīng)曲線在M*處的切線斜率與需求曲線在M*處切線斜率的絕對值。

根據(jù)市場經(jīng)濟(jì)的規(guī)律，當(dāng)供應(yīng)量為xt時(shí)，現(xiàn)時(shí)段的價(jià)格，又對價(jià)格，由供應(yīng)曲線解得下一時(shí)段的商品量

由此導(dǎo)出一階差分方程：（4.18）此差分方程的解在(b/a)<1時(shí)是穩(wěn)定的，從而證實(shí)了我們的猜測。注意到a和b的實(shí)際含義，上述結(jié)果在經(jīng)濟(jì)學(xué)上可作如下解釋：當(dāng)a>b時(shí)，顧客需求對價(jià)格的敏感度較?。ㄐ∮谏a(chǎn)者的敏感程度），商品供應(yīng)量和價(jià)格會(huì)自行調(diào)節(jié)而逐步趨于穩(wěn)定；反之，若a<b（商品緊缺易引起顧客搶購），該商品供售市場易造成混亂.如果生產(chǎn)者對市場經(jīng)濟(jì)的蛛網(wǎng)模型有所了解，為了減少因價(jià)格波動(dòng)而造成的經(jīng)濟(jì)損失，他應(yīng)當(dāng)提高自己的經(jīng)營水平，不應(yīng)當(dāng)僅根據(jù)上一周期的價(jià)格來決定現(xiàn)階段的生產(chǎn)量。例如可以根據(jù)本時(shí)段與前一時(shí)段價(jià)格的平均值來確定生產(chǎn)量。此時(shí)，若t時(shí)段的商品量為xt

時(shí)，仍有（4.21）將（4.19）式、（4.21）式代入（4.20）式，整理得（4.19）但t+1時(shí)段的商品量則不再為而被修正為（4.20）由（4.19）式得（4.22）（4.22）式是一個(gè)常系數(shù)二階線性差分方程，特征方程為其特征根為記。若，則此時(shí)差分方程（4.22）是不穩(wěn)定的。

，若，此時(shí)特征根為一對共軛復(fù)數(shù)，。

由線性差分方程穩(wěn)定的條件，當(dāng)r<2即b<2a時(shí)（4.22）式是穩(wěn)定的，從而M*是穩(wěn)定的平衡點(diǎn)。不難發(fā)現(xiàn)，生產(chǎn)者管理方式的這一更動(dòng)不僅使自己減少了因價(jià)格波動(dòng)而帶來的損失，而且大大消除了市場的不穩(wěn)定性。生產(chǎn)者在采取上述方式來確定各時(shí)段的生產(chǎn)量后，如發(fā)現(xiàn)市場仍不穩(wěn)定（b≥2a），可按類似方法試圖再改變確定生產(chǎn)量的方式，此時(shí)可得到更高階的差分方程。對這些方程穩(wěn)定性條件的研究很可能會(huì)導(dǎo)出進(jìn)一步穩(wěn)定市場經(jīng)濟(jì)的新措施。例4.15

國民經(jīng)濟(jì)的穩(wěn)定性國民收入的主要來源是生產(chǎn)，國民收入的開支主要用于消費(fèi)資金、投入再生產(chǎn)的積累資金及政府用于公共設(shè)施的開支?，F(xiàn)在我們用差分方程方法建立一個(gè)簡略的模型，粗略地分析一下國民經(jīng)濟(jì)的穩(wěn)定性問題。再生產(chǎn)的投資水平It取決于消費(fèi)水平的變化量，設(shè)政府用于公共設(shè)施的開支在一個(gè)不太大的時(shí)期內(nèi)變動(dòng)不大，設(shè)為常數(shù)G。故由可得出。將及代入。

記yt為第t周期的國民收入，Ct為第t周期的消費(fèi)資金。Ct的值決定于前一周期的國民收入，設(shè)（4.23）（4.23）式是一個(gè)二階常系數(shù)差分方程，其特征方程為，相應(yīng)特征根為（4.24）成立時(shí)才是穩(wěn)定的。（4.24）式可用于預(yù)報(bào)經(jīng)濟(jì)發(fā)展趨勢?，F(xiàn)用待定系數(shù)法求方程（4.23）的一個(gè)特解。令代入（4.23）式，得故當(dāng)（4.24）式成立時(shí)，差分方程（4.23）的通解為其中ρ為的模，ω為其幅角。例如，若取，易見，此時(shí)關(guān)系式（4.12）成立，又若取y0=1600，y1=1700，G=550，則由迭代公式求得y2=1862.5,y3=2007.8,y4=2110.3,y5=2171.2,y6=2201.2,y7=2212.15,y8=2213.22,y9=2210.3,…。易見例4.16

商品銷售量預(yù)測

(實(shí)例)某商品前5年的銷售量見表?，F(xiàn)希望根據(jù)前5年的統(tǒng)計(jì)數(shù)據(jù)預(yù)測第6年起該商品在各季度中的銷售量。從表中可以看出，該商品在前5年相同季節(jié)里的銷售量呈增長趨勢，而在同一年中銷售量先增后減，第一季度的銷售量最小而第三季度的銷售量最大。預(yù)測該商品以后的銷售情況，一種辦法是應(yīng)用最小二乘法建立經(jīng)驗(yàn)?zāi)Ｐ?。即根?jù)本例中數(shù)據(jù)的特征，可以按季度建立四個(gè)經(jīng)驗(yàn)公式，分別用來預(yù)測以后各年同一季度的銷售量。例如，如認(rèn)為第一季度的銷售量大體按線性增長，可設(shè)銷售量由15253217152430151320271512182614111625121234第五年第四年第三年第二年第一年銷售量季度

年份求得a=1.3，b=9.5。根據(jù)預(yù)測第六年起第一季度的銷售量為

=17.3，=18.6，…如認(rèn)為銷售量并非逐年等量增長而是按前一年或前幾年同期銷售量的一定比例增長的，則可建立相應(yīng)的差分方程模型。仍以第一季度為例，為簡便起見不再引入上標(biāo)，以表示第t年第一節(jié)季度的銷售量，建立形式如下的差分方程：或等等。上述差分方程中的系數(shù)不一定能使所有統(tǒng)計(jì)數(shù)據(jù)吻合，較為合理的辦法是用最小二乘法求一組總體吻合較好的數(shù)據(jù)。以建立二階差分方程為例，為選取a0,a1,a2使最小，解線性方程組：即求解得a0=-8，a1=-1，a2=3。即所求二階差分方程為

雖然這一差分方程恰好使所有統(tǒng)計(jì)數(shù)據(jù)吻合，但這只是一個(gè)巧合。根據(jù)這一方程，可迭代求出以后各年第一季度銷售量的預(yù)測值y6=21，y7=19，…等。上述為預(yù)測各年第一季度銷售量而建立的二階差分方程，雖然其系數(shù)與前5年第一季度的統(tǒng)計(jì)數(shù)據(jù)完全吻合，但用于預(yù)測時(shí)預(yù)測值與事實(shí)不符。憑直覺，第六年估計(jì)值明顯偏高，第七年銷售量預(yù)測值甚至小于第六年。稍作分析，不難看出，如分別對每一季度建立一差分方程，則根據(jù)統(tǒng)計(jì)數(shù)據(jù)擬合出的系數(shù)可能會(huì)相差甚大，但對同一種商品，這種差異應(yīng)當(dāng)是微小的，故應(yīng)根據(jù)統(tǒng)計(jì)數(shù)據(jù)建立一個(gè)共用于各個(gè)季度的差分方程。為此，將季度編號為t=1,2,…,20，令或等，利用全體數(shù)