[计算方法复习.docVIP

第一章 序言 什么是最有效的算法？ 电子计算机实质上只会做加、减、乘、除等算术运算和一些逻辑运算，由这些基本运算及运算顺序规定构成的解题步骤，称为算法．它可以用框图、算法语言、数学语言或自然语言来描述。用计算机算法语言描述的算法称为计算机程序。 最有效的算法：运算量少，应用范围广，需用存储单元少，逻辑结构简单，便于编写计算机程序，而且计算结果可靠。 在数值计算中，为避免运算带来较大的误差，应注意哪些问题？（数值稳定性原则） 1）防止大数吃小数 2）防止相近的两数相减 3）防止接近零的数做除数 4）简化计算步骤,减小运算次数,避免误差积累 5）要控制舍入误差的累积和传播 绝对误差（限）、相对误差（限）以及有效数字（位数）： 规格化浮点数 x=±0.a1a2...at′10c ai?{0,1,2,…,9}, a110，L￡c ￡U 定义 设近似数x=±0.a1a2…an×10m，其中ai∈{0，1，2，…，9}(i=1,2,…,n), a1≠0，m为整数，如果，则称近似值x有n位有效数字，其中a1,a2,…,an都是x的有效数字,也称x为有n位有效数字的近似值 定理 设近似数x=±0.a1a2…an×10m有n位有效数字，则其相对误差限为: （课后做过的练习）如：P12—13 3、4、9、11、12 第二章 方程求根 二分法(P18例2.2) 二分法就是将方程的有根区间对分,然后再选择比原区间缩小一半的有根区间,如此继续下去,直到得到满足精度要求的根为止的一种简单的区间方法。 基本法原理:给定方程f(x)=0,设f(x)在区间[a,b]连续,且f(a)×f(b)0，则方程f(x)在(a,b)内至少有一根，为便于讨论,不妨设方程f(x)=0在(a,b)内只有一实根 x *.采取使有根区间逐步缩小，从而得到满足精度要求的实根 x * 的近似值 x k 。 取[a,b]区间二等分的中点，若f(x0)=0,则x0是f(x)=0的实根； 若f(a)f(x0)0 成立,则 x * 必在区间(a, x0)内,取a1=a，b1= x0；否则 x *必在区间(x0,b)内，取a1= x0，b1=b, 这样,得到新区间(a1,b1),其长度为[a,b]的一半, 如此继续下去，进行k次等分后,得到一系列有根区间：，其中每一个区间长度都是前一个区间长度的一半，从而[ak ,bk ]的长度为如此继续下去,则有这些区间将收敛于一点，该点即为所求的根.当做到第k步时，有: 即 （ε为给定的精度） 此时即为所求方程的近似解。 一般迭代法及其收敛性的判别：(例题，作业题) 不动点迭代法又称简单迭代法。 基本思想：构造不动点方程，以求得近似根。即由方程f(x)=0变换为等价方程 x=j(x) ，这样原方程的根必满足：x*= j(x*) ，即j(x) 作用在x*上，其值不发生变化，因此我们也称x*为j(x) 的不动点，要求方程f(x)=0的根就转化为求j(x) 的不动点了。 具体迭代如下： 先取一个估计值x0来试探，若j(x0) =x0，则x*=x0(可能性很小)一般 j(x0) ≠x0，记 x1=j(x0) ，若x1=j(x1) , 则x*=x1 若x1≠j(x1) ，记 x2=j(x1) ，再用x2继续试探…… 如此反复计算，即形成一迭代公式 xk+1=j(xk) ，(k=0,1,2,…) 如果{xk}收敛，则称迭代公式是收敛的；否则称迭代公式是发散的。 如果{xk}收敛于x*，而j(x)是连续函数时，那么x*即是j(x)的不动点。也即x*就是方程的根。 定理1： 设j(x)在x= j(x)的根x*邻近有连续的一阶导数，且| j’(x*)|1， 则迭代公式xk+1=j(xk)具有局部收敛性。 注：有局部收敛性的条件| j’(x*)|1可用 | j’(x0)|1来近似代替。 (没要求计算近似值时，不需迭代，而用该定理判断其收敛性) 定理2：对于迭代公式xk+1= j(xk) ，如果j(p)(x) 在所求根x*的邻近连续，并且j’(x*)= j’’(x*) =...= j(p-1)(x*) =0,j(p)(x*)≠0, 则该迭代公式在点x* 邻近是P阶收敛的。 牛顿迭代法及其收敛性（例题，作业题） —— 牛顿迭代公式 牛顿迭代公式具有2阶收敛的速度。 迭代过程的加速方法：（例题，作业题） 例：方程x3-3x-1=0在x =2附近有一个正根 试给出两种迭代公式，并判断其收敛性； 用牛顿迭代法求其根的近似值（要求精确度达）。 解：1）迭代公式：及 收敛性判断：记， ∵ ∴迭代公式是