数值分析PPT教案.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数值分析,1,绪论,第一章插值法,第二章数值积分和数值微分,第三章曲线拟合的最小二程法,第四章,求非线性方程根的近似方法,第五章,线性代的方程组的直接法,第六章,解线性方程组的迭代法,第七章矩阵特征值和特征向量计算,第八章常微分方程数值解法,计算方法,2,参考书,1.数值分析，翟瑞彩，天津大学出版社；,2.计算方法，中山大学与武汉大学编写,3.数值计算计算原理，李庆杨，关治，,白峰彬，清华大学出版社,4.计算方法引论，,徐萃薇，科学出版社,3,1.计算方法的任务与特点,绪论,实际问题数学问题提供计算方法,程序设计上机计算结果分析,计算方法,4,2.基本的数学问题:,1.大型线性代数方程组Ax=b求解;,2.矩阵A的特征值和特征向量计算;,3.非线性方程 求解(求根);,4.积分 计算;,5.常微分方程初值问题求解;,6.其它。,5,求精确解(值)一般非常困难。例如：,1.方程组阶数n很大，例如n=20,计算机运算速度,1亿次/秒,用不好的方法,大约需算30多万年;,好方法不到一分钟。另外，有计算结果可靠性,问题。,2.特征值定义,6,3.形式复杂时求根和求积分很困难。,4.线性微分方程易解，如,非线性方程难解，如,希 望：求近似解，但方法简单可行，行之有效,（计算量小，误差小等）。以计算机为工具，易在计算机上实现。,计算机运算:只能进行加，减，乘，除等算术运,算和一些逻辑运算。,计算方法：把求解数学问题转化为按一定次序只,进行加，减，乘，除等基本运算,数值方法。,7,3.数值分析研究对象与特点,8,先看两个例子。,例1,求方程 x,2,=2sinx，在区间(1,2)内的根。,理论上可知显然找不出根的解析式，即无法求出精确解。,例2,用Cramer法则求解n元线性方程组。,显然理论上可行，且有精确表达式。实际计算时会出现什么问题呢？,9,实际问题,数学模型,上机计算求出结果,数值计算方法,看用数学和计算机解决实际问题的过程：,应用数学研究的任务,数值分析研究的对象,最终提供的是针对各类数学问题的数值算法（即计算公式、计算方案、计算过程）,10,3、具有好的计算复杂性,4.,数值分析提供的算法具有下面四个特点：,1、面向计算机,2、有可靠的理论分析,4、通过数值实验验证有效性,11,3、化整为零,5.,数值分析共同思想和方法：,1、迭代法,2、以直代曲,4、外推法,12,1.认识建立算法和对每个算法进行理论分析是基本,任务，主动适应,“,公式多,”,的特点；2.注重各章建立算法的问题的提法，搞清问题的基,本提法，逐步深入；3.理解每个算法建立的数学背景，数学原理和基本,线索，对最基本的算法要非常熟悉；4.认真进行数值计算的训练，学习各章算法完全是,为用于实际计算，必须真会算。,如何进行学习？,13,本课程的基本要求,掌握数值方法的基本原理,掌握常用的科学与工程计算的基本方法,能用所学方法在计算机上算出正确结果,14,课程学习结束后你具备的能力,1.对具体的数值计算问题，你会选择合适的算法，并通过计算机计算出正确结果；,2.对给定的算法会从理论上分析其优劣性；,3.会根据原理构造解决较简单数值计算问题的算法。,15,1.2 误差基础知识,一.误差来源（分类）,1.模型误差。,2.观测误差。,3.截断误差，如,右端是截断误差。,16,4.舍入误差。计算机字长有限，一般实数不能精确存储，于是产生舍入误差。例如：在10位十进制数限制下：,舍入误差很小，本课程将研究它在运算过程中,是否能有效控制。,17,实际问题,确定数,值解法,上机求解,用计算机解决实际问题的一般过程,建立数,学模型,模型误差、观测误差,截断误差,舍入误差,应用数学解决的问题,数值分析解决的问题,在此主要研究这两种误差,18,二误差基本概念,1绝对误差。设,准确值，,近似值。,称 为 的绝对误差。,为 的绝对误差限。,2相对误差。称 为 的相对误差。,实用中，常用 表示 的相对误差。,称 为 的相对误差限。,19,3有效数字,设,若 (1.1),则说 具有n位有效数字，分别是,若 ，则称 为有效数。,20,例1.1,设 =0.0270是某数 经,“,四舍五入,”,所得，则,误差 不超过 末位的半个单位，即：,又 ,故该不等式又可写为,由有效数字定义可知,有3位有效数字，分别,是2,7，0。,21,例1.2,=32.93,=32.89,故 有3位有效数字，分别是3,2，8。,由于 中的数字9不是有效数字，故 不是有效数。,22,三、有效数位与误差的关系,1.有效数位n越多，则绝对误差 越小,(由定义1.1),2.,定理1.1 若近似数 具有n位有效数字，则,(1.2),反之，若 则,至少有n位有效数字。,23,两边除以 得,(1.3)和（1.4）给出了由自变量的误差引起的函,数值的误差的近似式（误差传播）。,四、数值运算的误差估计(误差的传播),1.一元函数情形,设 则 ，由Taylor展开公式,(1.4),（1.3）,24,2.多元函数情形,设 ，,则，,由多元函数的Taylor展开公式类似可得,（1.5）,（1.6）,在（1.6）式中，分别取,可得,同号,),（1.7）,（1.8）,（1.9）,(,25,例1.3：,测得某桌面的长a的近似值a*=120cm,宽b的,近似值b*=60cm。若已知|e(a*)|0.2cm,|e(b*)|0.1cm。试求近似面积s*=a*b*,的绝对误差限与相对误差限。,解:面积s=ab,在公式（1.5）中,将,换为 s=ab,则,相对误差限为,26,1.3 选用算法应遵循的原则,1.尽量简化计算步骤，减少乘除运算的次数.,例如，计算多项式,通常运算的乘法次数为,若采用递推算法,则乘法次数仅为n.又如,27,2.防止大数,“,吃掉,”,小数,当|a|b|时，尽量避免a+b。例如，假设计算机,只能存放10位尾数的十进制数，则,3.尽量避免相近数相减,例如，当x很大时，应,，,当x接近于0时，应,28,4.避免绝对值很小的数做分母,当|b|a|时，应尽量避免 。,5.选用数值稳定性好的算法，以控制舍入误差高速,增长,例如,若 （误差 ）则计算,时误差扩大了 倍,而,（n=1,2,）,是稳定的。,29,范数,范数是长度概念的推广,是一种度量定义,是测量两个函数,向量,矩阵等之间距离的一个非负实数.范数的定义形式多种多样,采用同的范数定义,可得不同的范数,但都满足以下的三个条件(公理化定义):,1.(非负性),2.(齐次性),3.(三角不等式),称实数|X|为向量 X的范数.,#不同范数间的关系:等价.,30,基本要求：,1.熟悉计算方法在解决实际问题中所处的地位，熟悉计算方法是以计算机为工具求近似解的数值方法；,2.熟悉绝对误差（限），相对误差（限）及有效数字概念；,3.熟悉公式（1.2）-（1.9）；,4.熟悉选用算法应遵循的原则；,31,计算方法,f(x)=0根或f(x)零点，当f(x)复杂时，很难求,（找近似有效简单方法）。,第二章 求方程根的近似方法,2.1 区间二分法,理 论:f(x)Ca,b,单调，f(a)f(b)0,f(x)=0在(a,b)有惟一根。,根分离：画草图，试算.多项式方程根的模,的上下界。,32,例2.1 用二分法求,在(1,2)内的根，要求绝对误差不超过,解,：,f(1)=-50 -(1,2)+,f(1.25)0 (1.25,1.375),f(1.313)0 (1.313,1.375),f(1.344)0 (1.344,1.375),f(1.360)0 (1.360,1.368),f(1.5)0 (1,1.5),33,优点：条件简单.,缺点：收敛慢.,不易求偶数重根.,如图,，,则,（,事后估计,）,x,y,34,2.2 迭代法,一.迭代法的建立与收敛性,35,36,2.收敛定理定理2.2）,37,38,(2),，故收敛。,()1,39,(3),注：L越小，收敛越快。,40,3编程停机判断,（取定初值,）计算，当,时，由（）,3,式知,比较小，此时停机，,二、迭代加速公式（略）,由,41,2.3Newton 迭代法,一 Newton 迭代法,1.,迭代公式建立,在,点Taylor展开,Taylor展开线性化（重要思想）,近似于,解出 记为,，则,将,42,2.Newton迭代法的几何意义,过,切线,与,求交点，解出,则,43,3.Newton迭代法收敛定理（定理 2.6）,在,有根，且,在,（1）,连续，且分别不变号；,使,则 Newton 迭代法（2.1）产生的数列,的收敛到根。,为例证明（其它情况类似）,（2）取初值,设,证：,以,44,将,处Taylor展开,说明数列,有下界,又,故,单调递减。,收敛。设,则由（2.1），,，,45,例2.2,解：设,取,，则由（2.1）,用 Newton 迭代法求,46,基本要求,熟悉区间分法；,熟悉迭代法的建立，会使用收敛定理；,熟悉Newton迭代法及其几何意义和收敛条件。,作业：,习题4：,1、2、3、4、6,47,计算方法,二.迭代法的收敛阶(收敛速度),1.定义:设,若有实数p0,使,则称,p阶收敛,相应的迭代法称为p阶方法.特别,p=1时叫线性收敛,p=2时叫平方收敛.,p越大越好(why?),48,2.定理2.7,49,所以，此时Newton法至少二阶收敛.,(2)由2.6的证明有：,50,3.Newton法改进：,2.4 弦截法,(略),51,第三章 线性代数方程组解法,解线性方程组,52,一、Gauss消去法,设 有,线性代数：方法不好时工作量非常大，,工作量小的方法是 Gauss 消去法。,消 元：,3.1直接法,53,二 列主元素消去法-计算结果可靠,54,到此原方程组化为,55,到此原方程组化为,56,（3.3)是回代过程。,(上三角方程组)（3.2),(n)回代求解公式,(n-1)原方程组化为,以上为消元过程。,（3.3),57,三、Gauss 全主元消去法：,优点-计算结果更可靠；,缺点-挑主元花机时更多，,次序有变动，程序复杂。,说明：,(1)也可采用无回代的列主元消去法(叫Gauss-,-Jordan消去法)，但比有回代的列主元消,去法的乘除运算次数多。,(2)有回代的列主元消去法所进行的乘除运算,次数为 ，量很小。,58,四、应用,（1）求行列式,（2）求逆矩阵,(以上过程都应选主元),59,记,，则,（三角因子分解）,Gauss消元，初等行变换，化原方程组为上三角型。,五矩阵三角分解法,60,定义3.1,叫,的三角（因子）分解，其中 是,是上三角。,下三角,为单位下三角阵（对角元全为1），,为上三角阵，则称,为Doolittle分解;,若 是下三角，,是单位上三角，则称,定理3.1 n阶阵,有唯一Doolittle分解(Crout）,的前n-1个顺序主子式不为0.（证略）,三角分解不唯一,为此引入,定义3.2 若,为Crout分解。,61,为什么要讨论三角分解？若在消元法进行前能实,现三角分解,，则,容易回代求解,62,回代求解很容易，如,63,基本要求：,1.熟悉收敛阶的定义；,2.熟悉Newton法及改进方法的收敛阶；,3.熟悉列主元消去法解线性方程组的计算,过程；,4.熟悉矩阵三角分解中Doolittle分解和,Crout分解定义；,5.熟悉利用三角分解来求解线性方程组的,思路；,作业：,作业集（A）第三章 1，2,64,计算方法,1直接三角分解法（以Doolittle分解为例）设,65,由矩阵乘法,66,(k),67,68,69,例31,选主元的三角分解法（略）,70,2平方根法,定理3.2,设A对称正定，则有非奇异下三角阵L，使,-理论基础 (证略）,分解方法：设,(choleskey分解),71,72,73,六、解三对角方程组,追赶法,(Crout分解),74,75,故有,(3.1),76,解,解,(3.1),(3.3)叫追赶法，工作量小，非常有效。,(3.2),（3.3）,77,基本要求,1.会矩阵的直接三角分解法的过程（不记公式）；,2.熟悉平方根法的计算过程（不记公式）及其优缺,点。,作业：,作业集（A）第三章 3.,78,一.简单迭代法,1.迭代法建立.考虑,(矩阵B不唯一),对应写出,3.2 解线性方程组的迭代法,计算方法,产生向量序列,若收敛,记,79,则于(3.4)两端取极限有：,上式说明：,是解向量,从而当k充分大时,注意:迭代阵B不唯一,影响收敛性。,解向量,(1)叫简单迭代法,B叫迭代矩阵。,2.收敛性.,定义3.3 称,为矩阵B的谱半径。,定理3.3 简单迭代法,80,定理3.4,81,收敛列解 (i=1,2,n),即,=0,例3.2 设有方程组(其中 )Ax=b,即,(3.5),作等价变形,(3.6),82,-Jacobi迭代法,于是有迭代公式,(k=0,1,2,),(3.7),83矩阵形式为：,84,(3)设方程组（3.5）的系数矩阵A按行严格对角占优即：,或按列严格对角占优，即,二、迭代法,设有简单迭代法 即,(3.8),85,称如下迭代法,(3.9),为与(3.8)对应的 迭代法，其迭代矩阵,可用,“,代入法,”,求得。,86,（1）迭代法(3.9)对任意 收敛,（2）若 则 迭代法(3.9)对,任意 收敛；,（3）若简单迭代法(3.8)的迭代矩阵 满,足 或 ，则相应的Seidel迭代法,(3.9)对任意 收敛（证略）,迭代法(3.9)的收敛性,87,例3.3 迭代方法,（3.10）,称为与Jacobi迭代法（3.7）对应的Seidel方法,其收敛情况如下：,(1)使用一般的Seidel方法（3.9）的收敛性判别法,(2)若系数矩阵A对称正定，则求解方程组（3.5）的,与Jacobi迭代法对应的Seidel方法（3.10）对任意,收敛。（证略）,88,松弛因子,=1 即Seidel方法(3.10),(3)若系数矩阵A按行（或按列）严格对角占优，则,求解（3.5）的与Jacobi方法对应的Scidel方法,（3.10）对任意 收敛.（练习）,(3.11)是一种加权平均。,三.逐次超松弛迭代法(SOR法),89,SOR方法的收敛性如下（不加证明）：,(1)SOR方法对任意 都收敛的必要条件是：,(2)若系数矩阵A对称正定，则 时SOR方法,求解 对任意 收敛；,(3)若系数矩阵A按行（或按列）严格对角占优，,则 时SOR方法对任意 收敛。,最佳松弛因子 选取问题。,90,例3.4 用Seidel迭代法求解方程组,解,：,因为系数矩阵严格对角占优，故Seidel方,法对任意 收敛。,取初始向量,要求,时迭代终止。,Seidel迭代格式为,91,计算结果可列表如下,注意：未必Seidel方法一定比Jacobi方法好。,92,1 熟悉简单迭代法及其收敛条件的使用；,2 熟悉Jacobi迭代法及其相应的Seidel迭代法的,计算公式以及它们的收敛条件；,3,熟悉SOR方法的计算公式及其收敛条件；,作业：,作业集(A)第三章 4，5，6，7,基本要求：93,复习：线代：,1.定义：若 则 叫A的特征,值，叫其相应的特征向量。,说明 还是特征向量。,2.求法,十分困难;应寻求近似解法,且简单、,可行、有效。,计算方法,第四章 矩阵特征值和特征向量计算,94,设A的特征值,特征向量,4.1乘幂法与反幂法,一乘幂法,求A的主特征值（按模最大者）及,其相应的特征向量,（假定,线形无关,）,95,96,97,说明:,有算法：,98,99,100,101,6.几何解释,102,解：,103,二反幂法,求A的按摸最小的特征值,。,设A可逆，由,104,对实对称矩阵A的全部特征值及特征向量,Jacobi旋转法,基本思想：,求一般矩阵全部特征值和特征向量的QR方法,参考书。,4.2 Jacobi旋转法,105,1.熟悉特征值和特征向量的定义；,2.熟悉乘幂法求主特征值的计算过程；,3.了解反幂法的思路；,基本要求,：,作业：,作业集（A）第四章 1.,106,第二章 插值法,107,108,注:不用待定系数法-(1)计算量大;(2)不易讨论误,差;,二次多项式插值-过两点直线;,三次多项式插值-过三点抛物线;,3.几何意义,109,插值满足的条件:找一个多项式 满足:1.2.p(x)是一个次数不超过n的多项式,110,一.插值基函数.,2.1 Lagrange插值公式,111,二.Lagrange插值多项式,112,三 截断误差：,113,一差商,2.2 Newton插值公式,1.定义,114,3.造差商表(实用),115,二Newton插值公式,116,117,118,119,解：先造差商表,120,由Newton公式得四次插值多项式为：,121,1.熟悉插值法的含义及其几何意义；,2.熟悉Lagrange插值公式及其余项的使用；,3.会造差表，并熟悉Newton插值公式的使用；,4.熟悉差商与导数的关系式。,基本要求：,作业：,P40-41:2，3,4,5,6,8,13,14,122,牛顿基本插值公式对结点是否等矩没有限制.不过当结点等距时前述牛顿插值公式可进行简化.为此先介绍差分概念.,2.3 等矩结点插值公式,123,1.定义 设,为,在,的以h为,步长一阶向前差分,m阶,一.差分,叫步长,称,一般:,一阶,二阶,124,(1)差分可表为函数值的线性组合 (证略),(2),(3),2.性质:,(2)(证明用归纳法,略),3.差分表(实用),125,二 等矩结点插值公式:,将Newton插值公式,中的差商用性质(2)换为差分,可整理为如下的,Newton向前插值公式,设,（5.6）,126,截断误差可表示为,(5.7),Newton向后插值公式及Bessel,插值公式,参考文献,127,5.4 Hermite插值简介,前述插值问题:要求被插函数与插值多项式在结点取,相同值,Lagrange型插值条件,然而,实际许多问题还常常要求两曲线进一步有共同切线:插值条件为:求一次数,多项式,使之满足给定的Hermite型插值条件,(5.8),128,求,不用待定系数法.可设,其中,，且,插值基函数表示法 （5.9）,（5.10）,（5.11）,129,满足条件（5.10）和（5.11）的多项式（5.9）一定满足（5.8），故即为所求,所以主要是求插值基函数,可借用Lagrange插值基函数,得公式（5.37）,有规律,余项,易验证：,130,例5.3 给定函数值表如下:,131,132,133,问题：结点增多，多项式次数增高，逼近精度越,好？未必！多结点高次插值往往在局部误,差更大,Runge现象。,实用：采用分段低次插值,有分段线形，分段二次插值等，几何上,5.5三次样条插值简介,分段插值法：,缺点：分段插值函数只能保证连续性，,不能保证光滑性。,折线代替曲线,134,分段插值可以得到整体连续函数，但在连,接点处一般不光滑，而Hermite插值虽然,在连节点处一阶光滑，但整体插值由于结,点多，次数高而有可能发生Runge现象。,2.三次样条插值,既想分段插值，又想在结点处保持光滑，甚至二阶光滑三次样条。,希望：,样条来源：,135,定义：在a,b上取n+1个点,若函数S(x)满足：,此时S(x)叫插值函数；,(3),在内结点或在整个区间上具二阶连续导数。,则称S,(,x,),为y=f(,x,)的三次样条插值函数。,(2)在每个小区间,上是三次多项式；,2.构造：有两种方法，导出三对角方程组，用追,赶法。,(1),136,三次样条插值,分段线性插值的优点,：计算简单、稳定性好、收敛性有保证且易在计算机上实现,缺点,：它只能保证各小段曲线在连接点的连续性，却无法保证整条曲线的光滑性，这就不能满足某些工程技术的要求。,三次Hermit插值优点,：有较好的光滑性，,缺点,：要求节点的一阶导数已知。,从世纪年代开始，首先由于航空、造船等工程设计的需要而发展起来所谓样条(Spline)插值方法，,既保留了分段低次插值多项式的各种优点，又提高了插值函数的光滑性。,今天，样条插值方法已成为数值逼近的一个极其重要的分支，在许多领域里得到越来越多广泛应用。,我们介绍应用最广的具二阶连续导数的三次样条插值函数。,137,一、三次样条插值函数的定义：,给定区间 上的个节点 和这些点上的函数值,若 满足：,（1）；,（2）在每个小区间 上至多是一个三次多项式；,（3）在 上连续。,则 称为函数 关于节点 的,三次样条插值函数。,138,二、边界问题的提出与类型,单靠一个函数表是不能完全构造出一个,三次样条插值函数。,我们分析一下其条件个数，条件（2）三次样条插值函数 是一个分段三次多项式，若用 表示它在第 i个子区间 上的表达式，则 形如:,139,其中有四个待定系数 ，子区间共有 n个，所以,共有4n个待定系数。,由条件（3）在 上连续，即它们在各个子区间上的连接点 上连续即可，共有4n-2个条件，即,140,共有3(n-1)+(n+1)=4n-2个条件，未知量的个数是 n个。,这样需要加2个条件,。,这两个条件通常在插值区间的边界点a,b处给出，称为边界条件。边界条件的类型很多，常见有：,(1)给定一阶导数值,(2)给定一阶导数值,（特别地 时称为自然边界条件，满足自然边界条件的,次样条插值函数称为自然样条插值函数）,（3)当 是周期为b-a的函数时，要求 及其导数都是以b-a为周期的函数，相应的边界条件为：,141,见word 文档,142,熟悉差分的定义，会造差分表；,熟悉等距节点的Newton插值公式的运用及等距节点的插值余项公式的运用；,熟悉简单的带导数条件的插值（如例5.3）；,熟悉分段插值法的含义。,基本要求：,作业,：,作业集(B)第五章 6，7,143,