数值计算课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数值计算方法,机械工业出版社,1,第,1,章,数值计算引论,第,2,章 非线性方程的数值解法,第,3,章 线性代数方程组的数值解法,第,4,章 插值法,第,5,章 曲线拟合的最小二乘法,第,6,章 数值积分和数值微分,第,7,章 常微分方程初值问题的数值解法,数值计算方法,2,第,1,章,数值计算引论,1.1,数值计算方法,1.2,误差的来源,1.3,近似数的误差表示法,1.4,数值运算误差分析,1.5,数值稳定性和减小运算误差,3,第,1,章,数值计算引论,数值计算方法与误差分析,理工科大学本科生,科学研究。,现代科学研究的三大手段,理论分析、科学实验、科学计算。,1.1,数值计算方法,1.1.1,数值计算方法及其主要内容,1.,课程名称：科学与工程数值计算方法,简称：科学计算、科学与工程计算、数值分析、计算方法、数值计算方法。,科学与工程：从实用的角度，将科学研究与工程技术上遇到的实际问题用数学模型来描述，以便进行定量的分析、研究。,4,数值：数、数字，由,0-9,十个数字、小数点和正负号等组成的数。,计算方法：解题的方法。可以用自然语言、数学语言或约定的符号语言来描述。,计算：只能包括计算机能够直接处理的运算,即加减乘除等基本运算。,数值计算：相对于非数值计算，如查表、排序等。用（,0-9十个数字、小数点、正负号等组成的）数，通过计算机进行加减乘除等基本运算。,2,。数值算法：对科学研究与工程技术上遇到的实际数学问题的解法归结为用数值进行加减乘除等基本运算，并有确定运算顺序，完整而准确的描述称为数值算法。,数值计算方法是研究用数字计算机解决数学问题的数值算法及其理论的一门课程。,5,3.,主要内容：工程上遇到的数学问题,数值计算的误差分析,非线性方程,线性方程组,插值法,最小二乘法,数值积分和数值微分,常微分方程,1.1.2,用计算机解题的步骤,当给定一个科学研究与工程技术上遇到的实际问题时，首先根据专业知识建立实际问题的数学模型，即模型化（,modeling,),或建模。然后对数学模型进行求解。,数学模型（包括公式、表格、图形等）求解有两条途径：求解析解和数值解。,6,求解析解，解以表达式表示，这是准确解。,求数值解，解是以一些离散点上取值的形式表示，多数情况下，数值解是近似的，求数值解要用计算机。求数学模型数值解的方法称为数值计算方法。,选择计算方法以后进行程序设计，即用程序语言把算法编成程序，然后上机得出数值解。,实际问题,-,数学问题,(,建模,)-,构造数值计算方法,-,程序设计,-,上机计算,-,数值解,-,结果分析,7,1.1.3,数值计算的特点：对算法的要求。,1.,只能包括计算机能够直接处理的运算,即加减乘除等基本运算。,2.,能任意逼近并达到精度要求，对近似算法要保证收敛性和稳定性。,3.,计算时间少，存储空间小。,4.,数值试验证明算法有效。,8,误差的来源即产生误差的原因。主要有四种：,1.,模型误差,-,建立的数学模型和实际的距离，客观量的准确值与数学模型的准确解的差。,例如自由落体运动方程,1-2,误差的来源,9,2.,观测误差：数学模型当中的参数或常数常常是是观测或实验来的，这样必然有误差，称为观测误差或测量误差，由观测数据而产生的误差。,例如自由落体运动方程,10,3.,截断误差,(,方法误差,)-,数学模型的准确解与利用数值计算方法得到的准确解之差。,无穷过程用有穷项代替,例如,:,无穷级数,取前,n,项代替,截断误差用有限的过程代替无限的过程，和用简单的计算问题,代替复杂的计算问题所产生 的误差。,11,4.,舍入误差：计算工具字长是有限位，在计算时只能对有限位数字进行运算，超过这个位数时，要舍入，于是产生舍入误差。原始数据、中间步骤和最终结果都可能产生舍入误差。,如圆周率,3.14159265,一般实数不能精确存储，例如：在,10,位十进制数限制下：,12,1-3,近似数的误差表示,13,14,15,16,17,18,1.3.2,相对误差,19,20,21,22,23,1.3.3,有效数字：由绝对误差决定。,24,若近似值,x,*,的绝对误差,(,限,),是某位的半个单位，则说,x,*,精确到该位，若从该位到,x,*,的左面第一位非零数字一共有,n,位，则称近似值,x,*,有,n,位有效数字。,25,26,27,1.,用四舍五入得到的近似数的误差限是末位的半个单位。近似数的误差限是末位的半个单位，则有,n,位有效数字。因此用四舍五入得到的近似数是有效数字。,2.,在公式运算中，要先区分准确量和近似数。准确数有无穷多位有效数字,.,3.,有效数字位与小数点后有多少位数无直接关系。,28,1.3.4,有效数字与相对误差,29,30,31,32,1.,定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。,2.,在实际应用时，为了要使所取近似数的相对误差满足一定要求，可以用定理，确定所取近似数应具有有效数字的位数。,33,34,35,1.,定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。即若近似数有,n,位有效数字，相对误差不一定满足定理。,2.,在实际应用时，为了要使所取近似数具有,n,位有效数字，要求所取近似数的相对误差满足定理的要求。,36,1.4,数值运算误差分析,函数运算误差,算术运算误差,37,1.5,数值稳定性和减小运算误差,在计算过程中误差不会扩大或对计算结果的精度要求影响不大。,减小运算误差,:,1,要避免两相近数相减。,2,要防止大数吃掉小数。,3,要避免除数绝对值远小于被除数绝对值。,4,注意简化计算步骤，减少运算次数。,38,例：计算积分写成递推公式,误差传递规律,公式改为,则误差按规律,逐渐缩小,1.5.1,数值稳定性,:,一个算法，如果计算结果受误差的影响小，就称这个算法具有较好的数值稳定性。否则，就称数值稳定性不好。因此要设法控制误差的传播。,39,1.5.2,减小运算误差,1.,要避免相近两数相减,13.5846-13.5839=0.0007,6,位有效数字变成了,1,位有效数字。损失了有效数字的位数。,当,x,接近于,0,时，应,40,例 解一元二次方程,a,x,2,+bx+c=0,，,其中,-,b,c,2,要防止大数,“,吃掉,”,小数，注意保护重要物理参数。,在,8,位十进制计算机上计算。要规格化和对阶。,结果大数“吃掉”小数。,类似地,改变计算方法,41,例 在,5,位十进制计算机上计算,在,5,位十进制计算机上计算。要规格化和对阶。,结果，,大数“吃掉”小数。,改变计算方法，按绝对值由小到大相加。,42,3,注意简化计算步骤，减少运算次数，避免误差积累,例：计算 的值。,又如,只需,14,次乘法。,43,采用“秦九韶算法”,例：计算多项式,只需,n,次乘法和,n,次加法。,44,第,2,章 非线性方程的数值解法,2.1,初始近似值的搜索,2.2,迭代法,2.3,牛顿迭代法（切线法）,2.4,弦截法（割线法）,45,2.1,初始近似值的搜索,2.1.1,方程的根,46,单根和重根,47,48,49,有根区间,50,假设,f(x),在区间,a,b,内有一个实根,x,*,若,b,a,较小，则可在,(a,b),上任取一点,x,0,作为,初始近似根。,一般情形，可用逐步搜索法。,2.1.2,逐步搜索法,51,52,例 对方程 搜索有根区间。,解 由于,f(x),是连续函数，,f,(,0,)=-10,，故方程,至少有一正实根。设从,x=0,出发，取,h=0.5,为步长，逐步,右跨搜索，得,x,0 0.5 1.0 1.5,f(x),+,所以,f(x),在区间（,1,1.5,）上单调连续，因而在,(1,1.5),内有且仅有一个实根，故可取,1,1.5,上任一点做初始近似根。,可见在（,1,，,15,）内有根。又,53,54,2.1.3,区间二分法,定理 函数,f,(,x,),在,a,b,上单调连续，且,f(a)f(b),0,，则方程,f(x)=0,在区间,a,b,上有且仅有一个实根,x,*,。,二分法的基本思想,将有根的区间二分为两个小区间，然后判断根在那个小区间，舍去无根的小区间，而把有根的小区间再一分为二，再判断根属于哪个更小的区间，如此反复，直到求出满足精度要求的近似根。,55,令,近似根,x,k,的误差估计,中点,这时有三种情况：,f(x,0,),=,0,x,0,为所求的根,.,f(x,0,),和,a,0,同号，取,x,0,=,a,1,f(x,0,),和,b,0,同号，取,x,0,=,b,1,x,*,x,*,新的有根区间为,(,a,1,b,1,),，长度是原来的一半。,56,如此反复，有,(a,k,b,k,),k=0,1,2,.,近似根,x,k,的误差估计,57,第,2,次二分，取中点,若,f(a,1,)f(x,1,)0,，则,x,*,(a,1,x,1,),，,令,a,2,=a,1,b,2,=x,1,；,否则 令,a,2,=x,1,b,2,=b,1,。,新的有根区间为,(,a,2,b,2,),。,58,由此得,二分过程结束的原则：,先给定精度要求,(,绝对误差限,),，,（,2,）,当,|b,k+1,a,k+1,|,时结束二分计算，取,x,*,x,k,；,（,1事先由,估计出二分的最小次数,k,，,取,x,*,x,k,59,60,61,62,63,64,65,66,2.2,迭代法,2.2.1,迭代原理,2.2.2,迭代的收敛性,2.2.3,迭代的收敛速度,2.2.4,迭代的加速,67,预备定理,68,2.2.1,迭代原理,69,计算结果见下表,70,方程,f,(,x,)=0,化为等价形式的方程,x=,(,x,),，,构造迭代公式,x,k+,1,=,(,x,k,),k,=0,1,2,取初始近似根,x,0,进行迭代计算,x,1,=,(,x,0,),x,2,=,(,x,1,),.,则有,x,1,x,2,.,x,k,.,得到迭代序列,x,k,.,如果这个序列有极限，则迭代公式是收敛的。这时,则 ，,x,*,为不动点，等价地有,f,(,x,*,)=0,x,*,即为方程的根。连续函数,(x),称为迭代函数。,实际计算到,|,x,k,x,k,-1,|,（,是预定的精度），取,x,*,x,k,。,71,迭代公式收敛,指迭代序列,x,k,收敛，,迭代公式发散,指迭代序列,x,k,不收敛，即发散。迭代公式不一定总是收敛。,例如求方程,f,(,x,),=x,3,-x,-1=0,的一个根,。,对应的迭代公式为,取初值,迭代序列,x,k,发散,.,72,73,x,1,=,(x,0,),x,2,=,(x,1,),迭代法收敛与发散的图示,74,迭代法的收敛与发散,收敛的情形 发散的情形,75,2.2.2,迭代的收敛性,迭代法的收敛条件及误差估计式,定理（充分性条件）,设函数,(x),在,a,b,上连续，且,(1),对,x,a,b,有,(,x,),a,b,(2),存在,0 L 1,，使对任意,x,a,b,有,|,(,x,),|L 1,则方程,x=,(x),在,a,b,上的根,x,*,存在且唯一；对初值,x,0,a,b,迭代过程,x,k,+1,=,(,x,k,),均收敛于方程的根,x,*,。,76,定理中的,(1),对,x,a,b,有,(x),a,b,，称为适定性（映内性）。,77,证明,先证根的存在性。,作连续函数,(,x,),=x-,(,x,),由条件1,）,x,a,b,(,x,),a,b,，即,a,(,x,),、,xb,于是,(,a,),=a-,(,a,)0,(,b,),=b-,(,b,)0,由于,(,x,),是连续函数，故必存在,x,*,a,b,使,(,x,*,)=0.,即,(,x,*,)=,x,*,-,(,x,*,)=0,.,于是,x,*,=,(,x,*,),即,x,*,为方程,x=,(,x,),的根。,其次，证根的唯一性。,设,y,*,也是方程的根，则,x,*,=,(x,*,),y,*,=,(y,*,),x,*,-y,*,=,(x,*,),(y,*,)=,()(x,*,-y,*,),x,*,-y,*,()(x,*,-y,*,)=0,，,（,x,*,-y,*,）,1-,(,)=0,由条件（,2,）,|,(x)|L 1,，,故有,x,*,-y,*,=0,，,即,x,*,=y,*,所以方程在,a,b,的根唯一,。,78,再证迭代的收敛性。,由,x,k,=,(x,k-1,),x,*,=,(x,*,),有,|,x,k,-x,*,|=|,()(x,k-1,-x,*,)|L|x,k-1,-x,*,|,L,2,|x,k-2,-x,*,|,L,3,|x,k-3,-x,*,|,L,k|,x,0,-x,*,|,0,（,k,）,所以，对,a,b,上任取的,x,0,迭代公式,x,k+,1,=,(x,k,),都收敛于,x,*,。,L,越小收敛得越快。,定理是充分性条件,x,k,-x,*,=,(x,k-1,),(x,*,)=,()(x,k-1,-x,*,),79,推论：在定理的条件下，有误差估计式,验后误差估计式,验前误差估计式,证明：,|,x,k,-x,*,|L|x,k-1,-x,*,|=L|x,k-1,-x,k,+x,k,-x,*,|,L,（,|x,k,-x,*,|+|x,k-1,-x,k,|,）,（,1-L)|x,k,-x,*,|L|x,k-1,-x,k,|,迭代法的终点判断：只要相邻两次迭代值的偏差充分小，就能保证迭代值足够准确，因而用,|x,k,-x,k,-1,|,控制迭代过程的结束。,80,定理,设在区间,a,b,上方程,x=,(,x,),有根,x,*,且对一切,x,a,b,都有,|,(,x,)|1,，则对于该区间上任意,x,0,(,x,*,),迭代公式,x,k,+1,=,(,x,k,),一定发散。,证明,不可能收敛于,0,。,81,82,83,计算结果见下表,取方程的根,2.0946,。,84,85,由于 ，故取,86,迭代法的,局部收敛性,87,由于在实际应用中根,x,*,事先不知道，故条件,|,(x,*,)|1,无法验证。但已知根的初值,x,0,在根,x,*,邻域，又根据,(x),的连续性，则可采用,|,(x,0,)|1,来代替,|,(x,*,)|1,，判断迭代的收敛性。,88,例,求方程,x=,e,x,在,x=0.5,附近的一个根，按,5,位小数计算，结果的精度要求为,=10,3,.,解,迭代公式,x,k+,1,=e,x,k,，,取,(,x,)=e,x,迭代公式,x,k,+1,=e,x,k,收敛。,89,迭代结果,:,0,1,2,3,4,5,0.5,0.606 53,0.545 24,0.579 70,0.560 07,0.571 17,0.106 53,0.061 29,0.034 46,0.019 63,0.011 10,6,7,8,9 10,0.564 86,0.568 44,0.566 41,0.567 56,0.566 91,0.006 31,0.003 58,0.002 03,0001 15,0.000 65,k,x,k,x,k,x,k-1,x,k,x,k-1,k,x,k,|x,10,-x,9,|=0.000650,),解,的正实根。因为,f(x)=2x,，,由牛顿迭代公式得,当,a=115,时，取初值,x,0,=10,，迭代,4,次可得,10,，,10.7500,，,10.723837,，,10.723805,，,10.723805,10.723805,是否还能用牛顿法计算一个正数的立方根？,115,则,x,3,-3=0,求,等价于求方程,令,例,用牛顿迭代法求,解,的正实根。由牛顿迭代公式得,当,a,=4111.7910,时，取初值,x,0,=8,，迭代,4,次可得,7.48,，,7.439977,7.439760,7.439760,116,令,例,用牛顿迭代法造倒数表，计算,解,117,3,、牛顿迭代法的计算步骤,(1),给出,x,0,，,N,(2),计算,(3),若,则转,(4),；否则,，转,(2);,(4),输出,x,1,结束。,118,牛顿迭代法局部收敛,:,2.4.2,牛顿迭代法的收敛情况,1.,局部收敛性,119,120,结论：,f(x)=0,的单根,x,*,附近存在着连续的二阶导数，当初值在单根,x,*,附近时，牛顿法具有平方收敛速度。,证,牛顿法迭代函数,当,f(x,*,)=0,，而,f,(x,*,)0,，则,x,*,是,f(x)=0,的单根,单根,x,*,附近存在着连续的二阶导数，有,牛顿法至少具有平方收敛速度。,121,122,123,124,125,2.3.3,牛顿迭代法的修正,1,.,简化牛顿法,(,平行弦法,),126,2,.,牛顿下山法,127,128,129,130,131,132,133,134,135,136,137,138,139,140,在牛顿法基础上，构造既有较高的收敛速度，又不 需要求导数的迭代公式。,公式的推导,用差商,则得两个弦截迭代公式,2.5,弦截法（割线法）,单点弦法,双点弦法,141,142,143,例,用单点弦截迭代法求方程,x,3,-0.2x-1.2=0,在,x=1.5,附近的根解,弦截迭代公式,据题意，取,x,0,=1.5,f(,x,0,),=1.425,代入单点弦迭代法所以有,k,1,2,3,4,5,6,7,x,k,1,1.150,1.190,1.193,1.198,1.199,1.200,144,145,例,用双点弦截迭代法求方程,xe,x,-1=0,在,x=0.5,附近的根,。,解,弦截迭代公式,方程化为,x-e,x,=0,令,，,代入双点弦迭代法,k,x,k,0,1,2,3,0.5,0.6,0.567 54,0.567 15,146,第,3,章 线性代数方程组的数值解法,3.1,高斯消去法,3.2,矩阵三角分解法,3.3,平方根法,3.4,向量和矩阵的范数,3.5,方程组的形态和误差分析,3.6,迭代法,3.7,迭代法的收敛性,147,矩阵形式,Ax=b,其中,n,个未知量,n,个方程的线性代数方程组,或写成,148,149,两类数值解法：,直接解法,:,假定计算过程没有舍入误差的情况下，经过有限步算术运算后能求得线性方程组精确解的方法。,经过有限步运算就能求得精确解的方法，但实际计算中由于舍入误差的影响，这类方法也只能求得近似解；,例如：高斯消去法、三角分解法等。,迭代解法,:,构造适当的向量序列，用某种极限过程去逐步逼近精确解。,例如：雅可比迭代法、高斯,-,赛德尔迭代法等。,150,上三 角形方程组,回代求解，得,151,152,下三角形方程组,顺代可求得,153,154,上二对角方程组,回代求解，得,155,156,下二对角方程组,顺代可求得,157,3.1,高斯消去法,3.1.1,顺序,高斯消去法,(,按方程和未知量的自然顺序进行,),基本思想：用逐次消去未知数的方法把原方程组化为上三角形方程组进行求解。求解 分成两步：,1.,消元过程：用初等行变换将原方程组的系数矩阵化为上三角形矩阵（简称上三角阵）。,2.,回代过程：对上三角形方程组的最后一个方程求解，将求得的解逐步往上一个方程代入求解。,158,顺序高斯消去法消元过程,:,依从左到右、自上而下的次序将主对角元下方的元素化为零。,1,不作行交换。,2,用不等于零的数乘某行，加至另一行。,159,160,161,系数行列式的计算：,例,消元过程,主元为,2,，,2.5,，,0.6,det A=22.50.6=3,162,163,消元过程,164,165,回代过程,166,顺序高斯消去法的,使用条件 使用条件之一,定理,线性方程组系数矩阵,A,的顺序主子矩阵,A,k,(,k,=1,2,n,),非奇异，则顺序高斯消去法能实现方程组的求解。,即方程组能用顺序高斯消去法求解的充要条件是系数行列式的顺序主子式非零。,167,高斯消去法能按顺序进行到底的充要条件是,在原方程组的系数矩阵中如何反映出这个条件呢,?,A,的,k,阶顺序主子矩阵,A,k,的行列式,168,使用条件之二,n,阶矩阵,A,为严格对角占优矩阵是指其每个主对角元的绝对值大于同一行其他元素绝对值之和，即,一阶严格对角占优矩阵指一个非零数。,169,定理 方程组系数矩阵,A,为严格对角占优矩阵则可实现,用顺序高斯消去法求解。,170,171,172,3.1.2,列主元高斯消去法,为什么列选主：数值不稳定,当高斯消去法的主元 时,尽管“,当,A,非奇异时，,det A0,，方程组有唯一解,”,，也不能实现,高斯消去法求解。,例 ，,A,非奇异，,det A0,，方程组有,唯一解，但 ，不能实现,高斯消去法求解。,173,高斯消去法的主元 ，但绝对值很小时，用绝对值小的数做除数，会导致其它元素数量级的严重增长和舍入误差的扩大。,174,列选主高斯消去法：避免用绝对值小的元素，作除数。,每次消元前选取一列中绝对值最大的元素作为主元素。用这个主元素作除数，这样便可以减少舍入误差。,列选主高斯消去法的优越性，不增加求解过程的运算量，而大大减小误差。,175,176,例,用列主元高斯消去法求解方程组,(,用三位有效数字计算,),解,选主元,选主元,177,消元过程完成，得到上三角形方程组,再作回代可求得,178,行列式的计算：,列主元法的消元过程,计算过程有,2,次行交换，故,m,=2,，主元为,5,，,-1.6,，,2,det,A=,(-1),2,5(-1.6)2=16,m,为消元过程中交换行的次数。,179,列主元高斯消去法,(,简称列主元消去法,),的计算框图,d,:,绝对值最大的主元素的存储单元。,l,:,绝对值最大的主元素所在的行的存储单元。,180,定理,系数矩阵为对称严格对角占优，则全是主元。,181,3.1.3,高斯,-,约当,(Jordan),消去法,1,。方法的描述,消元时将主元上方元素也消为,0,，最后系数矩阵化为对角矩阵。这种算法只有消元，没有回代，这种方法称做高斯,-,约当,(Jordan),消去法。,182,183,184,185,186,2,。归一方法,消元时将主元上方也消为,0,，并将第,k,行除以,a,kk,(,k,=1,2,n,),，使主元位置化为,1,，最后系数矩阵化为 单位矩阵。这种方法无须回代，称做归一的,高斯,-,约当,(Jordan),消去法,。,187,归一方法的例子,188,3,。列选主高斯,-,约当,(Jordan),消去法,。,189,190,4,。高斯,-,约当,(Jordan),消去法的计算量,191,5,。高斯,-,约当,(Jordan),消去法求逆矩阵,当,det,A,0,时，,A,存在逆矩阵，设,s=1,2,n,求,A,-1,就相当于求解,n,个线性方程组,192,高斯,-,约当,(Jordan),消去法求逆。,193,194,3.2,矩阵,三角分解法,195,。,定义 将矩阵,A,分解成一个下三角阵,L和一个上三角阵,U,的乘积，即,A=LU,称为,A,的三角分解或,LU,分解。,196,197,。,例如,A=,这里有,A,的两种不同的三角分解，类似可举出很多，一般，若,A=LU,是一个三角分解，任取与,A,同阶的非奇异对角矩阵,D,，则,A,=(,LD,)(,D,-1,U,)=,L,1,U,1,也是,A,的三角分解。,198,。,杜利特尔分解,(Doolittle),常用的两种三角分解,克洛特分解,(Crout),199,定理,n,阶矩阵,A,存在唯一的杜利特尔分解或克劳特分解的充要条件是,A,的顺序主子矩阵,A,k,(,k,=1,2,n,-1),非奇异。,200,例 设 讨论,a,取何值时，,矩阵,A,可作,LU,分解。,解,当,A,的,顺序主子式不为零，,矩阵,A,有,LU,分解。,所以，有,201,非奇异矩阵不一定存在,LU,分解。例,解,A,是,非奇异矩阵，假设有,LU,分解（,杜利特尔分解）,比较等式两端第,1,列，可得,上二式不能同时成立，即非奇异矩阵,A,不存在,LU,分解。,202,复习：矩阵乘法,A=BC,203,3.2.2Doolittle,分解步骤,A=LU,204,令,i=r,r+1,n,，,(,即,i,大于等于,r,),205,206,207,例,208,紧凑格式,209,210,211,212,213,3.2.3,用,三角,分解求解线性方程组,设,A,非奇异，并有三角分解,A=LU,，则方程组,Ax=b,就化为,LUx=b,只须求解两个简单的三角形方程组：,（,1,）解,Ly=b,顺代求出,y,（,2,）解,Ux=y,，回代求出,x,.,214,求得,L,、,U,后再求解方程组,Ly=b,Ux=y,215,216,例 用杜利特尔分解法求解方程组,解 先对系数矩阵进行杜利特尔分解,A=LU,217,218,求解两个三角形方程组，,得,219,方程组,Ax=b,化为,Ux=y,时，,A,通过,LU,分解得到,U,，,b,通过,LU,分解得到,y,，则,Ax=b,化,为,Ux=y,时，将,b,增广到,A,进行,LU,分解得到,y,。,220,例 用杜利特尔分解法求解方程组,解 先求增广系数矩阵的杜利特尔分解，即,221,222,223,224,225,例 用杜利特尔分解法求解方程组系,解 先求增广矩阵的杜利特尔分解，即,226,227,228,3.2.4,追赶法,(,托马斯法）：解三对角线性方程组,系数矩阵为三对角矩阵，非零元素分布在主对角线,及其相邻两条次对角线上。,三对角线性方程组,Ax=f,229,对系数矩阵,A,进行克劳特分解,A=LU,L,下二对角矩阵，,U,单位上二对角矩阵。,230,231,232,233,定理,当三对角矩阵满足条件,时，其所有顺序主子矩阵均非奇异。,234,235,236,237,238,解下三角形方程组,239,解下三角形方程组,240,241,242,243,244,对称正定矩阵,对称正定矩阵,对称正定矩阵,对称正定矩阵,3.3.2,对称正定矩阵的乔累斯基分解,245,246,247,248,249,250,251,252,253,254,255,256,257,3.3.3,改进平方根法,258,259,260,261,262,263,264,265,266,3.4,向量和矩阵的范数,3.4.1,向量范数,267,268,269,270,4,收敛性,271,272,3,4,2,矩阵范数,273,274,275,矩阵范数的性质,276,277,常用的矩阵范数有行（无穷）范数和列（一）范数。,例如,4,常用的矩阵范数,设,278,4,常用的矩阵范数,279,280,矩阵的收敛,281,矩阵的收敛,282,283,谱半径,284,谱半径的性质,285,3.6,线性代数方程组的迭代法,3.6.1,迭代原理,3.6.2,雅可比迭代,3.6.3,高斯,-,赛德尔迭代,3.6.4,松弛法,3.6.5,迭代公式的矩阵表示,286,写成矩阵形式,Ax=b,其中,3.6.1,迭代原理,设,线性代数方程组,287,288,289,例,用雅可比迭代法求解方程组,解,从,3,个方程分离出,构造雅可比迭代公式,3.6.2,雅可比迭代,290,迭代计算,291,k,0,1,2,3,4,5,x,1,(,k,),0,0.3,0.80,0.9180,0.9716,0.9894,x,2,(,k,),0,1.5,1.76,1.9260,1.9700,1.9897,x,3,(,k,),0,2.0,2.66,2.8640,2.9540,2.9823,292,设,线性方程组,其中系数矩阵非奇异，且主对角元,a,ii,0,，,(,i,=1,2,n,),，,由第,i,个方程解出,x,i,，有,293,建立迭代格式,写成,取初值 ，进行迭代。,这种方法称为,雅可比迭代法。,294,雅可比迭代公式,即,i=,1,2,n,295,雅可比迭代的算法框图,296,3.6.3,高斯,-,赛德尔,(Gauss-Seidel),迭代,迭代收敛时，新值,x,i,(,k+1,),比老值,x,i,(,k,),更准确，在雅可比迭代中，算出新值,x,i,(,k+1,),后，用新值,x,i,(,k+1,),代替用于后面计算的老值,x,i,(,k,),，期望这样会收敛得更快些。,例 用高斯,-,赛德尔迭代法求解方程组,解,方程组化为等价的方程组,构造,高斯,-,赛德尔,迭代公式,297,迭代计算：,1.56,2.684,2.95387,0.8804,1.94448,高斯,-,赛德尔迭代公式,0.3,298,计算结果,:,k,0,1,2,3,x,1,(,k,),0,0.3,0.8804,0.98428,x,2,(,k,),0,156,1.94448,1.99224,x,3,(,k,),0,2.684,2.95387,2.99375,299,高斯,-,赛德尔,(Seidel),迭代公式,300,3.6.4,松弛法,301,302,矩阵形式,Ax=b,其中,3.6.5,迭代公式的矩阵表示,n,个未知量,n,个方程的线性代数方程组,303,令,其中,D,为对角阵，,L,U,为严格下三角阵，严格上三角阵。,L+U=D-A,304,305,雅可比迭代公式,分量形式,矩阵形式,306,雅可比迭代的矩阵形式,雅可比迭代矩阵,将,L+U=D-A,代入,写成,307,雅可比迭代的矩阵形式为,J,为,雅可比迭代矩阵,。,308,309三种迭代格式总结,310,3.7,迭代法的收敛性,3.7.1,收敛的基本定理 迭代法收敛的,充分必要条件,定理 迭代法 收敛的充分必要条件是迭代矩阵,B,的谱半径,(B)1,。,.,311,例题 试判断迭代公式是否收敛。,解 迭代矩阵,故迭代发散。,312,迭代法收敛的充分条件,3.7.2,迭代矩阵法,313,314,315,316,例题 试判断以下迭代公式是否收敛：,解,(1),迭代矩阵,，,故迭代公式收敛。,(2),迭代矩阵,故迭代公式收敛。,317,.,定理给出的是充分条件，充分而不必要，因此满足定理一定收敛，不满足定理不一定不收敛。,例：雅可比迭代矩阵,高斯,-,赛德尔迭代矩阵,雅可比迭代收敛。,G-S,迭代收敛。,318,319,雅可比迭代收敛。,320,G-S,迭代收敛。,321,雅可比迭代收敛。,322,323,G-S,迭代收敛。,324,325,326,327,328,329,定理 方程组,Ax=b,，,构造雅可比迭代公式,x,(k+1),=Jx,(k),+f.,若雅可比迭代矩阵,J,满足,|,J,|1,则高斯,-,赛德尔迭代收敛。,330,331,332,333,3.7.3,系数矩阵法,334,335,336,定理 严格对角占优方程组的,Jacobi,迭代与对应的,Gauss-Scidel,迭代，对任意初值均收敛,.,337,338,339,松弛因子,=1,即,G-S,法,3.7.4,超松弛法,(SOR,法,),340,SOR,方法的收敛性,(1)SOR,方法对任意 都收敛的必要条件是：,(2),若系数矩阵,A,对称正定，则 时,SOR,方法,求解 对任意 收敛；,(3),若系数矩阵,A,按行（或按列）严格对角占优，,则 时,SOR,方法对任意 收敛。,341,第,4,章 插值法,4.1,引言,4.2,拉格朗日插值,4.3,逐次线性插值,4.4,牛顿插值,4.5,等距节点插值,4.6,反插值,4.7,埃尔米特插值,4.8,分段插值法,4.9,三次样条插值,342,定义 函数,y,=,f,(,x,),在区间,a,b,上有函数值,即,x,0,x,1,x,2,x,n,y,0,y,1,y,2,y,n,其中,x,0,x,1,x,2,x,n,是区间,a,b,上的互异点，要构造一个,简单的函数 作为,f,(,x,),的近似表达式，使满足,(,插值条件,),这类问题称为插值问题。,-,f,(,x,),的插值函数,f,(,x,)-,被插值函数,x,0,x,1,x,2,x,n,-,插值节点,，,a,b,称为插值区间,求插值函数的方法称为插值法。,若,x,a,b,，可计算,f(x),的近似值,(x),则,x,称为插值点。,4.1,引言,4.1.1,插值问题及代数多项式插值,插值 已知某些,(,有限,),点的函数值求其余点的函数值。,343,代数多项式插值 当选择代数多项式作为插值函数时，称为代数多项式插值。,定义,(,代数多项式插值,),设函数,y=f(x),在,a,b,上已知,n+,1,个点,ax,0,x,1,x,n,b,上的函数值,y,0,y,1,y,n,求一个次数不高于,n,的代数多项式,使满足插值条件,称,P,(,x,),为,f,(,x,),的,n,次插值多项式,。,代数插值的特点：,n,次代数多项式插值满足在,n+1,个节点上插值多项式,P(x),和被插值函数,y=f(x),相等，而且插值多项式,P(x),的次数不超过,n,次,。,344,定理,n,+1,个互异节点处满足插值条件,的,n,次代数多项式 是唯一的。,证,其系数行列式,方程组有唯一解,，因此,P,(,x,),存在且唯一。,4.1.2,代数多项式插值的唯一性,345,唯一性说明不论用那种方法构造的插值多项式只要满足相同的插值条件，其结果都是互相恒等的。,推论,当,f(x),是次数不超过,n,的多项式时，其,n,次插值多项式就是,f(x),本身。,例 在直线上取两个点进行插值，插值多项式就是这条直线。在二次抛物线上取三个点进行插值，插值多项式就是这条二次抛物线。,在直线上取三个点进行插值，插值多项式还是这条直线。在二次抛物线上取四个点进行插值，插值多项式也是这条二次抛物线。,346,347,4.1.3,插值的几何意义,几何意义是一条经过平面上,n,+1,个节点 ，,的n,次抛物线,y,=,P,(,x,),近似代替曲线,y,=,f,(,x,),。,348,4.2,拉格朗日插值,4.2.1,线性插值,(,二点一次插值）,1,定义,已知,f(x,0,)=y,0,，,f(x,1,)=y,1,x,0,x,1,x,x,0,x,1,y,y,0,y,1,要构造线性函数,P(x)=a,0,+a,1,x ,使满足插值条件,P(x,0,)=y,0,P(x,1,)=y,1,.,2,表达式,拉格朗日插值多项式,公式的结构：它是两个一次函数的线性组合,线性插值基函数,349,线性插值的几何意义,用直线 近似代替被插值函数,。,350,例 造数学用表。平方根表,给定函数在,100,、121,两点的平方根如下表，试用线性插值求,115,的平方根。,解,x,0,=100,x,1,=121,x=115,x,100 121,y,10 11,351,抛物线（二次）插值,:(,三点二次插值）,1,定义 已知,f,(,x,),在三个互异点,x,0,x,1,x,2,的函数值,y,0,y,1,y,2,x,x,0,x,1,x,2,y,y,0,y,1,y,2,构造一个次数不超过二次的多项式,使满足插值条件,352,插值,基函数,1,0,0,0,1,0,0,0,1,2,公式的构造：,拉格朗日二次插值多项式,满足插值条件,353,例 造,平方根表,已知,100,，,121,，,144,的平方根，计算,115,的平方根的近似值。,x,100 121 144,y,10 11 12,解,354,二次插值也称为,抛物插值,。,当三点,(x,0,y,0,),(x,1,y,1,),(x,2,y,2,),位于一条直线上时，显然插值函数的图形是直线。,355,4.2.2,拉格朗日插值多项式,定理 若,则,l,k,(,x,),称为关于节点,x,i,(,i,=0,1,n,),的,n,次插值基函数。,356,基函数的特点,基函数的个数等于节点数。,2.,n+,1,个节点的,基函数是,n,次代数多项式。,3.,基函数和每一个节点都有关。节点确定，基函数就唯一的确定。,4.,基函数和被插值函数无关。,5.,基