1、 第第二二章章 初等模初等模型型1 公平席位计算公平席位计算2 按揭还款按揭还款3 Markov链与Google网页排名4 选址问题与费马点5 切西瓜切西瓜与差分方程与差分方程1.公平席位计算问问题题三个系学生共200名(甲100,乙60,丙40),学生代表会议设20席,按比例分配,三个系分别为10,6,4席.1.现因学生转系,三系人数为103,63,34,问20席如何分配；2.若增加为21席,又如何分配。对对丙丙系系公公平平吗吗系别系别学生学生人数人数比例比例(%)20席的分配席的分配21席的分配席的分配比例比例结果结果比例比例结果结果甲甲10351.510.31010.8211乙乙6331
2、.56.366.627丙丙3417.03.443.573总和总和200100.020.02021.0021最大余数分配1.公平席位计算按这种最大剩余法的另一个重大缺陷是人口悖论,即人数增加了较多反而导致席位减少.系别系别学生学生人数人数比例比例(%)21席的分配席的分配人数人数变化变化21席的分配席的分配比例比例结果结果比例比例结果结果甲甲10351.510.821111411.2911乙乙6331.56.627646.346丙丙3417.03.573343.364总和总和200100.0 21.002121221.0021乙系人数增加1人，按最大剩余法反而少了1席，丙系人数未增加，反而多了一
3、席！“公平公平”分配方法分配方法需要一个衡量需要一个衡量公平分配的数量指标公平分配的数量指标 12121,;nnNN 当当分分配配公公平平 12122,A;nnNN 当当对对 不不公公平平11AnN代代表表 的的每每个个席席位位代代表表的的人人数数，iinN一一般般做做不不到到绝绝对对公公平平,但但可可以以使使尽尽量量接接近近.人数人数席位席位A方方n1N1B方方n2N2说明说明A增加增加1席席,仍对仍对 A不不公平公平,该席位应分给该席位应分给A.讨论讨论以下几种情况以下几种情况 121211nnNN 若若设设A,B已有已有N1,N2 席席,若若增加增加1席席,问问应分给应分给A,还是还是B
4、？不妨设分配开始时不妨设分配开始时 n1/N1 n2/N2,即即原方案对A不公平,121221nnNN 若若BA1.说说明明 增增加加 席席将将对对 不不公公平平 2既既然然情情况况分分给给谁谁都都不不公公平平,要要使使这这一一席席位位的的分分配配公公平平!接接近近这种情况最麻烦1212100,150,2,3,nnNN设设简简单单情情况况：111A1nN 若若分分配配给给，则则121250.nnnNNN 222B1nN 若若分分配配给给，则则10033.3,315037.5,41,当当增增加加 席席后后 最最公公平平分分配配应应该该是是感觉上,分配给B会相对公平.2250;nN 1150.nN
5、 121225041.7().6nnnNNN但但达达不不到到这种感觉如何用数学描述,并提炼成算法实现.模型假设 学生会共有N个席位,各系人数分别为n1,n2,.,nm，若各系分配的席位为N1,N2,.,Nm,则各系每席实际代表的人数分别为iiinaN 用目标函数衡量“公平度”maxiZa 要要求求目目标标函函数数最最小小.(.(最最小小除除数数法法)标标准准1 1miniZa 要要求求目目标标函函数数最最大大.标标准准2 2maxijZaa要要求求目目标标函函数数最最小小.标标准准3 3 2iZaa 要要求求目目标标函函数数最最小小.标标准准4 4回到21席例子(甲103,乙63,丙34),按
6、照标准1试算 maxminmaxiiiaiZaa 最最小小(或或)标标准准1 1系别系别人数人数比例比例Nni/n惯例惯例分配分配ai标准标准1分配分配ai甲甲10310.815119.361010.3乙乙636.6157979丙丙343.570311.348.5总和总和2002121212121第21席应该分配乙系,标准1的分配方案：10,7,4.ai比惯例分配的要小可用列表方法解决标准1(类似可解决标准2与3)席位可以看成是1位接1位分配的:每个系首先分配1位,并标以下划线;表中找出最大的下划线,把它右边的数加以下划线;重复步骤,直到下划线数字的个数=21.1234567891011甲甲1
7、03 51.5 34.3 25.8 20.6 17.2 14.7 12.9 11.4 10.3 9.4 乙乙63 31.5 21.0 15.8 12.6 10.5 9.0 7.9 7.0 6.3 5.7 丙丙34 17.0 11.3 8.5 6.8 5.7 4.9 4.3 3.8 3.4 3.1,1,2,inkk 计计算算成成表表可用列表方法解决标准11234567891011甲甲103 51.5 34.3 25.8 20.6 17.2 14.7 12.9 11.4 10.3 9.4 乙乙63 31.5 21.0 15.8 12.6 10.5 9.0 7.9 7.0 6.3 5.7 丙丙34
8、17.0 11.3 8.5 6.8 5.7 4.9 4.3 3.8 3.4 3.1 1234567891011甲甲103 51.5 34.3 25.8 20.6 17.2 14.7 12.9 11.4 10.3 9.4 乙乙63 31.5 21.0 15.8 12.6 10.5 9.0 7.9 7.0 6.3 5.7 丙丙34 17.0 11.3 8.5 6.8 5.7 4.9 4.3 3.8 3.4 3.1 可以归纳标准1的算法过程maxiZa 最最小小标标准准1 1可能最大值出现多个,则按某种约定来分配上述标准公平吗?是否存在公平的席位分配方法？1.1,iiiiiiinqNqqNnNq：为
9、为理理想想比比例例席席位位即即是是精精确确的的席席位位分分额额 向向下下或或向向上上取取整整得得到到;份份额额性性 2.1,iiNNNN：即即总总席席位位增增加加时时，各各方方的的席席位位都都不不减减少少；席席位位单单调调性性3.,ijijiijjn nn nNNNN ：当当则则与与人人口口单单调调性性公理化约定:,ijij即即当当 方方相相对对 方方人人数数增增加加时时 不不会会导导致致 方方席席位位减减少少而而 方方席席位位增增加加.上述标准公平吗?是否存在公平的席位分配方法？1.1,iiiqNq：份份额额性性 2.1,iiNNNN：席席位位单单调调性性3.,.ijijiijjn nn n
10、NNNN ：当当则则与与人人口口单单调调性性最大剩余法满足性质1,不满足性质2,3,准则1满足性质2,3，但不满足性质1.(见p285)经证明，当m4,N m+3,不存在满足满足3条性质的分配方案!从1930年后美国众议员席位选举采用相等比例法(EP)!ini比例比例最大剩余最大剩余(惯例惯例)最小除数最小除数(规则规则1)相等比例相等比例(EP)19149091.49928890216601.66222314601.46222414501.45122514401.44122614001.40121711001.10121总和总和100000100100100100不满足性质1的例子相等比例法
11、(EP)max(1)iiiinZNN 最最小小练习与思考1.学校共1000名学生,235人住A宿舍,333人住在B宿舍,432人住在C宿舍.学生要组织一个10人的委员会.使分别根据标准1与标准2给出分配方案.用房产在银行办理的贷款,该贷款要按照银行规定的利率支付利息。贷款形式 商业贷款和公积金贷款.还款形式 等额本息和等额本金.2.按揭还款调整日期调整日期商业基商业基准利率准利率公积金公积金利率利率2015.08.265.15%3.25%2015.06.285.40%3.50%2015.05.115.65%3.75%2015.03.015.90%4.25%2014.11.226.15%4.00
12、%2012.07.076.55%4.50%2012.06.096.80%4.70%2011.07.077.05%4.90%2011.04.066.80%4.70%2011.02.096.60%4.50%2010.12.266.40%4.30%2010.10.206.14%4.05%2008.12.235.94%3.87%2008.11.276.12%4.05%如贷款50万,分20年还清,年利率r,问月供是多少？2.1 等额本金计算方法 yzx 每每月月本本金金每每月月利利息息每每月月还还款款额额ywn 本本金金还还款款月月数数每每月月本本金金如贷款w=50万本金,分m=20年还清,年利率q=6
13、.55%,问月供(还款额)x是多少？zwsr本本金金累累计计还还款款本本金金月月利利率率每每月月利利息息计算原则：每月归还的本金额始终不变,利息会随剩余本金的减少而减少。固定则需n=240月还清,月利率r=0.54583%.111st xyz月月还还款款额额ywn 本本金金还还款款月月数数每每月月本本金金如贷款w=50万本金,分m=20年还清,年利率q=6.55%,问月供(还款额)x是多少？11stzwr月月利利息息2729.2 元元4812.5 元元2nd()2wyzr月月利利息息2717.8 元元222nd xyz月月还还款款额额4801.1 元元 (th1)kwkykzr月月利利息息 t
14、hkkkxyz月月还还款款额额累计已还本金则需n=240月还清,月利率r=0.54583%.每个月还款额是变化的2083.3 元元月份月份 每月每月本金本金 y 每月每月利息利息 z 每月月每月月供供 x 已还已还本金本金 s 已付已付利息利息 p12083.3 2729.2 4812.5 2083.3 2729.2 22083.3 2717.8 4801.1 4166.7 5446.9 32083.3 2706.4 4789.7 6250.0 8153.3 42083.3 2695.0 4778.4 8333.3 10848.4 52083.3 2683.7 4767.0 10416.7 1
15、3532.0 62083.3 2672.3 4755.6 12500.0 16204.3 1202083.3 1375.9 3459.3 250000.0 246305.8 1212083.3 1364.6 3447.9 252083.3 247670.4 1222083.3 1353.2 3436.5 254166.7 249023.6 1232083.3 1341.8 3425.2 256250.0 250365.4 237 2083.3 45.5 2128.8 493750.0 328794.3 238 2083.3 34.1 2117.4 495833.3 328828.5 239 2
16、083.3 22.7 2106.1 497916.7 328851.2 240 2083.3 11.4 2094.7 500000.0 500000.0 328862.6 328862.6 20年期的等额本金的月供列表月份月份 每月每月本金本金 y 每月每月利息利息 z 每月月每月月供供 x 已还已还本金本金 s 已付已付利息利息 p1 2777.8 2729.2 5506.9 2777.8 2729.2 2 2777.8 2714.0 5491.8 5555.6 5443.2 3 2777.8 2698.8 5476.6 8333.3 8142.0 4 2777.8 2683.7 5461.
17、5 11111.1 10825.7 5 2777.8 2668.5 5446.3 13888.9 13494.2 6 2777.8 2653.4 5431.1 16666.7 16147.6 90 2777.8 1379.7 4157.5 250000.0 184901.0 91 2777.8 1364.6 4142.4 252777.8 186265.6 92 2777.8 1349.4 4127.2 255555.6 187615.0 93 2777.8 1334.3 4112.0 258333.3 188949.3 177 2777.8 60.6 2838.4 491666.7 2468
18、98.6 178 2777.8 45.5 2823.3 494444.4 246944.1 179 2777.8 30.3 2808.1 497222.2 246974.4 180 2777.8 15.2 2792.9 500000.0 500000.0 246989.6 246989.6 15年期的等额本金的月供列表2.2 等额本息计算方法 yzx 每每月月本本金金每每月月利利息息每每月月还还款款额额xzy 每每月月还还款款额额每每月月本本息息每每月月本本金金 zwsr本本金金累累计计还还款款本本金金月月利利率率每每月月利利息息计算原则：月供总额保持不变,银行从每月月供款中,先收利息,后收本
19、金,利息会不断减少。固定如何求每月还款额x？111stxzs 月月累累计计已已还还本本金金如贷款w=50万本金,分n=240月还清,月利率r=0.54583%,求每个月供？11stzwr月月利利息息2729.2 元元12d()2nzwsr月月利利息息23d()3rzwsr月月利利息息2122n)d(sxsz月月累累计计已已还还本本金金3233r)d(sxsz月月累累计计已已还还本本金金239224040(240 h)tsxzsw 月月累累计计已已还还本本金金 11thnns 月月累累计计已已还还本本金金1(h)tnnwrnzs 月月利利息息1()nnnsxzs 1(1)()nr sxwr 1(
20、)1()nnxwrxwrsrsrr(1)1()nnrsxwrrw(1)(1)1nnrxwrr 01()nnxwrxwrsrsrr3742.59.s0=0月份月份 每月每月本金本金 y 每月每月利息利息 z 每月月每月月供供 x 已还已还本金本金 s 已付已付利息利息 p1 1013.4 2729.2 3742.6 1013.4 2729.2 2 1019.0 2723.6 3742.6 2032.4 5452.8 3 1024.5 2718.1 3742.6 3056.9 8170.8 4 1030.1 2712.5 3742.6 4087.1 10883.3 5 1035.7 2706.8
21、3742.6 5122.8 13590.1 6 1041.4 2701.2 3742.6 6164.2 16291.3 120 1937.0 1805.6 3742.6 171132.7 277977.7 121 1947.5 1795.1 3742.6 173080.2 279772.7 122 1958.2 1784.4 3742.6 175038.4 281557.2 123 1968.8 1773.7 3742.6 177007.3 283330.9 237 3662.0 80.6 3742.6 488893.7 398099.3 238 3682.0 60.6 3742.6 4925
22、75.7 398160.0 239 3702.1 40.5 3742.6 496277.7 398200.5 240 3722.3 20.3 3742.6 500000.0 500000.0 398220.8 398220.8 20年期的等额本息的月供列表按揭年数按揭年数首月月供首月月供还款总额还款总额支付利息款支付利息款106895.83665114.58165114.58155506.94746989.58246989.58204812.5828864.58328864.58254395.83910739.58410739.58304118.06992614.58492614.58按揭年数
23、按揭年数每月月供每月月供还款总额还款总额支付利息款支付利息款105818.32698198.02198198.02154508.13811463.36311463.36203891.52933963.65433963.65253549.861064958.06564958.06303343.321203594.95703594.95标准利率6.55%等额本息按揭贷款50万标准利率6.55%等额本金按揭贷款50万按揭年数按揭年数首月月供首月月供还款总额还款总额支付利息款支付利息款106041.67613437.5113437.5154652.78669687.5169687.5203958.33
24、725937.5225937.5253541.67782187.5282187.5303263.89838437.5338437.5按揭年数按揭年数每月月供每月月供还款总额还款总额支付利息款支付利息款105181.92621830.45121830.45153824.97688493.96188493.96203163.25759179.25259179.25252779.16833748.72333748.72302533.43912033.56412033.56公积金4.50%等额本息按揭贷款50万公积金4.50%等额本金按揭贷款50万2.3 用折现方式计算等额本息 若银行年利率为7%,则
25、一年后的107元(未来值)的现值就是100元.1001100,17%相相应应的的,年年后后元元的的现现值值就就是是21002100.(17%)年年后后元元的的现现值值就就是是设房贷月利率为r,每月月供x不变(未来值)1st,1xr 月月后后月月供供的的现现值值是是th,(1)nxnr 月月后后月月供供的的现现值值是是每个月的月供现值的总和应该等于贷款现值50万！每个月的月供现值的总和应该等于贷款现值50万！21(1)(1)nxxxSrrr 现现值值总总和和w 1(1)11111nrrxr (1)1(1)nnrxrr (1).(1)1nnrxwrr 与前面推导一致,并且简单一些！练习与思考1.假
26、设你借了好友5000元,计划3年内还清,准备第一年还1000,第二年还2000,为了不让好心的朋友吃亏,请问第三年应该还多少合适？(假设银行年利率5.0%)2.假设商业按揭贷款50万,首次置业享受标准利率5.15%的8.5折,计划13年还清的每月等额本息的月供是多少？3.同2题,现计划10年还清,要求前5年月供均为5000元,问后5年的月供是多少？4.淘宝招财宝变现计算 张三6月1日以6.6%购买了1年期个人贷10000，现9月3日发现资金困难，想以5.5%的年利率变现出去，假设招财宝上有人愿意接手，由于招财宝平台需要收取2%的变现手续费，请问张三可以最大实际到手多少钱？Markov链简单介绍
27、设学校有1000个学生,饭堂早餐只有鸡蛋和馒头,每个学生如果前一天吃了鸡蛋,今天再吃鸡蛋的概率为0.4;如果前一天吃的是馒头,则今天吃鸡蛋的概率是0.8.问经过一段时间后,每天吃鸡蛋与馒头的平均人数？昨天昨天 今天今天鸡蛋鸡蛋馒头馒头鸡蛋鸡蛋0.40.8馒头馒头0.60.2 Tx11,1,0,第第 天天其其中中一一个个学学生生吃吃的的是是鸡鸡蛋蛋 记记假假设设0.40.8A0.60.2 记记(,),Tnnnnxyz 只只需需求求出出该该生生 天天后后吃吃鸡鸡蛋蛋馒馒头头的的概概率率10001000()()111000.iinniinyz则则 天天后后个个学学生生吃吃鸡鸡蛋蛋馒馒头头的的个个数数
28、为为与与 昨天昨天 今天今天鸡蛋鸡蛋馒头馒头鸡蛋鸡蛋0.40.8馒头馒头0.60.20.40.8A0.60.2 记记 11,1,0,Tx 假假设设第第 天天其其中中一一个个学学生生吃吃的的是是鸡鸡蛋蛋 记记2第第 天天吃吃鸡鸡蛋蛋与与馒馒头头的的概概率率 20.4,0.6Tx 3第第 天天吃吃鸡鸡蛋蛋与与馒馒头头的的概概率率 30.64,0.36Tx 1Ax 2Ax 21A x 4第第 天天吃吃鸡鸡蛋蛋与与馒馒头头的的概概率率43Axx 31A x 11,Annnxx 由由此此得得 第第 天天吃吃鸡鸡蛋蛋与与馒馒头头的的概概率率为为11,Annnxx 由由此此得得 第第 天天吃吃鸡鸡蛋蛋与与馒
29、馒头头的的概概率率为为0.57140.5714lim AB0.42860.4286nn有有 1limlim0.5714,0.4286,TnnnxBx 1x如如果果第第一一天天全全部部学学生生都都是是吃吃鸡鸡蛋蛋的的 即即相相同同1lim,nnxx但但我我们们发发现现与与初初值值无无关关571,429.每每天天平平均均有有个个学学生生吃吃鸡鸡蛋蛋个个学学生生吃吃馒馒头头lim Ann求求比比较较麻麻烦烦，Markov由由可可简简单单求求得得.正正则则定定理理极限分布limnnx即即极极限限分分布布与与每每个个学学生生第第一一天天吃吃什什么么！无无关关Markov,.,Axxx 以以上上是是一一个
30、个链链 存存在在有有正正则则A1,1的的特特征征值值是是只只需需求求特特征征值值是是 所所对对应应的的!最最大大特特征征向向量量.limnnxx 且且lim Ann求求比比较较麻麻烦烦，Markov由由可可简简单单求求得得.正正则则定定理理1112121222112A,1nnnijjnnnnaaaaaaaaaa 若若若aij 0,则称为正则Markov链,Ax=x的特征值1只有1个特征向量x,x就是唯一的极限分布.,lim AB,0innja 若若存存在在则则只只能能求求1limlim Bnnnxx 再再求求此时特征值1对应多个特征向量正则Markov链转移概率矩阵 11500,500,Tx
31、假假设设第第 天天吃吃鸡鸡蛋蛋与与馒馒头头的的人人数数为为也也可可以以212A,xx 第第 天天吃吃鸡鸡蛋蛋与与馒馒头头的的人人数数为为0.40.8A0.60.2 记记11A,nnnxx 第第 天天吃吃鸡鸡蛋蛋与与馒馒头头的的人人数数为为0.57140.5714lim AB0.42860.4286nn由由 1lim571,429,Tnnxx 得得.与与初初值值无无关关另另解解练习：一个醉汉在床与三步之远的楼梯之间蹒跚,每走一步朝着床走的概率比朝着楼梯走的概率是3：1.如果到了位置1就会摔下楼梯;到了位置4就会睡个好觉.(1)试证明:这个醉汉最终一定回到床和楼梯这两个位置中的一个.(2)假设他现
32、在在位置2,计算他最终在床上的概率.1 2 3 4 非正则Markov链Markovlim Ann不不是是正正则则链链的的的的求求法法：由Markov链性质,An有极限,且极限不为0则An有一个特征值1,其他特征值绝对值小于1.1AU U,由由 1212U,mmuuu 其其中中,1lim Alim UUnnnn Aui=i ui112lim Udiag(,)Unnmmn ，1Udiag(1,1,1,0,0,0)U.把不是1的特征值置零地球由大气层包裹,是气液共存态.假设每天有6%的液体蒸发为气体,而又有2%的气体凝结(降雨、雪)为液体.假如开始时有70%的液体,30%的气体，写出转移概率矩阵,
33、A 并用软件计算液体与气体的最终稳定分布.思考与练习3.Google搜索引擎的奥秘q 据统计超过80%的用户靠搜索引擎获取信息q 网站排名是网络搜索引擎的核心q 目前Google数据库存储上百亿网页信息,每天提供查询服务达到3亿多次背景和问题背景和问题用时0.27s80万网页如何对Internet的的网页排名google查询过程示意图Google搜索的核心算法q PageRank是 Google 用于评价一个网页的重要性的一种方法.通过该方法,Google 将各个网站进行排名.用户进行相关搜索时,Google 会将符合条件的网站按排名顺序输出.q PageRank 算法中使用的数学知识包括：正
34、矩阵性质、特征值和特征向量、幂迭代算法、Gauss-Seidel迭代算法等.q PageRank 得分是介于 0 和 1 之间的一个数,得分越大表示网页越重要.PageRank算法思想简介n PageRank基于假设关系 “许多优质的网页中超链接的网页，必定是优质网页”，以此判定所有网页的重要性。重要性由该网页被访问的概率大小来刻画。p导入链接数 单纯意义上的受欢迎度指标p导入链接是否来自受欢迎程度高的页面 有根据的受欢迎指标p导入链接源页面的导出链接数 被选中的概率指标通过转移概率矩阵来求n PageRank 是基于这样一个理论：p若 B 网页上有连接到 A 网页的链接(称 B 为 A 的导
35、入链接),说明 B 认为 A 有链接价值，是一个“重要”的网页.当 B 网页级别(重要性)比较高时,则 A 网页可从 B 网页这个导入链接分得一定的级别(重要性),并平均分配给 A 网页上的所有导出链接.p 在PageRank算法中,一个网页的级别(重要性)大致由下面两个因素决定：该网页的导入链接的数量和这些导入链接的级别(重要性).PageRank算法思想简介n 互联网是一个有向图n 每一个网页是图的一个顶点n 网页间的每一个超链接是图的一个有向边n 用邻接矩阵G来表示有向图,即，若网页 j到网页i有超链接,则gij=1,否则为gij=0.00010110000001000001100000
36、1000001010G PageRank计算邻接矩阵是一个十分庞大有相当稀疏的方阵(用黑色代表1,用白色代表0)PageRank计算n 用邻接矩阵G来表示图,即，若网页 j 到网页i 有超链接,则gij=1,否则为gij=0.n 定义矩阵G的列和与行和 其中 cj 是页面 j 的导出链接数目,ri 是页面 i 的导入链接数目.kjjkcg iikkrg 000101100000010000011000001000001010G n假设我们在上网的时候浏览页面并选择下一个页面,这个过程与过去浏览过哪些页面无关,而仅依赖于当前所在的页面,那么这一选择过程可以认为是一个有限状态、离散时间的随机过程,
37、其状态转移规律可用Markov链描述.n定义转移概率矩阵 ,1,2,ijijijjAai jNgac PageRank计算n但还要考虑到用户虽然在许多场合都顺着当前页面中的链接前进,但时常又会跳跃到完全无关的页面.n经过统计,Google采用个15%来表示时常,即用户在85%的情况下沿着链接前进,但有15%的情况下突然跳跃到无关的页面中去.n从而修正状态转移矩阵(1)pApAEN (1)ijijjapgcpN 即即，0.85,1pEN 其其中中是是全全是是 矩矩阵阵所所有有网网页页数数量量n根据Markov链的基本性质,以上A 是一个正则Markov链,存在平稳分布x=(x1,x2,x3,.,
38、xN)T,满足nx表示在极限状态(转移次数趋于无限)下各网页被访问的概率分布.nx定义为网页的PageRank向量,xi 表示第 i 个网页的PageRank值.显然概率越大,其重要性越高是合理的.,1iiA xxx n分量 x 应满足方程n从另一角度看,网页 j 将它的PageRank值 xj 分成 cj 份,分别“投票”给它链出的网页.n网页k 的PageRank值 xk 就是所有页面投票给网页k的最终值.111kjNjkkjjjjgxpxa xpNc ,1iiA xxx 由Markov性质,A 的最大特征值是1,即求特征值1对应的特征向量.问：上述方程组的解是否唯一解？解是否有意义(即不
39、会出现负数或大于1的数)？答：上述方程组的解唯一且分量都大于0！理由：Perron-Frobnius 定理.,1iiA xxx 解的讨论特征向量的计算需要采用幂迭代、Gauss-Seidel迭代等算法如果 A 是正的方阵(所有元素均大于0),则Perron-Frobnius 定理 A 的谱半径 (A)0，其中 ,1,2,.,n 为 A 的特征值。=(A)是 A 的特征值,且代数重数为 1,即为单特征值。存在唯一的 x 0,满足 A x=x,且 若 是 A 的特征值,且 (A),则|3的情况,第n条直线与原有n-1条直线都相交,最多分成n段.每1段都落在一个区域上,并该区域分为两块新区域！那么比
40、S(n-1)多出n块新区域.1S nS nn(1)1.2n n 21.nnC012.nnnCCC8.2 n个平面最多能将空间分为多少个区域F(n)?分析要满足任意三个平面交于一点,且无四平面共点的情况,才会出现最多的分割区域.设这样的n个平面把空间分成F(n)个区域.目标 F(n)=F(n-1)+?第n个平面被其它n-1个平面分成一些平面碎片,每个平面碎片把旧空间区域分成两块新的空间区域.因此关键在于第n个平面被其它n-1个平面分成多少个碎片(区域)？思路因此关键在于第n个平面被其它n-1个平面分成多少个碎片(区域)？第n个平面与其它n-1个平面各有一条交线,而且这些直线两两相交,且无三线共点
41、。这n-1条直线把第n个平面分成的区域个数为:(1)S n ()(1)(1).F nF nS n即即求解(0)1,(1)2,(2)4,(3)8FFFF由由得得()3,F n 应应该该是是个个 次次多多项项式式 设设为为32().F nAnBnCnD所所以以(1)(1)1.2n nF n()(1)(1).F nF nS n315()166F nnn0123.nnnnCCCC依次类推n个3-维超平面将4维空间分成的最大区域数为443()(1)(1)F nF nF n01234.nnnnnCCCCCn个(k-1)-维超平面将k维空间分成的最大区域数为 1()(1)(1)kkkFnFnFn012.kn
42、nnnCCCC特殊地,n个(n-1)-维超平面将n维空间分成的最大区域数为 012()nnnnnnCCnCCF 2.n附录：一阶差分方程的求解方法1nnnyayf 非齐次差分方程分类：10nnyay 齐次差分方程1.齐次差分方程的通解nnyAa 2.非齐次差分方程的通解,nnyy 设设是是齐齐次次通通解解是是非非齐齐次次特特解解.nnnyyy 则则非非齐齐次次的的通通解解附录：一阶差分方程的求解方法2.非齐次差分方程的通解.nnnyyy 则则非非齐齐次次的的通通解解1nnnyayf,nf根根据据的的形形式式 可可得得通通解解的的形形式式 1nfC 2nnfCb 3knfCn 1,1,1nnCa
43、AaayACna *1,nnnAbbayAnbba 0101,1(),1kknkkAA nA nayn AA nA na 1043,1nnhhnh 求求的的通通项项表表达达式式.例例：4,nnnhAhBnC 其其中中143,nnnhhhn 把把代代入入得得 4(1)3BnCB nCnnnnhhh 解解：(43)44BnCBnCB4344BBCCB 14 3BC 等式两端要恒成立.044 31,nnhAnh把把代代入入得得7 3.A 7344 3nnhn一般不需要记通解形式！1043,2nnnhhh 求求的的通通项项表表达达式式.例例：4,3,nnnnhAhB 其其中中143,nnnnhhh 把
44、把代代入入得得134 33nnnBB nnnhhh 解解：343BB等式两端要恒成立.10431,nnnhAh 把把代代入入得得5.A 1543.nnnh 3B 附录：二阶差分方程的求解方法2112nnnnya ya yf非齐次差分方程分类：21120nnnya ya y齐次差分方程1.齐次差分方程的通解 212100aa 实实根根情情况况2111 212111 224242aaa aaaa a 12nnnyab则则通通解解形形式式12,.a byy常常数数由由与与 的的值值来来确确定定1.齐次差分方程的通解 1nnyabn 则则通通解解形形式式12,.a byy常常数数由由与与 的的值值来来
45、确确定定112.2a 212200aa 重重根根情情况况1,2.iaa 212300aa 复复根根情情况况 nnnyaibiaaaa则则通通解解形形式式 cossinnnyranbn或或22,tanraa a a 12,.a byy常常数数由由与与 的的值值来来确确定定如如兔兔子子序序列列(斐斐波波那那契契数数列列)1201,2,3,1,2.nnnyyynyy 数数列列为为210解解特特征征方方程程1,2152 一对小兔到第二个月长成大免子，第三个月生下一对小免子。每对小兔子到第二个月都长成大兔子，并且到第三个月也生下一对小兔子。假设这些兔子没有死亡，且总能繁衍后代。那么，逐月的兔子对数就构成
46、了以上数列。1,2,3,5,8,13,21,34,55,89,144,233,12.nnnyab1,2,3,5,8,13,21,34,55,89,144,233,兔兔子子序序列列(斐斐波波那那契契数数列列)1201,2,3,1,2.nnnyyynyy 数数列列为为210解解特特征征方方程程1,2152 151522nnnyab则则011,2,yy由由15152 52 5,.ab 111515112255nnny2.非齐次差分方程的通解,nnyy 设设是是齐齐次次通通解解是是非非齐齐次次特特解解.nnnyyy 则则非非齐齐次次的的通通解解21nnnnyaybyf 1,nmfPnnm 当当的的 次
47、次多多项项式式01i)1,;mnmyBB tB n 当当时时01ii)1();mnmyn BB tB n 当当是是单单根根,201iii)1();mnmynBB tB n 当当是是二二重重根根，2.非齐次差分方程的通解,nnyy 设设是是齐齐次次通通解解是是非非齐齐次次特特解解.nnnyyy 则则非非齐齐次次的的通通解解21nnnnyaybyf 2,nnmfPn C 当当01i)1,();mnnmyBB tB nC 当当时时01ii)1();mnnmyn BB tB nC 当当是是单单根根,201iii)1();mnnmynBB tB nC 当当是是二二重重根根，此部分内容不作要求1.有20级
48、台阶,一个人用每次走一级或走两级的方式从台阶最下面往上走,问一共有多少种不同的方式走到台阶的最高一级?2.在空间中,两两相交的n个平面最多可以产生多少条不同的交线?3.n个圆最多可将将平面分割成多少个区域?4.塔问题:3个柱子A,B,C,开始时有n个大小不同盘子放在A柱上,现在要求把这n个牌子移到C柱子上,问最小的移动步数.(要求在柱子上大盘子只能放在小盘子下面,可以借助B柱子中转)思考与练习5.求n条折线分割平面的最大数目.比如,1条折线可以将平面分成两部分,2条折线最多可以将平面分成7部分,具体如下所示.(HDU 2050)6.求以下数列的表达式 (1)hn=2hn-1+hn-2 2hn-3 (h0=1,h1=2,h2=0)(2)hn=4hn-1 4hn-2 (h0=1,h1=2)(3)hn=3hn-1 4n (h0=2)(4)hn=2hn-1+3n (h0=2)7.只有三个字母a,b,c组成的长度为n的一些单词将在通信信道上传输，满足条件：传输中不得有两个a连续出现在任意单词中。确定通信信道允许传输的单词个数。8.令hn表示具有n+2条边的凸多边形区域被其对角线所分成的区域数,假设没有三条对角线共点.定义h0=0.求hn的递推表达公式与通项公式.
