第四章基于線性代數(shù)與差分方程方法的模型實用課件

第四章

浙江大學數(shù)學建模實踐基地第四章浙江大學數(shù)學建模實踐基地1基于線性代數(shù)與差分方程方法的模型

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

例4.1

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

在具體轉(zhuǎn)移時，只考慮由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)移。問題化為：由初始狀態(tài)（1，1，1，1）出發(fā)，經(jīng)奇數(shù)次上述運算轉(zhuǎn)化為（0，0，0，0）的轉(zhuǎn)移過程。我們可以如下進行分析：（第一次渡河）規(guī)定一個狀態(tài)向量與轉(zhuǎn)移向量之間的運算。規(guī)定狀態(tài)向量與在具體轉(zhuǎn)5（第二次渡河）＝以下可繼續(xù)進行下去，直至轉(zhuǎn)移目的實現(xiàn)。上述分析實際上采用的是窮舉法，對于規(guī)模較大的問題是不宜采用的。（第二次渡河）＝以下可繼續(xù)進行下去，直至轉(zhuǎn)移目的實現(xiàn)。上述分6例4.2夫妻過河問題這是一個古老的阿拉伯數(shù)學問題。有三對夫妻要過河，船最多可載兩人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不場的情況下與其他男子在一起，問此時這三對夫妻能否過河？這一問題的狀態(tài)和運算與前一問題有所不同，根據(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)，這是因為總可以適當安排而使他們是i對夫妻。（ii）可取運算：過河方式可以是一對夫妻、兩個男人或兩個女人，當然也可以是一人過河。轉(zhuǎn)移向量可取成((－1)im,(－1)in)，其中m、n可取0、1、2，但必須滿足1≤m+n≤2。當j為奇數(shù)時表示過河。當j為偶數(shù)時表示由對岸回來，運算規(guī)則同普通向量的加法。

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

問題歸結(jié)為由狀態(tài)(3,3)經(jīng)奇數(shù)次可取運算，8步1將THANKYOU轉(zhuǎn)換成（20，8，1，14，11，25，15，21）農(nóng)場計劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。以這一方法得到的密文電碼是：基于線性代數(shù)與差分方程方法的模型16）的解，其中c1、c2為任意常數(shù)，這說明，傳統(tǒng)的密碼通訊只能在事先約定的雙方間進行，雙方必須掌握相同的密鑰，而密鑰的傳送必須使用另外的“安全信道”。（iii）在每一代中，配偶的同胞對也是六種類型之一，并現(xiàn)希望根據(jù)前5年的統(tǒng)計數(shù)據(jù)預(yù)測第6年起該商品在各季度中的銷售量。在一段足夠長且非特別專門化的文章中，字母的使用頻率是比較穩(wěn)定的。經(jīng)過計算，矩陣M的特征值和特征向量為對應(yīng)的明文(i=1,2,…,n)是什么，即可確定A，并將密碼破譯。由前，表兄妹結(jié)婚的近交系數(shù)為1/16,故其子女發(fā)生該疾病的概率為只要相應(yīng)的整數(shù)小于n即可。(mod26)即記全體明文組成的集合為U，全體密文組成的集合為V，稱U為明文空間，V為密文空間。的隨機矩陣。雙親隨機結(jié)合的較一般模型相對比較復(fù)雜，這些我們僅研究一個較簡單的特例。如果初始的父母體同胞對是（A,Aa）型，即b0=1，而a0=c0=d0=e0=f0=0，于是，當§4.2密碼的設(shè)計，解碼與破譯

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

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

早期密碼

替代密碼

移位密碼

代數(shù)密碼

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

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表

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

代替法密碼采用另一個字母表中的字母來代替明文中的字母，明文字12混合一個字母表，常見的有兩種方法，這兩種方法都采用了一個密鑰單詞或一個密鑰短語。

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表

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

明文字母表

ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表

KLMPQVWXYZCONSTRUABDEFGHIJ

混合一個字母表，常見的有兩種方法，這兩種方法都采用了一個密鑰13方法2：a)選擇一個密鑰單詞或密鑰短語，例如：constructb)去掉其中重復(fù)的字母，得：construc)這些字母構(gòu)成矩陣的第一行，矩陣的后續(xù)各行由標準字母表中去掉密鑰單詞的字母后剩下的字母構(gòu)成d)將所得矩陣中的字母按列的順序排出

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

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

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

以上兩種移位較易被人破譯，為打破字母表中原有的順序還可采用所謂路線加密法，即把明文字母表按某種既定的順序安排在一個矩陣中，然后用另一種順序選出矩陣中的字母來產(chǎn)生密文表。2.移位密碼體制移位密碼采用移位法進行加密，明文中的字母重新1527）有兩個平衡點，即x*=0和。的形式，其對應(yīng)的齊次方程為根據(jù)定理6，甲隊最后獲勝的概率表兄妹（或堂兄妹）結(jié)婚使子女發(fā)生該疾病的概率增大了大約7.c)自左向右選出這些數(shù)字,得到一個混淆數(shù)字組:143675928，混淆字母表由從小到大的順序取矩陣中相應(yīng)列得出。如果初始的父母體同胞對是（A,Aa）型，即b0=1，而a0=c0=d0=e0=f0=0，于是，當類似地，可以定義yt的n階差分。隨著人類的進化，為了揭示生命的奧秘，人們越來越注重遺傳學的研究，特別是遺傳特征的逐代傳播，已引起人們廣泛的注意。第一，有時變量事實上只能取自一個有限的集合；現(xiàn)在利用差分方程方法來研究蛛網(wǎng)模型，以驗證上述猜測是否正確。某人要帶狗、雞、米過河，但小船除需要人劃外，最多只能載一物過河，而當人不在場時，狗要咬雞、雞要吃米，問此人應(yīng)如何過河。在應(yīng)用差分方程研究問題時，一般不需要求出方程的通解，在給定初值后，通?？捎糜嬎銠C迭代求解，但我們常常需要討論解的穩(wěn)定性。記全體明文組成的集合為U，全體密文組成的集合為V，稱U為明文空間，V為密文空間。為任意常數(shù)，i=1,…,k。得a0=-8，a1=-1，a2=3。農(nóng)場計劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。例如，對明文：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS.14（市場經(jīng)濟的蛛網(wǎng)模型）我們知道，平衡點M*是否穩(wěn)定取決于在M*附近供、需曲線的局部性態(tài)。希爾密碼體系為破譯者設(shè)置了多道關(guān)口，加大了破譯難度。例如，對明文：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS.以7列矩陣表示如下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先約定的方式選出密文。例如，如按列選出，得到密文：touthyhrihueeysanahomndrifoorsszrnetjeed使用不同的順序進行編寫和選擇，可以得到各種不同的路線加密體制。對于同一明文消息矩陣，采用不同的抄寫方式，得到的密文也是不同的。當明文超過規(guī)定矩陣的大小時，可以另加一矩陣。當需要加密的字母數(shù)小于矩陣大小時，可以在矩陣中留空位或以無用的字母來填滿矩陣。

27）有兩個平衡點，即x*=0和16移位法也可和代替法結(jié)合使用，并使用約定的單詞或短語作密鑰，以進一步加強保密性，這就是鑰控列序加密法。

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

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

移位法也可和代替法結(jié)合使用，并使用約定的單詞或短語作密鑰，以17代替法與移位法密碼的破譯對竊聽到的密文進行分析時，窮舉法和統(tǒng)計法是最基本的破譯方法。窮舉分析法

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

在上述兩種加密方法中字母表中的字母是一一對應(yīng)的，因此，在截獲的密文中各字母出現(xiàn)的概率提供了重要的密鑰信息。根據(jù)權(quán)威資料報道，可以將26個英文字母按其出現(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;不僅單個字母以相當穩(wěn)定的頻率出現(xiàn)，相鄰字母對和三字母對同樣如此。統(tǒng)計法是根據(jù)統(tǒng)計資料進行猜測的。在一段足夠長且非特別專門化的19按頻率大小將雙字母排列如下：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)計的章節(jié)越長，統(tǒng)計結(jié)果就越可靠。對于只有幾個單詞的密文，統(tǒng)計是無意義的。下面介紹一下統(tǒng)計觀察的三個結(jié)果：a)單詞the在這些統(tǒng)計中有重要的作用；b)以e，s，d，t為結(jié)尾的英語單詞超過了一半；c)以t，a，s，w為起始字母的英語單詞約為一半。對于a)，如果將the從明文中刪除，那么t的頻率將要降到第二組中其他字母之后，而h將降到第三組中，并且th和he就不再是最眾多的字母了。以上對英語統(tǒng)計的討論是在僅涉及26個字母的假設(shè)條件下進行的。實際上消息的構(gòu)成還包括間隔、標點、數(shù)字等字符?？傊谱g密碼并不是件很容易的事。

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

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

(mod26)

即

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

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

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

1357911151719212325

1921153197231151725此外，我們還不難證明這樣的還是由唯一確定的。事實上設(shè)23例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ù)的情況了,只需在乘法運算中結(jié)合應(yīng)用取余，求逆矩陣時用逆元素相乘來代替除法即可。例1取a=3用希爾密碼體系加密語句THANKYOU24

例2

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

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

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

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

如

，

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

，

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

，

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

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

(i=1,2,…,n)對應(yīng)的明文(i=1,2,…,n)是什么，即可確定A，并將密碼破譯。希爾密碼體系為破譯者設(shè)置了多道關(guān)口，加大了破譯難度。破譯和解28得到密文JXCPIWEK（1）當時，，其中W為一分量均大于零另一種移位法采用將字母表中的字母平移若干位的方法來構(gòu)造密文字母表，傳說這類方法是由古羅馬皇帝凱撒最早使用的，故這種密文字母表被稱為凱撒字母表。總共有十個可取狀態(tài)，對一般情況，應(yīng)找出狀態(tài)為可取的充要條件。混合一個字母表，常見的有兩種方法，這兩種方法都采用了一個密鑰單詞或一個密鑰短語。5%是隱性患者，并且可計算出大約每出生400個黑人孩子，其中有一個是顯性患者?；颊呓?jīng)常未到成年就痛苦地死去，而他們的父母則是疾病的病源?，F(xiàn)用待定系數(shù)法求方程（4.6的概率被牛羊吃掉而轉(zhuǎn)換到牛羊體內(nèi)，0.上述用圖示法分析市場經(jīng)濟穩(wěn)定性的討論在經(jīng)濟學中被稱為市場經(jīng)濟的蛛網(wǎng)模型。父母同有A1基因的概率為1/16，而子女從父母那里獲得基因?qū)1A1的概率為1/64，而獲得相同基因?qū)ΓǚQ為基因純合子）A1A1，A2A2，A3A3或A4A4之一的概率為1/16,此概率被稱為表兄妹(或堂兄妹)結(jié)婚(表親)的近交系數(shù)。再生產(chǎn)的投資水平It取決于消費水平的變化量，設(shè)劃分的。雙親隨機結(jié)合的較一般模型相對比較復(fù)雜，這些我們僅研究一個較簡單的特例。問題歸結(jié)為由狀態(tài)(3,3)經(jīng)奇數(shù)次可取運算，即由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)移，轉(zhuǎn)化為(0,0)的轉(zhuǎn)移問題。（a）假設(shè)：令n=0,1,2,…。在上述兩種加密方法中字母表中的字母是一一對應(yīng)的，因此，在截獲的密文中各字母出現(xiàn)的概率提供了重要的密鑰信息。順序）。對竊聽到的密文進行分析時，窮舉法和統(tǒng)計法是最基本的破譯方法。第一，有時變量事實上只能取自一個有限的集合；定理1,若使得

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

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

，

由此可得，對應(yīng)上例則有例5有密文如下:goqbxcbuglosnfal;根據(jù)英文30

,

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

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

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

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

RSA公開密鑰體制傳統(tǒng)的密碼通訊只能在事先約定的雙方間進行32定義1設(shè)n為一正整數(shù)，將小于n且與n互素的正整數(shù)個數(shù)記為Φ(n)，稱之為歐拉（EulerL.）Φ函數(shù)。不難證明：若p，q為兩個相異素數(shù)，n=p×q，則

φ(n)=(p-1)(q-1)令p,q為隨機選取的兩個大素數(shù)（大約為十進制100位或更大）,n=pq,n是公開的，而p,q則是保密的。僅知道歐拉函數(shù)φ(n)=(p-1)(q-1)，但如果不知道因式分解就不能用這個公式計算。隨機選取一個數(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組成公開密鑰的加密密鑰，而其余的項p,q,φ(n)和d組成了秘密陷門。很顯然，陷門信息包含了四個相關(guān)的項。定義1設(shè)n為一正整數(shù)，將小于n且與n互素的正整數(shù)個數(shù)記33若知道φ(n),則由

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

(modn)

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

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

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

?900≡1510(mod2773).在以上整個過程中，為減少計算量應(yīng)隨時注意取模。這樣900對應(yīng)的密碼是1510。以這一方法得到的密文電碼是：1510041715241445054226921684076116442488178718771672解密過程與此類似，只不過使用密鑰(157,2773)，直接計算很煩瑣，但用計算機處理這一問題卻非常簡單。本例中將四位數(shù)字劃分為一組，是為了使每組的數(shù)字不超過n=2773.當使用一個很大的n時，每次完全可以處理一個位數(shù)更多的數(shù)碼組。只要相應(yīng)的整數(shù)小于n即可。以第一個數(shù)為例，由于n=2773,比這里任何可能出現(xiàn)的四位數(shù)37§4.3馬氏鏈模型隨著人類的進化，為了揭示生命的奧秘，人們越來越注重遺傳學的研究，特別是遺傳特征的逐代傳播，已引起人們廣泛的注意。無論是人，還是動、植物都會將本身的特征遺傳給下一代，這主要是因為后代繼承了雙親的基因，形成自己的基因?qū)?，由基因又確定了后代所表現(xiàn)的特征。本節(jié)將利用數(shù)學的馬氏鏈方法來建立相應(yīng)的遺傳模型等，并討論幾個簡單而又有趣的實例。馬氏鏈（馬爾柯夫鏈）研究的是一類重要的隨機過程，研究對象的狀態(tài)s(t)是不確定的，它可能取K種狀態(tài)si(i=1,…,k)之一，有時甚至可取無窮多種狀態(tài)。在建模時，時間變量也被離散化，我們希望通過建立兩個相鄰時刻研究對象取各種狀態(tài)的概率之間的聯(lián)系來研究其變化規(guī)律，故馬氏鏈研究的也是一類狀態(tài)轉(zhuǎn)移問題?！?.3馬氏鏈模型隨著人類的進化，為了揭示生命的奧秘，人38例4.6設(shè)某商店經(jīng)營情況可能有三種狀態(tài)：好（S1：利潤豐厚）、一般（S2）和不好（S3：虧損）。根據(jù)統(tǒng)計資料，上月狀態(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.6設(shè)某商店經(jīng)營情況可能有三種狀態(tài)：好（S1：利潤豐39父母同有A1基因的概率為1/16，而子女從父母那里獲得基因?qū)1A1的概率為1/64，而獲得相同基因?qū)ΓǚQ為基因純合子）A1A1，A2A2，A3A3或A4A4之一的概率為1/16,此概率被稱為表兄妹(或堂兄妹)結(jié)婚(表親)的近交系數(shù)。定義1設(shè)n為一正整數(shù)，將小于n且與n互素的正整數(shù)個數(shù)記為Φ(n)，稱之為歐拉（EulerL.即使初始時刻的供應(yīng)量和價格對應(yīng)于平衡點，一點微小的波動也會導致市場供求出現(xiàn)越來越大的混亂。記t時段初市場上的供應(yīng)量(即上類似可以討論船每次可載三人的情況,其結(jié)果是5對夫妻是可以過河的,而六對以上時就無法過河了。定義2對于馬氏鏈，若存在一正整數(shù)K，使其轉(zhuǎn)移矩陣的K次冪MK>0（每一分量均大于0），則稱此馬爾鏈為一正則（regular）鏈。移位密碼采用移位法進行加密，明文中的字母重新排列，本身不變，只是位置改變了。這樣的矩陣被稱為隨機矩陣。定理2若A為正則鏈的轉(zhuǎn)移矩陣，則必有：但是，如果供應(yīng)曲線和需求曲線呈圖②中的形狀，則平衡點M*是不穩(wěn)定的，Mt將越來越遠離平衡點。在本問題中，可采取如下方法：一物在此岸時相應(yīng)分量為1，而在彼岸時則取為0，例如（1,0,1,0）表示人和雞在此岸，而狗和米則在對岸。定理6設(shè)B=FR=（bij），其中F為吸收鏈的基矩陣，R為T中1510041715241445054226921684以這一方法得到的密文電碼是：例如，某村鎮(zhèn)共有2000對婚配關(guān)系，其中有59對表親，22對半堂親和28對從表親，則該村鎮(zhèn)的近親系數(shù)為第一行減去第二行的2倍并取同余，得為A的伴隨矩陣。近親繁殖是指父母雙方有一個或兩個共同的祖先，一般追蹤到四代，即至少有相同的曾祖父（母）或外曾祖父（母）。例4.7研究某一草原生態(tài)系統(tǒng)中物質(zhì)磷的循環(huán)，考慮土壤中含磷、牧草含磷、牛羊體內(nèi)含磷和流失于系統(tǒng)之外四種狀態(tài)，分別以S1，S2，S3和S4表示這四種狀態(tài)。以年為時間參數(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)外。我們可以建立一個馬爾柯夫鏈來研究此生態(tài)系統(tǒng)問題，其轉(zhuǎn)移概率列表于下：1000S4流失系統(tǒng)外0.10.200.7S3羊體含磷00.60.30.1S2牧草含磷0.200.40.4S1土壤含磷i時段狀態(tài)S4S3S2S1i+1時段狀態(tài)狀態(tài)轉(zhuǎn)移概率父母同有A1基因的概率為1/16，而子女從父母那里獲得基因40相應(yīng)的轉(zhuǎn)移矩陣為：且Sj+1=SjM馬氏鏈模型的性質(zhì)完全由其轉(zhuǎn)移矩陣決定，故研究馬氏鏈的數(shù)學工具是線性代數(shù)中有關(guān)矩陣的理論。首先，任一轉(zhuǎn)移矩陣的行向量均為概率向量，即有（1）（I,j=1,…,n）（2）（i=1,…,n）這樣的矩陣被稱為隨機矩陣。相應(yīng)的轉(zhuǎn)移矩陣為：且Sj+1=SjM首先，任一轉(zhuǎn)移矩陣的行41常染色體遺傳模型

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

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

1000aa010Aa0001AA后代基因型aa－aaAa－aaAa－AaAA－aaAA－AaAA－AA父體——母體的基因型雙親隨機結(jié)合的較一般模型相對比較復(fù)雜，這些我們僅研究一個較簡單的特例。常染色體遺傳模型下面給出雙親體基因型的所有可能的結(jié)合，以及42例4.8農(nóng)場的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場計劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過若干年后，這種植物的任一代的三種基因型分布情況如何？（a）假設(shè)：令n=0,1,2,…。（i）設(shè)an,bn和cn分別表示第n代植物中，基因型為AA,Aa和aa的植物占植物總數(shù)的百分比。令x(n)為第n代植物的基因型分布：當n=0時表示植物基因型的初始分布（即培育開始時的分布）例4.8農(nóng)場的植物園中某種植物的基因型為AA,Aa和aa。農(nóng)場計劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過若干年后，這種植物的任一代的三種基因型分布情況如何？例4.8農(nóng)場的植物園中某種植物的基因型為AA,Aa和a43（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型。因此當n=1,2…時即類似可推出cn=0

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

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

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

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

例4.9常染體隱性疾病模型52現(xiàn)在，我們考慮在控制結(jié)合的情況下，如何確定后代中隱性患者的概率。

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

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

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

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

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

(A,AA),(A,Aa),(A,aa),(a,AA),(a,Aa),(a,aa)6種。初始一對雌雄的同胞對，是這六種類型中的任一種，其后代的基因型如下表所示。例4.10X—鏈遺傳模型的一個實例（a）假設(shè)61（iii）在每一代中，配偶的同胞對也是六種類型之一，并有確定的概率。為計算這些概率,設(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é)合是隨機的，那么第n代配偶的同胞對將等可能地為四種類型(A,AA),(A,Aa),(a,AA),(a,Aa)之一，對于其它類型的同胞對，我們可以進行同樣分析，因此有11/20000aa01/2111/20Aa00001/21AA11/2011/20a01/2101/21AA后代基因型(a,aa)(a,Aa)(a,AA)(A,aa)(A,Aa)(A,AA)父體——母體的基因型(4.11)（iii）在每一代中，配偶的同胞對也是六種類型之一，并1162其中從（4.11）式中易得經(jīng)過計算，矩陣M的特征值和特征向量為

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

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

吸收的概率。定理4吸收鏈的基矩陣F中的每個元素，表示從一個非吸收72例4.12（競賽問題）甲乙兩隊進行一場搶答競賽，競賽規(guī)則規(guī)定：開始時每隊各記2分，搶答題開始后，如甲取勝則甲加1分而乙減1分，反之則乙加1分甲減1分,(每題必需決出勝負)。規(guī)則還規(guī)定，當其中一方的得分達到4分時，競賽結(jié)束?，F(xiàn)希望知道：（1）甲隊獲勝的概率有多大？（2）競賽從開始到結(jié)束，平均轉(zhuǎn)移的次數(shù)為多少？（3）甲獲得1、2、3分的平均次數(shù)是多少？設(shè)甲勝一題的概率為p，（0<p<1），p與兩隊的實力有關(guān)。甲隊得分有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ù)甲隊贏得1分的概率為p，建立轉(zhuǎn)移矩陣：例4.12（競賽問題）設(shè)甲勝一題的概率為p，（0<p<1）73S

0S

1

S

2S

3S

4

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

計算F：令q=1-p，則因為a2是初始狀態(tài)，根據(jù)定理4，75==根據(jù)定理5，以a2為初始狀態(tài)，甲隊最終獲勝的平均轉(zhuǎn)移欠數(shù)為。又因為，根據(jù)定理6，甲隊最后獲勝的概率。==根據(jù)定理5，以a2為初始狀態(tài)，甲隊最終獲勝的平均轉(zhuǎn)移76§4.4差分方程建模

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