计算方法复习.ppt

1、主 讲：祁 鑫 办公室：计算机馆313 电 话：8398789 email： ,计算方法总复习,教学目标,掌握常用的数值计算方法 掌握计算方法的数学原理 学会选择恰当的计算方法 学会判定数值算法的优劣,最终目标： 提高编程和应用计算机解决实际问题的能力！,第一章 绪 论,知识点： 绝对误差（限）、相对误差（限） 有效数字 有效数位与误差的关系 数值运算的误差估计 数值计算中应注意的几个问题,基本要求 【了解】 计算方法的研究对象和特点； 数值计算方法设计中应注意的基本原则。 【掌握】 误差的概念、分类和估计方法； 有效数字的概念及判定方法。 【重点掌握】 有效数字的概念及判定方法。 习题（作业

2、）：习题一 1、2、4、5,2 误差和有效数字(重点） 一、误差的来源 1、 模型误差 -建立近似数学模型产生的误差 2、 观测误差 -观测手段和工具限制等带来的误差 3、 截断误差（方法误差） -模型的准确解与数值方法的准确解之间的误差 4、 舍入误差 - -受计算机字长限制而导致的误差称为舍入误差,二、绝对误差和相对误差 1、 绝对误差与绝对误差限,设 为真值（精确值）， 为 的一个近似值 称 为近似值 的绝对误差，简称误差。,定义1 绝对误差(P2),绝对误差限绝对值的上界,2、 相对误差与相对误差限,相对误差限相对误差的绝对值的上界,定义3 有效数字（P4） 设X * 是精确值X的近似

3、值,将其写成如下标准形式： X * =0.X1X2Xn 10m 科学计数法 其中： X1： 1-9之间的一切数字 X2.Xn： 0-9之间的一切数字 m为整数，如果X *的绝对误差限为： | X * -X | 10m-n,则称X * 作为X的近似值具有n位有效数字， X1，X2，Xn为X * 的有效数字,最后有效数位,最后有效数位的半个单位,三、有效数字,有效数字确定步骤： （1）根据定义先表示成标准形式：科学计数法， （2）再根据误差限确定最后的有效数位，其误差限是该位的半个单位， （3）从最后一位有效位到最左边第一个非零数之间的一切数字都是有效数字。,如果近似数是“四舍五入”得来的，显然其

4、绝对 误差限是最后单位的半个单位，因此最后一位 是有效数位。 一个“四舍五入”得来的数都是有效数字。 不是“四舍五入”得来的数，按照定义3确定有 效数字,有效数字同相对误差的关系 定理1 设X * 是具有n位有效数字的近似数，且可以表示成 X * =0.X1X2Xn 10m 则： 绝对误差限,相对误差限,若X *的相对误差限满足 则x*至少有n位有效数字。,相对误差限 有效数字位数,四、函数计算时的误差估计（tailor展开 ） 对于一个一元函数 f(x) = f(x*) + f (x*) (x-x*) + (x-x* )2 + (x-x*)3 + . f(x) = f(x*) + f (x*

5、) (x-x*) + (x-x* )2 | f(x) - f(x*) | = | f (x*) | | (x*) |+ (x*) 2 假设忽略(x*) 的高阶项 ，则可得到计算函数的误差限 |(f(x*) | | f (x*) | | (x*) |,3数值计算中应注意的问题 1、 避免除数绝对值远远小于被除数的除法（小分母） （舍入误差加大）(p7例） 2、 避免两相近数相减 （损失有效数字） 如 1- cos 2=0.0006 若换 2sin2(x/2) =2sin21=6.1310-4 3、 防止大数吃掉小数 （损失有效数字） 如 4+ 0.000000005+0.00000005,4、

6、简化运算步骤，减少运算次数 （减少舍入误差） p5(x) = a5x5+a4x4+a3x3+a2x2+a1x+a0 计算多项式函数 若按逐个相乘 a5.x.x.x.x.x 再相加需要15次乘法，5次加法 改为： p5(x) =（a5 x +a4 )x+a3 )x+a2 )x+a1)x +a0 只需5次乘法，5次加法 -秦九韶算法 5、 注意算法的稳定性 (抗干扰性）- 即：初始误差对结果的影响 稳定性定义：初始值有小的舍入误差而引起计算结果有大的误差的算法称为数值不稳定的，否则称为数值稳定的。 根据稳定性定义判断一个算法是稳定的还是不稳定的，关键是推导出误差传播公式。,小结： 1、什么是舍入误

7、差？什么是截断误差？它们的来源是什么？ 2、什么是绝对误差、相对误差和有效数字？ 3、绝对误差、相对误差和有效数字之间的关系是什么？ 4、 =3.141592654 (1) 若其近似值取5位有效数字，则该近似值是多少？其绝对、相对误差限是多少？ （2）若其近似值取3.1415, 绝对误差限是什么？有效数字是什么？ （3）若其近似值的绝对误差限为0.5 10-5 则该近似值是什么？,第二章 方程求根,1 引言 2 对分法（二分法） 3 迭代法（重点） 4 迭代过程的收敛速度 5 牛顿迭代法（重点） 6 割线法,二、基本要求 【了解】 迭代法的构造思想； 迭代法的收敛性判定定理的证明； 割线法的迭

8、代格式及其收敛性。 【掌握】 二分法的对分次数的计算； 一般迭代法的收敛性判定定理的应用； 牛顿法的迭代格式及其收敛性。,【重点掌握】 二分法的对分次数的计算； 一般迭代法的收敛性判定定理的应用； 牛顿法的迭代格式及其收敛性。 三、思考与练习 【练习】 习题二： 2、4、5、6、8 、10,2、基本思想（步骤） 取 a0=a ,b0=b (隔根) ， 计算其中点，x0=1/2 (a0+b0) 如果f(x0)=0,则根x*为x0，计算结束 如果f(x0) 0，计算f(a)与f(x0), 若 f(a)f(x0)0 则根x*(a,x0),令 a1=a,b1=x0 否则根x*(x0,b),令 a1=x

9、0,b1=b,2 对分法（二分法）,3.误差估计 由式(22)和(23)还可得到误差估计式为,(2-4),对于确定的精度,从式(2-4)易求得: 需要二等分的次数k ,二分法具有简单和易操作的优点，但缺点是收敛慢，不能求重根。 4.计算步骤 输入有根区间的端点a,b及预先给定的精度; (a+b)/2 x; 若f(x)=0,则结束 若f(a)f(x)0,则x b,转向;否则x a,转向 。 若b-a,则输出方程满足精度的根x,结束;否则转向。,迭代法就是一种利用递推公式进行运算的方法，用其生成一个迭代数列，来逼近方程的根。 一、迭代格式 考察方程f(x)=0,将f(x)=0改写为下列等价形式 x

10、=(x) 并可以做出下列的迭代格式 xk+1= (xk) k=0,1,2, (2-7) 则(x) 称为迭代函数,3 迭代法,从给定的初始近似根x0出发,按迭代公式(2-7)可以得到一个 数列 x0,x1,x2,xk, 如果(x0)是连续的，且这个数列xk收敛到x*,则有,则x*就为f(x)的根，满足x*= (x*)，称x* 为的一个不动点 （即 f(x)=0 的根）。 根据误差要求，计算到某一步，就可以把xk作为f(x)=0 的近似值。 注意迭代法的三步曲： 改写迭代格式求数列，且数列收敛， (x) 连续，则x*为原方程的根。,二、迭代格式的收敛性 收敛定理1 ：设(x)在a,b上具有连续的一

11、阶导数，且满足下列条件： (1)对任意x a,b，（x） a, b ， (2)对任意xa,b，存在常数L(0,1)，使 |(x)|L1， 则(1)方程x=(x)在a,b上有唯一的根x*,且对任意初值x0a, b,迭代格式xk+1= (xk) k=0,1,2, 均收敛于x*； （2） （3）,( k = 1, 2, ),由上面的定理知： （1）迭代过程是一个求极限的过程，实际计算不能无限次计算 ，可按事先给定的误差，当相邻两次迭代的差|xk+1-xk| 时，取xk+1 作为根的近似值； （2）由于给定x0后，x1=(x0)就确定了，则|x1-x0|为一定值，由式（2-8）,| x*- x k |

12、 |x1 x0 | 解之得迭代次数k的值：,k = ln / ln L,二、计算步骤,迭代法的突出优点是算法的逻辑结构简单,且在计算时,中间结果若有扰动,仍不会影响计算结果。其计算步骤为: (1)确定方程f(x)=0的等价形式x= (x),为确保迭代过程的收敛,要求(x) 满足李普希茨条件(或|(x)|L1); (2)选取初始值x0,按公式 x k+1= (xk), k=0,1,2,进行迭代，得到迭代序列; (3)若x k+1-xk,则停止计算,xx k+1。,4 迭代法的收敛速度 一、收敛速度 定义2 (p20)设序列 xk 收敛到 x*，记误差ek = xk- x* 如果存在实数p 1 及

13、非零常数C， 使,则称 xk 收敛于x*的收敛速度为p阶， C称为渐进误差常数， 当p=1时 称 xk为线形（一次）收敛；当p=2时称 xk为平方 （二次）收敛;当1p2时 称 xk为超线性收敛。,由该定义可见，一个方法的收敛速度实际上就是绝对误差的收缩率，敛速的阶p越大，绝对误差减得越快，也就是该方法收敛的越快。,定理3： 对于迭代过程xk+1 =(xk)，如果迭代函数(x) 在x* 的邻近有连续的二阶导数，且|(x*)| 1， 则对于充分靠近x*的初始值x0，迭代过程是收敛的（局部收敛性），且 ( 1 ) 当(x*) 0 ，迭代过程为线性收敛； （2）当(x*) =0 ，”(x*) 0 ，

14、迭代过程为平方收敛。,例3 考查 取 (x) = 1+ 1/x + 1/x2 时 ， 用 xk+1 =(x k）求解 x3-x2-x-1=0 在区间 1，2 根的收敛性和收敛阶 （ x* =1.839) 解： 由 (x) = 1+ 1/x + 1/x2 得知 (x) = -（1/x2 + 2/ x3 ) 对任意 1,2 区间上的x ,不满足 | (x) | 1 , 也即不满足全局收敛定理（定理1） 但可验证 ：当 x 1.7 , 2 时 | (x) | 1 若取 x 0 =2 可算出 x 1=1.91293 .x 13=1.83929 对(x) = -（1/x2 + 2/ x3 ) ， 显然

15、(x*) 0 ，p=1 一阶收敛,5 Newton迭代法 （逐步线性法, 切线法） 1、迭代格式 （1） 设有一非线性方程 f(x)=0 设f(x)在a,b上连续， f(a) .f(b) 0 ，且x0为 a, b上根x* a, b的一个近似值。过（x0,f(x0)）作曲线f(x)的切线，其方程是：,2、牛顿迭代法的收敛性 定理4.设 f (x) 存在， 在包含零点x*的某个区间内有二阶连续导数, 且f (x*)不为零 ，若 则Newton迭代格式至少是二阶收敛. 上述定理中,要求x0要充分靠近于x*才能保证收敛，因此是局部收敛性，下面考虑大范围的收敛定理。,定理5 全局收敛定理（p24大范围收

16、敛定理） 设 f( x) 在 a ,b 上满足下列条件： f(a)f(b) 0 则Newton迭代序列收敛于f(x) =0 在 a, b的唯一根。 证明略。,-.保证有根,-.保证单根,-.保证凸凹性不变,-.如何取x0,第三章 线性代数方程组的解法,引言 高斯消去法 高斯列主元消去法 矩阵分解法 向量和矩阵范数 解线性代数方程组的迭代法,二、基本要求 【了解】 1. 高斯消去法的求解思想； 2. 高斯约当消去法； 3. 方程组的性态和条件数； 【掌握】 1. 高斯列主元消去法的求解过程； 2. 矩阵分解法中LU分解和平方根法； 3. 解三对角方程组的追赶法； 4. 向量和矩阵的1-范数、2-

17、范数、-范数的计算； 5. 求解线性代数方程组的雅可比迭代和高斯-赛德尔迭代。 【重点掌握】 1. 矩阵分解法中LU分解和平方根法； 2. 向量和矩阵的1-范数、2-范数、-范数的计算； 3. 求解线性代数方程组的雅可比迭代和高斯-赛德尔迭代。,高斯消去法是解线性方程组最常用的方法之一，它的基本思想是通过逐步消元，把方程组化为系数矩阵为三角形矩阵的同解方程组，然后用回代法解此三角形方程组可得方程组的解。,第二节 高斯消去法,高斯消去法的主要思路： 将系数矩阵 A 经过消元过程化为上三角矩阵，然后回代求解。,考虑 一般n 阶线性方程组：,即:,三、特点 1、优点： 公式简明，容易程序化 2、缺点

18、： 第k次消元时， 必须 a kk 0 , 且当 a kk 0 时 ，误差很大， 数值不稳定 (p35 N-S图）,二、列主元消去法 1、选主元再消元 在每一步消元之前，即第k次消元时 ，在第k列上选取绝对值最大的元素为主元素 ai0k(最大值在i0行上） 若 | a i0k | p 中断 否则 若i0 k 将i0 和 k 行互换 再按高斯消去法消元 2、回代 不改变方程组的解，同时又有效地克服了Gauss消元的缺陷,四、 高斯约当消去法,前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程稍加改变可以把方程组化为对角形,第四节 矩阵分解法（直接法） 一、三角分解法 把A分解为

19、一个单位下三角阵L和一个上三角阵的乘积，称为A的LU分解，也叫Doolittle（杜利特尔）分解。 一般的，如果能把系数矩阵分解为A=LU，其中L为单位下三角阵，U为非奇异上三角阵，那么方程Ax=b可化为 LUx=b 令Ux=y，则有Ly=b，这样原方程组转化为先解下三角方程组Ly=b，求出y，再解上三角方程组Ux=y求出x。,正如高斯消去法中的消元过程不一定能进行到底那样，一个矩阵也不一定能进行LU分解。 由下面讨论能进行LU分解的条件。,定理1 ：(p40) n x n阶矩阵有唯一LU分解的充分必要条件是 矩 阵A的各阶顺序主子式都不等于0。 证明略。 我们关心的是如何进行LU分解，即如何

20、把LU求出来。设A的各阶顺序主子式都不等于0，并设L=(lij),U=(uij)。,由A=LU知：,a11 a12 a1n a21 a22 a2n ar1 ar2 arn an1 an2 ann,lr1 lr2 lr3,U=,先计算U的第一行，L的第一列元素，有矩阵乘法知 a1j=u1j(j=1,2,n) ai1=li1u11(i=2,3,n) 得到 u1j=a1j (j=1,2,n) li1=ai1/u11(i=2,3,n) 类似的由A的第二（r）行元素，计算U的第二（r）行，由A的第二（r）列元素计算L的第二（r）列元素。,一般的计算U的第r行，L的第r列元素的方法设计考虑A的第r行，第r

21、列元素，由矩阵乘法知： 由 得到,由 得到,注意计算顺序,u11 u12 u13 .u1n,l21,l31,.,ln1,第一步计算,u22 u23 u2n,l32,.,ln2,第二步计算,.,unn,第n步计算,L U计算的紧凑格式,二、解对称正定的平方根法 定理2：若 n阶方阵A对称正定，则存在唯一的对角元素为正的下三角阵L，使A=LLT (Cholesky分解） 证明略,a11 a12 a1n a21 a22 a2n ar1 ar2 arn an1 an2 ann,由a11=l211，得l11= 考虑第一行元素，a1j=l11lj1,j=2,3,n，得lj1=a1j/l11 这样就计算出L

22、的第一列，LT的第一行 考虑第二列的下三角元素， 由a22=l221+l222，得到 由ai2=li1l21+li2l22,得到 li2=（ai2-li1l21）/l22,i=3,n 这样就计算出L的第二列，LT的第二行 一般的,由上面的推导可求出按行计算公式:对i=1,2,n,将A分解后，即A=LLT，代入 Ax=b，得 LLTx = b 将其化为下列与原方程组等价的两个方程组 Ly = b LTx = y 然后回代，求出y与x。,此时 AX=b LLTX=b 令 LTX=Y 则AX=b 等价于 LY=b LTX=Y,=,三、解三对角阵的追赶法 解三对角方程组的追赶法（Thomas算法） 基

23、本思想： AX=F = 若A为对角占优 即 |b1|c1| |bi|ai|+|ci| i=2,.n-1 ai.ci 0 |bn|an| 则A可以写成：A=LU 即,对比法求得pi与qi的递推公式： p1=a1 a1=p1*1 q1=c1/p1 c1=p1*q1 对于i=2,3,n 行计算 pi=ai-bi*qi-1 ai=bi*qi-1+pi qi=ci/pi,AX=F 即 LUX=F 可写成 由 LY=F知 = 由矩阵乘法可求 将（3.29)代入可得 i=2,.n,求出yi后再由 UX=Y 即 = 同样根据矩阵乘法求 (3.32) i=n-1,.1,第五节 向量和矩阵的范数 一、向量的范数

24、定义1: 若向量xRn 即x=(x1,x2.xn) T ,定义某个实数值函数 N(X)=|X|，若满足以下三个条件： (1) | X |0 当且仅当X =0时，| X |=0 正定性 (2) |C.X|=|C|.|X| C为任意常数 齐次性 (3) |X+Y| |X| + |Y| 三角不等式 则称N(X)是R 上的一个向量范数 或模。,2、常用的向量范数 1- 范数 | X|1 = 2-范数 |X|2 = ( )1/2,-范数 |X|= max |xi| 1=i=n,p-范数 |X|p= ( )1/p,例2 已知向量 X=（1,- 2 , 3)T 求| X|1 ， |X|2 ， |X| 要求:

25、会计算向量的范数,3、向量范数的性质 设 x, y Rn 则 | |x| - | y| | = - | x-y| 所以：| |x| - | y| | = | x-y |,（2）设 |x|与|x| 是R n上任意两种向量范数， 则存在正常数m和M 使一切 x Rn 有 m|x| = |x| = M|x| 如： |X| = |X|1 = n |X| 说明：向量范数的等价性，说明x的一切范数都是等价的。 一种范数对应一种长度，一种长度对应一种收敛性，等价性表明，当|x|趋于0时， |x| 也趋于0，只不过趋于0的速度不一样，即收敛的速度不一样。但收敛性是一样的。,定义3 :设向量序列 X (K) =

26、(x1(K) ,x2 (K) .xn (K) ) T 和向量X* = (x1* ,x2* .xn* )T 对任意i(i=1,2.n) 有 则称向量序列X (K) 收敛于X * 记做 说明：如果向量的每一个分量都收敛，则向量收敛于X * 。,定理3 ： 对R n上的任一种向量范数|.|，向量序列 x(k) 收敛于向量x*的充要条件是： | x(k) x* | 0 （当k-时 ) x(k) x* = （x1(k)-x1*, x2(k)-x2* , xn(k)-xn*）T xi(k) -xi* xi(k) - xi* -0 | x(k) x* | 0 由范数的等价性知 ，存在M ，m 0 使得 m

27、| x(k) x* | | x(k) x* | M | x(k) x* | 说明：看向量x(k) 是否熟练于向量x*，就要看| x(k) x* | 是否收敛于0。,二、矩阵的范数 1、 定义4 若矩阵AR n n 的某个非负实值函数 N(A)=|A| 满足 (1) |A|0 当且仅当A=0时，|A|=0 正定性 (2) |C.A|=|C|.|A| C为任意常数 齐次性 (3) |A+B| |A| + |B| 三角不等式 (4) |AB|A|B| 相容性 则称N(A)是R n n 上的一个矩阵范数 或模。,定义5 设XRn ，AR nn，且给出一种向量范数|X|， 则称 为矩阵A的算子范数。 说

28、明: |AX|A| .|X| 常用公式 由向量范数诱导出的矩阵范数，即矩阵范数和向量范数的关系。,A的行范数 |A| = max 1=i=n,2、常用的矩阵范数,A的列范数 |A|1 = max 1=j=n,A的2范数 |A|2 =,A的p范数 |A|p = ( )1/2,例3 已知 A= -1 3 0 2 计算A的1，2，范数 要求:会计算矩阵的范数,定义6 谱半径 设 AR n n 的特征值为i(i=1,2.n) 称 (A)=max|i| 为A的谱半径 1in 那么,谱半径和范数之间是什么关系呢?,定理4 ：特征值上界定理 设 A R n n ,则 (A) |A| ， 即A的谱半径不超过A

29、的任何一种范数。 证明： 设是A的任一特征值， x为相应的特征向量，则 AX= x | | |x| =| x| =|AX|= |A|X| 所以 | |= |A| 也即 (A)= |A| 结论：任何一种特征值都小于范数，最大的特征值是谱半径。,三、 方程组的性态和条件数 方程组的系数和右端项都或多或少的带有误差，这种误差有时会使方程组的解面目全非，有时却影响不大。 这涉及到方程组解的敏感程度。,定义7 设 A为非奇异阵， 称Cond (A) =|A-1|A|为矩阵A的条件数 由此可知，方程组AX=b 的病态程度可由系数矩阵A的条件数Cond (A) 来刻画，其值越大，方程组的变态就越严重。 常用

30、的条件数有： (1) Cond(A) = |A-1| |A| (2) Cond(A) 2= |A-1| 2 |A| 2 =,当A为对称正定时 Cond(A) 2=| 1| / | n | , 其中 1， n为矩阵A的最大和最小特征值 例: 求矩阵A的条件数 逆阵的求法 A-1= A* / |A| A*为A的伴随矩阵,1、雅克比迭代公式,方程组AX=b 即: a11x1 + a12x2+. . a1nxn =b1 a21x1+ a22x2+. a2nxn =b2 . ai1x 1+ ai2x2+aiixi .ainxn = bi . an1x1+ an2x2+annxn =b n,若aii0，则

31、可从第i个方程分离出xi (i=1,2.n),若aii0，则从第i个方程分离出:,其中 cij= -aij / aii , di= bi/aii ( i=1,.,n, j=1,.,n, ji ) cii =0,xi = (bi - ) /aii = + di (i=1,.,n),即: x1 = c11x1 + c12x2+. . c1nxn +d1 x2 = c21x1+ a22x2+. c2nxn +d2 . xi = ci1x 1+ ci2x2+ciixi .cinxn +di . xn = cn1x1+ cn2x2+annxn +d n,xi(k+1) = + di (i=1,.,n k

32、=0,1,2.)(3.40) - Jacobi迭代公式(分量形式) 也可写成 X (K+1) = CX (K) +d - Jacobi迭代公式(矩阵形式) 其中 cij= -aij / aii ji cii=0 选一初始近似值x(0)=(x1(0),x2(0),xn(0)T，用上式进行迭代计算，可得到一个近似解序列 x1(k),x2(k),xn(k) (k=0,1,2,) 如果极限 存在，则称迭代格式收敛，其 极限值 (x1,x2,xn)T就是原方程组的解。 按照上述格式进行迭代求方程组的解的方法称为简单迭代法，又称为雅可比迭代法。,2、迭代格式的收敛条件 充分条件1 在迭代格式中，若 则雅可

33、比迭代格式对任意初始值x(0)和d都是收敛的。 证明：回忆定义3:设精确解为X* = (x1* ,x2* .xn* )T 对任意i(i=1,2.n) 有 则称向量序列X (K) 收敛于X *，记作 根据定理4，要证明当k-时，,充分条件2 在迭代格式中，若 则雅可比迭代格式收敛。 充分条件3 在迭代格式中，若 则雅可比迭代格式收敛。 汇总充分条件1，2，3，只要迭代矩阵至少有一种范数1，则雅可比迭代格式收敛。 迭代收敛格式，什么时候终止？ 每次迭代后判断|xi(k+1)-xik|=|xi(k)|是否成立， 如果成立，可停止迭代。,由Jacobi迭代公式 xi(k+1) = + di (i=1,

34、.,n k=0,1,2.) ， 在迭代的每一步计算过程中，是用x（k)的全部分量来求x (k+1) 的所有分量， 显然，在计算第i个分量xi(k+1)时，已经计算出的最新分量 x 1(k+1),.x i -1(k+1)没有被利用， 对这些最新计算出的分量加以利用，也即在Jacobi迭代中用: x1(k+1),.x i-1(k+1）来代替x1(k),.x i-1(k） 所得公式即为Gauss-seidel迭代。,2、迭代格式的收敛条件 充分条件1 在迭代格式中，若 则高斯-赛德尔迭代格式对任意初始值x(0)和d都是收敛的。 充分条件2 在迭代格式中，若 则高斯-赛德尔迭代格式收敛。,汇总充分条件

35、1，2，只要迭代矩阵至少有一种范数1，则高斯-赛德尔迭代格式收敛。 迭代收敛格式，什么时候终止？每次迭代后判断 |xi(k+1)-xik|=|xi(k)|是否成立，如果成立，可停止迭代。,三、严格对角占优矩阵的雅可比和高斯-赛德尔迭代格式 定义8 设 A=( aij) 是一个 n x n 矩阵，若 | aii | (i=1,2.,n) 则称A为严格对角占优矩阵。,定理4: 方程组Ax=b，其中A为n阶严格对角占优矩阵时，一定存在收敛的雅可比迭代和高斯-赛德尔迭代格式。 证明。,总结： Jacobi迭代收敛条件 充分条件(1) : 方程组 AX=b的系数矩阵A为 严格对角占优阵 充分条件(2)

36、:迭代矩阵至少存在一种矩阵范数|.|, 使 | C | 1 充要条件(3)：迭代矩阵的谱半径(C) 1,总结： 高斯-赛德尔迭代收敛条件 充分条件1 :方程组 AX=b 的系数矩阵A对称正定 充分条件2: 方程组 AX=b 的系数矩阵A严格对角占优 充分条件3 ： 迭代矩阵C的范数 |C| 1 充要条件 4：迭代矩阵C的谱半径 ( C ) 1,第四章 插值与拟合,二、教学基本要求 【了解】 1. 代数插值问题的插值余项形式； 2. 差商性质与关系； 3. 分段线性插值的构造方法； 4. 样条函数插值的构造方法。 【掌握】 1. 拉格朗日插值的计算方法； 2. 差商表的构造和牛顿插值的计算方法；

37、 3. 样条函数插值的定义及其构造思想； 4. 曲线拟合的最小二乘法的应用。,【重点掌握】 1. 拉格朗日插值的计算方法； 2. 差商表的构造和牛顿插值的计算方法； 3. 差商、差分和导数三者之间的关系； 4. 曲线拟合的最小二乘法的应用。,代数插值 定义1 ：( p66) 已知函数 y = f(x)在区间 a, b上有定义，且已知n+1个点 （xi ，y i) ( i=0,1.n ) ax0 x1x2xnb 若存在一个次数不超过n次的代数多项式： Pn (x)=a0 + a1 x + a2 x2.+ a n x n 满足条件 Pn( xi ) = f ( xi ) = y i (i=0,1,

38、.n) , （4-1） 则称： Pn (x)为 f (x)的插值函数（插值多项式） f (x) 为被插值函数 xi (i=0,1,.n) 为插值节点 a , b 为插值区间 （4-1）称为插值条件 Rn (x) = f (x) - Pn(x) 为插值余项（ Pn(x)近似代替f (x)的截断误差）,定理1 ：满足 Pn( xi ) = f ( xi ) = y i (i=0,1,.n)(插值条件4-1)的n 次插值多项式 Pn(x) 是存在且是唯一的。,证明： 分析： 设Pn (x) = a0 + a1 x + a2 x2 . + an xn 只要证系数ai唯一，多项式唯一， 因为它通过n+1

39、个已知点(xi , yi) (i=0,1n)，等价于线性方程组的解。Pn(x)满足：,一般Lagrange 插值多项式 将li(x)代入pn(x)，得到pn(x) 的表达式： pn(x) = y0 l0(x) + y1 l1(x)+ + yn ln(x)= = 上式称为f(x)的 Lagrange插值多项式，并记为：Ln(x) 其中li(x)= ，满足下列性质： 称 li(x) 为对应节点的 xi 的插值基函数。 下面我们考虑插值基函数的另一种表示方式：,设 在区间 a,b上连续， 在区间 (a,b)上存在, pn(x)是满足插值条件（4-1）的不超过n次的插值多项式，则对 ,存在 ，满足 其

40、中 ,且当 在区间 a,b有上 界 时，有,四 、插值余项,pn(x),一、差商 (均差) 定义：函数y=f(x)在区间xi , xj上的平均变化率称为函数关于点 xi , xj的一阶差商，记为fxi , xj，即 例如：,一阶差商的再差商,称为函数f(x)在点xi , xj , xk的二阶差商记为 f xi , xj , xk ,(ij),2. 牛顿插值多项式 由差商的概念，得到另一种新的插值多项式牛顿插值多项式： Nn ( x )=f(x0) + f x0,x1 (x-x0) + f x0,x1,x2( x-x0)(x-x1)+ + f x0,x1,x2,x3 (x-x0)(x-x1)(x

41、-x2) . + f x0,x1,.x n (x-x0 )(x-x1)(x-x n-1),3、差商表的构造,利用牛顿插值多项式，必须先计算各阶差商。计算差商可以从定义出发，一般采用如下形式的差商表来计算。,表格中斜线上对应的数字就是系数，由此可直接写出牛顿插值多项式。,差商是一个非常重要的概念，在牛顿插值多项式构造和微分方程数值解等学科中都具有十分重要的作用，现在来讨论差商的一些重要性质：,4、差商的性质,性质1 n阶差商fx0 x1xn可由函数值f(x0)f(xn)的线性组合而成。即： (4-24),性质2 差商具有对称性，即在n阶差商中，任意调换xi,xj的顺序，其值不变。 由性质1知，,

42、任意改变xi,xj的位置，变化仅是求和顺序的变化。 由这个性质知： f x0 , x1 , x2 = f x0 , x1 , x2 = f x0 , x1 , x2 ,性质3 如果 f (x) 的 k-1阶差商 f x, x0,x k-1 是关于x的 m 次多项式， 则f (x) 的 k阶差商 f x, x0,xk 是x的 m-1 次多项式. 性质4 差商与导数的关系 设f(x)在a,b区间上具有n阶导数，则这一区间上至少有一点 ，使 f x0,x1,.x n = f (n) ()/n!,5、插值多项式的余项 我们已讲过Lagrange 插值多项式和牛顿插值多项式 根据pn ( x )的唯一性

43、知： Ln ( x ) = N n ( x ) 则两个插值多项式的余项也相等。 则Rn (x) = f(x)-Nn(x)=f x,x0,x1.x n n+1 (x),第五节 分段线形插值 为使插值更准确，自然希望增加数据点。误差Rn(x)是否随着数据点的增多，即随n的增大而减小？这是我们关心的一个问题。 考察余项公式(4-15)看出，余项Rn(x)的大小与插值节点的个数n+1有关，但是不能简单的认为在一确定的区间里节点越多（即n越大），误差Rn(x)就越小。,几何意义：用一条折线近似的代替曲线f(x),关键： 分段、低阶插值,类似 拉格朗日插值多项式的表示，应用各节点的分段插值基函数，则分段插

44、值函数可表式为： 分段线性插值函数的光滑性虽然差一些，但从整体上来看，它逼近f(x)的效果是好的。 分段线性插值函数的余项可通过线性插值多项式的余项估计。,第六节 三次样条插值 分段低次插值方法的特点： 用低次多项式“装配”插值函数，它只能保证各段曲线在连接点的连续性，不能保证整个曲线在连接点的光滑性。 样条函数插值就是能保证在节点上满足一定光滑性的分段插值多项式。,三次样条函数 定义：在a,b上取n+1个点,若函数 满足：,此时 叫插值函数；,(3) 在内结点或在整个区间上具有连续的k-1阶导数。 则称S(x)为y=f(x )的 k 次多项式样条插值函数。 x0,x1,xn 就称为样条节点，

45、 x1,xn-1称为内部节点， x0,xn 称为边界节点。,(2) 在每个小区间,上是k 次多项式；,(1),3,2,3,二、三次样条插值函数的构造方法 1、系数用节点处二阶导数表示的三次样条插值函数（M关系式） (重点） 引入记号 Mi= s (x i) mi= s(x i) i=0,1n 用节点处二阶导数表示样条插值函数时称为大M 关系式 用节点处一阶导数表示样条插值函数时称为小m 关系式 问题: 给定插值点 ，怎样构造用二阶导数表示的样条插值函数，即怎样构造 M关系式？,基本思想： si(x)是三次的 (条件3) ，si (x)是一次的， 对si(x)可构造线性插值，然后对si(x)积分

46、两次得s(x)，所有的常数按条件求出. 设在小区间 xi-1 , x i 上 s (x) =s i (x) i=1,2n 因si (x)是三次的, 故 s i (x)是一次的 s“i(x) 在 x i-1 ,xi 上是线性函数，对si(x)线性插值： 记si(x) =Mi i=0,1,n 不用掌握公式，只要掌握步骤即可,插值方法小结,拉格朗日插值（高次多项式插值）：曲线光滑；误差估计有表达式；收敛性不能保证（振荡现象）。用于理论分析，实际意义不大。,4.7 曲线拟合的最小二乘法 一、引言 设一组观测数据为,其中xixj(ij),我们要根据这一系列数据找出函数关系y=f(x)。 若用插值函数 p

47、(x)代替函数关系f(x),要求满足插值原则 p(xi)=f(xi)=yi, i=1,2,n 插值缺陷： 1、插值点多时，高次插值，收敛性无法把握，计算量大 2、分段低次插值，没有统一的表达式 3、由于观测点和观测数据本身就有误差,就会使函数保留这些误差,而影响逼近函数的精度。,拟 合 问 题 实 例 1,求600C时的电阻R。,设 R=at+b a,b为待定系数,拟 合 问 题 实 例 2,求血药浓度随时间的变化规律c(t).,半对数坐标系(semilogy)下的图形,拟 合 问 题 实 例 3,已知某大学生工作以后6年的工资,预测他10年后的工资,即：并不要求近似函数p(x)所表示的曲线通

48、过这些观测点,而只要求由已知数据(xi,yi)(i=0,1,n)找出x,y之间的依赖关系,使得近似函数p(x)能充分地反映函数y=f(x)的大致面目,也即与f(x)有最好的拟合(或逼近)。这就是曲线拟合问题。,二、线性拟合和最小二乘法 下面我们通过例子说明建立近似函数(x)的一种方法最小二乘法 1、引例： 为测刀具的磨损速度，经一定时间x，测一下刀具厚度y 研究y与x的关系。也就是找一个能大体反映上述数据变化的近似函数(x) 解:(1)首先需要确定(x)的类型。先画出散点图，可以用坐标纸，将x，y数据描于图上，叫散点图。从散点图上可以直观看出两个变量之间的大致关系。,从上面的例子可以看出，对于

49、一组给定的数据用最小二乘法找出其合适的拟合曲线，可以按以下步骤进行： (1)分析数据，将已知数据画在坐标纸上，得到散点图，从图上可以直接地看出数据的变化趋势。 (2)建立数学模型，根据上述分析，确定拟合函数(x) 的类型。 (3)应用最小二乘法，确定拟合函数中的未知参数。 若取(x) =a+bx是线性函数，这样的拟合是线性拟合。,2、用最小二乘法解矛盾方程组 设有如下方程组 其中nm,即方程的个数大于未知数的个数。一般情况下，上述方程组往往无解，这样的方程组就称为矛盾方程组。现在来求x1,x2,xm,使方程组的两端近似相等。（误差达到最小的近似解）,总结：求解矛盾方程组的最小二乘法的步骤： 1

50、、矛盾方程组Ax=b的正规方程组为 ATAx= ATb, x=(ATA)-1 ATb 相当于用AT去乘方程组的两端。 计算ATA， ATb得到正规方程组ATAx= ATb 2、求解正规方程组，得到矛盾方程组的最小二乘解。,三、可化为线形拟合的情况 线形拟合使用方便，但有时变量之间的关系并不是线形关系，可考虑通过变量替换把较复杂的非线性拟合转化为线性拟合，如： 双曲线 1/y= a+ b/x 变换：可令 y = 1/y x =1/x 则有 y =a+bx ,指数函数 y=aebx 变换：两边取对数 lny=lna+bx 令 y =lny x =x a =lna 则有 y = a bx ,指数函数

51、 y=aeb/x 变换： 两边取对数 lny=lna+ b/x 令 y =lny x = 1 /x a =lna 则有 y = a bx ,4对数函数 y=ab lg x 变换： 令 y =y x = lg x 则有 y = a bx ,5幂函数 y=axb 变换：两边取对数 lny=lna+ blnx 令 y =lny x = lnx a =lna 则有 y = a bx ,6S曲线 y=1/(abe-x ) 变换：两边取倒数 y=a+ be-x 令 y =y x = e-x 则有 y = a bx （例p105例10）,四、多项式拟合,第5章 数值积分与微分,5.2 牛顿 柯特斯(Newt

52、onCotes) 公式 5.3 复化求积公式 5.4 龙贝格(Romberg)积分方法,【掌握】 1. 数值积分公式的一般形式； 2. 代数精度的定义与求法； 3. 梯形公式与辛浦生公式的计算； 4. 梯形公式与辛浦生公式的代数精度及其截断误差； 5. 复化梯形公式与复化辛浦生公式的计算及其截断误差； 6. 高斯求积公式的定义。 【重点掌握】 1. 代数精度的定义与求法； 2. 复化梯形公式与复化辛浦生公式的计算及其截断误差；,此处，xk+1-xk是a ,b每一个分割小区间的长度与f(x)无关.,一、数值求积公式的一般形式,为了计算积分的近似值，用分点x0,x1xn,将区间分为n份，相应的曲边

53、梯形被分为n个小曲边梯形，计算第k个小曲边面积时，可以用矩形面积(xk+1-xk)f(xk)近似代替，则有积分的近似计算公式：,二、求积公式的代数精度 1、定义 若求积公式（5.1) 对于一切不高于m次的多项式都准确成立，而对于某个m+1次多项式不能精确成立，则称该求积公式具有： m次代数精度 2、判定定理（充要条件） 求积公式（5.1)具有m次代数精度的充要条件为： 当f(x)=1, x ,x2, x3,.x m ,求积公式（5.1)准确成立 而当f(x)= x m+1， 求积公式（5.1)不能准确成立,f(-1) + 2f(0) +f(1) ,例1 下列求积公式具有几次代数精度？,解: 当

54、 f(x)=1时 左=右=2 当f(x)=x时 左=右=0 当f(x)=x2时 左=2/3 右=1 左右 所以,该求积公式具有1次代数精度,例2:确定下列求积公式中的待定参数，使其有尽可能高的代数精度，并指明求积公式所具有的代数精度,三、插值型求积公式 基本思想：应用插值多项式来近似代替f(x)，并用插值多项式的积分近似的代替 的积分。,这样就得到一个数值求积公式： 其中 称式（5-4）为插值型求积公式。 该公式的特点是直接利用某些点上的函数值计算积分值，将积分求值问题归结为函数值的计算问题，从而避开了牛顿莱布尼兹公式需要寻找原函数的困难。,由插值余项知，对于插值型求积公式的余项是： 公式（5

55、-5）称为插值型求积公式的余项，也称为插值型求积公式的截断误差。,3、代数精度 对于插值型求积公式 ，当f(x)取次数不超过n次多项式时， f(x)=a0+a1x+a2x2+.+anxn f (n+1)(x)=0 , 余项 R=0 也即：求积公式 对一切次数不超过n次的多项式精确成立， 所以： 含有n+1个结点x k的插值型求积公式至少具有n 次代数精度。,定理2(p118 ) 形如 的求积公式至少有n次代数精度的充要条件是: 它是插值型求积公式。 只要证明 就能证得上式是插值型求积公式。 对,例3:证明插值型求积公式中求积系数之和等于插值区间的长度即:,证明: 因为含有n+1个插值节点的插值型求积公式 至少具有 n次代数精度, 则也至少具有0次代数精度,即对f(x)=1恒成立 此时,因f(x)=1所以有,5.2 牛顿 柯特斯(NewtonCotes) 公式 （等距节点下的插值型求积公式 ),若节点可以自由选取，则一个自然的办法就是取等距节点，即对区间做等距分割。,该数值积分称为Newton-Cotes积分,1、梯形公式(重点) 当n=1时，即给定两个节点 ( a,f(a)和（b,f(b), 可算出：,此时,(58),梯形公式,2、抛物式求积公式（ Simpson公式）(重点) 同样 n=2时,-