《数值分析PPT教案》由会员分享，可在线阅读，更多相关《数值分析PPT教案（143页珍藏版）》请在金锄头文库上搜索。
1、数值分析,绪论 第一章插值法 第二章数值积分和数值微分 第三章曲线拟合的最小二程法 第四章 求非线性方程根的近似方法 第五章 线性代的方程组的直接法 第六章 解线性方程组的迭代法 第七章矩阵特征值和特征向量计算 第八章常微分方程数值解法,计算方法,参考书,1.数值分析，翟瑞彩，天津大学出版社； 2.计算方法，中山大学与武汉大学编写 3.数值计算计算原理，李庆杨，关治， 白峰彬，清华大学出版社 4.计算方法引论，徐萃薇，科学出版社,1.计算方法的任务与特点,绪论,实际问题数学问题提供计算方法 程序设计上机计算结果分析,计算方法,2.基本的数学问题:,1.大型线性代数方程组Ax=b求解; 2.矩阵
2、A的特征值和特征向量计算; 3.非线性方程 求解(求根); 4.积分 计算; 5.常微分方程初值问题求解; 6.其它。,求精确解(值)一般非常困难。例如：,1. 方程组阶数n很大，例如n=20,计算机运算速度 1亿次/秒,用不好的方法,大约需算30多万年; 好方法不到一分钟。另外，有计算结果可靠性 问题。 2. 特征值定义,3. 形式复杂时求根和求积分很困难。 4.线性微分方程易解， 如 非线性方程难解，如,希 望： 求近似解，但方法简单可行，行之有效 （计算量小，误差小等）。以计算机为工 具，易在计算机上实现。 计算机运算: 只能进行加，减，乘，除等算术运 算和一些逻辑运算。 计算方法： 把
3、求解数学问题转化为按一定次序只 进行加，减，乘，除等基本运算 数值方法。,3. 数值分析研究对象与特点,先看两个例子。 例1 求方程 x2=2sinx，在区间(1,2)内的根。 理论上可知显然找不出根的解析式，即无法求出精确解。 例2 用Cramer法则求解n元线性方程组。 显然理论上可行，且有精确表达式。实际计算时会出现什么问题呢？,实际问题,数学模型,上机计算求出结果,数值计算方法,看用数学和计算机解决实际问题的过程：,应用数学研究的任务,数值分析研究的对象,3、具有好的计算复杂性,4. 数值分析提供的算法具有下面四个特点：,1、面向计算机,2、有可靠的理论分析,4、通过数值实验验证有效性
4、,3、化整为零,5.数值分析共同思想和方法：,1、迭代法,2、以直代曲,4、外推法,1. 认识建立算法和对每个算法进行理论分析是基本 任务，主动适应“公式多”的特点；2. 注重各章建立算法的问题的提法，搞清问题的基 本提法，逐步深入；3. 理解每个算法建立的数学背景，数学原理和基本 线索，对最基本的算法要非常熟悉；4. 认真进行数值计算的训练，学习各章算法完全是 为用于实际计算，必须真会算。,如何进行学习？,本课程的基本要求 掌握数值方法的基本原理 掌握常用的科学与工程计算的基本方法 能用所学方法在计算机上算出正确结果,课程学习结束后你具备的能力,1. 对具体的数值计算问题，你会选择合适的算法
5、，并通过计算机计算出正确结果； 2. 对给定的算法会从理论上分析其优劣性； 3. 会根据原理构造解决较简单数值计算问题的算法。,1.2 误差基础知识,一 .误差来源（分类） 1. 模型误差。 2. 观测误差。 3. 截断误差，如,右端是截断误差。,4. 舍入误差。计算机字长有限，一般实数不能精确存储，于是产生舍入误差。例如：在10位十进制数限制下： 舍入误差很小，本课程将研究它在运算过程中 是否能有效控制。,实际问题,用计算机解决实际问题的一般过程,模型误差、观测误差,截断误差,舍入误差,应用数学解决的问题,数值分析解决的问题,在此主要研究这两种误差,二误差基本概念,1绝对误差。设 准确值，
6、近似值。 称 为 的绝对误差。 为 的绝对误差限。 2相对误差。称 为 的相对误差。 实用中，常用 表示 的相对误差。 称 为 的相对误差限。,3有效数字 设 若 (1.1) 则说 具有n位有效数字，分别是 若 ，则称 为有效数。,例1.1 设 =0.0270是某数 经“四舍五入”所得，则 误差 不超过 末位的半个单位，即： 又 ,故该不等式又可写为 由有效数字定义可知, 有3位有效数字，分别 是2,7，0。,例1.2 = 32.93, = 32.89, 故 有3位有效数字，分别是3,2，8。 由于 中的数字9不是有效数字，故 不是有效数。,三、有效数位与误差的关系,1. 有效数位n越多，则绝
7、对误差 越小 (由定义1.1) 2. 定理1.1 若近似数 具有n位有效数字，则 (1.2) 反之， 若 则 至少有n位有效数字。,两边除以 得 (1.3)和（1.4）给出了由自变量的误差引起的函 数值的误差的近似式（误差传播）。,四、数值运算的误差估计(误差的传播) 1. 一元函数情形 设 则 ，由Taylor展开公式,(1.4),（1.3）,2. 多元函数情形 设 ，,则，,由多元函数的Taylor展开公式类似可得,（1.5）,（1.6）,在（1.6）式中，分别取,可得,同号),（1.7）,（1.8）,（1.9）,(,例1.3：测得某桌面的长a的近似值a*=120cm,宽b的 近似值b*=
8、60cm。若已知|e(a*)|0.2cm, |e(b*)|0.1cm。 试求近似面积s*=a*b* 的绝对误差限与相对误差限。,解: 面积s=ab,在公式（1.5）中,将 换为 s=ab, 则,相对误差限为,1.3 选用算法应遵循的原则,1.尽量简化计算步骤，减少乘除运算的次数. 例如，计算多项式 通常运算的乘法次数为 若采用递推算法, 则乘法次数仅为n. 又如,2.防止大数“吃掉”小数 当|a|b|时，尽量避免a+b 。例如，假设计算机 只能存放10位尾数的十进制数，则 3.尽量避免相近数相减 例如，当x很大时，应,，,当x接近于0时，应,4.避免绝对值很小的数做分母 当|b|a|时，应尽量
9、避免 。 5. 选用数值稳定性好的算法，以控制舍入误差高速 增长 例如 若 （误差 ）则计算 时误差扩大了 倍,而,（n=1,2,）,是稳定的。,范数,范数是长度概念的推广,是一种度量定义,是测量两个函数,向量,矩阵等之间距离的一个非负实数.范数的定义形式多种多样,采用同的范数定义,可得不同的范数,但都满足以下的三个条件(公理化定义): 1.(非负性) 2.(齐次性) 3.(三角不等式) 称实数|X|为向量 X的范数. # 不同范数间的关系:等价.,基本要求：,1.熟悉计算方法在解决实际问题中所处的地位，熟悉计算方法是以计算机为工具求近似解的数值方法； 2.熟悉绝对误差（限），相对误差（限）及
10、有效数字概念； 3.熟悉公式（1.2）-（1.9）； 4.熟悉选用算法应遵循的原则；,计算方法,f(x)=0根或f(x)零点，当f(x)复杂时，很难求 （找近似有效简单方法）。,第二章 求方程根的近似方法,2.1 区间二分法 理 论 : f(x) Ca,b,单调， f(a)f(b)0 f(x)=0在(a,b)有惟一根。 根分离：画草图，试算. 多项式方程根的模 的上下界。,例2.1 用二分法求 在(1,2)内的根，要求绝对误差不超过 解： f(1)=-50 -(1,2)+ f(1.25)0 (1.25,1.375) f(1.313)0 (1.360,1.368),f(1.5)0 (1,1.5)
11、,优点：条件简单. 缺点：收敛慢. 不易求偶数重根. 如图,，则,（事后估计）,x,y,2.2 迭代法,一. 迭代法的建立与收敛性,2.收敛定理（定理2.2）,(2),，故收敛。,( )1,(3),注：L越小，收敛越快。,3编程停机判断,（取定初值,）计算，当,时，由（） 3 式知,比较小，此时停机，,二、迭代加速公式（略）,由,2.3Newton 迭代法 一 Newton 迭代法 1.迭代公式建立,在,点Taylor展开,Taylor展开线性化（重要思想）,近似于,解出 记为,，则,将,2.Newton迭代法的几何意义 过,切线,与,求交点，解出, 则,3. Newton迭代法收敛定理（定理
12、 2.6）,在,有根，且,在,（1）,连续，且分别不变号；,使,则 Newton 迭代法（2.1）产生的数列,的收敛到根。,为例证明（其它情况类似）,（2） 取初值,设,证：,以,将,处Taylor展开,说明数列,有下界,又,故,单调递减。,收敛。设,则由（2.1），,，,例2.2,解：设,取,，则由（2.1）,用 Newton 迭代法求,基本要求 熟悉区间分法； 熟悉迭代法的建立，会使用收敛定理； 熟悉Newton迭代法及其几何意义和收敛条件。 作业： 习题4： 1、2、3、4、6,计算方法,二.迭代法的收敛阶(收敛速度) 1.定义:设,若有实数p0,使,则称,p阶收敛,相应的迭代法称为p阶
13、方法. 特别,p=1时叫线性收敛, p=2时叫平方收敛. p越大越好(why?),2.定理2.7,所以，此时Newton法至少二阶收敛.,(2)由2.6的证明有：,3. Newton法改进：,2.4 弦截法(略),第三章 线性代数方程组解法,解线性方程组,一、 Gauss消去法,设 有,线性代数：方法不好时工作量非常大， 工作量小的方法是 Gauss 消去法。,消 元：,3.1直接法,二 列主元素消去法-计算结果可靠,到此原方程组化为,到此原方程组化为,（3.3) 是回代过程。,(上三角方程组) （3.2),(n) 回代求解公式,(n-1) 原方程组化为,以上为消元过程。,（3.3),三、 G
14、auss 全主元消去法： 优点-计算结果更可靠； 缺点-挑主元花机时更多， 次序有变动，程序复杂。,说明： (1)也可采用无回代的列主元消去法(叫Gauss- -Jordan消去法)，但比有回代的列主元消 去法的乘除运算次数多。 (2)有回代的列主元消去法所进行的乘除运算 次数为 ，量很小。,四、应用 （1）求行列式 （2）求逆矩阵,(以上过程都应选主元),记,，则,（三角因子分解）,Gauss消元，初等行变换，化原方程组为上三角型。,五矩阵三角分解法,定义3.1,叫,的三角（因子）分解，其中 是,是上三角。,下三角,为单位下三角阵（对角元全为1），,为上三角阵，则称,为Doolittle分解
15、;,若 是下三角，,是单位上三角，则称,定理3.1 n阶阵,有唯一Doolittle分解(Crout）,的前n-1个顺序主子式不为0.（证略）,三角分解不唯一,为此引入,定义3.2 若,为Crout分解。,为什么要讨论三角分解？若在消元法进行前能实 现三角分解,， 则,容易回代求解,回代求解很容易，如,基本要求： 1. 熟悉收敛阶的定义； 2. 熟悉Newton法及改进方法的收敛阶； 3. 熟悉列主元消去法解线性方程组的计算 过程； 4. 熟悉矩阵三角分解中Doolittle分解和 Crout分解定义； 5. 熟悉利用三角分解来求解线性方程组的 思路； 作业：作业集（A） 第三章 1，2,计算方法 1直接三角分解法（以Doolittle分解为例）设,
