课件-数值分析(第五版)1-3章

2019/12/171数值分析第5版李庆扬王能超易大义编清华大学出版社2019/12/17第1章数值分析与科学计算引论2第1章数值分析与科学计算引论数值分析研究对象、作用与特点数值计算的误差误差定性分析与避免误差危害数值计算中算法设计的技术数学软件2019/12/17第1章数值分析与科学计算引论3研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件1研究对象用计算机求解数学问题的数值计算方法、理论及软件实现实际问题数学模型数值计算方法程序设计（数学软件）上机计算求出结果应用数学计算数学即数值分析数值分析（计算方法）的研究对象(理论与计算结合)插值与函数逼近（2、3）数值微分与数值积分（4）非线性方程数值解（7）数值线性代数（5、6、8）常微与偏微分方程的数值解（9）等1.1数值分析的对象、作用与特点2019/12/17第1章数值分析与科学计算引论4研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件例考虑线性方程组数值解问题相关理论与精确解法根据方程的特点研究算法及相关理论纯数学计算数学Axb3数值分析特点面向计算机提供有效算法；TSP问题可靠的理论分析（精度、收敛、稳定）;好的计算复杂性（时、空）;阿基米德、刘徽、祖冲之数值实验B.C.3A.D.3A.D.52数值分析作用科学研究的手段：科学理论、科学实验与科学计算Axb2019/12/17第1章数值分析与科学计算引论5研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件1.2数值计算的误差1误差分类模型误差:数学模型实际问题观测误差:由观测产生截断误差/方法误差:近似解精确解舍入误差:计算机字长的限制(不讨论)2误差与有效数字记x为准确值，x*为x的一个近似值定义1称为近似值的绝对误差，简称误差。xxe***x强近似值:当弱近似值:当00**ee2019/12/17第1章数值分析与科学计算引论6研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件误差限:误差绝对值的上界(不能完全反映近似值的好坏)**xx相对误差:)(*******实际中取值或xxxxeexxxxer相对误差限:(可反映出近似程度的好坏)***xr定义2有效数字若近似值的误差限是某一位的半个单位，该位到的第一位非零数字共有n位，就说有n位有效数字。*x*x*x*1(1)121**110(1010),011023.143.1413.mnlmnxaaaaxnxx设若有位有效数字，则例：和作为的近似值都是位有效数字003.1,00314.110001003.0,00314.01000**yyxx2019/12/17第1章数值分析与科学计算引论7注:有效位数与小数点后有多少位无关；m相同情况下，有效位数越多，误差限越小；相对误差及相对误差限是无量纲的，绝对误差及误差限是有量纲的。研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件**1(1)121**(1)1**(1)1*110(1010)(1,2,,)090.,:11021102(1).mllinrnrxxaaaailamxnaxaxn定理：设近似数表示为其中是到中的一个数字，，为整数若具有位有效数字则其相对误差限为反之，若的相对误差限则至少具有位有效数字2019/12/17第1章数值分析与科学计算引论8研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件3数值运算的误差估计****1212****1212******122112****2112**122*21.,(),(),:()()();()()();()()(/)xxxxxxxxxxxxxxxxxxxxx与为两近似数误差限为则)()())((:)(2)()()()()()Taylor(.2****2***xxfxfxfxxfxfxf忽略高阶项展开利用一元函数误差限nkkkrnkkknAxxfAxxfAxxfATaylor1****1***1)()()(,)()()(),,()(.3展式多元函数多元函数误差限2019/12/17第1章数值分析与科学计算引论9研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件1.3误差定性分析及避免误差危害概率分析法向后误差分析法区间分析法1.病态问题与条件数病态问题输入(微小的扰动)输出(相对误差很大)条件数pC)()()()()()()()())(()(******xfxfxxxxfxfxfCxfxfxfxfexxexxxxxfprr　　有微小的扰动，对于即认为是病态10pC()nfxx2019/12/17第1章数值分析与科学计算引论10研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件2.算法的数值稳定性定义3一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。例1.1：P.９110nxnIexedx,2,1,0n)1(10684.0)(0684.0)10110(21,10110,111552.7~,7280.0~~1~6321.03679.01~)(1,1**1*9*9199119810110nnnnnnnInIIBIeIIenIneIIInIIAnIIeI2019/12/17第1章数值分析与科学计算引论116321.0,3679.0,2643.0,2073.0,1708.0,1455.0,1268.0,1121.0,1035.0,0684.0)1(10684.0)(0684.0)10110(21,10110,111552.7~,7280.0~,2160.0~,1120.0~,1480.0~,1704.0~,2074.0~,2642.0~,3679.0~,6321.0~~1~6321.03679.01~)(1,1*0*1*2*3*4*5*6*7*8*9**1*9*919911987654321010110IIIIIIIIIIInIIBIeIIenIneIIIIIIIIIIInIIAnIIeInnnnnnn研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件000025.03679.0Rerrortruncation!7)1(!2)1()1(1!177210eenxennx2019/12/17第1章数值分析与科学计算引论12研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件3.误差危害的避免（1）避免除数的绝对值远远小于被除数绝对值的除法；（2）避免两相近数相减，引起有效数字严重损失；（3）防止大数吃小数；（4）简化计算步骤，减少运算次数；秦九韶、Horner（5）数值稳定性。)(xPn01101111000001))(()()1(100000axaxaxaaxaxaxaxPnnnnnnniiixxxx1111sin22cos110000000032.0123456789020）（）秦九韶方法（1837-1786'1268-1208methodsHorner2019/12/17第1章数值分析与科学计算引论13研究对象作用特点数值计算误差误差分析避免危害数值计算算法设计数学软件算法设计的三种基本技术（1）化大为小的缩减技术Zeno悖论古希腊哲学家结绳记数（13）10=（1101）2（2）化难为易的校正技术用四则运算计算开方（3）化粗为精的松弛技术a1.４数值计算中算法设计的技术19219296307236()3.1416105SSSSSxxxxaxxa0102,,0,也永远追不上乌龟。一个人不管跑得多快，VUiSV1iSU《周易.系辞下》说：“上古结绳而治，后世圣人（伏羲）易之以书契“。2019/12/17第1章数值分析与科学计算引论14谢谢!第一章习题1,5,７,12,1４2019/12/17第2章插值法15第2章插值法引言拉格朗日（Lagrange）插值均差与牛顿（Newton）插值埃尔米特（Hermite）插值分段低次插值三次样条插值2019/12/17第2章插值法16引言拉格朗日插值牛顿插值埃尔米特插值分段低次插值三次样条插值2.1引言在科学计算中经常要用较简单的函数来逼近较复杂的函数。按函数逼近问题提法的不同，通常有插值、函数逼近及曲线拟合等三种问题。)(xfybxxxan10nyyy,,,10)(xp（1）插值设函数在点上的函数值分别为，求一简单函数，使（2.1）),,1,0()(niyxpii00y()yfx()ypxnyy0xnxx02019/12/17第2章插值法17nxxx,,,10],[ba)(xf)(xp)(xf)(xp称点为插值节点，区间为插值区间，为被插值函数，为的插值函数。引言拉格朗日插值牛顿插值埃尔米特插值分段低次插值三次样条插值由于多项式具有结构简单，数值计算和理论分析都很方便的优点，因此通常取为多项式。相应的插值法称为多项式插值。nnxaxaxaaxp2210)(2019/12/17第2章插值法18引言拉格朗日插值牛顿插值埃尔米特插值分段低次插值三次样条插值A],[baBAAxf)(Bxp)()(xp)(xf（2）函数逼近设为定义在区间上的某类函数构成的线性空间，为的子集，对于，求，使与的差在某种度量意义下最小，这就是函数逼近问题。AB通常取为连续函数空间，而通常是多项式、有理函数或三角多项式函数等。)()(xpxf2)()(xpxf另一种是2-范数对应的函数逼近分别称为最佳一致逼近和最佳平方逼近。常用的度量标准有两种：一种是∞-范数2019/12/17第2章插值法19引言拉格朗日插值牛顿插值埃尔米特插值分段低次插值三次样条插值)(xfy),,1,0(),(miyxii)(),,,;(10mnaaaxgyn),,1,0(nkakix),,2,1,0(),,,;(10miyaaaxginiimii02（3）曲线拟合设已知函数的数据点为，在某一函数类中求函数其中为待定系数，使在节点处的误差的平方和最小。2019/12/17第2章插值法20引言拉格朗日插值牛顿插值埃尔米特插值分段低次插值三次样条插值2.2拉格朗日插值n次插值多顶式：nnxaxaaxP10)(1线性插值（一次）11111111)()()()(),(],[1kkkkkkkkkkyxLyxLxLxfyxfyxxn，，满足：要求线性插值多项式已知，区间，yOxxkxk+1ykyk+1)()(1xfxL对称式点斜式1111111)()(kkkkkkkkkkkkkkyxxxxyxxxxxxxxyyyxL2019/12/17第2章插值法21引言拉格朗日插值牛顿插值埃尔米特插值分段低次插值三次样条插值1)(,0)(,0)(,1)()()(01)(1)(,0)(,0)(,1)()(,)(1111111111111111kkkkkkkkkkkkijjikkkkkkkkkkkkkkkkxlxlxlxlyxLyxLjijixlxlxlxlxlxxxxxlxxxxxl与，比较条件，或，满足其中插值基函数对称式点斜式111111111)()()()