数值分析1(数值分析概论)

赵熙乐

photographyer@主页:/shiziduiwu/teainfo.php?teacher=zhaoxileGoogleScholar:.hk/citations?user=88Zs8pAAAAAJ&hl=en百度网盘账号：matrix2007603密码：analysis2014*Humanbeingsareincrediblyslow,inaccurate,andbrilliant.Computersareincrediblyfast,accurate,andstupid.Togethertheyarepowerfulbeyondimagination.*数值分析(NumericalAnalysis)研究内容:算法的构造与分析近似的手段构造适合计算机的算法

化大为小、化繁为简、化难为易分析近似对计算结果的影响

围绕病态性、收敛性、稳定性和复杂度展开研究用计算机求解数学问题的数值方法(算法)及其相关理论。一、数值分析概论*数值分析的特点:近似替代:在误差允许的范围内,用近似解代替精确解或有限次计算代替无限次的计算递推性:将复杂计算过程归结为一系列适合计算机计算的简单过程重复数值模拟:还要通过数值模拟验证算法行之有效。数值模拟和数学理论一样,都是数值分析的重要研究手段。*推动科学和社会发展Computationalsciencehasbecomethethirdpillarofscientificenterprise(科学研究的第三种方法),apeeralongsidetheoryandphysicalexperiment——摘自2005年美国总统顾问委员会报告大规模、高维数、多尺度、非线性、不适定、长时间、

复杂区域*趣例1:线性方程组求解*趣例2:特征值与特征向量计算*趣例3:数据插值*趣例4:Poisson方程*推荐书单[1]白峰杉,数值计算引论(高教)[2]李庆扬

关治

白峰杉,数值计算原理(清华)[3]李庆扬王能超易大义,数值分析(清华)[4]C.Moler,NumericalComputingwithMatlab[5]R.

Burden

J.Fairs,NumericalAnalysis[6]A.Quarteronietal,NumericalMathematics[7]王能超,算法演化论*数据观测数学建模数值方法程序设计数据结果观测误差模型误差截断误差舍入误差二、误差与有效数字将地球考虑成一个球体,设R为地球半径,h为卫星高度,计算覆盖面积参考P.190*截断误差:由于问题不能精确求解,数值方法求得的近似解和精确解之间的误差。微积分中sinx

可展开为例1但计算机计算时,常用前几项来代替精确解,即抛弃了无穷级数的后段,这样就产生了截断误差。

当|x|很小时,常用x代替sinx,其截断误差大约为x3/6。

*尾数部阶码部

舍入误差:一个非零的二进制一般的描述形式为计算机表示的数只有有限多个,且同时只有有限精度,这个有理数的子集称为浮点数。绝大部分实数在计算机上总不能精确表示,总要经“舍”或“入”而由一个与之相近的浮点数代替,由此引起的误差称为舍入误差。*

假设某一数据的准确值为

x*,其近似值为x,则称

而称为

x

的相对误差。误差的有关概念

e(x)=x

-x*

为

x的绝对误差。*如果存在一个适当小的正数ε,使得

则称ε为绝对误差限。

称εr为相对误差限。

如果存在一个适当小的正数εr,使得

*有效数字概念取的有限位数如下(≈3.1415926)取

x1=3.14,3位有效数字;取

x2=3.1416,5位有效数字。若近似值x的绝对误差限是某一位上的半个单位,该位到x的第一位非零数字一共有n

位,则称近似值x有n位有效数字。*用科学计数法,记

n

位有效数字的相对误差限满足：其中都是0~9中的任一整数,且。有效数字和误差的关系若绝对误差限满足：

则称x

有n

位有效数字。*例2

已知

的十进制浮点数第一位是5,要使近似值的相对误差限小于0.1%,问浮点数的有效数字的位数至少应该为多少？解:利用不等式

所以浮点数的有效数字位数至少应取3位。取n≥3,有

|er(x)|≤10-3*函数计算的误差估计(准确值

y*=f(x*))

同理所以数值运算的误差估计*算术运算的误差估计*三、算法设计的基本原则

稳定:算法控制误差的传播和积累以保证计算结果有足够的精度

存储:算法所需的存储空间

效率:算法所需的运算次数*1.减少运算次数

不仅能提高计算效率,而且能减少误差的积累。(b)利用秦九韶算法：(a)计算每一项再求和：例3*

Moore'sLaw集成电路上可容纳的晶体管数目约每隔18个月便会增加一倍,性能也将提升一倍。*2.减少存储量*3.构造数值稳定的计算方法计算机浮点数系统的特点:一个算法如果输入数据有误差,在计算过程中舍入误差不增长,则此算法是数值稳定;否则此算法数值不稳定。浮点数是有限精度的,如IEEE的双精度浮点数,其精度eps=2^(-52),大约是2.2204e-16。有限的精度会导致舍入误差。但舍入误差并不可怕,关键是在算法设计中控制舍入误差的传播、放大和积累。*防止大数“吃掉”小数

例如a=1013和b=4,假设两数在具有12位浮点数计算机系统中相加a+b=1013+4

=0.10000000000000

×1014

+0.00000000000004

×1014

(机器中相等)=0.100000000000×1014

*避免绝对值小的数作除数

*避免两个相近数相减

如果y≈x,现分析两个数的近似数作减法所得结果的误差。设z=y–x,则利用误差估计相对误差估计

当y≈x

时,有z≈0,计算结果的相对误差限很大。*设法控制误