中国矿亚大鉴CHINA UNIVERSITY OFMININGANDTECHNOLOGY绪论第一章纟81.计算方法的研究对象和特点S2误差及其基本概念S3数值计算的原则
CHINA UNIVERSITY OF MINING AND TECHNOLOGY 第一章 绪论 §1 计算方法的研究对象和特点 §2 误差及其基本概念 §3 数值计算的原则
中国矿亚大医CHINA UNIVERSITYOF MININGANDTECHNOLOGY81计算方法的研究对象和特点计算方法的研究内容：构造算法（数学问题数值解的计算方法）基本的数学问题？1.大型线性代数方程组Ax=b求解；2.矩阵A的特征值和特征向量计算：3.非线性方程f(x)=0的求解（求根）；分f(x)dx计算；4.积分5.常微分方程初值问题求解；6.其它
CHINA UNIVERSITY OF MINING AND TECHNOLOGY §1 计算方法的研究对象和特点 计算方法的研究内容：构造算法（数学问题数值 解的计算方法） •基本的数学问题？ 1.大型线性代数方程组Ax = b求解; 2.矩阵A的特征值和特征向量计算; 3.非线性方程 的求解(求根); 4.积分 计算; 5.常微分方程初值问题求解; 6.其它。 f x() 0 = ( ) b a f x dx ∫
中国矿亚大整CHINAUNIVERSITYOF MININGANDTECHNOLOGY为什么要求数值解？y=1-2xy例如 常微分方程的初值问题y(0) = 0其解析解（精确解）为 以(x)=e-「e"dt而实际只需知道y(1),y(1.5）等近似值。这些近似值就是数值解
CHINA UNIVERSITY OF MINING AND TECHNOLOGY •为什么要求数值解？ 例如 常微分方程的初值问题 1 2 (0) 0 y xy y ⎧ ′ = − ⎨ ⎩ = 其解析解（精确解）为 2 2 0 ( ) x x t y x e e dt − = ∫ 而实际只需知道 y(1), (1.5) y 等近似值。这些近似值 就是数值解
中国矿亚大整CHINA UNIVERSITYOF MININGANDTECHNOLOGY如何构造方法（主要思想）1.选代法2.以直线代替曲线（非线性问题线性化）3.化整为零（离散化）4.外推法（加速）·构造什么样的方法实用的好的算法有三个标准：快准省计算步骤少，收敛速度快数值稳定性好，计算结果可靠性高节省计算机内存(大型稀疏矩阵问题
CHINA UNIVERSITY OF MINING AND TECHNOLOGY •如何构造方法（主要思想） 1. 迭代法 2. 以直线代替曲线（非线性问题线性化） 3. 化整为零（离散化） 4. 外推法（加速） •构造什么样的方法 实用的好的算法有三个标准： 快 ——— 计算步骤少，收敛速度快 准 ——— 数值稳定性好，计算结果可靠性高 省 ——— 节省计算机内存 (大型稀疏矩阵问题 )
中国矿亚大整CHINAUNIVERSITYOFMININGANDTECHNOLOGY1. 快例1 多项式求值的Horner算法(秦九韶算法P7)P,(x)= a,x" +an-ix"- +..+ ax+ ao给定x的值，计算P(x)的值。算法一按自然顺序计算加法次数=nn(n + 1)乘法次数=n+(n-1)+..+1='2算法二嵌套算法（Hornor秦九韶）P,(x)=(a,x+an-1)x+an-2)x+...+a)x+ao乘法次数=加法次数=n
CHINA UNIVERSITY OF MINING AND TECHNOLOGY 1. 快 例 1 多项式求值的Horner算法 (秦九韶算法P7 ) 1 1 10 ( ) n n P x ax a x ax a n nn − − = + ++ + " 给定 x的值，计算 的值。 ( ) P x n 算法一 按自然顺序计算 乘法次数＝ ( 1) ( 1) 1 2 n n n n + + − + += " 加法次数＝ n 算法二 嵌套算法（Hornor,秦九韶） 乘法次数＝加法次数＝ n 1 2 10 ( ) ((( ) ) ) P x ax a x a x a x a n nn n − − = + + ++ +
中国矿亚大医CHINAUNIVERSITY OFMININGAND TECHNOLOGYai1j+a12x2+...+ainn=bia211+a2272+..+a2nxn=b2例2解线性方程组[anij+an2X2+..+annin=bn≤算法l：Cramer法则D;,(i=1,2,,n), D=- E(-1)aj"2i?*·ninXi=D乘除法次数A,= n!(n-1)(n+1)+n如n=20,A。~9.7×102°假设计算机1秒钟进行1亿=108次乘除法，共需时：
CHINA UNIVERSITY OF MINING AND TECHNOLOGY ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + + + = + + + = + + + = 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 " " " " " 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 例 2 解线性方程组 "算法1: Cramer法则 乘除法次数A n ＝ , ( i 1 , 2 , , n), D D x i i = = " = ∑ − njn D a j a j " a 1 2 1 2 ( 1 ) τ n ! ( n − 1)( n + 1 ) + n 20 20 如n A = ≈× 20 9 7 10 ,., 假设计算机１秒钟进行 １亿=108 次乘除法，共需时：
中国矿亚大医CHINA UNIVERSITY OFMININGAND TECHNOLOGY9.7×1020(万年)~30t=710×60×60×24×365算法2：Gauss消去法乘除法次数：An=-nn33A20 = 3060耗时：t,=3×10-(秒)例3计算积分的梯形公式与Simpson公式：非线性方程求根，Newton法比二分法快
CHINA UNIVERSITY OF MINING AND TECHNOLOGY "算法2: Gauss消去法 乘除法次数： An n n n 3 1 3 1 3 2 = + − 3060 A20 = 耗时： t − = × 5 2 3 10 ( 秒 ) 例 3 计算积分的梯形公式与Simpson公式； 非线性方程求根，Newton法比二分法快。 . t × = × ××× 20 1 8 9 7 10 10 60 60 24 365 ≈ 30 (万年 )
中国矿亚大业CHINAUNIVERSITY OF MININGANDTECHNOLOGY2. 准例4求根x2-56x+1=0，假设计算机有尾数为5位，V783=27.98256±/783×4=28±V783算法一 Xi,2=2X,=28+V783=55.982第二个解的精确值为0.0178628X, = 28- V783 = 0.018算法二X,=28+V783=55.98211=0.017863X2=128+78355.9820
CHINA UNIVERSITY OF MINING AND TECHNOLOGY 2. 准 例 4 求根 ，假设计算机有尾数为 5位， 2 x x − 56 1 0 + = 算法一 1 x =+ = 28 783 55.982 算法二 783 27.982 = 1,2 56 783 4 28 783 2 x ± × = =± 2 x =− = 28 783 0.018 1 x =+ = 28 783 55.982 2 1 1 0.017863 28 783 55.982 x = == + 第二个解的精确 值为0.0178628
中国矿亚大鉴CHINAUNIVERSITYOF MININGANDTECHNOLOGY例5（P1例1，P5例3）计算积分I(n)=e-'x"e*dx (n=0,1,2,..,9)直接积分I(0)=1-e-1解法一由分部积分法可得导 I(n)=1-nl(n-1)取初值I(0)=1-e-" = 0.6321≤ii, =1-ni.-则递推公式计算得1，=0.3679,,，=-0.7280,1，=7.552i
CHINA UNIVERSITY OF MINING AND TECHNOLOGY 例 5 （ P1 例 1 ，P5 例 3）计算积分 1 1 0 ( ) ( 0,1, 2, , 9) n x I n e x e dx n − = = ∫ " 由分部积分法可得 I n nI n ( ) 1 ( 1) = − − 1 0 Ie I (0) 1 0.6321 − =− = 取初值 则递推公式 1 1 n n I nI − = − 计算得 1 89 I II = =− = 0.3679, , 0.7280, 7.552 " 1 I e (0) 1 − 解法一 直接积分 = −
中国矿亚大鉴CHINA UNIVERSITY OF MININGAND TECHNOLOGY算法1结果算法2结果精确值I(1)0.36790000.36787950.36787941(2)0.26420000.26424110.26424111(3)0.20740000.20727680.20727661( 4)0.17040000.17089290.17089341( 5)0.14800000.14553570.1455329I(6)0.11200000.12678570.1268024I(7)0.21600000.11250000.11238361( 8)-0.72800000.10000000.10093231(9)0.09161237.55200000.10000001(10)0.0000000-74.52000000.0838771
CHINA UNIVERSITY OF MINING AND TECHNOLOGY 算法 1结果 算法 2结果 精确值 I( 1) 0.3679000 0.3678795 0.3678794 I( 2) 0.2642000 0.2642411 0.2642411 I( 3) 0.2074000 0.2072768 0.2072766 I( 4) 0.1704000 0.1708929 0.1708934 I( 5) 0.1480000 0.1455357 0.1455329 I( 6) 0.1120000 0.1267857 0.1268024 I( 7) 0.2160000 0.1125000 0.1123836 I( 8) -0.7280000 0.1000000 0.1009323 I( 9) 7.5520000 0.1000000 0.0916123 I(10) -74.5200000 0.0000000 0.0838771