矩阵分析建模课件

《矩阵分析建模课件》由会员分享，可在线阅读，更多相关《矩阵分析建模课件（80页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 矩阵分析方法建模矩阵分析方法建模4.1 4.1 循环联赛的奖金分配及排名次问循环联赛的奖金分配及排名次问题题4.2 4.2 有限网络的一些有趣问题有限网络的一些有趣问题4.3 4.3 数据处理的一些有趣问题数据处理的一些有趣问题矩阵分析建模课件4.14.1 循环联赛的数学建模问题循环联赛的数学建模问题随着人们生活水平的提高随着人们生活水平的提高, ,人们不但喜人们不但喜爱体育爱体育, ,而且喜爱体育比赛而且喜爱体育比赛, ,出现千千万出现千千万万的各种体育比赛迷万的各种体育比赛迷. .随着我国经济的迅速崛起随着我国经济的迅速崛起, ,各种超级联各种超级联赛也应运而生赛也应运而生.

2、 .大型赛事常常是人们饭大型赛事常常是人们饭后茶余的主要话题后茶余的主要话题. .体育比赛中也有数学建模问题体育比赛中也有数学建模问题, ,本节就本节就来介绍来介绍, ,循环联赛的奖金分配及排名次循环联赛的奖金分配及排名次所涉及的数学建模问题所涉及的数学建模问题. .矩阵分析建模课件A A 循环联赛的奖金分配问题循环联赛的奖金分配问题背景背景 已有多年循环比赛历史的已有多年循环比赛历史的 n n支球队支球队: :T T1 1,T,T2 2,T,Tn n 今年照例举行今年照例举行无平局无平局的的循环联赛循环联赛, ,约定约定按下列规则发放奖金按下列规则发放奖金: :规则规则 战胜战胜T Ti i

3、得奖金得奖金 x xi ia a 元元,a,a 为待定的奖金为待定的奖金单位单位( (换句话说换句话说, ,战胜各队奖金按比例战胜各队奖金按比例 x x1 1:x:x2 2: : :x:xn n发放发放).).问题问题 如何合理地决定奖金如何合理地决定奖金( (系数系数) )向量向量 x=x=(x(x1 1,x,x2 2,x,xn n) )T T( (准确到相差正因子准确到相差正因子 a),a),使对每一队来说都保持公平使对每一队来说都保持公平? ?矩阵分析建模课件问题分析与假设问题分析与假设奖金向量的公平性体现在奖金向量的公平性体现在: : T Ti i越强越强 x xi i越大越大. .

4、( (战胜强队是衡量球队发挥好的标志战胜强队是衡量球队发挥好的标志) ) 各队强弱程度用各队强弱程度用胜负概率矩阵胜负概率矩阵 F=(fF=(fijij) ) 来刻画来刻画,f,fijij 表示过去表示过去 T Ti i 战胜战胜 T Tj j 的概率的概率. .假设假设: : n n 个队中没有特别强或特别弱的个队中没有特别强或特别弱的队队( (否则该队早已升级或降级离开了否则该队早已升级或降级离开了),),即即 i,j,0i,j,0f fijij1,( )0)0; ;非负方阵非负方阵 A A 称为本原矩称为本原矩 阵阵, ,如果存在正整数如果存在正整数 m m 使得使得 A Am m 为正

5、矩阵为正矩阵. .定理定理4.14.1: :任意本原矩阵任意本原矩阵A A都恰有一个正特征都恰有一个正特征值值r(A),r(A),其值大于其它特征值的模数其值大于其它特征值的模数( (故故r(A)r(A)为单特征值为单特征值, ,任意两个对应于它的任意两个对应于它的特征向量都线性相关特征向量都线性相关),),并且存在对应于并且存在对应于 r(A)r(A)的正特征向量的正特征向量x.x.定理定理4.24.2: :当当n n 3 3时时, ,奖金分配问题中定义的奖金分配问题中定义的矩阵矩阵 A A 是本原矩阵是本原矩阵, ,并且并且 r(A)=1.r(A)=1.矩阵分析建模课件定理定理4.24.2

6、 的证明的证明定理定理4.24.2: : 奖金分配问题中定义的矩阵奖金分配问题中定义的矩阵 A A 是本原矩阵是本原矩阵, ,并且并且 r(A)=1. r(A)=1.证证: : 因因 i i j,j,a aijij=f=fijij/u/ui i 0, 0,故故当当n n 3 3时时, , A A2 2 是一个正矩阵是一个正矩阵, ,即即 A A 是本原矩阵是本原矩阵. . 从而从而, ,按定理按定理4.1,4.1,有对应于有对应于 r(A) r(A)的正特的正特征向量征向量x: Ax=r(A)x.x: Ax=r(A)x.令令v=(uv=(u1 1,u,un n) )T T, ,则则 v vT

7、TA = vA = vT T. . 于是于是 v vT Tx = vx = vT TAx = r(A)vAx = r(A)vT Tx.x. 因因 v vT Tx x 0,0,由上式推出由上式推出 r(A)=1. r(A)=1.矩阵分析建模课件A A2 2=AA=AA=v vT TA=A=(u(u1 1,u,un n) )f11/u1 1f1n/u1 1fn1/un nfnn/un n= =(u(u1 1,u,un n)=)=v vT T其中其中,u,ui i= = j=1j=1n nf fjiji矩阵分析建模课件求奖金向量方法与例求奖金向量方法与例方法方法: : 首先由历史记录确定胜负概率矩阵

8、首先由历史记录确定胜负概率矩阵 F; F; 其次由其次由 F F 确定矩阵确定矩阵 A; A; 最后由适当数学最后由适当数学软件软件, ,例如例如,Matlab,Matlab,求出对应于求出对应于 A A 的特的特征值征值1 1的任一个正特征向量的任一个正特征向量 x,x,则此向量则此向量 x x 可取为合理的奖金向量可取为合理的奖金向量. .矩阵分析建模课件对于前面讨论的对于前面讨论的例例1 1: :我们首先由胜负概率我们首先由胜负概率矩阵矩阵F F求得矩阵求得矩阵A A为为: : A A = = 其次其次, ,利用数学软件利用数学软件 Matlab Matlab 的行命令的行命令: :A=

9、0,6/7,1;2/7,0,1/7;1/3,8/9,0;V,D=eig(A)A=0,6/7,1;2/7,0,1/7;1/3,8/9,0;V,D=eig(A)(D(D的对角元是特征值的对角元是特征值,V,V的第的第i i列是对应第列是对应第i i特征特征值的正特征向量值的正特征向量) )求得对应于求得对应于A A的最大特征值的最大特征值为为1,1,对应于对应于1 1的一个正特征向量是的一个正特征向量是: :x xT T=(0.7910,0.3020,0.5321),=(0.7910,0.3020,0.5321),这个正向量就是我们要求的奖金向量这个正向量就是我们要求的奖金向量. .06/712/

10、701/71/38/90矩阵分析建模课件方法方法: : 设奖金总额预算值为设奖金总额预算值为S,S,则则由上式立即求得由上式立即求得 a=S/(x a=S/(x1 1u u1 1+x+xn nu un n).).对对例例1 1有有 a=Sa=S/(/(0.79100.7910 0.7+0.7+0.30200.3020 1.4+1.4+0.53210.5321 0.90.9) )= =S/1.455S/1.455. .如何由奖金总额决定奖金单位如何由奖金总额决定奖金单位? ?矩阵分析建模课件例如对例如对例例1 1有有 a=S/1.455. a=S/1.455. 如果循环联赛组委会的奖金总额预算为

11、如果循环联赛组委会的奖金总额预算为 3 3万元左右时万元左右时,S=3(,S=3(万万).).则则 a=3/1.455=2.062.a=3/1.455=2.062.所以所以, ,战胜战胜T T1 1得奖金得奖金 x x1 1a=0.791a=0.791 2.0622.062=1.631(=1.631(万元万元););战胜战胜T T2 2得奖金得奖金 x x2 2a=0.302a=0.302 2.0622.062=0.623(=0.623(万元万元););战胜战胜T T3 3得奖金得奖金 x x3 3a=0.532a=0.532 2.0622.062=1.097(=1.097(万元万元).).注

12、注: :此三数之和为此三数之和为3.353.35万万, ,并不正好是并不正好是3 3万万. .如果强队均输如果强队均输, ,则奖金总数为则奖金总数为: : 2 2 1.631+1.097=4.36(1.631+1.097=4.36(万元万元););如果弱队均输如果弱队均输, ,则奖金总数为则奖金总数为2 2 0.623+1.097=2.34(0.623+1.097=2.34(万元万元),),它它们的平均值正是们的平均值正是3.353.35万元万元. .矩阵分析建模课件B B 循环联赛各队排名次问题循环联赛各队排名次问题背景背景 已有多年循环比赛历史的俱乐部欲为已有多年循环比赛历史的俱乐部欲为所

13、属所属n n支球队支球队:T:T1 1,T,T2 2,T,Tn n按强弱排名次按强弱排名次. .方法方法 首先制定评分标准首先制定评分标准, ,即确立评分向量即确立评分向量u=u=(u(u1 1,u,un n),u),uj j的意义是每个战胜的意义是每个战胜T Tj j的队都得的队都得分分u uj j; ;其次根据胜负概率矩阵其次根据胜负概率矩阵F=(fF=(fijij) )和评分和评分向量向量u u计算各队的得分向量计算各队的得分向量v=(vv=(v1 1,v,vn n) )其其规则是规则是: :规则规则 v vi i= = j=1j=1n nf fijiju uj j, i=1,n , i

14、=1,n 或或 v=Fu (1) v=Fu (1) 问题问题 如何决定向量如何决定向量u(u(从而从而v),v),使对每一队使对每一队都保持公平都保持公平? ?矩阵分析建模课件问题分析与假设问题分析与假设公平地决定向量公平地决定向量v=(vv=(v1 1,v,vn n) )和和u=(uu=(u1 1,u,un n) )体现在体现在: :v v1 1: : :v:vn n=u=u1 1: : :u :un n, ,或存在正数或存在正数 满足满足 = =v v1 1/u/u1 1=v=vn n/u/un n 即即 v= v= u. (2)u. (2) 将将(2)(2)代入代入(1)(1)得得 Fu

15、= Fu= u. (3)u. (3)结论结论: :胜负概率矩阵胜负概率矩阵F F是本原矩阵是本原矩阵(F(F2 2为正矩阵为正矩阵),),从而由前面的定理从而由前面的定理4.1,F4.1,F恰有一个正特恰有一个正特征值征值 , ,其所对应的任何正特征向量其所对应的任何正特征向量( (只有倍只有倍数差别数差别) )都可取为得分向量都可取为得分向量v v或评分向量或评分向量u.u.因向量因向量v v与与u u相差正常数倍相差正常数倍, ,故可按故可按u u的各分的各分量的大小为各队排名次量的大小为各队排名次. .矩阵分析建模课件例例1 1例例1 1: :我们有胜负概率矩阵我们有胜负概率矩阵 利用利

16、用MatlabMatlab的下列行命令的下列行命令: :F F=0,0.6,0.7;0.4,0,0.2;0.3,0.8,0;V,D=eig(F)=0,0.6,0.7;0.4,0,0.2;0.3,0.8,0;V,D=eig(F)求得对应于求得对应于F F的正特征值的正特征值0.94140.9414的一个特征的一个特征向量是向量是:v:vT T=(0.6985,0.4199,0.5794), =(0.6985,0.4199,0.5794), 此向量此向量v v即可取为我们要求的得分向量即可取为我们要求的得分向量. .按按v v的分量的大小为各队排名次的结果是的分量的大小为各队排名次的结果是: :

17、T T1 1, T, T3 3, T, T2 2F=F=00.60.70.400.20.30.80矩阵分析建模课件也可用奖金向量为各队排名次也可用奖金向量为各队排名次例例1 1: :由合理奖金向量由合理奖金向量x xT T=(x=(x1 1,x,xn n) )的性质的性质知知: :对任二球队对任二球队T Ti i和和T Tj j都有都有x xi i x xj j T Ti i比比T Tj j强强. .因此因此, ,也可按也可按x x1 1,x,xn n的大小为各队排名次的大小为各队排名次. .例如例如, ,对于例对于例1 1我们已求得合理的奖金我们已求得合理的奖金向量为向量为 x xT T=(

18、0.7910,0.3020,0.5321).=(0.7910,0.3020,0.5321).按按x x的分量的大小为各队排名次的结果是的分量的大小为各队排名次的结果是: :T T1 1, T, T3 3, T, T2 2. .矩阵分析建模课件 这个结果与前面按得分向量这个结果与前面按得分向量v v的分量的大的分量的大小为各队排名次的结果相一致的事实也小为各队排名次的结果相一致的事实也说明我们以上的分析是正确的说明我们以上的分析是正确的. . 如果要对这两个方法进行评优的话如果要对这两个方法进行评优的话, ,应该应该说说, ,本节的方法较优本节的方法较优, ,因为此方法直接利因为此方法直接利用矩

19、阵用矩阵F F即可求出结果即可求出结果, ,而用上节的方法而用上节的方法, ,则还需要从则还需要从F F再计算矩阵再计算矩阵A A的额外工作量的额外工作量. .两个方法的比较两个方法的比较矩阵分析建模课件 一个实例一个实例: :下表为某个俱乐部的下表为某个俱乐部的4 4支足球支足球队的比赛记录队的比赛记录, ,试用本节方法为这试用本节方法为这4 4支球队支球队排名次排名次. .T2T3T43:0, 1:1, 2:22:1, 2:3, 0:02:1, 3:1T11:43:1, 2:3T25:2, 4:2T3规定规定f fijij=0.6u=0.6uijij+0.4v+0.4vijij, ,u u

20、ijij为平均为平均场分场分;v;vijij为平均为平均进球分进球分. . 场分场分: :胜胜2,2,平平1,1,负负0;0;进球分进球分: :进一球进一球1 1分分. .例如例如,u,u2121=(2+1+1)/(2+2+2)=2/3(=(2+1+1)/(2+2+2)=2/3(每场总分是每场总分是2)2), , v v2121=(3+1+2)/(3+2+4)=2/3; =(3+1+2)/(3+2+4)=2/3; f f2121=0.6 u=0.6 u2121+0.4 v+0.4 v2121=2/3.=2/3.f f1212=1-f=1-f2121=1-2/3=1/3.=1-2/3=1/3.矩

21、阵分析建模课件T2T3T43:0, 1:1, 2:22:1, 2:3, 0:02:1, 3:1T11:43:1, 2:3T25:2, 4:2T3u u4242=(2+0)/(2+2)=1/2,v=(2+0)/(2+2)=1/2,v4242=(3+2)/(4+5)=5/9=(3+2)/(4+5)=5/9 f f4242=(3/5)(1/2)+(2/5)(5/9)=47/90=(3/5)(1/2)+(2/5)(5/9)=47/90 f f2424=1-f=1-f4242=43/97=43/97再如再如,u,u3131=(2+0+1)/(2+2+2)=1/2(=(2+0+1)/(2+2+2)=1/2

22、(每场总分是每场总分是2)2), , v v3131=(2+2+0)/(3+5+0)=1/2; =(2+2+0)/(3+5+0)=1/2; f f3131=0.6 u=0.6 u3131+0.4v+0.4v3131=1/2.=1/2.f f1313=1-f=1-f3131=1-1/2=1/2.=1-1/2=1/2.矩阵分析建模课件0 01/31/31/21/24/354/352/32/30 023/2523/2543/9043/901/21/22/252/250 08/658/6531/3531/3547/9047/9057/6557/650 0U=(0.329,0.617,0.242,0.6

23、73)U=(0.329,0.617,0.242,0.673)T T, ,用它为各队用它为各队排名次排名次得得: : T T4 4,T,T2 2,T,T1 1,T,T3 3其次用其次用MatlabMatlab算出矩阵算出矩阵F F的对应于唯一正的对应于唯一正特征值特征值1.22631.2263的一个正特征向量是的一个正特征向量是: :首先请大家验证矩阵首先请大家验证矩阵F F有如下数值有如下数值: : F= F=矩阵分析建模课件G12346579812543G=G= V,EV,E ,V=1,2,3,4,5,V=1,2,3,4,5,E=(1,2),(1,5),(2,3),E=(1,2),(1,5)

24、,(2,3), (2,5),(3,4),(4,5) (2,5),(3,4),(4,5)矩阵分析建模课件4.24.2 有限网络的一些有趣问题有限网络的一些有趣问题 计算机网计算机网, ,交通网交通网, ,灌溉网灌溉网, ,输电网输电网, ,电话网等都电话网等都是常见的有限网络是常见的有限网络. . 有限网络的数学模型是有限网络的数学模型是有限无向图有限无向图. .无向无向图图G G是是一个二重组一个二重组:G=:G= V,EV,E , ,其中其中V V是非空有限集是非空有限集合合, ,它的元素称为它的元素称为结点结点,E,E也是也是( (非空非空) )有限集有限集合合, ,它的元素称为它的元素称

25、为边边. .图图G G的边的边e e是一个结点二是一个结点二重组重组:e=(a,b),a,b:e=(a,b),a,b V,V,称称e e与与a,ba,b关联关联, ,或或a,ba,b与与e e关联关联, ,或或a a与与b b相邻接相邻接. .无向图可用一些点无向图可用一些点和连接两点间的连线和连接两点间的连线( (边边) )的一个图形来表示的一个图形来表示. .本节将讨论关于有限网络的两个有趣问题本节将讨论关于有限网络的两个有趣问题. .矩阵分析建模课件问题问题1 10 11 11111110000000000 背景背景: :设有限网络的各点仅取设有限网络的各点仅取0 0或或1 1两种状态两

26、种状态; ;开开始时刻每点都取始时刻每点都取0;0;以后每一步以后每一步, ,在上一在上一步基础上作如下的状态改变步基础上作如下的状态改变: :从各点中任选从各点中任选一点令其改变状态一点令其改变状态, ,同时也令与此点相邻接同时也令与此点相邻接的所有结点改变状态的所有结点改变状态. .例例1:1:下列下列5 5点网络前几次状态改变情况如下点网络前几次状态改变情况如下: :矩阵分析建模课件问题问题1 1: :对对任何任何网络是否网络是否总能总能经有限次改经有限次改变状态后使网络从变状态后使网络从全全00状态变为状态变为全全11状态状态? ? 这里网络的这里网络的“任意性任意性”适用于有任意适用

27、于有任意( (有限有限) )数目结点并且这些结点可任意邻接数目结点并且这些结点可任意邻接的网络的网络. .不言而喻不言而喻, ,这问题的肯定答案这问题的肯定答案, ,将是将是一个有理论和应用价值的有趣结果一个有理论和应用价值的有趣结果. . 矩阵分析建模课件 问题问题1 1在一些情况下具有明确的实际意义在一些情况下具有明确的实际意义. .例如例如: :如果所考虑的网络代表某些装置的如果所考虑的网络代表某些装置的电路网络电路网络;0,1 ;0,1 分别代表装置的分别代表装置的关机关机, ,开机状态开机状态. . 则问题则问题1 1的的意义意义是是: :每一每一次选定一个装置令它及与之相关联的装次

28、选定一个装置令它及与之相关联的装置都改变状态置都改变状态, ,能否经有限次改变后能否经有限次改变后, ,能能使任何此类装置网络从开始时全部关机使任何此类装置网络从开始时全部关机都能过渡到全部开机都能过渡到全部开机? ?问题问题1 1的实际意义的实际意义矩阵分析建模课件数学建模准备数学建模准备用用(0,1)(0,1)向量描述网络状态向量描述网络状态: :第第k k次改变结束时次改变结束时, ,网络状态用向量网络状态用向量x(k)=(xx(k)=(x1 1(k)(k),x,xn n(k)(k) )T T表示表示, ,其中其中,x,xi i(k)(k)=0=0或或1 1表示第表示第k k次改变结束时

29、网络次改变结束时网络的第的第i i个结点的状态是个结点的状态是00或或11.(.(例例1 1结点编号办法：结点编号办法：最上面结点编号为最上面结点编号为1 1, ,并按反并按反时针顺序把其余点依次标号为时针顺序把其余点依次标号为2,3,4,5.2,3,4,5.) )例例1 1: :x(0)=(0,0,0,0,0)x(0)=(0,0,0,0,0)T T,x(1)=(1,1,0,0,1),x(1)=(1,1,0,0,1)T T, , x(2)=(0,0,1,0,0) x(2)=(0,0,1,0,0)T T,x(3)=(1,1,1,1,1),x(3)=(1,1,1,1,1)T T. . 关键关键是是

30、: :寻求寻求x(k)x(k)与与x(k+1)x(k+1)的关系的关系. .如能得到从如能得到从x(k)x(k)计算计算x(k+1)x(k+1)的公式的公式, ,则问题的解决就有则问题的解决就有了办法了办法. .矩阵分析建模课件作网络的作网络的邻接矩阵邻接矩阵A=(aA=(aijij),a),aijij=0=0或或1(A1(A是是对称矩阵对称矩阵),),由结点由结点i i与结点与结点j j邻接或不邻接邻接或不邻接而定而定; ;并令并令 i,i,a aiiii=1. =1. 对对例例1 1得得1100111101011100011111111A =令令 e ei i表示第表示第i i个元素为个元

31、素为1 1其余元素为其余元素为0 0的的n n维维列向量列向量(n(n阶单位矩阵第阶单位矩阵第i i列列),),则则AeAei i表示表示A A的的第第i i列列. . 易见易见: : 14235矩阵分析建模课件x(1)=(1,1,0,0,1)x(1)=(1,1,0,0,1)T T=(0,0,0,0,0)=(0,0,0,0,0)T T+(1,1,0,0,1)+(1,1,0,0,1)T T =x(0)+Ae =x(0)+Ae1 1 ( (第第1 1次选择了第次选择了第1 1点点); ); x(2)=(0,0,1,0,0)x(2)=(0,0,1,0,0)T T=(1,1,0,0,1)=(1,1,0

32、,0,1)T T+(1,1,1,0,1)+(1,1,1,0,1)T T =x(1)+Ae =x(1)+Ae2 2 =x(0)+A(e=x(0)+A(e1 1+e+e2 2) ) ( (第第2 2次选择了第次选择了第2 2点点, ,取取按位加按位加:1+1=0); :1+1=0); x(3)=(1,1,1,1,1)x(3)=(1,1,1,1,1)T T=(0,0,1,0,0)=(0,0,1,0,0)T T+(1,1,0,1,1)+(1,1,0,1,1)T T =x(2)+Ae =x(2)+Ae5 5=x(0)+A(e=x(0)+A(e1 1+e+e2 2+e+e5 5).). ( (第第3 3次

33、选择了第次选择了第5 5点点) )矩阵分析建模课件命题命题1 1 x(k+1)=x(k)x(k+1)=x(k)+ +AeAeu u( (即即x(k)与与A的第的第u u列按位列按位加加) ), ,这里这里,u,u是第是第k k次选定点的序数次选定点的序数. .证证:Ae:Aeu u为为A A的第的第u u列列,x(k)+Ae,x(k)+Aeu u的第的第i i元是元是x(k)x(k)的的与与AeAeu u的第的第i i元的元的按位加按位加, ,注意当注意当AeAeu u的第的第i i元元是是0 0时时, ,表示第表示第i i结点与选定的第结点与选定的第u u结点不相结点不相邻邻, ,按我们的规

34、则按我们的规则, ,第第i i点保持原状态点保持原状态, ,即与即与第第k k次的状态相同次的状态相同, ,这正与按位加法性质这正与按位加法性质:”0:”0加何数仍为何数加何数仍为何数”的结论相一致的结论相一致; ; 当当AeAeu u的第的第i i元是元是1 1时时, ,表示第表示第i i结点与选定的结点与选定的第第u u结点相邻结点相邻( (规定规定: :每个结点都与自己相邻每个结点都与自己相邻),),按我们的规则按我们的规则, ,第第i i点要改变状态点要改变状态, ,即与第即与第k k次的状态不同次的状态不同, ,这正与按位加法性质这正与按位加法性质: : 1+1+0=1,0=1,1+

35、1+1=0 1=0 的结论相一致的结论相一致. .矩阵分析建模课件结论结论命题命题2 2: : 令令e e表示元素全为表示元素全为1 1的的n n维列向量维列向量. .如果方程如果方程0+0+ Ax=eAx=e 在在2 2元域元域 Z Z2 2 中有解中有解x=ex=ei i1 1+e+ei i2 2+e+ei im m, ,则依次选点则依次选点i i1 1,i,i2 2 ,i,im m 让网络作让网络作m m次改变状态次改变状态, ,可使网络可使网络从全从全0 0状态变为全状态变为全1 1状态状态. .注注: :由于域由于域Z Z2 2中加法是可交换的中加法是可交换的, ,故结果只故结果只与

36、此与此m m个点有关个点有关, ,而与选择他们的顺序无而与选择他们的顺序无关关, ,即按任意顺序选择此即按任意顺序选择此m m个点个点, ,让网络让网络作作m m次改变状态次改变状态, ,其结果都可使网络变为其结果都可使网络变为全全1 1状态状态. .请你对例请你对例1 1作一个试验作一个试验. .矩阵分析建模课件2 2元域元域定义为代数系统定义为代数系统: :Z Z2 2 = = 0,1,+,0,1,+, ,其中其中 加法定义为加法定义为 0+1=1+0=1;1+1=0+0=0 0+1=1+0=1;1+1=0+0=0 乘法定义为乘法定义为 0 0 1=11=1 0=00=0 0=00=0;1

37、;1 1=11=1易见易见:0,1:0,1关于上述加法关于上述加法, ,乘法构成交换群乘法构成交换群; ;满满足加法足加法, ,乘法的分配律乘法的分配律; ;并且非并且非0 0元元(1)(1)有乘法有乘法逆元逆元(1),(1),所以所以, ,Z Z2 2是一个域是一个域. .可以象实矩阵一样可以象实矩阵一样, ,定义定义Z Z2 2上的矩阵上的矩阵( (元素取值元素取值于于Z Z2 2的矩阵的矩阵) )及其加及其加, ,乘法运算乘法运算, ,只须注意两只须注意两点点:1+1=0;:1+1=0;运算结果是运算结果是Z Z2 2上的矩阵上的矩阵. .Z Z2 2上的线性方程组的理论与实线性方程组的

38、理上的线性方程组的理论与实线性方程组的理论完全类似论完全类似. .解法也差不多解法也差不多. .这个只有两个元这个只有两个元素的有限域素的有限域, ,在许多领域都有重要应用在许多领域都有重要应用. .矩阵分析建模课件算法算法目的目的: :寻求寻求方程方程Ax=eAx=e在在2 2元域元域Z Z2 2中的解中的解x.x.算法算法: :为在域为在域Z Z2 2中解线性方程组中解线性方程组Ax=e,Ax=e,我们把增广我们把增广矩阵矩阵(Ae)(Ae)用域用域Z Z2 2中初等行变换中初等行变换( (仅两类仅两类, ,即即, ,交换两行交换两行; ;和把一行加到另一行和把一行加到另一行),),化为化

39、为 的形式的形式, ,其中其中r r n n(r=rank(A)(r=rank(A)矩阵矩阵F F的每行恰的每行恰有一个有一个1,1,并分别属于不同的列并分别属于不同的列;u;u为为r r维列向量维列向量;v;v为为n n r r维列向量维列向量. .若若r=0r=0或或v v 0,0,则则Ax=eAx=e无解无解( (增广矩阵的秩大于系数矩阵的秩增广矩阵的秩大于系数矩阵的秩););否则否则, , x=(u,v)x=(u,v)T T即为所要求的解即为所要求的解. . 矩阵分析建模课件11001 111101 101110 100111 111011 1(Ae) =1 1 0 0 1 10 0

40、1 0 0 00 1 1 1 0 10 0 1 1 1 10 0 0 1 0 01 1 0 0 1 10 1 1 1 0 10 0 1 0 0 00 0 0 1 0 00 0 1 1 1 11 1 0 0 1 10 1 1 1 0 10 0 1 0 0 00 0 0 1 0 00 0 0 0 1 11 0 0 0 0 10 1 0 0 0 10 0 1 0 0 00 0 0 1 0 00 0 0 0 1 1交交换换上三角阵上三角阵对角矩阵对角矩阵 | x1100111101011100011111011邻接矩阵邻接矩阵:23451例例1 1矩阵分析建模课件思考题思考题4-14-1: :对开始为

41、全对开始为全0 0状态的下列网络状态的下列网络, ,如何选一些结点如何选一些结点, ,每次改变一点状态每次改变一点状态, ,使使网络最后变为全网络最后变为全1 1状态状态? ?你能编一个你能编一个( (例例如如Matlab)Matlab)程序求解有关方程组吗程序求解有关方程组吗? ?123465798矩阵分析建模课件Ax=eAx=e在域在域Z Z2 2中恒有解中恒有解证证: :由数域由数域Z Z2 2上线性方程组一般理论知上线性方程组一般理论知: Ax=e: Ax=e在域在域Z Z2 2上无解当且仅当在上无解当且仅当在Z Z2 2中该方程组可中该方程组可经初等变换化为经初等变换化为0=10=1

42、的矛盾方程的矛盾方程* *. .因此因此, ,若若此方程组无解此方程组无解, ,则把它的一些方程则把它的一些方程, ,不失一不失一般性般性, ,可假设为前可假设为前k k个方程加到一起会得到个方程加到一起会得到矛盾方程矛盾方程:0=1.:0=1.于是有于是有 i=1i=1k ka aijij=0,j=1,n,1=1+1+1(=0,j=1,n,1=1+1+1(共共k k个个).).因此因此,k,k是奇数是奇数, ,和和 i=1i=1k k j=1j=1k ka aijij=0 (*)=0 (*)但由于但由于A A是对角元全为是对角元全为1 1的对称矩阵和的对称矩阵和k k是奇数是奇数, ,又推出

43、又推出(*)(*)式左边等于式左边等于1 1的矛盾的矛盾. . Ax=e Ax=e在域在域Z Z2 2上不可能无解上不可能无解. .矩阵分析建模课件有关理论说明有关理论说明域域Z Z2 2上的线性方程组有解的充要条件是增广矩上的线性方程组有解的充要条件是增广矩阵与系数矩阵的秩相等阵与系数矩阵的秩相等. .Ax=eAx=e在上无解当且仅当在在上无解当且仅当在Z Z2 2中该方程组可经初中该方程组可经初等变换化为等变换化为0=10=1的矛盾方程的矛盾方程. .证证 充分性显然充分性显然. . 必要性必要性: : 用用Z Z2 2中适当初等行变换一定能将原方程中适当初等行变换一定能将原方程组等价地变

44、换为形如组等价地变换为形如A A x=(1,0,0)x=(1,0,0)T T的方程组的方程组. .若原方程组无解若原方程组无解, ,则此方程组的增广矩阵的秩大则此方程组的增广矩阵的秩大于系数矩阵于系数矩阵A A 的的秩的的秩r,r,由此推出由此推出: :1 1 r rn,n,从而从而A A 的第的第1 1行是其第行是其第i i1 1,i,ir r行的线性组合行的线性组合, ,换句话换句话说说,A,A 的第的第1 1行与这行与这r r行之和是行之和是0.0.于是于是, ,将上述方程将上述方程组的第组的第1,1,第第i i1 1,i,ir r个方程相加就能产生一个左个方程相加就能产生一个左端不出现

45、任何未知变元同时右端出现端不出现任何未知变元同时右端出现1 1的矛盾方的矛盾方程程. .矩阵分析建模课件矩阵矩阵A A是对称的蕴涵其非是对称的蕴涵其非0 0对角元的个数对角元的个数必为偶数必为偶数.(*).(*)式左边等于式左边等于A A的前的前k k行行k k列列的非的非0 0元之和在元之和在Z Z2 2中的值中的值. .因为因为, ,在这里在这里非非0 0元就是元就是1;1;对角元全为对角元全为1;1;并且并且k k是奇数是奇数. .所以所以,(*),(*)式左边等于奇数个式左边等于奇数个1 1在在Z Z2 2中之中之和和, ,此值必等于此值必等于1.1.矩阵分析建模课件应用于问题应用于问

46、题1 1得出的结论得出的结论结论结论: : 对对任意任意有限网络有限网络, ,适当依次选点作有限次适当依次选点作有限次改变状态改变状态, ,都可使都可使网络网络从全从全0 0状态变为全状态变为全1 1状态状态. .矩阵分析建模课件思考题思考题4-24-2: :对任意有限网络及对任意有限网络及任意任意初始初始状态状态, ,适当依次选点作有限次改变状态适当依次选点作有限次改变状态都可使网络变为全都可使网络变为全1 1状态吗状态吗? (? (提示提示: :以以下列网络为例下列网络为例, ,考虑你的答案考虑你的答案.).)矩阵分析建模课件从任意状态变为全从任意状态变为全1 1状态的讨论状态的讨论由思考

47、题由思考题4-24-2知知: :一般不能保证从任意状一般不能保证从任意状态都能变为全态都能变为全1 1状态状态. .自然要提出自然要提出问题问题: :网络满足什麽条件网络满足什麽条件, ,才能保证从任才能保证从任意初始状态出发意初始状态出发, ,都能经有限次按规则都能经有限次按规则改变状态后达到全改变状态后达到全1 1状态状态?(?(等价于等价于: :从任从任意初始状态开始变到任意指定的状态结意初始状态开始变到任意指定的状态结束束) )利用前面建立的数学模型不难找到我们利用前面建立的数学模型不难找到我们需要的答案需要的答案, ,其理论依据是下面的定理其理论依据是下面的定理4.3.4.3.矩阵分

48、析建模课件二元域二元域Z Z2 2上线性方程组的一个定理上线性方程组的一个定理定理定理.3.3 在二元域在二元域Z Z2 2上上, ,若若detAdetA 0,0,则线性则线性方程组方程组Ax=bAx=b对任意右端对任意右端b b恒有唯一解恒有唯一解. .证证: :设设detAdetA 0,0,对线性方程组对线性方程组Ax=bAx=b的系数矩阵的系数矩阵 施行施行Z Z2 2中行初等变换中行初等变换( (仅两类仅两类),),任何时候都任何时候都不会变出零列不会变出零列, ,否则否则, ,令变换矩阵的乘积为令变换矩阵的乘积为P P便有便有det(PA)=0det(PA)=0蕴涵蕴涵detA=0d

49、etA=0的矛盾的矛盾. .因此因此, ,对增广矩阵对增广矩阵(Ab)(Ab)在在Z Z2 2中施行行初等变中施行行初等变换换, ,一定可化为一定可化为(Ex)(Ex)的形式的形式(E(E为单位矩阵为单位矩阵),),从而从而, ,所唯一确定的所唯一确定的x x就是该方程组的唯就是该方程组的唯一解一解. .矩阵分析建模课件也可用也可用二元数域二元数域Z Z2 2上的上的矩阵理论证明定矩阵理论证明定理理4.3,4.3,其其要点要点如下如下: : 按按Z Z2 2上的上的矩阵理论矩阵理论, ,当当detAdetA 0 0时时, ,A A在在Z Z2 2上有逆矩阵上有逆矩阵A A-1-1, ,满足满足

50、: :A A-1-1是是Z Z2 2上的上的矩阵矩阵, ,并且并且A A-1-1A=E.A=E.以以A A-1-1左乘左乘线性方程组线性方程组Ax=bAx=b的两端即得的两端即得 x=A x=A-1-1b.b.这就证明了这就证明了,Ax=b,Ax=b对任意右端对任意右端b b恒有唯一解恒有唯一解A A-1-1b.b.矩阵分析建模课件应用举例应用举例例如例如, ,对于例对于例1 1中的网络中的网络, ,我们知道它的系我们知道它的系数矩阵数矩阵A,A,经经Z Z2 2中行初等变换可以化为下中行初等变换可以化为下列矩阵列矩阵: :由此可以断定由此可以断定detA=1detA=1 0,0,从而按定理从

51、而按定理4.3,4.3,此网络无论从任何指定状态开始此网络无论从任何指定状态开始, ,经有经有限次改变状态都可以变到全限次改变状态都可以变到全1 1状态状态. .矩阵分析建模课件12345矩阵分析建模课件例例1 1的几个不同初始状态的几个不同初始状态例如例如, , 选第选第1,3,4,5四个结点作四次状态改四个结点作四次状态改变变,可使例可使例1中的网络从状态中的网络从状态 变为全变为全1状态；选第状态；选第1,2,3,4,5五个结点作五个结点作五次状态改变五次状态改变,可使例可使例1中的网络从状态中的网络从状态 变为全变为全1状态；等等。状态；等等。 矩阵分析建模课件1 00101 1010

52、10111110001000 1 矩阵分析建模课件问题问题 2 2背景背景: :设有限网络的各点仅取设有限网络的各点仅取+或或-两种状态两种状态; ;已知其开始时刻每点的已知其开始时刻每点的状态状态; ;以后按下列规则以后按下列规则, ,定时改变网络的定时改变网络的状态状态. .规则规则: :对于每点对于每点, ,若上一时刻其邻点取若上一时刻其邻点取+,+,取取-的数目相同时维持原状的数目相同时维持原状态态; ;否则否则, ,将此点改变为其多数邻点的状将此点改变为其多数邻点的状态态. .矩阵分析建模课件+- - - -+- - -+- - -+- - -+- - -变化规律变化规律: : 例例

53、1 1趋于稳定趋于稳定, ,例例2 2趋于交叉循环趋于交叉循环. .自然要问自然要问: :对对任意任意网络和网络和任意任意初始状态初始状态, ,是是否否都有都有这个变化规律这个变化规律, ,即即: :不是不是趋于稳定趋于稳定, ,便便是趋于交叉循环是趋于交叉循环? ?例例1 1例例2 2矩阵分析建模课件问题问题2 2: :对对任何任何网络和网络和任意任意初始状态初始状态, ,是否是否总会总会趋于稳定或趋于交叉循环趋于稳定或趋于交叉循环? ? 换句话说换句话说, ,是否是否总是成立总是成立: :当当k k充分大时充分大时, ,第第k+2k+2时刻的状态恒与第时刻的状态恒与第k k时刻的状态相时刻

54、的状态相同同? ?试对你的结论给出严格证明试对你的结论给出严格证明. .矩阵分析建模课件数学建模准备数学建模准备用用(1,-1)(1,-1)向量描述网络状态向量描述网络状态: :第第 k k 次改变次改变 后后, ,网络状态用网络状态用( (行行) )向量向量x(k)=(xx(k)=(x1 1(k)(k),x,xn n(k)(k) )表示表示, ,其中其中,x,xi i(k)(k)=1=1或或-1-1表示第表示第k k次改变后网次改变后网络的第络的第i i个结点的状态是个结点的状态是”+”+”或或”-”.”-”.例例1:1:将该网络的最上面一结点编号为将该网络的最上面一结点编号为1,1,并并按

55、反时针顺序把其余结点标号为按反时针顺序把其余结点标号为 2,3,4, 2,3,4, 5,5,则则 x(0)x(0)T T=(1,-1,1,1,-1),=(1,-1,1,1,-1), x(1) x(1)T T=(-1,1,1,1,1), =(-1,1,1,1,1), x(2) x(2)T T=(1,1,1,1,1)=x(k)=(1,1,1,1,1)=x(k)T T,k=3,4, ,k=3,4, 矩阵分析建模课件数学建模数学建模问题问题2 2的数学模型归结为证明的数学模型归结为证明 定理定理4 4: :对任何网络和任意初始状态都存在对任何网络和任意初始状态都存在正整数正整数N,N,使得使得 k k

56、 N,x(k+2)=x(k).N,x(k+2)=x(k).( (例如例如, ,对例对例1,N=2;1,N=2;对例对例2,N=0.)2,N=0.)矩阵分析建模课件分析与证明分析与证明关键仍是求关键仍是求 x(k+1)x(k+1)与与 x(k)x(k)间的关系间的关系, ,与前面与前面一样一样, ,需要巧妙地构作一个网络矩阵需要巧妙地构作一个网络矩阵A=(aA=(aijij).).这个矩阵应与网络的邻接结构和问题的游戏这个矩阵应与网络的邻接结构和问题的游戏( (改变状态改变状态) )规则密切相关规则密切相关, ,具体作法是具体作法是: :a aijij=0=0或或1,1,由结点由结点i i与结点

57、与结点j j邻接或不邻接而定邻接或不邻接而定; ; a aiiii=1/2(1/2=1/2(1/2可代以小于可代以小于1 1的任意正数的任意正数).).例如例如, ,对例对例1,1,例例2 2有有1/2100111/2101011/2100011/2111011/2A=矩阵分析建模课件引理引理1 1: :对任意对任意k k 0,x(k+1)0,x(k+1)与与 Ax(k) Ax(k)的每个对应的每个对应分量都同号分量都同号. .证证: :这直接由网络矩阵这直接由网络矩阵A A的定义及网络改变状态的的定义及网络改变状态的规则推出规则推出. .例如例如, ,对例对例1,1,几个引理几个引理与与x(

58、1)=(-1,1,1,1,1)x(1)=(-1,1,1,1,1)T T同号同号. .这里这里,01/21,01/21和和1/21/2 1= 1= 1/21/2蕴涵蕴涵: :Ax(k)Ax(k)每个分量当上一时刻对应点的邻点取每个分量当上一时刻对应点的邻点取+,+,取取- -的数目相同时与上时刻对应点同号的数目相同时与上时刻对应点同号; ;否则否则, ,取多数邻取多数邻点的符号点的符号. .由规则知必与由规则知必与x(k+1)x(k+1)同号同号. .矩阵分析建模课件引理引理1的严格证明的严格证明在分析在分析Ax(0)的第个分量的符号时的第个分量的符号时,只需考虑与第只需考虑与第i个结点相邻的所

59、有结点上一时刻的状态个结点相邻的所有结点上一时刻的状态,这是这是因为因为Ax(0)的第的第i个分量等于个分量等于A的第的第i行与行与x(0)的的乘积乘积,而按邻接矩阵的定义而按邻接矩阵的定义(2)有有aii=1或或0,当当(i,j) E或或 E.从而与第从而与第i个结点不相邻的结点个结点不相邻的结点j对对Ax(0)的第的第i个个分量不产生影响分量不产生影响;与第与第i个结点相邻的结点个结点相邻的结点j对对Ax(0)的第的第i个分量贡献值为个分量贡献值为1或或 1则由结点前则由结点前一时刻的状态是一时刻的状态是“+”或或“ ”而定而定;第第i个结个结点自身对点自身对Ax(0)的第的第i个分量贡献

60、值为个分量贡献值为0.5或或 0.5由结点前一时刻的状态是由结点前一时刻的状态是“+”或或“ ”而定而定.矩阵分析建模课件因因| 0.5|1)n(1)阶实方阵阶实方阵A=(aA=(aijij) )的每行的每行最大二元素之和都等于最大二元素之和都等于 u;u;并且每列最大并且每列最大二元素之和都等于二元素之和都等于 v.v.试证试证: : u=v.u=v.证证: :用反证法用反证法. .不失一般性设不失一般性设u u v v. (*). (*)所需结论可通过以下三步推理来完成所需结论可通过以下三步推理来完成: : A A 的第的第i i行最大元行最大元, ,第二大元必可表为第二大元必可表为u/2

61、+pu/2+pi i,u/2-p,u/2-pi i, p, pi i 0,i=1,n.0,i=1,n.( (显然成立显然成立) )矩阵分析建模课件设设A A 的第的第i i行最大元行最大元, ,第二大元分别为第二大元分别为M Mi i,m,mi i, ,则则u=Mu=Mi i+m+mi i 它们的平均数为它们的平均数为u/2.u/2.令令M Mi i m mi i=p=pi i, ,则则M Mi i=u/2+p=u/2+pi i,m,mi i=u/2-p=u/2-pi i,p,pi i 0,i=1,n.0,i=1,n.m mi iM Mi iu/2pi/2pi/2矩阵分析建模课件 A A的行最

62、大元必两两不同列的行最大元必两两不同列. .因若有两个行最大元因若有两个行最大元 a asjsj,a,atjtj 都属于第都属于第j j列列, ,则则 v v a asjsj+a+atjtj u+u+p ps s+ +p pt t u,u,便与假设便与假设(*)(*)矛盾矛盾. . 令令 p pk k = = minpminp1 1,p,pn n.由由知第知第 k k行行第第 二大元二大元 u/2-pu/2-pk k 必与某必与某i i行最大元行最大元 u/2+pu/2+pi i 同在一列同在一列, ,于是有于是有v v u/2-pu/2-pk k+(+(u/2+pu/2+pi i)=)= u+(u+(p pi i- -p pk k) ) u,u,也也与假设与假设(*)(*)矛盾矛盾. . 证毕证毕. .矩阵分析建模课件思考题思考题4-44-4: : 试对问题试对问题 D D 给出别的证明给出别的证明. .征集不同于参考答案的解法！征集不同于参考答案的解法！矩阵分析建模课件