《计算方法1_绪论与误差等》由会员分享，可在线阅读，更多相关《计算方法1_绪论与误差等（109页珍藏版）》请在金锄头文库上搜索。
1、计算方法计算方法 Numerical Analysis能源与动力工程学院 刘火星 课程介绍l 绪论l 误差分析l 线性方程组的解法l 常微分方程的初值问题l 矩阵的特征值和特征向量l 插值和拟合l 数值微分和数值积分l 非线性方程解法Course Outlinel徐翠薇、孙绳武，计算方法引论（第二版）， 高等教育出版社，2002lRichard L. Burden Gaussian elimination; Gauss quadrature; least squares fitting; Adams and Runge- Kutta formulas;Richardson extrapolat
2、ion 1940-1970 floating point arithmetic; Fortran ; finite differences; finite elements; FFT; simplex algorithm; Monte Carlo; orthogonal linear algebra; spline function 1970-2000 quasi-Newton iterations; adaptivity; stiff ODE solvers; software libraries; Matlab; multigrid; sparse and iterative linear
3、 algebra; spectral methods; interior point methods计算数学未来50年的展望l将更多的通过声音，而不是键盘向计算机传递信 息，而计算机将更多地以图象而不是数字反映结 果l数值计算将更具有适应性、迭代性、灵活性。计 算能力大得惊人l数值计算中更具智能性l算法：一系列近似计算步骤的组成，目的是找到问题的近似解l算法的特征：收敛性、稳定性l计算量：一个算法所需的乘除运算总次数，单位是flop.计算量是衡量一个算法好坏的重要标准算法和收敛矩阵乘积AB的计算量分析a11 a12 a13 a1n a21 a22 a23 a2n . . . am1 am2 a
4、mm-1 amnb11 b12 b13 b1s b21 b22 b23 b2s . . . bn1 bn2 bnn-1 bns=cijms因为 cij=aik bkj 计算量为n所以上面A mn B ns的计算量为N= m n s误差分析Error Analysisl误差的来源l误差 误差限 有效数字l相对误差和绝对误差l误差的传播l在近似计算中需要注意的问题目次l模型误差l观测误差l舍入误差l截断误差1.1 误差的来源计算机字长有限，一般实数不能精确存储，于是产 生舍入误差。 例如：在10位十进制数限制下： 130.3333333333 本应130.33333333331.0000022-1
5、.000004=0 本应1.0000022-1.000004=1.0000040000 04-1.000004=0.0000000000 041.1.1 舍入误差(Round-off Errors)舍入误差很小，本课程将研究它在运算过程中是否 能有效控制。1.1.2 截断误差(Truncation Error )用近似的值去代替数学上的准确值带来的误差。例如： 泰勒级数 零阶近似 : 一阶近似 : 二阶近似 :完全的泰勒级数: 余项 (n阶近似) : : 介于 xi and xi+1 x = xi+1- xi 余项：Taylor 级数表示为: 截去的部分 零阶近似 :截断误差 : 一阶近似 R
6、n :零阶近似 Rn :斜率 :1.2 误差 误差限 有效数字Def1.1若用x*表示x准确值的一个近似值。则此 近似值x*和准确值x的差称为误差，用e*来表示e*x*xDef1.2若|e*|x*x|*称为近似值x*的误差限。例1.2已知x*=3.14159，求近似值x1=3.14， x2=3.142，x3=3.1416的误差限。解所以误差限1=0.002，2=0.0005，3=0.000008有效数字Def1.3若用x的近似值x*的误差限是某一位上的半 个单位，该位到x*的第一位非零数字共有n位，则称 x*有n位有效数字若用x*表示x的近似值，并将x*表示成x*0.a1a2an10m若 |x
7、*x|0.510mn则近似值x*有n位有效数字(1.1)例1.3 设x*=0.0270是某数x经“四舍五入”所得 ，则误差|e(x*)|不超过x*末位的半个单位，即：|x*x|0.510 -4又 x*=0.2710-1 ,故该不等式又可写为|x*x|0.510 -1-3由有效数字定义可知, x*有3位有效数字,分别是2,7，0。例1.4 设x32.93,x*32.89,则|x*x|0.040.050.510-1即|x*x|0.5102-3由有效数字定义可知, x*有3位有效数字,分别是3,2,8。由于x*中的数字9不是有效数字，故x*不是有效数。1.3 相对误差和绝对误差设 x准确值 x* 近
8、似值 称为近似值x* 的相对误差 实用中，常用表示近似值x* 的相对误差，称为相对误差限相应的，e*称 为绝对误差， 称为绝对误差 限有效数位与误差的关系有效数位n越多，则绝对误差|e*|越小 形如(1.1)式的近似数x*具有n位有效数字，则其 相对误差限可取为基本算术运算设x*和y*分别是x和y的近似值，把它们的误差近似地看 做是相应地微分，即dx x*x， dy y*y则d（xy）dx dyd（xy）xdy ydxd（x/y）（xdyydx ）/y21.4 误差传播(1.3)和(1.4)给出了由自变量的误差引起的函数值 的误差的近似式（误差传播）。一元函数设yf(x)，若x的近似值是x*，
9、用f(x*) 去近似f(x)的误 差可用Taylor公式估计(1.3)(1.4) 多元函数情形由多元函数的Taylor展开公式类似可得(1.5)(1.6)(1.8)(1.9)例1.5测得某桌面的长a的近似值a*=120cm, 宽b的近似值b*=60cm。若已知 |e(a*)|0.2cm, |e(b*)|0.1cm。 试求近似面 积s*=a*b* 的绝对误差限与相对误差限。解: 面积s=ab,在公式（1.5）中,将y=f(x1,x2)换为 s=ab, 则相对误差限为1.5 在近似计算中需要注意的问题1.尽量简化计算步骤，减少乘除运算的次数例如，计算多项式 通常运算的乘法次数为若采用递推算法, 则
10、乘法次数仅为n. 又如 2.防止大数“吃掉”小数当|a|b|时，尽量避免a+b 。例如，假设计算 机只能存放10位尾数的十进制数，则 108+0.04=108 3.尽量避免相近数相减例如，当x很大时，应当x接近于0时，应4.避免绝对值很小的数做分母当|b|a|时，应尽量避免a/b5. 选用数值稳定性好的算法，以控制舍入误差高速 增长第2章 线性代数方程组解法本章研究的对象是 n 阶线性代数方程组 2.1 对象(2.1)线性系统广泛存在于工程、科学以及社会科学、 商业和经济问题的定量分析等领域中用矩阵和向量的记法来表示，(2.1)式可写成对象（续）(2.2)其中A(aij)是方程组(2.1)的系
11、数aij构成的nn阶矩阵，称为系数矩阵。Bbi,X xi是n维向量，X是未知量，B称为右端项。使方程组(2.1)中每一个方程都成立的一组数 x1*,x2*, ,xn* 称为式，(2.1)的解，把它记为向量 的形式，称为解向量。我们总是希望方程组有解,且有唯一解.由线性代数的克莱 姆(cramer)规则可知,如果方程组(2.1)的系数矩阵A的行列式 不等于零,那么,这个方程组有唯一解,而且它们可以表示为 xi=Di/D (i=1,n)这里,Di是指D中第i列元素用右端b1, bn代替构成的行列式.如果方程组(2.1)有唯一解,我们按上面的等式求解,就必 须计算n+1个n阶行列式.由行列式的定义,
12、n阶行列式包含有n! 项,每一项含有n个因子,计算一个n阶行列式就需要做(n-1)n! 次乘法.而我们一共要计算n+1个n阶行列式,共需做(n2-1)n!次 乘法.此外,还要做n次除法才能算出xi(i=1, n).也就是说, 用这个办法求解就要做 N=(n2-1)n!+n次乘除法运算,这个计算量是大得惊人的.例如,当n=10(即求解 一个含10个未知量的方程组),乘除法的运算次数共为32659210 次; 消(元)去法是求解线性方程组(2.2) 和满秩矩阵的 逆阵A-1的一种直接方法.尽管它比较古老,但它具有 演算步骤,推算公式都系统化的特点(对其中主元素 消去法,还可以证明是稳定的).因此,
13、它至今仍然是 求解方程组的一种有效的方法.消去法可以引出几种计算方法,下面按三角形方 程组和一般线性方程组的顺序来讨论。消去法上三角方程组的一般形式是：对于(2.1)式，有以下运算可简化方程组线性方程组的解法有两类：直接法：即在没有舍入误差的情况下，用有限 步的四则运算得出精确解的方法。但实际运算 中舍入误差不可避免，此类方法也只能得到近 似解。目前常用的是列主元消去法和矩阵三角 分解法迭代法：先给一个初始值，按一定法则逐步求 解出各个更准确的近似值的方法。目前常用的 有Jacobi法、Seidel迭代法、松弛法和梯度法将A和B写在一起，称为增广矩阵将例2.1用增广矩阵的变化写成高斯消去法的求
14、解过程分为两个阶段:首先，把原方程组化为上三角形方程组， 称之为“消元”过程；然后，用逆次序逐一求出三角方程组(原方 程组的等价方程组)的解，并称之为“回代” 过程。2.2 高斯消去法(Gaussian elimination)消元 ：将(2.1)式写成矩阵形式(2.3)(2.4)第1步:若a11 (1) 0，用第二个方程减去第一个方程乘以 a21(1)/ a11(1),用第三个方程减去第一个方程乘以a31(1)/ a11(1) 则有矩阵形式(2.5)(2.6)第2步:若a22 (2) 0，用第三个方程减去第二个方程乘以 a32(2)/ a22(2),用第四个方程减去第二个方程乘以a42(2)
15、/ a22(2) 则有矩阵形式(2.7)(2.8)第k步:若akk (k) 0，用第k+1个方程减去第k个方程乘以 ak+1k(k)/ akk(k) 则有矩阵形式(2.9)(2.10)重复n1次，得到等价的上三角形方程组矩阵形式(2.11)(2.12)以上过程把系数矩阵A(1)变成上三角矩阵A(n)，称之为 消元，计算公式可归纳为(2.13)回代(2.12)2.3 主元素消去法因此，x10 x21因此，x11 x21精确解，x110000/9999 x29998/9999在做除法运算时，选取绝对值大的作分母。 主元素消去法的基本思路。列主元素消去法列主元素消去法基本思想 1.用高斯消去法求解线性方程组时,应避免小的主元.在实际计算中 ,进行第k步消去前,应该在第k列元素aik (i=k,n)中找出绝对值 最大者,例如a = max a 2.再把第p个方程与第k个方程组进行交换,使apk(k-1)成为主元
