数值分析第一章.

第一章数值分析与科学计算引论1.1数值分析对象、作用与特点许多科学问题的解决都离不开科学计算。本门课程将着重绍进行科学计算所必须掌握的一些最基本、最常用的算法,并分析其误差。数值分析包括：函数的数值逼近；数值积分与数值微分；非线性方程的数值解法；数值线性代数；微分方程的数值解法。1.2数值计算的误差1.来源与分类/*Source&Classification*/从实际问题中抽象出数学模型——模型误差/*ModelingError*/通过测量得到模型中参数的值——观测误差/*MeasurementError*/求近似解——方法误差(截断误差/*TruncationError*/)机器字长有限——舍入误差/*RoundoffError*/数值分析讨论后两个误差。2.误差与有效数字1.2数值计算的误差绝对误差/*absoluteerror*/xxe**其中x为精确值，x*为x的近似值。||*e*ε10006074302..dxex**εxx，例如：工程上常记为，称为绝对误差限/*accuracy*/，的上限记为相对误差/*relativeerror*/xeer**||***xεεrx的相对误差上限/*relativeaccuracy*/定义为有效数字/*significantdigits*/用科学计数法，记（其中）。若（即的截取按四舍五入规则），则称为有n位有效数字，精确到。mnaa.ax10021*01anm.xx1050||*na*xnm101415.3*;8979321415926535.3例问：有几位有效数字？请证明你的结论。**10501050*and103141504131..π||π,.π*证明：有4位有效数字，精确到小数点后第3位。1.2数值计算的误差有效数字与相对误差的关系有效数字相对误差限11121102102101001050*nnmnnmra.aaa.a.x*ε*ε已知x*有n位有效数字，则其相对误差限为1.2数值计算的误差相对误差限有效数字nmmnmnr.aaa.aaxεxx105010)1()1(210100)1(210|*|*|*|111121111110)1(21*nraε已知x*的相对误差限可写为则可见x*至少有n位有效数字。1.2数值计算的误差例：为使的相对误差小于0.001%,至少应取几位有效数字？*π解：假设*取到n位有效数字，则其相对误差上限为111021*nraε要保证其相对误差小于0.001%，只要保证其上限满足%001.01021*11nraε已知a1=3，则从以上不等式可解得n6log6，即n6，应取*=3.14159。1.2数值计算的误差分析：e*(y)=f(x*)f(x)e*(x)=x*x=f’()(x*x)x*与x非常接近时，可认为f’()f’(x*)，则有：|e*(y)||f’(x*)|·|e*(x)|即：x*产生的误差经过f作用后被放大/缩小了|f’(x*)|倍。故称|f’(x*)|为放大因子/*amplificationfactor*/或绝对条件数/*absoluteconditionnumber*/.问题：对于y=f(x)，若用x*取代x，将对y产生什么影响？1.2数值计算的误差例:计算y=lnx。若x20，则取x的几位有效数字可保证y的相对误差0.1%?*ln|)(*||)(*|*)(*)(*|)(|xxexexyxyxy*errr解：设截取n位有效数字后得x*x，则)(**ln)(*yxxrr%1.0*ln102111xann4估计x和y的相对误差上限满足近似关系1.2数值计算的误差算法的数值稳定性用一个算法进行计算，如果初始数据误差在计算中传播使计算结果的误差增长很快，这个算法就是数值不稳定的.1.3避免误差危害的若干原则病态问题与条件数对一个数值问题本身,如果输入数据有微小扰动（即误差），引起输出数据（即问题解）相对误差很大，这就是病态问题.例如计算函数值时，)(xf若有扰动，其x*xxx相对误差为，xx函数值的相对误差为*)(xf)(*)()(xfxfxf1.3避免误差危害的若干原则,)()(/)(*)()(pCxfxfxxxxfxfxf（3.3）称为计算函数值问题的条件数.pC相对误差比值自变量相对误差一般不会太大，如果条件数很大，pC将引起函数值相对误差很大，出现这种情况的问题就是病态问题.1.3避免误差危害的若干原则例如，，nxxf)(它表示相对误差可能放大倍.n如，10n有，24.1)02.1(,1)1(ff,02.1*x自变量相对误差为，%2函数值相对误差为，%24一般情况下,条件数就认为是病态，越大病态越严重.10pCpC则有)()(xfxfxCp,1nxnxxnn,1x若取这时问题可以认为是病态的.1.3避免误差危害的若干原则1.避免相近二数相减2.避免小分母:分母小会造成浮点溢出3.避免大数吃小数4.先化简再计算，减少步骤，避免误差积累5.选用稳定的算法1.3避免误差危害的若干原则算法设计的好坏不但影响计算结果的精度，还可以大量节省计算时间.1.4数值计算中算法设计的技术一个计算问题如果能减少运算次数，不但可以及减少计算量还可以减少误差，这是算法设计中一个重要原则.多项式求值的秦九韶算法以多项式求值为例，设给定次多项式,0,)(01110aaxaxaxaxpnnnn求处的值.n*x*)(xp可表示为,,,2,1*,100niaxbbabiii（4.1）若直接计算再相加，共需做inixa)(2)1(2120nOnnnni次乘法和次加法.n若采用,))(()(110nnaxaxaxaxp则即为所求.这就是秦九韶算法.*)(xpbn用它计算次多项式的值只用次乘法和次加法,且只用个存储单元，这是计算多项式最好的方法.nn)(xpn2n1.4数值计算中算法设计的技术秦九韶算法的另一个好处是求在点的值.由（4.1）式有)(xp其中对求导得,*)(,)(*)()*)(()(1210nnnnnnbxpbxqxxbbxbxbxxxp),(*)()()(xqxxxqxp故.从而得用秦九韶算法计算的算法如下：x*)(xp*x.)(122110nnnnbxbxbxbxq*)(*)(xqxp1.4数值计算中算法设计的技术.49)2()2(,7542)(,10)2(3234pqcxxxxqpb此处例11设，用秦九韶算法求和的值.*).(*)(1xpxqcn则)2(p,1,,2,1*,100nibxccbciii（4.1）4332)(24xxxxp)2(p解用（4.1）和（4.2）式构造出计算表格（1-2）1.4数值计算中算法设计的技术1014*4)2(4942*710*32116*58*384*44*02222*2*2-14343232321212101010001234bxbapcxcbxbacxcbxbacxcbxbacbaxxxxxx常数项系数系数系数系数系数表表1.4数值计算中算法设计的技术迭代法与开方求值以直代曲与化整为“零”加权平均的松弛技术1.4数值计算中算法设计的技术