线性代数应用课件.ppt

1、线性代数的应用举例线性代数的应用举例v一、搜索引擎一、搜索引擎v二、矩阵在密码学中的应用二、矩阵在密码学中的应用v三、线性方程组的应用三、线性方程组的应用 矩阵的英文怎么说？矩阵的英文怎么说？matrixmeitriks n. (pl. matrixes, -trices 5meitrisi:z (生物形成生长的生物形成生长的)母体母体, 母体组织母体组织;【解】子宫【解】子宫 发源地发源地, 策源地策源地 【生】细胞间质【生】细胞间质, 基质基质 【矿】母岩【矿】母岩, 杂矿石杂矿石, 基岩基岩;【地质】脉石【地质】脉石, 填质填质; (岩石中化石等的岩石中化石等的)痕印痕印 【冶】【冶】(

2、合金的合金的)基体基体 【刷】纸型【刷】纸型, 字模字模 唱片模子唱片模子 【数】阵【数】阵, 矩阵矩阵, 真值表真值表, 母式母式;【无】矩阵变换电路【无】矩阵变换电路; 【语】主句、独立句【语】主句、独立句 matrixmatrix矩阵矩阵-MatrixmnmmnnaaaaaaaaaA212222111211这两个人是谁？这两个人是谁？1998年斯坦福大学两位博士生年斯坦福大学两位博士生Larry Page 和和 Sergey Brin 创立了创立了Google.Google搜索引擎搜索引擎vGoogle的核心技术是通过的核心技术是通过 网页级别（网页级别（PageRank） 对多达对多达

3、30多亿的网页进行重要性分析，多亿的网页进行重要性分析， 如果网页如果网页A链接到网页链接到网页B，google 就认为就认为“网页网页A投了网页投了网页B一票一票”否则链到若其中,0i, 1,)(ijijnnijgjggGnn1100011110101101GG是一个巨大而稀疏的矩阵是一个巨大而稀疏的矩阵81030n各个页面的链入数目：各个页面的链入数目：各个页面的链出数目：各个页面的链出数目：n1iijjgcn1jijjgr再定义矩阵再定义矩阵A: nnijaAnp1,85. 0pcgpajijij其其中中则则A是是Markov链的转移概率矩阵，可以证明：链的转移概率矩阵，可以证明：A的的

4、最大特征值为最大特征值为1，相应的特征向量，相应的特征向量x满足满足Axx 则则x是是Markov链的平稳分布，也就是链的平稳分布，也就是Google的的PageRank.这两个人是这两个人是Larry Page 和和 Sergey Brin 这两个人是谁？这两个人是谁？二、矩阵在密码学中的应用二、矩阵在密码学中的应用原来的消息原来的消息明文明文密文密文加密加密nR当矩阵当矩阵A可逆时，对可逆时，对 中所有的中所有的X，等式，等式XAXA1XAX1A左乘以左乘以A左乘以左乘以用可逆矩阵来加密用可逆矩阵来加密余则成和翠平都知道的密码矩阵是余则成和翠平都知道的密码矩阵是22111223430311

5、11A其逆矩阵为：其逆矩阵为：15312133119511571192111A余则成和翠平共同约定：余则成和翠平共同约定：1 2 3 4 5 6 7 8 9 10，25, 26A B C D E F G H I J , Y Z 另外，另外，0表示空格，表示空格，27表示句号，等等表示句号，等等 1,3,3,15,13,16,12,9,19,8,0,20, 8,5,0,20,1,19,11,27 于是例如密文：于是例如密文：表示：表示：ACCOMPLISH THE TASK把这个消息：把这个消息：ACCOMPLISH THE TASK按列写成按列写成45矩阵矩阵X2720209151100123

6、19581631819131X然后加密：然后加密：2720209151100123195816318191312211122343031111CAX14435192240621221278104137395422331610AXC发送发送简单！我用简单！我用 左乘收到的密文左乘收到的密文AX就行了就行了1ACA12720209151100123195816318191311531211331195115711921AXA114435192240621221278104137395422331610 1,3,3,15,13,16,12,9,19,8,0,20, 8,5,0,20,1,19,11,

7、27 原来是：原来是：也就是也就是ACCOMPLISH THE TASK 为了使加密的保密性更强，用为了使加密的保密性更强，用于加密的矩阵于加密的矩阵A的阶数越大越好，的阶数越大越好，而且还得保证密码矩阵的元素都而且还得保证密码矩阵的元素都 是整数是整数三、线性方程组的应用三、线性方程组的应用v3.1 九章算术九章算术中方程术中方程术v3.2 文学作品中的方程组文学作品中的方程组v3.3 交通流量交通流量v3.4 电路网络电路网络v3.5 化学平衡方程式化学平衡方程式v3.6 构造有营养的减肥食谱构造有营养的减肥食谱3.1九章算术九章算术v从先秦到西汉中叶经众多学者编撰、修从先秦到西汉中叶经众

8、多学者编撰、修改的一部数学著作改的一部数学著作全书全书246个问题，分为个问题，分为9章：章：方田、粟米、衰分、少广、商功、均输、方田、粟米、衰分、少广、商功、均输、盈不足、盈不足、方程方程、勾股、勾股有一些问题可以追溯到周代有一些问题可以追溯到周代周礼周礼的的“六艺六艺” 其中一门是其中一门是“九数九数”方程术：方程术：今有今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗；问上、中、下禾实

9、一秉各几何？问上、中、下禾实一秉各几何？设上、中、下禾各一秉打出的粮食分别为设上、中、下禾各一秉打出的粮食分别为x ,y,z 斗，则问题就是斗，则问题就是263234323923zyxzyxzyx解决方法：遍乘直除法解决方法：遍乘直除法 -Gauss消去法消去法射雕英雄传射雕英雄传3.2 文学作品中的方程组文学作品中的方程组郭靖扶着黄蓉跟着过去，只见那内室墙壁围成圆形，地下满铺郭靖扶着黄蓉跟着过去，只见那内室墙壁围成圆形，地下满铺细沙，沙上画细沙，沙上画 着许多横直符号和圆圈，又写着些着许多横直符号和圆圈，又写着些“太太”、“天元天元”、“地元地元”、“人元人元”、“物元物元”等等 字。郭靖看

10、得不知所云，生怕字。郭靖看得不知所云，生怕落足落足踏坏了沙上符字，站在门口，不敢入内。黄蓉自幼受父亲踏坏了沙上符字，站在门口，不敢入内。黄蓉自幼受父亲 教导，教导，颇精历数之术，见到地下符字，知道尽是些术数中的难题，那颇精历数之术，见到地下符字，知道尽是些术数中的难题，那是算经中的是算经中的“天元之天元之 术术”，虽然甚是繁复，但只要一明其法，也，虽然甚是繁复，但只要一明其法，也无甚难处无甚难处 （按：即今日代数中多元多次方程式，我国古代算经中早记（按：即今日代数中多元多次方程式，我国古代算经中早记其法，天、地、人、物四字其法，天、地、人、物四字 即西方代数中、四即西方代数中、四未知数）。未知

11、数）。 黄蓉从腰间抽出竹棒，倚在郭靖身上，随想随在沙上书写，黄蓉从腰间抽出竹棒，倚在郭靖身上，随想随在沙上书写，片刻之间，将沙上所列的七片刻之间，将沙上所列的七 八道算题尽数解开。这些算题那女子八道算题尽数解开。这些算题那女子苦思数月，未得其解，至此不由得惊讶异常，呆了半苦思数月，未得其解，至此不由得惊讶异常，呆了半 晌，忽问：晌，忽问：“你是人吗？你是人吗？”黄蓉微微一笑，道：黄蓉微微一笑，道：“天元四元之术，何足道哉？天元四元之术，何足道哉？算经中共有一算经中共有一 十九元，十九元，人人之上是仙，明、霄、汉、垒、层、高、之上是仙，明、霄、汉、垒、层、高、上、天，上、天，人人之下是地、下、低

12、、之下是地、下、低、 减、落、逝、泉、暗、鬼。减、落、逝、泉、暗、鬼。算到第十九元，方才有点不易罢啦！算到第十九元，方才有点不易罢啦！”那女子沮丧失色，身子摇那女子沮丧失色，身子摇 了几摇，突然一交跌在细沙之中，双手捧头，苦苦思索，过了一会，了几摇，突然一交跌在细沙之中，双手捧头，苦苦思索，过了一会，忽然抬起头来，脸有喜忽然抬起头来，脸有喜 色，道：色，道：“你的算法自然精我百倍，可是你的算法自然精我百倍，可是我问你：将一至九这九个数字排成三列，不论纵横我问你：将一至九这九个数字排成三列，不论纵横 斜角，每三字斜角，每三字相加都是十五，如何排法？相加都是十五，如何排法？”黄蓉心想：黄蓉心想：“

13、我爹爹经营桃花岛，五行生克之变，何等精奥？这九我爹爹经营桃花岛，五行生克之变，何等精奥？这九宫之法是桃花岛阵图的根基，岂有不知之理？宫之法是桃花岛阵图的根基，岂有不知之理？”当下低声诵道：当下低声诵道：“九宫九宫 之义，法以灵龟，二四为肩，六八为足，左三右七，之义，法以灵龟，二四为肩，六八为足，左三右七，戴九履一，五居中央。戴九履一，五居中央。”边说边画，在边说边画，在 沙上画了一个九宫之图。沙上画了一个九宫之图。那女子面如死灰，叹道：那女子面如死灰，叹道：“只道这是我独创的秘法，原来早有歌只道这是我独创的秘法，原来早有歌诀诀 传世。传世。”黄蓉笑道：黄蓉笑道：“不但九宫，即使四四图，五五图，

14、以至不但九宫，即使四四图，五五图，以至百子图，亦不足为奇。黄蓉笑道：百子图，亦不足为奇。黄蓉笑道：“不但九宫，即使四四图，不但九宫，即使四四图，五五图，以至百子图，亦不足为奇。就说四五五图，以至百子图，亦不足为奇。就说四 四图罢，以十六字四图罢，以十六字依次作四行排列，先以四角对换，一换十六，四换十三，后以依次作四行排列，先以四角对换，一换十六，四换十三，后以内四角对内四角对 换，六换十一，七换十。这般横直上下斜角相加，皆换，六换十一，七换十。这般横直上下斜角相加，皆是三十四。是三十四。”那女子依法而画，果然丝那女子依法而画，果然丝 毫不错。毫不错。黄蓉道：黄蓉道：“那九宫每宫又可化为一个八卦

15、，八九七十二数，以从那九宫每宫又可化为一个八卦，八九七十二数，以从一至七十二之数，一至七十二之数， 环绕九宫成圈，每圈八字，交界之处又有四圈，环绕九宫成圈，每圈八字，交界之处又有四圈，一共一十三圈，每圈数字相加，均为二百九一共一十三圈，每圈数字相加，均为二百九 十二。这洛书之图十二。这洛书之图变化神妙如此，谅你也不知晓。变化神妙如此，谅你也不知晓。”举手之间，又将七十二数的九宫举手之间，又将七十二数的九宫八卦图八卦图 在沙上画了出来。在沙上画了出来。 那女子瞧得目瞪口呆，颤巍巍的站起身来，问道：那女子瞧得目瞪口呆，颤巍巍的站起身来，问道：“姑娘是姑娘是谁？谁？”不等黄蓉回答，忽地不等黄蓉回答，

16、忽地 捧住心口，脸上现出剧痛之色，急从捧住心口，脸上现出剧痛之色，急从怀中小瓶内取出一颗绿色丸药吞入腹中，过了半晌，脸怀中小瓶内取出一颗绿色丸药吞入腹中，过了半晌，脸 色方见色方见缓和，叹道：缓和，叹道：“罢啦，罢啦！罢啦，罢啦！”眼中流下两道泪水。眼中流下两道泪水。 4 9 2 8 1 63 5 71x2x3x4x5x6x7x8x9x九宫之义，法以灵龟，二四为肩，六八为足，九宫之义，法以灵龟，二四为肩，六八为足，左三右七，戴九履一，五居中央左三右七，戴九履一，五居中央有关幻方的最早记录，是约公元前有关幻方的最早记录，是约公元前2200年在中国年在中国出现的出现的“洛书洛书”，传说这个幻方最初

17、是大禹在黄河，传说这个幻方最初是大禹在黄河岸边的一只神龟的背上看到的。岸边的一只神龟的背上看到的。4515151515151515159876543275395196385274198765432xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx113.3交通流量交通流量4x3004001003x2x1x3005006005xABCD4x3004001003x2x1x3005006005xABCD图中给出了某城市中心图中给出了某城市中心区，几条单行道彼此区，几条单行道彼此交叉，驶入和驶出如图交叉，驶入和驶出如图所示。所示。图中给出了上下班高峰时每个道路交叉路口的交通图中给出了上

18、下班高峰时每个道路交叉路口的交通流量（以每小时平均车辆数计），试确定这个交通流量（以每小时平均车辆数计），试确定这个交通流量图的一般模型。流量图的一般模型。关于交通流量的基本假设是交通网络的关于交通流量的基本假设是交通网络的总流入量总流入量等于等于总流入量总流入量,且流经一个交叉口的且流经一个交叉口的总输入总输入等于等于总输出总输出交叉口交叉口A交叉口交叉口B交叉口交叉口C交叉口交叉口D21xx 50030032x300 xx 454400100 xx 6005 xx1另外，该交通网络中总流入量等于总流出量，即另外，该交通网络中总流入量等于总流出量，即6003004001003005003 x

19、化简整理得：化简整理得： 400 x600 xx500 xx300 xxx800 xx3515443221是自由变量是自由变量53545251x400 xx500 xx200 xx600 x 解之得：解之得：注意：注意：由于本问题中由于本问题中的道路是单行道，所的道路是单行道，所以每一个变量不能以每一个变量不能取负值取负值3.4电路网络电路网络v如图所示的电路中，设电压源如图所示的电路中，设电压源已知已知求求V10US , 2R4R12R4R12R4R2R7654321743UUi,1R2R4U6R4R3R5R7R7UsUaibici+-+3i设各个网孔的回路电流分别为和设各个网孔的回路电流分

20、别为和, baiici根据基尔霍夫定律，任何回路中各个元件的电压之和根据基尔霍夫定律，任何回路中各个元件的电压之和等于零，于是，列出各回路的电压方程为：等于零，于是，列出各回路的电压方程为： 0iRRRiR0iRiRRRiRUiRiRRRc765b5c5b543a3sb3a321 写成矩阵形式：写成矩阵形式：scba7655554333321U001iiiRRRR0RRRRR0RRRR 把已知数据代入，得：把已知数据代入，得： 0010iii1812012281201218cba解之得：解之得： 370405556092590iiicba.3.5化学平衡方程式化学平衡方程式化学方程式描述了因化

21、学反应而消耗与增生的物质数量，化学方程式描述了因化学反应而消耗与增生的物质数量，例如，当丙烷气体燃烧时，根据状态方程式例如，当丙烷气体燃烧时，根据状态方程式为了配平这个方程式，化学家必须求出整数为了配平这个方程式，化学家必须求出整数,4321xxxx方程式左边方程式左边碳（）氢（碳（）氢（H），氧（），氧（O）原子的总数原子的总数方程式右边方程式右边碳（）氢（碳（）氢（H），氧（），氧（O）原子的总数原子的总数OHxCOxOxHCx242322831)()()()( 配平化学方程式的一个有条理的方法是建立一个向量配平化学方程式的一个有条理的方法是建立一个向量方程，说明化学反应中出现的每一类原子

22、的数目方程，说明化学反应中出现的每一类原子的数目构造如下向量构造如下向量，： 08383HC，： 200O2，： 201O2C 120O2：H碳碳氢氢氧氧要配平方程式，系数要配平方程式，系数 必须满足必须满足,4321xxxx 083 200 201 1201x2x 3x4x 083 200 201 1201x2x 3x 4x 000即：即： 000 xxxx43211-2-202-00801-03解之得：解之得：443424434541xxxxxxx1， 是自由未知量是自由未知量因为化学方程式的系数必须是整数，取因为化学方程式的系数必须是整数，取，44 x因此因此，351321 xxx配平后

23、的方程式为配平后的方程式为OHCOOHC22283435 虽然虽然 可以取可以取4的倍数，但建议大的倍数，但建议大家所求平衡方程式的系数最好是用家所求平衡方程式的系数最好是用尽可能小的整数尽可能小的整数4x3.6构造有营养的减肥食谱构造有营养的减肥食谱一种在一种在20世纪世纪80年代很流行的食谱年代很流行的食谱-剑桥食谱剑桥食谱 这是由剑桥大学这是由剑桥大学Alan H.Howard博士领导的团队博士领导的团队经过经过8年对过度肥胖病人的年对过度肥胖病人的临床研究成果。临床研究成果。 剑桥食谱剑桥食谱精确地平衡了精确地平衡了碳水化合物、蛋白质和脂肪、碳水化合物、蛋白质和脂肪、配合维生素、矿物质

24、、微量配合维生素、矿物质、微量元素和电解质。元素和电解质。 近年来，有数百人应用近年来，有数百人应用这一食谱成功减肥这一食谱成功减肥举例说明这个食谱的小规模情形举例说明这个食谱的小规模情形剑桥食谱中剑桥食谱中3种食物以及种食物以及100克每种食物中所含的克每种食物中所含的某些营养素的数量某些营养素的数量营养素（克营养素（克)每每100克成分所含营养素克成分所含营养素脱脂牛奶脱脂牛奶大豆粉大豆粉乳清乳清每天供应量每天供应量(克克)蛋白质蛋白质碳水化合物碳水化合物脂肪脂肪36 51 13 3352 34 74 450 7 1.1 3求出脱脂牛奶、大豆粉、乳清的某种组合，使该食谱求出脱脂牛奶、大豆粉

25、、乳清的某种组合，使该食谱每天能供给上表中规定的蛋白质、碳水化合物和脂肪每天能供给上表中规定的蛋白质、碳水化合物和脂肪的含量的含量 05236脱脂牛奶脱脂牛奶蛋白质蛋白质碳水化合物碳水化合物脂肪脂肪大豆粉大豆粉乳清乳清 73451 117413.所需营养所需营养素总量素总量 345331x单位单位2x单位单位3x单位单位 05236 73451 117413. 345331x2x 3x 即即 34533xxx1170743452135136321.求解过程留给大家！求解过程留给大家！ 233039202770 xxx321.32xxx1，求出的求出的 必须是非负的，否则没有意义必须是非负的，否则没有意义大家不用担心剑桥食谱太单调，我们可以大家不用担心剑桥食谱太单调，我们可以用用33种食物来供给种食物来供给31种营养素，这时需要种营养素，这时需要解一个解一个33阶的方程组阶的方程组学好线性代数学好线性代数为专业课学习打好基础为专业课学习打好基础谢谢大家！谢谢大家！谢谢