第三讲方程组的背景及计算

数学建模与实验主讲人：宋叔尼教授2009年3月第三讲与方程组有关的问题数学必须解决实际问题首届国家最高科学技术奖获得者、中国科学院院士吴文俊指出：任何数学都要逻辑推理，但这只是问题的一个方面，更重要的是用数学去解决问题，解决日常生活及其他学科中出现的数学问题。学校给的数学题目都是有答案的，已知什么，求证什么，都是清楚的，题目也一定是做得出的。但是将来到了社会上，所面对的问题大多是预先不知道答案的，甚至不知道是否会有答案。这就要求培养学生的创造能力，学会处理各种实际数学问题的方法。什么是数学建模与实验众所周知，学习物理要做物理实验，学习化学要做化学实验，为适应现代科学技术的发展，学习数学也需要做数学实验。传统数学的教学体系和内容侧重于培养学生准确、快捷的计算和严密的逻辑推理。如何运用所学的数学理论将一个实际问题用适合的数学语言描述？如何运用计算机求解该问题？如何结合实际问题对所求解进行分析和修正？这些综合起来就是数学建模与实验。目次试验项目授课教师一数学建模初步韩铁民二Matlab使用简介方程组计算薛定宇宋叔尼三线性规划非线性规划张薇四数理统计孙平五MATLAB求解薛定宇六图论孙艳蕊七组合数学张祥德八模糊数学张国伟课程内容1.介绍数学建模过程中基本的数学方法(32学时)2.(测验，同时选拔部分队员培训(案例教学))3.竞赛题讲解（8月底）许多实际问题可以归结为方程组的求解例如：冶金工程、机械结构、大型的土木结构、最优控制大型输电网络、图像处理、种群繁殖、经济规划等。1.投入产出分析1949年，哈佛大学教授Leontief把美国经济分解成500个部门(如农业、制造业、服务业等)，对每个部门，其产出如何分配给其它经济部门？构建了500个未知数，500个方程的方程组，受计算机的限制只好把问题简化为42个未知数，42个方程的方程组。该成果获1973年诺贝尔经济学奖。下面假设：经济体系中仅由农业、制造业、服务业构成，这些部门生产商品和服务。产出投入农业制造业服务业外部需求总产出农业15203035100制造业301045115200服务业2060070150初始投入3511075总投入100200150各部门间的投入产出平衡关系上表中第一行表示农业总产出为100时，15农产品用于农业生产，20用于制造，30用于服务，35用于外部需求。1.给定外部需求，建立求解各部门总产出模型。2.如果对农业、制造业、服务业的外部需求分别为50，150，100，问三个部门的总产出分别应为多少？3.若三部门外部需求分别增加1单位，总产出应增加多少？4.若对任意给定的非负外部需求，都能得到非负总产出，称模型可行。为使模型可行，应满足什么条件？问题产出投入农业制造业服务业外部需求总产出农业15203035100制造业301045115200服务业2060070150初始投入3511075总投入100200150设有n个部门，第i个部门的总产出为xi，用于(投入到)第j个部门xij，外部需求为di，则iiiniixdxxx21假设每个部门的产出与投入成正比，即xij/xj为常数，记为aij.1.给定外部需求，建立求解各部门总产出模型121,2,,iiiniixxxdxin11221,2,,iiinniiaxaxaxdxin转换成记投入系数矩阵，产出向量()ijAa12(,,,)Tnxxxx12(,,,)Tndddd需求向量，则方程组记为Axdx即()IAxd这就是线性代数方程组。产出投入农业制造业服务业农业0.150.100.20制造业0.300.050.30服务业0.200.300投入产出系数表产出投入农业制造业服务业外部需求总产出农业15203035100制造业301045115200服务业2060070150初始投入3511075总投入100200150各部门间的投入产出平衡关系0.150.100.200.300.050.300.200.300A得到数学模型（线性方程组）1230.850.100.20350.300.950.301150.200.301.0070xxx1230.850.100.20500.300.950.301500.200.301.00100xxx2.如果对农业、制造业、服务业的外部需求分别为50，150，100，问三个部门的总产出分别应为多少？用MATLAB求出即可3.若三部门外部需求分别增加1单位，总产出应增加多少？00()IAxd()IAxd得()IAxd令(1,1,1)d求解x4.若对任意给定的非负外部需求，都能得到非负总产出，称模型可行。为使模型可行，应满足什么条件？要使模型可行，即对任意的外部需求得.0d0x由知，如果(即每个元素非负).1()xIAd1()0IA即满足结论.21()()kkIAIAAAIA如果，就有0kA1()0IA如果，必有.1A0kA11nijia得到这等价于11,2,,nijjixxjn又因为数学模型还没有一个统一的准确的定义，我们这样理解:数学模型是关于部分现实世界和为一种特殊目的而作的一个抽象的、简化的结构。数学建模就是为了某种目的，用字母、数学及其它数学符号建立起来的等式、不等式、图表、图象、框图等描述客观事物的特征及其内在联系的数学结构表达式。一般来说数学建模过程如下：实际问题模型假设模型建立模型求解模型分析检验与评价应用设A，B是重力场中给定的两点，且A点高于B点，B点不正好位于A点下方。2最速降线问题一个在A点静止的质点在重力作用下沿着怎样的路线C无摩擦地从A点滑到B点，才能使所花的时间最短？该曲线C称为最速降线。如何求出该曲线？ABC2.1问题的提出)(xyy0)0(y1)(yaydxdtydtdsv21dxvydt21Tadxvy021考虑连接A,B的曲线显然，质点运动的速度s这里表示弧长。因此故所需时间为ABCxy构造坐标系dsdymgmgdtsdmcos22y设曲线上一点处的切线与轴方向的夹角为；mg设质点的质量为，重力加速度为；由牛顿运动第二定律两端同乘以，则dtds2dtdygdtdsdsdygdtsddtds22222两边积分，则有Cgydtds220C但已设初速为零，故，gyv2从而.adxgyyT02210)0(y1)(yay于是我们的问题便是在条件，之下寻求使)(xyy取最小的函数。Ty由上可知，是的函数，yx同时是的函数；yT因此是函数的函数。yT工程上常常称是的泛函。记为adxgyyyJT0221)(2.2求解问题的初步设想AB先考虑从到的以下曲线：(i)直线段；(ii)圆弧(自己选择一条)；(iii)抛物线(自己选择一条)；分别计算所花的时间（练习）。axxxxxnn12100a,01kkkxxdn这样将分成个小段，每段长度。nnankaxk将区间等份，每段长度等于，而a,01n)11(nkxk在区间内插入个分点，使nk0对成立。此时，曲线相应地被分成小段：Cn)()(:1kkkxxxxfyC2.3近似计算注意和不能改变，是固定点。00yhynBAAAn,0)(kkxfykA),(kkyx记，是坐标为的点。kAkyC而其余及纵坐标随着曲线的不同而改变。nkd如果比较大，并且每个都比较小，则kC1kAkA可近似地看成从到的直线段。质点在，两点的速度分别是，；12kgykgy21kAkA在直线段内的平均速度为1kAkA2/)22(1kkgygy121222)(2~kkkkkkgygyyydTnkkTT1~~质点经过这条直线段的时间是T总时间近似地等于T这样即求出了的值．求合适的使最小.12,,nyyynkkTT1~~3.多元函数的极小值问题（非线性方程组的计算问题）3.1函数的极小值问题与方程求根一元函数极值转化为函数方程求根多元函数极值问题转化为求非线性方程组解的问题12(,,,)nxxx设在取极小值，则00012(,,,)nxxx00012(,,)01,2,,nixxxinx设在取极小值，则()yx0x0()0x即求f(x)=0的根.12(,,,)01,2,,infxxxin3.2Newton迭代法3.2.1Newton迭代公式设(x)在有根区间[a,b]上二阶连续可微,给定根的某个近似值x0（初值）,200000)(2)())(()()(xxfxxxfxfxf取(x)(x0)+(x0)(x-x0),方程(x)=0近似为(x0)+(x0)(x-x0)=0若(x0)0,其解为因为)()(0001xfxfxx得到根的新的近似值x1,一般地,在xk附近线性化方程为(xk)+(xk)(x-xk)=0设(xk)0,其解为迭代格式称为Newton迭代法.xyox0y=(x)x1x2直线y=(x0)+(x0)(x-x0)就是y-(x0)=(x0)(x-x0)Newton迭代法也叫切线法.k,2,1,0,)()(1kxfxfxxkkk设(x)在根附近具有二阶连续导数,则对充分接近的初值x0,Newton迭代法产生的序列xk收敛于,且定理)(2)()(lim21ffxxkkk例用Newton迭代法求方程xex-1=0在0.5附近的根.3.2.2Newton迭代法的收敛性例用Newton迭代法求8x5-12x4-26x3-13x2+58x+30=0的根,在1.5附近的根.为了简化计算(xk),采用格式,2,1,0,)(1kMxfxxkkk称为简化Newton迭代法.oxyy=(x)x0x1x2x3在区间I=[-,+]上,取M与(x)同号,且M1/2max|(x)|时,简化Newton迭代法对x0I收敛.通常取M=(x0).简化Newton迭代法一般只具有线性收敛.简化Newton迭代法非线性方程组的求解112(,,,)0nfxxx212(,,,)0nfxxx12(,,,)0nnfxxx11112211nnaxaxaxb21122222nnaxaxaxb1122nnnnnnaxaxaxb11211(,,)(,,)()0(,,)nnnnfxxfxxfxfxxAxb向量记法对于函数方程f(x)=0,如果(xk)0,其近似解为迭代格式称为Newton迭代法.,2,1,0,)()(1kxfxfxxkkkk12kkkknxxxx11211(,,)(,,)()(,,)kknkkknkknnfxxfxxfxfxx11()()kkkkxxfxfx1,2,k上式改为111122221212()nknnnnnfffxxxfffxxxfxfffxxx1(,,)kknxxHessen矩阵11()()kkkkxxfxfx1,2,k例用Newton迭代法求解非线性方程组2211212212121(,)5=0(,)(1)310fxxxxfxxxxx在初值(1,1)的解。例用Newton迭代法求解非线性方程组211211222121121(,)3ln=0(,)2510fxxxxxfxxxxxx在初值(2,2)附近的解。理论问题收敛性，收敛区域，修改方法