二数值计算原则好算法的三个标准快准省计算步骤少，收敛速度快数值稳定性好，计算结果可靠性高节省计算机内存(大型稀疏矩阵问题
二 数值计算原则 好算法的三个标准： 快 — 计算步骤少，收敛速度快 准 — 数值稳定性好，计算结果可靠性高 省 — 节省计算机内存(大型稀疏矩阵问题)
1.快：计算步骤少，收敛速度快例2多项式求值的Hornor算法(秦九韶算法P7)P,(x) = a,x" + an-ix"-- +...+ a,x+ ao给定x的值，计算 P,(x)的值。≤算法1：按自然顺序计算加法次数=nn(n + 1)乘法次数= n+(n-1)+...+1= "2α算法2：嵌套算法（Hornor,秦九韶）P,(x) =(a,x + an-1)x + an-2)x +... + a,)x + ao乘法次数一加法次数一n
1. 快:计算步骤少，收敛速度快 例2 多项式求值的Hornor算法(秦九韶算法P7) 1 1 1 0 ( ) n n P x a x a x a x a n n n 给定x的值，计算 P x n ( ) 的值。 算法1：按自然顺序计算 乘法次数＝ ( 1) ( 1) 1 2 n n n n 加法次数＝ n 算法2: 嵌套算法（Hornor,秦九韶） 乘法次数＝加法次数＝ n 1 2 1 0 ( ) ((( ) ) ) P x a x a x a x a x a n n n n
ai1xi + a12x2 + ..: + ainxn = bia21X1 + a22x2 + :::+ a2nxn = b2例3解线性方程组aniXi +an2x2 +:.:+ annxn = bn≤算法l：Cramer法则D;,(i - 1,2,,n), D -E(-1) a1j,'2i-- mj,.xiD乘除法次数A = n!(n-l)(n+1)+ n如n =20,A20 ~ 9.7×1020，假设计算机 1 秒钟进行1 亿=108次乘除法，共需时：9.7 ×1020～30(万年)ti=10°×60 ×60 × 24 ×365
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 例3 解线性方程组 算法1: Cramer法则 乘除法次数An ＝ ,(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, 9.7 10 , 20 如n A20 假设计算机１秒钟进行 １亿=108次乘除法，共需时： . t 20 1 8 9 7 10 10 60 60 24 365 30 (万年)
算法2：Gauss消去法乘除法次数：An=n +n2A20 = 3060耗时：t,=3×10～ (秒)例4 如FFT(快速傅立叶变换ab+ac =a(b+c)； 零乘一个数省去例5 计算积分的梯形公式与Simpson公式非线性方程求根，Newton法比一分法快
算法2: Gauss消去法 乘除法次数： An n n n 3 1 3 1 3 2 A20 3060 耗时： t 5 2 3 10 (秒) 例5 计算积分的梯形公式与Simpson公式； 非线性方程求根，Newton法比二分法快。 例4 如FFT(快速傅立叶变换) ab ac a(b c); 零乘一个数省去
2.准：数值稳定性好，计算结果可靠性高例6 求根 x2－56x+1=0，假设计算机有尾数为5位783 = 27.98256± /783×4=28 ± 783α算法1:xi.2 =2韦达定理：x, = 28 + V783 = 55.982设ax2 + bx + c = 0(a ± 0)x, = 28 - V783 = 0.018bC则xi + X2 =Xix20a区算法2:x, = 28 + ~783 = 55.982110.0178630Xz =28 + ~78355.982注：x2 = 0.0178628
2. 准:数值稳定性好，计算结果可靠性高 例6 求根 ，假设计算机有尾数为5位， 2 x x 56 1 0 算法1: 1 x 28 783 55.982 算法2: 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 注：x2 * 0.0178628 a c x x a b x x ax bx c a 1 2 1 2 2 , 0( 0), 则 设 韦达定理：