矩阵论大论文(张晋红)

“矩阵论”课程研究报告科目：矩阵理论及应用教师：舒永录姓名：张晋红学号：20140702109专业：机械工程类别：学术上课时间：2014年09月至2014年12月考生成绩：阅卷评语：阅卷教师(签名)航班问题摘要：针对城市路线选择中的航道数目统计问题，采用最小多项式的方法，得出了城市A到B的某个数目的相连的航班数目和不超过某个数目的相连的航班数目。本文所提出的方法适用于多城市间航道统计问题。正文一、问题描述一家航空公司经营A、B、C、D和H五个城市的航线业务，其中H为中心城市。各个城市间的路线见图1。图1假设你想从A城市飞往B城市，因此要完成这次路线，至少需要两个相连的航班，即A→H和H→B。如果没有中转站的话，就不得不要至少三个相连的航班。那么问题如下：(1)从A到B，有多少条路线刚好是三个相连的航班；(2)从A到B，有多少条路线要求不多于四个相连的航班。二、方法简述定义：设A是n阶方阵，若存在多项式)(f，使得()f0A=，即()fA是零矩阵，称)(f是矩阵A的零化多项式。下面指出两点：1）对任何n阶方阵A，都存在零化多项式。因为线性空间nnK是2n维的，故E,A,……,2nA必线性相关。故存在不全为0的数0122,,......,nkkkk，使220122......nnkkkk0EAAA即多项式220122().....nnfkkkk是A的零化多项式。2）任何矩阵的零化多项式不唯一。因为若)(f是A的零化多项式，则)()(gf也是A的零化多项式，这里的)(g可以是任意的非零多项式。定理（Hamliton-Caley定理）设111()||nnnnfaaaEA则11()...nnnnfaaa0AAAAE定义：在n阶方阵A的所有零化多项式中，次数最低的首一多项式，称为A的最小多项式，记为)(m。由Hamliton-Cayley定理可知，任何n阶方阵A的最小多项式是存在的，并且次数不超过n。定理：n阶方阵A的任意零化多项式都可以被A的最小多项式整除。定理：A的最小多项式唯一。定理：A的最小多项式的根是A的特征根，反过来，A的特征根必是A的最小多项式的根。设)(h是有限次多项式，)(m是方阵A的最小多项式（不妨tm)](deg[），用)(m去除)(h，余式为)(r，便有)()()()(rgmh这里1)](deg[tr，或)(r=0，由()mA=0,有()()()()hmgrAAAA上式说明方阵A的任意一个多项式()hA总可以表示为A的次数不超过1t的多项式()rA。具体的说，方阵A的任何有限次多项式()hA都可E,A,A2,…,At-1线性表示，且E,A,A2,…,At-1是线性无关的，所以上述表示法中的()rA还是唯一的。三、实验数据和结果将不同城市间的航道情况矩阵表示，从A城市到B城市有航道时，设置对应矩阵元素，当从i到j有航道则置1，否则置0，同一个城市间对应元素置0，因此就得到不同城市间的航道分布矩阵M，矩阵各元素用ijb表示。该矩阵的n次幂中各元素ija表示从第i个城市到j个城市的航道情况，如果不为0则表示到达j城市有n个相连的航班可以到达。同时，如果从i到s有航班发出sc置1，否则置0，得出isx=).............(1321nnccccc则isxM中元素sqm表示，从i→s→q的航班情况。nisxM表示从i出发经过n+1个航道后到达某城市的情况，如果对应元素不为0则表示经过n+1个航道可以到达该城市，反之如果为0则表示没有足够多的航道可以到达该城市。如果从某城市到达j城市的航道分布为121(......)jnnkkkky则TjMy中各元素表示各个城市到j的航道情况，如果该元素不为0则表示两个城市之间有航道到达j，反之，该元素为0表示没有航道到达j。综上所述121....nTisjnnbbbbxMy其中jb表示从i经过n+1次个航道后到达j的情况，如果该元素不为0则说明从i到j可以经过n+1次航道到达，为0则说明不可以经过n+1次航道到达。问题要求求出从A城市到B城市中间经过一定中转站时的线路条数，将出发城市发出的航道建模，设为asx=)(54321ccccc，asx表示从A出发到S目的地的航道情况，如果有航道则sc=1，反之sc=0。根据上图航道分布图可得asx=)10100(五个城市间航道的总体分布矩阵为M=0110010000110001000010100其中M的横坐标ijm表示，i城市到j城市的航道情况，1表示i→j有航道，0表示没有。asxM=12100asxM表示从A出发到达的第二个城市有没有通向第三个城市的航道情况，相应元素不为0表示有航道，反之没有航道。设12345()bkkkkky，by表示到达城市B的航班分布情况，(00011)by所以3TasbxMy，则可以推出从A到B经过三个相连航道到达有三条路线，经分析分别是ACHB,AHDB,ACDB。245TasbxxMy则可以推出从A到B经过四个相连航道到达有5条线路，经分析分别是AHCDB,ACHDB,AHDHB,AHCHB,ACDHB。题目要求求出从A到B，要求不多于四个相连的航班的线路数，求)4,3,2,1(x012()TasbxMMMy设()fAM0+M1+M2)(f=|EA|=)1)(1(22经验算，最小多项式为)(m)1)(1(2因为)()(mf余数为)(f，所以2()fAAAE=3210012100222001111022201)4,3,2,1(x012()TasbxMMMy=()TasbfxAy=9即从A到B有9条不多于四条相连航道的线路。检验证，从A到B经过一条航道到达的线路为0条，经过两条到达的线路为1条，经过三条到达的线路为3条，经过四条到达的线路为5条，一共有九条满足要求航道数目条件，因此利用上述方法得出的结果与实际结果相同。四、结果分析与说明本文采用了最小多项式的方法解决了路线选择中的航道数目统计问题，得出了从A到B，有3条路线刚好是三个相连的航班，有9条路线要求不多于四个相连的航班。利用本文所提出的方法特别适用于多城市间航道统计问题，由于本问题只考虑五个城市，所以本文提出的方法对于解决城市数目较少的类似问题计算量不免有些繁琐。参考资料[1]李新，河传江.矩阵理论及其应用[M].重庆：重庆大学出版社，2005.[2]同济大学数学系.工程数学：线性代数（第五版）[M].北京：高等教育出版社，2007.[3]杨大地，涂光裕.数值分析[M].重庆：重庆大学出版社，1998.[4]李正元，李永乐，范培华.数学复习全书[M].北京：中国政法大学出版社，2013.