计算方法学习指导 温师院数学与信息科学学院 2003.7
计 算 方 法 学 习 指 导 温师院数学与信息科学学院 2003.7
目录 第一章引论 1.1内容提要 1.2典型例题 第二章解线性方程组的直接法 2.1内容提要 2.2典型例题 第三章插值法与最小二乘法… 3.1内容提要 3.2典型例题 第四章数值积分与微分 4.1内容提要 4.2典型例题 第五章常微分方程数值解法 5.1内容提要 5.2典型例题 第六章逐次逼近法… 6.1内容提要 6.2典型例题
目 录 第一章 引论...........................................................................................................................1 1.1 内容提要...................................................................................................................1 1.2 典型例题................................................................................................................3 第二章 解线性方程组的直接法..............................................................................7 2.1 内容提要...................................................................................................................7 2.2 典型例题..............................................................................................................14 第三章 插值法与最小二乘法..................................................................................21 3.1 内容提要.................................................................................................................21 3.2 典型例题.................................................................................................................27 第四章 数值积分与微分.............................................................................................47 4.1 内容提要.................................................................................................................47 4.2 典型例题..............................................................................................................50 第五章 常微分方程数值解法..................................................................................63 5.1 内容提要.................................................................................................................63 5.2 典型例题..............................................................................................................68 第六章 逐次逼近法........................................................................................................79 6.1 内容提要.................................................................................................................79 6.2 典型例题..............................................................................................................84
第一章引论 1.1内容提要 1.绝对误差与绝对误差限 设x为准确值,x是x'的一个近似值,称ε=x-x为近似值x的绝对误差,简称误 差。如果有常数E使得l≤E,则称E为近似值x的绝对误差限,简称误差限。 2.相对误差和相对误差限 设x是准确值,x是x的一个近似值,称(x-x)/x为近似值x的相对误差,记作e。 在实际计算中,x是未知的,常以E=(x-x)/x作为相对误差。如果有常数En使得 ln≤6,(或问≤6,则称E,为相对误差限 3.有效数字 如果近似数x的绝对误差不超过其上某一位数字的半个单位,且该位数字到x的第一位 非零数字共有n位,则称x近似x时具有n位有效数字,简称x有n位有效数字。 定理11设x是x的近似值,它的表达式为x=±10×0a1a2…an,则x的有效数 字位数与x的相对误差之间有如下关系: (1)若x具有n位有效数字时,x的相对误差E满足 ×10-n (2)若x的相对误差E,满足ls ×10m时,x至少具有n位有效数字 4.数据误差的影响 给定函数y=f(x,x2)。设x1,x2分别为x,x2的近似值,则
第一章 引论 1.1 内容提要 1. 绝对误差与绝对误差限 1 * 设 x 为准确值， x 是 的一个近似值，称e 为近似值 * x = x − x * x 的绝对误差，简称误 差。如果有常数ε 使得 e ≤ ε ，则称ε 为近似值 x 的绝对误差限，简称误差限。 2. 相对误差和相对误差限 设 是准确值， * x x 是 的一个近似值，称 为近似值 * x * * (x − x)/ x x 的相对误差，记作 。 在实际计算中， 是未知的，常以 r e * x x )/ x * er = (x − 作为相对误差。如果有常数 使得 r ≤ ε r e (或 r ε r e ≤ )，则称 r ε 为相对误差限。 r ε 3. 有效数字 如果近似数 x 的绝对误差不超过其上某一位数字的半个单位，且该位数字到 x 的第一位 非零数字共有 n 位，则称 x 近似 时具有 位有效数字，简称 * x n x 有 n 位有效数字。 定理 1.1 设 x 是 的近似值，它的表达式为 ，则 * x n k x a1a2 La * = ±10 × 0. x 的有效数 字位数与 x 的相对误差之间有如下关系： ⑴若 x 具有 n 位有效数字时， x 的相对误差 r ε 满足 1 1 10 2 1 − + ≤ × n r a ε ⑵若 x 的相对误差 r ε 满足 1 1 10 2( 1) 1 − + × + ≤ n r a ε 时， x 至少具有 n 位有效数字。 4. 数据误差的影响 给定函数 y = f (x1 , x2 )。设 x1 , x2 分别为 的近似值，则 * 2 * 1 x , x
e(y)=f(x1,x2)-f(x1,x2) (x1,x2 x1-x) (x1x2 (xx1+(x)2 (y,互+9型五 由以上两式得 e(x1+x)≈e(x)+e(x),e(x1+x2)≈-x1-c(x)+-2-e,(x2) x1+x2 x1+x2 e(x1-x)≈e(x1)-e(x2),c(x1-x2)≈ (x1) M- e(x1x2)≈x2e(x1)+xe(x2),e,(x1x2)≈e,(x1)+e,(x2) x,-e(x,)_x, e(x2),e()≈e(x1)-e,(x2),x2≠0 5.设计算法时要注意的几个问题 (1)应用数值稳定的递推公式 设x x…是由递推公式 xn=F(xm1),n=1,2 (1.1) x给定 得到的。若x0有误差e0,则实际上只能得到 记en=xn-xn,n=1,2,…。如果存在不依赖于n的常数C使得 ≤Cl 则称递推公式(1.1)是数值稳定的。否则称为数值不稳定的。 (2)注意简化运算步骤,减少运算次数 (3)要避免相近数相减 (4)多个数相加,应先将绝对值较小的数相加之后,再依次与绝对值较大的数相加 (5)避免小数作除数和大数作乘数
2 2 1 2 1 1 1 2 2 * 2 2 1 2 1 * 1 1 1 2 1 2 * 2 * 1 ( , ) ( , ) ( ) ( , ) ( ) ( , ) ( ) ( , ) ( , ) e x f x x e x f x x x x x f x x x x x f x x e y f x x f x x ∂ ∂ + ∂ ∂ = − ∂ ∂ − + ∂ ∂ ≈ = − r r r e y x x f x x e y x x f x x y e y e y 2 2 2 1 2 1 1 1 1 2 ( ) ( , ) ( , ) ( ) ∂ ∂ + ∂ ∂ = ≈ 由以上两式得 ( ) ( ) ( ) 1 2 1 2 e x + x ≈ e x + e x ， ( ) ( ) ( ) 2 1 2 2 1 1 2 1 1 2 e x x x x e x x x x e x x r r r + + + + ≈ ( ) ( ) ( ) 1 2 1 2 e x − x ≈ e x − e x ， ( ) ( ) ( ) 2 1 2 2 1 1 2 1 1 2 e x x x x e x x x x e x x r r r − − − − ≈ ( ) ( ) ( ) 1 2 2 1 1 2 e x x ≈ x e x + x e x ， ( ) ( ) ( ) 1 2 1 2 e x x e x e x r ≈ r + r ( ) ( ) 2 2 2 1 2 1 2 1 e x x x x e x x x e ≈ − ， ( ) ( ) ( ) 1 2 2 1 e x e x x x er ≈ r − r ， 0 x2 ≠ 5. 设计算法时要注意的几个问题 ⑴应用数值稳定的递推公式 设 x1 , x2 ,L, xn ,L是由递推公式 （1.1） = − = 给定 ( ), 1,2, 0 1 x x F x n n n L 得到的。若 x0 有误差e0 ，则实际上只能得到 = − = − = 0 0 0 1 ~ ), 1,2, ~( ~ x x e x F x n n n L 记 n n n e x x ~ = − ， n = 1,2,L。如果存在不依赖于 n 的常数 C 使得 0 e C e n ≤ ， n = 1,2,L 则称递推公式（1.1）是数值稳定的。否则称为数值不稳定的。 ⑵注意简化运算步骤，减少运算次数 ⑶要避免相近数相减 ⑷多个数相加，应先将绝对值较小的数相加之后，再依次与绝对值较大的数相加 ⑸避免小数作除数和大数作乘数 2
1.2典型例题 例11问3.142,3.141,二分别作为x的近似值各具有几位有效数字 7 解丌=3.14159265记x1=3.142,x2=3.141,x3=1 由x-x1=-00…知1×10-<x-x|≤1×10,因而x具有4位有效数字 2 由x-x2=000050知×103<x-x2|≤×10-2,因而x2具有3位有效数字。 2 由x-x3=-0.00126…知x103</221 775,×10-2,因而x3具有3位有效数字 例12已知近似数x有两位有效数字,试求其相对误差限。 解有效数字n=2,所以相对误差限为E,≤×10≤×10-21=5%。 例13已知近似数x的相对误差限为0.3%,问x至少有几位有效数字? 解设x具有n位有效数字,则0.3%3 ≤ 10-1 10002×1022×(a1+1) 所以1-n=-1,即n=2 例14为使√70的近似数的相对误差小于01%,问查开方表时,要取几位有效数字? 解设查表时取n位有效数字,由于8≤√70≤9,所以a1=8, 由公式E.≤×10-m≤0.1%知,只需取n=3。 例1.求方程x2-56x+1=0的两个根,使它们至少具有4位有效数字,取 783=27982? 解方程的两个根为 x1=28+√783≈55.98,x2=28-√783= 28+√78355820.01786 注:此处若直接利用x2=28-√783≈28-27982=0018,则只能得到两位有效数字
1.2 典型例题 例 1.1 问 7 22 3.142, 3.141, 分别作为π 的近似值各具有几位有效数字？ 解 π = 3.14159265L，记 3.142 x1 = ， 3.141 x2 = ， 7 22 x3 = 。 由π − x1 = −0.00040L知 3 1 4 10 2 1 10 2 1 − − × < π − x ≤ × ，因而 x1具有 4 位有效数字。 由π − x2 = 0.00059L知 2 2 3 10 2 1 10 2 1 − − × < π − x ≤ × ，因而 x2 具有 3 位有效数字。 由π − x3 = −0.00126L知 3 2 10 2 1 7 22 10 2 1 − − × < π − ≤ × ，因而 x3具有 3 位有效数字。 例 1.2 已知近似数 x 有两位有效数字，试求其相对误差限。 解 有效数字 n = 2 ，所以相对误差限为 10 5% 2 1 10 2 1 1 2 1 1 ≤ × ≤ × = −n+ − + r a ε 。 例 1.3 已知近似数 x 的相对误差限为 0.3%，问 x 至少有几位有效数字？ 解 设 x 具有 n 位有效数字，则 1 1 2 10 2 ( 1) 1 2 10 1 1000 3 0.3% − × × + ≤ × = < a 所以1− n = −1，即 n = 2 。 例 1.4 为使 70 的近似数的相对误差小于 0.1%，问查开方表时，要取几位有效数字？ 解 设查表时取 n 位有效数字，由于8 ≤ 70 ≤ 9 ，所以 8 a1 = ， 由公式 10 0.1% 2 1 1 1 ≤ × ≤ −n+ r a ε 知，只需取 n = 3。 例 1.5 求方程 56 1 0 的两个根，使它们至少具有 4 位有效数字，取 2 x − x + = 783 = 27.982 ？ 解 方程的两个根为 x1 = 28 + 783 ≈ 55.98 ， 0.01786 55.982 1 28 783 1 2 28 783 ≈ ≈ + x = − = 注：此处若直接利用 x2 = 28 − 783 ≈ 28 − 27.982 = 0.018 ，则只能得到两位有效数字。 3
x-+1+x 当1时, xx+1x(x+1) 例16计算a=(√2-1)°,取√2≈14,利用下列等式计算: (299-70√2:(3)(3-2√2)3:() (3+2√2) 问哪一个得到的结果最好? 解显然以上四个算式是恒等的,但当取√2≈14计算时,四个算式的误差是不同的。 记x=√2,x=14,|A=(一对 (1)设y=f1()= (+1)°’则按(1)式计算产生的误差为 e(H)=/f(x)-f(x)2=1(x) 同理 (2)设y2=f2(1)=99-701,则按2式计算产生的误差为 e(y)=|(x)-(x)=/(x)A (3设y3=f3(1)=(3-21)3,则按3)式计算产生的误差为 e(y)=(x)-f(x)≈|(x)△x (4)设y4=f4(1) (3+2)3’则按(式计算产生的误差为 e(y)=|(x)-f(x)=U/{x)| 估计以上四个式子中的f(x)(x)f(x)(x),即可得出4)式误差最小的结论。 具体计算结果如下:
一般地， x x x x + + + − = 1 1 1 2 2 当 x > 1时， ( 1) 1 1 1 1 + = + − x x x x 例 1.6 计算 6 a = ( 2 −1) ，取 2 ≈ 1.4，利用下列等式计算： ⑴ 6 ( 2 1) ! + ；⑵99 − 70 2 ；⑶ 3 (3 − 2 2) ；⑷ 3 (3 2 2) 1 + 问哪一个得到的结果最好？ 解 显然以上四个算式是恒等的，但当取 2 ≈ 1.4计算时，四个算式的误差是不同的。 记 2 4 * x = ， x = 1. ， ∆x = x − x * ⑴设 1 1 6 ( 1) 1 ( ) + = = t y f t ，则按⑴式计算产生的误差为 e( y ) = f (x ) − f (x) ≈ f ′(x) ∆x 1 1 * 1 1 同理， ⑵设 y2 = f 2 (t) = 99 − 70t ，则按⑵式计算产生的误差为 e( y ) = f (x ) − f (x) ≈ f ′(x) ∆x 2 2 * 2 2 ⑶设 ，则按⑶式计算产生的误差为 3 3 3 y = f (t) = (3 − 2t) e( y ) = f (x ) − f (x) ≈ f ′(x) ∆x 3 3 * 3 3 ⑷设 4 4 3 (3 2 ) 1 ( ) t y f t + = = ，则按⑷式计算产生的误差为 e( y ) = f (x ) − f (x) ≈ f ′(x) ∆x 4 4 * 4 4 估计以上四个式子中的 ( ), ( ), ( ), ( ) 1 2 3 4 f ′ x f ′ x f ′ x f ′ x ，即可得出⑷式误差最小的结论。 具体计算结果如下： 4
5.2 +1)° (2)99-702≈10: 3(3-22)3≈8.0×10-3 4) 5.1×10 例1:7数列{xn}满足递推公式xn=10xn1-1,(n=1,2,…),若取x=√2≈141 问按上述递推公式,从x0计算到x10时误差有多大?这个计算过程稳定吗? 解记x=141作为x=V2的近似值,则E=6-x<05×102,由 x1=10x0-1,x1=10x0-1 -x1|=(10x0-1)-(10 0-x10<100s<0.5×108 显然,误差积累很大,按递推公式xn=10xn1-1求x0时,会把初始误差c0扩大10°倍, 使计算精度受到严重影响,因此,这个计算过程不稳定
⑴ 3 6 5.2 10 ( 2 1) ! − ≈ × + ； ⑵99 − 70 2 ≈ 1.0 ； ⑶ 3 3 (3 2 2) 8.0 10− − ≈ × ； ⑷ 3 3 5.1 10 (3 2 2) 1 − ≈ × + 例 1.7 数列{xn }满足递推公式 10 1, ( 1,2, ) xn = xn−1 − n = L ，若取 2 1.41 x0 = ≈ ， 问按上述递推公式，从 x0 计算到 x10 时误差有多大？这个计算过程稳定吗？ 解 记 1.41作为 * x0 = 2 x0 = 的近似值，则 * 2 0 0 0 0.5 10− ε = x − x < × ，由 10 1, 10 1 * 0 * x1 = x0 − x1 = x − 得 0 * 0 0 * 0 0 * x1 − x1 = (10x −1) − (10x −1) = 10 x − x < 10ε 0 * 2 1 1 * 1 1 * x2 − x2 = (10x −1) − (10x −1) = 10 x − x < 10 ε M 8 0 * 10 x10 − x10 < 10 ε < 0.5×10 显然，误差积累很大，按递推公式 xn = 10xn−1 −1求 x10 时，会把初始误差 0 ε 扩大10 倍， 使计算精度受到严重影响，因此，这个计算过程不稳定。 10 5
第二章解线性方程组的直接法 2.1内容提要 1.直接法概述 目前,计算机上解线性代数方程组的数值方法尽管很多,但归纳起来,大致可以分为两 大类:一类是直接法;另一类是迭代法。一般,对中、低阶以及高阶带形线性代数方程组, 用直接法有效,而对于高阶线性代数方程组,特别是对于系数矩阵为大型稀疏矩阵的线性代 数方程组,用迭代法有效。 2.高斯(Gaus消去法 高斯消去法是一个古老的求解线性代数方程组的直接法,但由它的改进、变形得到的如 选主元消去法、三角分解法等,仍然是目前计算机上解中、低阶稠密矩阵方程组的常用有效 方法。 设有n阶代数线性方程组 x In b 写为矩阵形式 Ax=b 其中 11 为保证方程组有唯一解,设系数矩阵A为非奇异阵。将Ax=b记为A(x=b(),高斯消去 法描述如下 (1)消元过程 第k次消元(1≤k≤n-1):假定已完成k-1步消元,得到Ax=b()
第二章 解线性方程组的直接法 2.1 内容提要 1. 直接法概述 目前，计算机上解线性代数方程组的数值方法尽管很多，但归纳起来，大致可以分为两 大类：一类是直接法；另一类是迭代法。一般，对中、低阶以及高阶带形线性代数方程组， 用直接法有效，而对于高阶线性代数方程组，特别是对于系数矩阵为大型稀疏矩阵的线性代 数方程组，用迭代法有效。 2. 高斯(Gauss)消去法 高斯消去法是一个古老的求解线性代数方程组的直接法，但由它的改进、变形得到的如 选主元消去法、三角分解法等，仍然是目前计算机上解中、低阶稠密矩阵方程组的常用有效 方法。 7 设有 n 阶代数线性方程组 + + + = + + + = + + + = n n nn n n n n n n a x a x a x b a x a x a x b a x a x a x b L L L L 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 写为矩阵形式 Ax = b， 其中 = n n nn n n a a a a a a a a a A L M M M M L L 1 2 21 22 2 11 12 1 ， ， = n x x x M 2 1 x = bn b b M 2 1 b 为保证方程组有唯一解，设系数矩阵 A 为非奇异阵。将 Ax = b记为 ，高斯消去 法描述如下： (1) (1) A x = b ⑴消元过程 第 k 次消元(1 ≤ k ≤ n −1)：假定已完成 k −1步消元，得到 A(k ) x = b(k )
2) 此时,A(的右下角n-k+1阶矩阵必非奇异 不妨设a*)≠0(a4称为主元素),消去方程组Ax=b)的第k+1至n个方程中 的x,计算公式为: (a)计算行乘数m1=,(=k+1…,m) (b)第i行元素减去第k行对应元素乘以mk,即 (k)-mikukj b (i=k+1,…,n,j=k+1,…,n) 得到A+)x=b+),此时A+的右下角n-k阶矩阵必非奇异。当完成第n-1次消 元后,得到A(x=b("),其中 b (A(,b)= a()b1(),am≠0 (n) b 原方程组变形为
= ( ) ( ) ( ) ( ) ( ) ( ) (2) 2 (2) 2 (2) 22 (1) 1 (1) 1 (1) 12 (1) 11 ( ) ( ) ( , ) k n k nn k nk k k k kn k kk n n k k a a b a a b a a b a a a b A L M M L O M M L L L L L L b 8 k ) k n k x 此时， 的右下角 阶矩阵必非奇异。 ( A n − k +1 不妨设 （ 称为主元素），消去方程组 的第 至 个方程中 的 ，计算公式为： 0 ( ) ≠ k kk a (k ) kk a (k ) (k ) A x = b +1 (a)计算行乘数 ( ) ( ) k kk k ik ik a a m = ，(i = k +1,L, n) (b)第i 行元素减去第 k 行对应元素乘以 mik ，即 ( 1) ( ) (k ) ik kj k ij k aij = a − m a + ， ( 1) ( ) (k ) ik k k i k i b = b − m b + ， (i = k +1,L, n, j = k +1,L, n) 得到 A(k +1) x = b(k +1) ，此时 的右下角 (k +1) A n − k 阶矩阵必非奇异。当完成第 次消 元后，得到 ，其中 n −1 (n) (n) A x = b = ( ) ( ) ( ) ( ) ( ) (2) 2 (2) 2 (2) 22 (1) 1 (1) 1 (1) 12 (1) 11 ( ) ( ) ( , ) n n n nn k k k kn k kk n n n n a b a a b a a b a a a b A M L M M L L L L b ， ann (n) ≠ 0 。 原方程组变形为
