数值计算课件.ppt

数值计算方法,机械工业出版社,第1章 数值计算引论第2章 非线性方程的数值解法第3章 线性代数方程组的数值解法第4章 插值法第5章 曲线拟合的最小二乘法第6章 数值积分和数值微分第7章 常微分方程初值问题的数值解法,数值计算方法,第1章数值计算引论1.1 数值计算方法 1.2 误差的来源1.3 近似数的误差表示法1.4 数值运算误差分析1.5 数值稳定性和减小运算误差,第1章 数值计算引论 数值计算方法与误差分析 理工科大学本科生 科学研究。现代科学研究的三大手段 理论分析、科学实验、科学计算。1.1数值计算方法1.1.1 数值计算方法及其主要内容 1.课程名称：科学与工程数值计算方法 简称：科学计算、科学与工程计算、数值分析、计算方法、数值计算方法。科学与工程：从实用的角度，将科学研究与工程技术上遇到的实际问题用数学模型来描述，以便进行定量的分析、研究。,数值：数、数字，由0-9十个数字、小数点和正负号等组成的数。计算方法：解题的方法。可以用自然语言、数学语言或约定的符号语言来描述。计算：只能包括计算机能够直接处理的运算,即加减乘除等基本运算。数值计算：相对于非数值计算，如查表、排序等。用（0-9十个数字、小数点、正负号等组成的）数，通过计算机进行加减乘除等基本运算。2。数值算法：对科学研究与工程技术上遇到的实际数学问题的解法归结为用数值进行加减乘除等基本运算，并有确定运算顺序，完整而准确的描述称为数值算法。数值计算方法是研究用数字计算机解决数学问题的数值算法及其理论的一门课程。,3.主要内容：工程上遇到的数学问题 数值计算的误差分析 非线性方程 线性方程组 插值法 最小二乘法 数值积分和数值微分 常微分方程1.1.2 用计算机解题的步骤 当给定一个科学研究与工程技术上遇到的实际问题时，首先根据专业知识建立实际问题的数学模型，即模型化（modeling)或建模。然后对数学模型进行求解。数学模型（包括公式、表格、图形等）求解有两条途径：求解析解和数值解。,求解析解，解以表达式表示，这是准确解。求数值解，解是以一些离散点上取值的形式表示，多数情况下，数值解是近似的，求数值解要用计算机。求数学模型数值解的方法称为数值计算方法。选择计算方法以后进行程序设计，即用程序语言把算法编成程序，然后上机得出数值解。实际问题-数学问题(建模)-构造数值计算方法-程序设计-上机计算-数值解-结果分析,1.1.3 数值计算的特点：对算法的要求。1.只能包括计算机能够直接处理的运算,即加减乘除等基本运算。2.能任意逼近并达到精度要求，对近似算法要保证收敛性和稳定性。3.计算时间少，存储空间小。4.数值试验证明算法有效。,误差的来源即产生误差的原因。主要有四种：1.模型误差-建立的数学模型和实际的距离，客观量的准确值与数学模型的准确解的差。例如自由落体运动方程,1-2 误差的来源,2.观测误差：数学模型当中的参数或常数常常是是观测或实验来的，这样必然有误差，称为观测误差或测量误差，由观测数据而产生的误差。例如自由落体运动方程,3.截断误差(方法误差)-数学模型的准确解与利用数值计算方法得到的准确解之差。无穷过程用有穷项代替例如:无穷级数取前n项代替,截断误差,用有限的过程代替无限的过程，和用简单的计算问题代替复杂的计算问题所产生 的误差。,4.舍入误差：计算工具字长是有限位，在计算时只能对有限位数字进行运算，超过这个位数时，要舍入，于是产生舍入误差。原始数据、中间步骤和最终结果都可能产生舍入误差。如圆周率3.14159265 一般实数不能精确存储，例如：在10位十进制数限制下：,1-3 近似数的误差表示,1.3.2 相对误差,1.3.3 有效数字：由绝对误差决定。,若近似值x*的绝对误差(限)是某位的半个单位，则说 x*精确到该位，若从该位到 x*的左面第一位非零数字一共有n位，则称近似值x*有n位有效数字。,1.用四舍五入得到的近似数的误差限是末位的半个单位。近似数的误差限是末位的半个单位，则有n位有效数字。因此用四舍五入得到的近似数是有效数字。2.在公式运算中，要先区分准确量和近似数。准确数有无穷多位有效数字.3.有效数字位与小数点后有多少位数无直接关系。,1.3.4 有效数字与相对误差,1.定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。2.在实际应用时，为了要使所取近似数的相对误差满足一定要求，可以用定理，确定所取近似数应具有有效数字的位数。,1.定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。即若近似数有n位有效数字，相对误差不一定满足定理。2.在实际应用时，为了要使所取近似数具有n位有效数字，要求所取近似数的相对误差满足定理的要求。,1.4 数值运算误差分析 函数运算误差 算术运算误差,1.5 数值稳定性和减小运算误差 在计算过程中误差不会扩大或对计算结果的精度要求影响不大。减小运算误差:1 要避免两相近数相减。2 要防止大数吃掉小数。3 要避免除数绝对值远小于被除数绝对值。4 注意简化计算步骤，减少运算次数。,例：计算积分,写成递推公式,误差传递规律,公式改为,则误差按规律,逐渐缩小,1.5.1 数值稳定性:一个算法，如果计算结果受误差的影响小，就称这个算法具有较好的数值稳定性。否则，就称数值稳定性不好。因此要设法控制误差的传播。,1.5.2 减小运算误差,1.要避免相近两数相减 13.5846-13.5839=0.00076位有效数字变成了1位有效数字。损失了有效数字的位数。,当x接近于0时，应,例 解一元二次方程a x2+bx+c=0，其中-b,c,2 要防止大数“吃掉”小数，注意保护重要物理参数。,在8位十进制计算机上计算。要规格化和对阶。,结果，大数“吃掉”小数。,类似地,改变计算方法,例 在5位十进制计算机上计算,在5位十进制计算机上计算。要规格化和对阶。,结果，大数“吃掉”小数。,改变计算方法，按绝对值由小到大相加。,3 注意简化计算步骤，减少运算次数，避免误差积累,例：计算 的值。,又如,只需14次乘法。,采用“秦九韶算法”,例：计算多项式,只需n次乘法和n次加法。,第2 章 非线性方程的数值解法 2.1 初始近似值的搜索 2.2 迭代法 2.3 牛顿迭代法（切线法）2.4 弦截法（割线法）,2.1 初始近似值的搜索2.1.1方程的根,单根和重根,有根区间,假设f(x)在区间a,b内有一个实根x*,若 b a较小，则可在(a,b)上任取一点x0作为初始近似根。一般情形，可用逐步搜索法。,2.1.2 逐步搜索法,例 对方程 搜索有根区间。解 由于f(x)是连续函数，f(0)=-10，故方程至少有一正实根。设从x=0 出发，取h=0.5为步长，逐步右跨搜索，得,所以f(x)在区间（1,1.5）上单调连续，因而在(1,1.5)内有且仅有一个实根，故可取1,1.5上任一点做初始近似根。,可见在（1，1.5）内有根。又,2.1.3 区间二分法 定理 函数f(x)在a,b上单调连续，且f(a)f(b)0，则方程f(x)=0在区间a,b上有且仅有一个实根x*。二分法的基本思想 将有根的区间二分为两个小区间，然后判断根在那个小区间，舍去无根的小区间，而把有根的小区间再一分为二，再判断根属于哪个更小的区间，如此反复，直到求出满足精度要求的近似根。,令,近似根xk的误差估计,中点,这时有三种情况：,f(x0)=0,x0为所求的根.f(x0)和a0 同号，取x0=a1 f(x0)和b0 同号，取x0=b1,x*,x*,新的有根区间为(a1,b1)，长度是原来的一半。,如此反复，有,(a k,b k),k=0,1,2,.,近似根xk的误差估计,第2次二分，取中点,若 f(a1)f(x1)0，则 x*(a1,x1)，,令a2=a1,b2=x1；,否则 令 a2=x1,b2=b1。,新的有根区间为(a2,b2)。,由此得二分过程结束的原则：,先给定精度要求(绝对误差限)，,（2）当|bk+1 ak+1|时结束二分计算，取 x*xk；,（1）事先由估计出二分的最小次数 k，取 x*xk,2.2 迭代法2.2.1 迭代原理2.2.2 迭代的收敛性2.2.3 迭代的收敛速度2.2.4 迭代的加速,预备定理,2.2.1 迭代原理,计算结果见下表,方程f(x)=0化为等价形式的方程 x=(x)，构造迭代公式 xk+1=(xk),k=0,1,2,取初始近似根x0,进行迭代计算 x1=(x0),x2=(x1),.则有x1,x2,.,xk,.,得到迭代序列xk.如果这个序列有极限，则迭代公式是收敛的。这时 则，x*为不动点，等价地有 f(x*)=0,x*即为方程的根。连续函数(x)称为迭代函数。实际计算到|xk xk-1|（是预定的精度），取x*xk。,迭代公式收敛指迭代序列xk 收敛，迭代公式发散指迭代序列xk 不收敛，即发散。迭代公式不一定总是收敛。例如求方程 f(x)=x3-x-1=0的一个根。对应的迭代公式为,取初值,迭代序列xk 发散.,x1=(x0),x2=(x1),迭代法收敛与发散的图示,迭代法的收敛与发散,收敛的情形 发散的情形,2.2.2 迭代的收敛性 迭代法的收敛条件及误差估计式定理（充分性条件）设函数(x)在a,b上连续，且(1)对 xa,b,有(x)a,b(2)存在0 L 1，使对任意 x a,b有|(x)|L 1则方程x=(x)在 a,b上的根x*存在且唯一；对初值 x0 a,b,迭代过程 xk+1=(xk)均收敛于方程的根x*。,定理中的(1)对 xa,b,有(x)a,b，称为适定性（映内性）。,证明 先证根的存在性。作连续函数(x)=x-(x),由条件（1）xa,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的根唯一。,再证迭代的收敛性。,由xk=(xk-1),x*=(x*),有,|xk-x*|=|()(xk-1-x*)|L|x k-1-x*|,L2|xk-2-x*|,L3|xk-3-x*|,Lk|x0-x*|,0（k）,所以，对a,b上任取的x0,迭代公式xk+1=(xk)都收敛于x*。L越小收敛得越快。,定理是充分性条件,xk-x*=(xk-1)(x*)=()(xk-1-x*),推论：在定理的条件下，有误差估计式 验后误差估计式 验前误差估计式证明：,|xk-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|控制迭代过程的结束。,定理 设在区间a,b上方程 x=(x)有根x*,且对一切xa,b 都有|(x)|1，则对于该区间上任意x0(x*),迭代公式xk+1=(xk)一定发散。,证明,不可能收敛于0。,计算结果见下表,取方程的根 2.0946。,由于，故取,迭代法的局部收敛性,由于在实际应用中根 x*事先不知道，故条件|(x*)|1无法验证。但已知根的初值x0在根 x*邻域，又根据(x)的连续性，则可采用|(x0)|1 来代替|(x*)|1，判断迭代的收敛性。,例,求方程 x=e x在x=0.5附近的一个根，按5位小数计算，结果的精度要求为=10 3.,解,迭代公式 xk+1=e xk，取(x)=e x,迭代公式 xk+1=e xk 收敛。,迭代结果:,k,xk,xk xk-1,xk xk-1,k,xk,|x10-x9|=0.00065，,故 x*x10 0.567,x0=0.5,x2=e x1=0.54524,.,x1=e x0=0.60653,xk+1=e xk,迭代的计算步骤,迭代法计算框图的说明,2.2.3 迭代过程的收敛速度,2.2.4 迭代的加速,2 埃特金加速与斯蒂芬森迭代法,埃特金迭代,将不动点迭代法与埃特金加速结合即得斯蒂芬森迭代法,2.3 牛顿迭代法2.3.1 迭代公式的建立2.3.2 牛顿迭代法的收敛情况2.3.3 牛顿迭代法的修正法,2.3.1 迭代公式的建立,3.几何意义 过曲线上的点pk(xk,f(xk)作切线，切线方程 y=f(xk)+f(xk)(x xk)切线方程和横轴的交点(xk+1,0)，即 0=f(xk)+f(xk)(xk+1 xk)若 f(xk)0，解出xk+1，则得Newton迭代公式,例 用牛顿迭代法求方程 xex-1=0 在x=0.5附近的根。,解,牛顿迭代法,取x0=0.5，经计算可得,普通迭代法18次才能得到的计算结果。,则x2-a=0,求,等价于求方程,令,例,造平方根表。用牛顿迭代法计算(其中a0),解,的正实根。因为 f(x)=2x，由牛顿迭代公式得,当a=115时，取初值 x0=10，迭代4次可得10，10.7500，10.723837，10.723805，10.723805,10.723805,是否还能用牛顿法计算一个正数的立方根？,则x3-3=0,求,等价于求方程,令,例,用牛顿迭代法求,解,的正实根。由牛顿迭代公式得,当a=4111.7910时，取初值 x0=8，迭代4次可得7.48，7.439977,7.439760,7.439760,令,例,用牛顿迭代法造倒数表，计算,解,3、牛顿迭代法的计算步骤,(1)给出x0,，N,(2)计算,(3)若,则转(4)；否则,，转(2);,(4)输出x1,结束。,牛顿迭代法局部收敛:,2.4.2 牛顿迭代法的收敛情况,1.局部收敛性,结论：f(x)=0的单根x*附近存在着连续的二阶导数，当初值在单根x*附近时，牛顿法具有平方收敛速度。,证 牛顿法迭代函数当 f(x*)=0，而 f(x*)0，则x*是f(x)=0的单根,单根x*附近存在着连续的二阶导数，有,牛顿法至少具有平方收敛速度。,2.3.3 牛顿迭代法的修正,1.简化牛顿法(平行弦法),2.牛顿下山法,在牛顿法基础上，构造既有较高的收敛速度，又不 需要求导数的迭代公式。,公式的推导 用差商,则得两个弦截迭代公式,2.5 弦截法（割线法）,单点弦法,双点弦法,例,用单点弦截迭代法求方程 x3-0.2x-1.2=0 在x=1.5附近的根。,解,弦截迭代公式,据题意，取x0=1.5,f(x0)=1.425,代入单点弦迭代法所以有,k1234567,xk11.1501.1901.1931.1981.1991.200,例,用双点弦截迭代法求方程 xex-1=0 在x=0.5附近的根。,解,弦截迭代公式,方程化为 x-e x=0,令，代入双点弦迭代法,第3章 线性代数方程组的数值解法3.1 高斯消去法3.2 矩阵三角分解法3.3 平方根法3.4 向量和矩阵的范数3.5 方程组的形态和误差分析3.6 迭代法3.7 迭代法的收敛性,矩阵形式 Ax=b,其中,n个未知量n个方程的线性代数方程组,或写成,两类数值解法：直接解法:假定计算过程没有舍入误差的情况下，经过有限步算术运算后能求得线性方程组精确解的方法。经过有限步运算就能求得精确解的方法，但实际计算中由于舍入误差的影响，这类方法也只能求得近似解；例如：高斯消去法、三角分解法等。迭代解法:构造适当的向量序列，用某种极限过程去逐步逼近精确解。例如：雅可比迭代法、高斯-赛德尔迭代法等。,上三 角形方程组,回代求解，得,下三角形方程组,顺代可求得,上二对角方程组,回代求解，得,下二对角方程组,顺代可求得,3.1 高斯消去法 3.1.1 顺序高斯消去法(按方程和未知量的自然顺序进行)基本思想：用逐次消去未知数的方法把原方程组化为上三角形方程组进行求解。求解 分成两步：1.消元过程：用初等行变换将原方程组的系数矩阵化为上三角形矩阵（简称上三角阵）。2.回代过程：对上三角形方程组的最后一个方程求解，将求得的解逐步往上一个方程代入求解。,顺序高斯消去法消元过程:依从左到右、自上而下的次序将主对角元下方的元素化为零。1 不作行交换。2 用不等于零的数乘某行，加至另一行。,系数行列式的计算：,例,消元过程,主元为2，2.5，0.6 det A=22.50.6=3,消元过程,回代过程,顺序高斯消去法的使用条件 使用条件之一 定理 线性方程组系数矩阵A的顺序主子矩阵Ak(k=1,2,n)非奇异，则顺序高斯消去法能实现方程组的求解。即方程组能用顺序高斯消去法求解的充要条件是系数行列式的顺序主子式非零。,高斯消去法能按顺序进行到底的充要条件是,在原方程组的系数矩阵中如何反映出这个条件呢?,A的k阶顺序主子矩阵Ak的行列式,使用条件之二 n阶矩阵A为严格对角占优矩阵是指其每个主对角元的绝对值大于同一行其他元素绝对值之和，即,一阶严格对角占优矩阵指一个非零数。,定理 方程组系数矩阵A为严格对角占优矩阵则可实现用顺序高斯消去法求解。,3.1.2 列主元高斯消去法 为什么列选主：数值不稳定 当高斯消去法的主元 时,尽管“当 A 非奇异时，det A0，方程组有唯一解”，也不能实现高斯消去法求解。例，A 非奇异，det A0，方程组有唯一解，但，不能实现高斯消去法求解。,高斯消去法的主元，但绝对值很小时，用绝对值小的数做除数，会导致其它元素数量级的严重增长和舍入误差的扩大。,列选主高斯消去法：避免用绝对值小的元素，作除数。每次消元前选取一列中绝对值最大的元素作为主元素。用这个主元素作除数，这样便可以减少舍入误差。列选主高斯消去法的优越性，不增加求解过程的运算量，而大大减小误差。,例 用列主元高斯消去法求解方程组(用三位有效数字计算),解,选主元,选主元,消元过程完成，得到上三角形方程组,再作回代可求得,行列式的计算：,列主元法的消元过程,计算过程有2次行交换，故m=2，主元为5，-1.6，2,det A=(-1)25(-1.6)2=16,m为消元过程中交换行的次数。,列主元高斯消去法(简称列主元消去法)的计算框图 d:绝对值最大的主元素的存储单元。l:绝对值最大的主元素所在的行的存储单元。,定理 系数矩阵为对称严格对角占优，则全是主元。,3.1.3 高斯-约当(Jordan)消去法 1。方法的描述 消元时将主元上方元素也消为0，最后系数矩阵化为对角矩阵。这种算法只有消元，没有回代，这种方法称做高斯-约当(Jordan)消去法。,2。归一方法 消元时将主元上方也消为0，并将第k行除以akk(k=1,2,n)，使主元位置化为1，最后系数矩阵化为 单位矩阵。这种方法无须回代，称做归一的高斯-约当(Jordan)消去法。,归一方法的例子,3。列选主高斯-约当(Jordan)消去法。,4。高斯-约当(Jordan)消去法的计算量,5。高斯-约当(Jordan)消去法求逆矩阵,当det A0时，A存在逆矩阵，设,s=1,2,n,求A-1就相当于求解n个线性方程组,高斯-约当(Jordan)消去法求逆。,3.2 矩阵三角分解法,。,定义 将矩阵A分解成一个下三角阵L和一个上三角阵U的乘积，即 A=LU称为A的三角分解或LU分解。,。,例如A=这里有A的两种不同的三角分解，类似可举出很多，一般，若A=LU是一个三角分解，任取与A同阶的非奇异对角矩阵D，则 A=(LD)(D-1U)=L1U1也是A的三角分解。,。,杜利特尔分解(Doolittle),常用的两种三角分解,克洛特分解(Crout),定理 n阶矩阵A存在唯一的杜利特尔分解或克劳特分解的充要条件是A的顺序主子矩阵Ak(k=1,2,n-1)非奇异。,例 设 讨论a 取何值时，矩阵A可作LU分解。,解,当A的顺序主子式不为零，矩阵A有LU分解。,所以，有,非奇异矩阵不一定存在LU分解。例,解,A是非奇异矩阵，假设有LU分解（杜利特尔分解）,比较等式两端第1列，可得 上二式不能同时成立，即非奇异矩阵A不存在LU分解。,复习：矩阵乘法,A=BC,3.2.2Doolittle分解步骤,A=LU,令i=r,r+1,n，(即 i大于等于r),例,紧凑格式,3.2.3 用三角分解求解线性方程组 设A非奇异，并有三角分解A=LU，则方程组 Ax=b 就化为 LUx=b 只须求解两个简单的三角形方程组：（1）解Ly=b 顺代求出 y（2）解Ux=y，回代求出x.,求得L、U后再求解方程组Ly=b,Ux=y,例 用杜利特尔分解法求解方程组,解 先对系数矩阵进行杜利特尔分解 A=LU,求解两个三角形方程组，,得,方程组 Ax=b 化为 Ux=y 时，A通过LU分解得到U，b 通过LU分解得到y，则Ax=b化为Ux=y 时，将b增广到A进行 LU分解得到y。,例 用杜利特尔分解法求解方程组,解 先求增广系数矩阵的杜利特尔分解，即,例 用杜利特尔分解法求解方程组系,解 先求增广矩阵的杜利特尔分解，即,3.2.4 追赶法(托马斯法）：解三对角线性方程组,系数矩阵为三对角矩阵，非零元素分布在主对角线及其相邻两条次对角线上。,三对角线性方程组 Ax=f,对系数矩阵A进行克劳特分解 A=LU,L下二对角矩阵，U单位上二对角矩阵。,定理,当三对角矩阵满足条件,时，其所有顺序主子矩阵均非奇异。,解下三角形方程组,解下三角形方程组,对称正定矩阵,对称正定矩阵,对称正定矩阵,对称正定矩阵,3.3.2 对称正定矩阵的乔累斯基分解,3.3.3 改进平方根法,3.4 向量和矩阵的范数3.4.1 向量范数,4 收敛性,342 矩阵范数,矩阵范数的性质,常用的矩阵范数有行（无穷）范数和列（一）范数。,例如,4 常用的矩阵范数,设,4 常用的矩阵范数,矩阵的收敛,矩阵的收敛,谱半径,谱半径的性质,3.6 线性代数方程组的迭代法 3.6.1 迭代原理 3.6.2 雅可比迭代 3.6.3 高斯-赛德尔迭代 3.6.4 松弛法 3.6.5 迭代公式的矩阵表示,写成矩阵形式 Ax=b其中,3.6.1 迭代原理 设线性代数方程组,例 用雅可比迭代法求解方程组,解 从3个方程分离出,构造雅可比迭代公式,3.6.2 雅可比迭代,迭代计算,设线性方程组,其中系数矩阵非奇异，且主对角元aii0，(i=1,2,n)，由第i 个方程解出xi，有,建立迭代格式,写成,取初值，进行迭代。这种方法称为雅可比迭代法。,雅可比迭代公式,即,i=1,2,n,雅可比迭代的算法框图,3.6.3 高斯-赛德尔(Gauss-Seidel)迭代 迭代收敛时，新值xi(k+1)比老值xi(k)更准确，在雅可比迭代中，算出新值xi(k+1)后，用新值xi(k+1)代替用于后面计算的老值xi(k)，期望这样会收敛得更快些。例 用高斯-赛德尔迭代法求解方程组,解 方程组化为等价的方程组,构造高斯-赛德尔迭代公式,迭代计算：,1.56,2.684,2.95387,0.8804,1.94448,高斯-赛德尔迭代公式,0.3,计算结果:,高斯-赛德尔(Seidel)迭代公式,3.6.4 松弛法,矩阵形式 Ax=b其中,3.6.5 迭代公式的矩阵表示n个未知量n个方程的线性代数方程组,令,其中 D为对角阵，L,U为严格下三角阵，严格上三角阵。L+U=D-A,雅可比迭代公式,分量形式,矩阵形式,雅可比迭代的矩阵形式,雅可比迭代矩阵,将L+U=D-A代入,写成,雅可比迭代的矩阵形式为,J为雅可比迭代矩阵。,三种迭代格式总结,3.7 迭代法的收敛性 3.7.1 收敛的基本定理 迭代法收敛的充分必要条件 定理 迭代法 收敛的充分必要条件是迭代矩阵B的谱半径(B)1。,.,例题 试判断迭代公式是否收敛。,解 迭代矩阵,故迭代发散。,迭代法收敛的充分条件,3.7.2迭代矩阵法,例题 试判断以下迭代公式是否收敛：,解(1)迭代矩阵,，故迭代公式收敛。,(2)迭代矩阵,故迭代公式收敛。,.,定理给出的是充分条件，充分而不必要，因此满足定理一定收敛，不满足定理不一定不收敛。,例：雅可比迭代矩阵,高斯-赛德尔迭代矩阵,雅可比迭代收敛。,G-S迭代收敛。,雅可比迭代收敛。,G-S迭代收敛。,雅可比迭代收敛。,G-S迭代收敛。,定理 方程组 Ax=b，构造雅可比迭代公式 x(k+1)=Jx(k)+f.若雅可比迭代矩阵J满足|J|1,则高斯-赛德尔迭代收敛。,3.7.3 系数矩阵法,定理 严格对角占优方程组的Jacobi迭代与对应的Gauss-Scidel迭代，对任意初值均收敛.,松弛因子,=1 即G-S法,3.7.4 超松弛法(SOR法),SOR方法的收敛性,(1)SOR方法对任意 都收敛的必要条件是：(2)若系数矩阵A对称正定，则 时SOR方法 求解 对任意 收敛；(3)若系数矩阵A按行（或按列）严格对角占优，则 时SOR方法对任意 收敛。,第4章 插值法4.1 引言4.2 拉格朗日插值 4.3 逐次线性插值4.4 牛顿插值4.5 等距节点插值4.6 反插值4.7 埃尔米特插值4.8 分段插值法4.9 三次样条插值,定义 函数y=f(x)在区间a,b上有函数值,即 x0 x1 x2 xn y0 y1 y2 yn,其中x0,x1,x2,xn是区间a,b上的互异点，要构造一个简单的函数 作为f(x)的近似表达式，使满足,(插值条件),这类问题称为插值问题。,-f(x)的插值函数,f(x)-被插值函数,x0,x1,x2,xn-插值节点，a,b称为插值区间,求插值函数的方法称为插值法。,若xa,b，可计算f(x)的近似值(x),则 x 称为插值点。,4.1 引言4.1.1 插值问题及代数多项式插值插值 已知某些(有限)点的函数值求其余点的函数值。,代数多项式插值 当选择代数多项式作为插值函数时，称为代数多项式插值。,定义(代数多项式插值)设函数y=f(x)在a,b上已知 n+1个点 ax0 x1xnb上的函数值 y0,y1,yn求一个次数不高于n的代数多项式,使满足插值条件,称P(x)为 f(x)的n次插值多项式。,代数插值的特点：n次代数多项式插值满足在n+1个节点上插值多项式P(x)和被插值函数y=f(x)相等，而且插值多项式P(x)的次数不超过n次。,定理 n+1个互异节点处满足插值条件 的n次代数多项式 是唯一的。,证,其系数行列式,方程组有唯一解,，因此P(x)存在且唯一。,4.1.2 代数多项式插值的唯一性,唯一性说明不论用那种方法构造的插值多项式只要满足相同的插值条件，其结果都是互相恒等的。推论 当f(x)是次数不超过n的多项式时，其n次插值多项式就是f(x)本身。例 在直线上取两个点进行插值，插值多项式就是这条直线。在二次抛物线上取三个点进行插值，插值多项式就是这条二次抛物线。在直线上取三个点进行插值，插值多项式还是这条直线。在二次抛物线上取四个点进行插值，插值多项式也是这条二次抛物线。,4.1.3 插值的几何意义,几何意义是一条经过平面上 n+1个节点，的n次抛物线 y=P(x),近似代替曲线 y=f(x)。,4.2 拉格朗日插值4.2.1 线性插值(二点一次插值）,1 定义,已知f(x0)=y0，f(x1)=y1,x0 x1,要构造线性函数 P(x)=a0+a1 x,使满足插值条件 P(x0)=y0,P(x1)=y1.,2 表达式 拉格朗日插值多项式,公式的结构：它是两个一次函数的线性组合,线性插值基函数,线性插值的几何意义用直线 近似代替被插值函数。,例 造数学用表。平方根表 给定函数在100、121两点的平方根如下表，试用线性插值求115的平方根。,解 x0=100,x1=121,x=115,抛物线（二次）插值:(三点二次插值）,1 定义 已知f(x)在三个互异点x0,x1,x2的函数值y0,y1,y2,构造一个次数不超过二次的多项式,使满足插值条件,2 公式的构造：拉格朗日二次插值多项式满足插值条件,例 造平方根表 已知100，121，144的平方根，计算115的平方根的近似值。,解,二次插值也称为抛物插值。当三点(x0,y0),(x1,y1),(x2,y2)位于一条直线上时，显然插值函数的图形是直线。,4.2.2 拉格朗日插值多项式 定理 若,则,lk(x)称为关于节点xi(i=0,1,n)的n次插值基函数。,基函数的特点基函数的个数等于节点数。2.n+1个节点的基函数是n次代数多项式。3.基函数和每一个节点都有关。节点确定，基函数就唯一的确定。4.基函数和被插值函数无关。5.基函数之和为1。,定理 n次拉格朗日插值多项式,证 基函数是关于x的n次多项式，所以p(x)是关于x的不超过n次的多项式。又满足插值条件。,拉格朗日三次多项式,n次拉格朗日插值多项式,又,其中 可以证明则,4.2.3 插值余项和误差估计：余项(截断误差),定理 设函数f(x)在包含节点x0,x1,xn的区间a,b上有n+1阶导数，则,其中,证 令x是区间a,b上任一固定点，当x=xi(i=0,1,n)时，由插值条件知R(xi)=0，左=右，结论显然成立。,(a,b),当x是a,b上除节点外任一个固定点时，作辅助函数,当 t=x,x0,x1,xn时 F(t)=0，F(t)在区间a,b上至少有n+2个互异的零点x,x0,x1,xn。根据罗尔定理，F(t)在连续函数F(t)每两个零点之间有一个零点。即F(t)在(a,b)内至少有n+1个互异的零点，F(t)在(a,b)内至少有n个互异零点。依此类推，可知 F(n+1)(t)在(a,b)内至少有一个零点，即F(n+1)()=0，辅助函数两端对t求n+1阶导数，并比较其两端，有从而结论成立。,当插值点x(a,b)时称为内插，否则称为外插。内插的精度高于外插的精度。,线性插值多项式的截断误差为,是在包含x,x0,x1 的区间内某数。,例1 给定函数y=lnx在两点10、11的值如下表，试用线性插值求ln10.5的近似值，并估计截断误差。,解 f(x)=ln x,x0=10,x1=11,x=10.5,ln 10.5P1(10.5)=,4.3 逐次线性插值,逐次线性插值解决拉格朗日插值为提高精度增加插值节点时，要重新计算全部基函数，整个插值多项式的结构都会改变的问题。,4.3.1 三个节点的情形,已知 f(x)在三个互异节点x0,x1,x2的函数值y0,y1,y2 用（x0,y0),(x1,y1)做插值,用（x0,y0),(x2,y2)做插值,用（x1,P01),(x2,P02)做插值,上式即是拉格朗日二次插值多项式。两个线性插值的结果再进行线性插值，得到抛物线性插值。,三个节点的情形写成表格的形式,的近似值为1.5。,已知f(x)在三个互异点 0,1,2的函数值1,3,9用（0,1),(1,3)作插值,用（0,1),(2,9)作插值,用（1,P01),(2,P02)作插值,4.3.2 埃特金插值,4.3.3 内维尔插值,4.4 牛顿插值,牛顿插值解决拉格朗日插值为提高精度增加插值节点时，要重新计算全部基函数，整个插值多项式的结构都会改变的问题。差商及其性质,牛顿插值多项式。,零阶差商定义为函数值本身，即,4.4.1 差商（均差）及其性质1 差商的定义 差商是函数增量与其自变量的增量的比(商)。,函数f关于点xi,xj的一阶差商一阶差商是函数f在区间xi,xj 的平均变化率。二阶差商 是一阶差商在区间的平均变化率,例如 设则,函数f的n阶差商,高阶差商是由比它低一阶的两个差商的差商组成。例如,差商表,（1）n 阶差商 是函数值 的线性组合，即（2）差商具有对称性：任意改变节点的次序差商值不变。例如 f0,2,4=f2,0,4=f4,2,0等。,2 差商的性质,按差商的定义,4.3.2牛顿插值公式 1。牛顿插值公式的建立,牛顿插值多项式(f(x)的前n+1项）,牛顿插值余项(f(x)的最后一项）,牛顿插值多项式的构成,2。牛顿插值的特点(1)P(x)次数不超过n次，项数不超过n+1项。各项系数是差商表上对角线的各阶差商值。(2)P(x)满足插值条件，在节点上f(xi)=P(xi).(3)增加一个节点，只需增加一项。,n次牛顿插值多项式,计算牛顿插值多项式的步骤(1)作差商表.(2)写出牛顿插值多项式（表中对角线上各差商值就是P(x)的各项系数）。(3)计算插值点的近似值。,余项公式,又证:牛顿插值多项式,根据线性插值的点斜式,可得牛顿差商型线性插值多项式：,设,由,可得,牛顿差商型二次插值多项式：,解 先作差商表,xi,f(xi),1阶,2阶,3阶,4阶,0.400.550.650.800.90,1.1160 1.1860 1.2757 1.3841,0.410750.578150.696750.888111.02652,0.28000.35880.4336,0.1910.214,0.034,由Newton公式得四次插值多项式,4.4.3 差商和导数若 f(x)在a,b 上存在n 阶导数，由余项表达式可得，n 阶差商与导数有如下关系,例 求n次多项式的n 阶差商。,4.6 反插值,4.8 分段插值法 给定(x-5,5)。取等距节点xi=-5+i(i=0,1,10),试建立插值多项式L10(x),并作图形,观察L10(x)对f(x)的逼近效果。,分段三次埃尔米特插值为了避免Runge现象的发生,很自然地会想到把区间-5,5等分为10个小区间,在每一个小区间内应用低次插值。但由于每个小区间只有两个端点（插值节点）,按照已知的方法,得到的将是一个分段线性插值函数。,已知xi,f(xi),f(xi)(i=0,1,n),求分段三次插值函数H(x)满足 H(xi)=f(xi),H(xi)=f(xi)i=0,1,n为了得到插值函数,考虑任意子区间xi,xi+1,i(0,1,n-1),采用Lagrange插值函数结构,在第i个子区间上H(x)=f(xi)h1(x)+f(xi+1)h2(x)+f(xi)h3(x)+f(xi+1)h4(x)这样，就把H(x)的构造问题转化为四个插值基函数hk(x)(k=1,2,3,4)的构造问题。,4.9 三次样条插值,“样条”一词本来是指在飞机或轮船设计过程中为了描绘出光滑的外形曲线所用的一种工具，即一个具有弹性的细长木条。事实上，在作了某些近似简化后，样条的数学模型并不复杂，它只是分段的三次多项式曲线：在相邻两块压铁之间是三次多项式曲线；在压铁处，左右两段曲线的切线和曲率是连续的。,定义 给定a,b的分划：a=x0 x1xn=b,如果函数s(x)在区间a,b上满足以下条件：（1）在每一个子区间（xi,xi+1）(i=0,1,n-1)上s(x)是三次多项式；（2）s(x)在区间a,b上具有二阶连续导数；（3）s(xi)=yi(i=0,1,n),s(x0)=y0,s(xn)=yn。称s(x)为三次样条函数。,第5章 曲线拟合的最小二乘法 5.1 最小二乘法原理 5.2 超定方程组的最小二乘解 5.3 可线性性化模型的最小二乘拟合 5.4 多变量的数据拟合 5.5 多项式拟合 5.6 正交多项式及其 最小二乘拟合,5.1 最小二乘原理,设已知某物理过程y=f(x)在m个互异点的观测数据,求一个简单的近似函数(x)，使之“最好”地逼近f(x)，而不必满足插值原则。称函数y=(x)为经验公式或拟合曲线。这就是曲线拟合问题。,5.2 超定方程组的最小二乘解设线性方程组,(mn),即,如果有向量x使得,达到最小，则称x为超定方程组的最小二乘解。,定理 超定方程组Ax=b 存在最小二乘解，且即为方程组ATAx=ATb 的解。当A的列向量线性无关时ATA非奇异，这时有唯一的解。,称方程组ATAx=ATb 为方程组Ax=b 的正则方程组、正规方程组、法方程组,曲线拟合的最小二乘法可以看成求下述超定方程组的最小二乘解的问题,简写为,一般计算步骤,(1)计算,，其中,(2)计算ATA,ATb，形成法方程组ATAx=ATb(3)求解法方程组，输出 a1,a2,an,构成,5.