计算方法简明教程王能超 引论

1、 0.1 算法重在设计 0.1.1 科学计算离不开算法设计 0.1.2 算法设计要有“智类之明” 0.1.3 数学思维的化归策略 0.1.1 科学计算离不开算法设计 线性方程组：线性方程组： 11112211 21122222 1122 nn nn nnnnnn a xa xa xb a xa xaxb a xaxaxb 1112111 2122222 12 n n nnnnnn aaaxb aaaxb aaaxb 矩阵形 式 Homogeneous term Coefficie nt matrix Axb or 1112111 2122222 12 , n n nnnnnn aaaxb aa

2、axb Axb aaaxb Unknow n variables 线性方程组由增广矩阵唯一确定 A b !0solutionA How to get the solution？ Coefficient matrix A 低阶稠密阵 高阶稀疏阵 small dense matrix large sparse matrix Direct methods Iteration methods Gaussian elimination 列列/行行/完全主元素完全主元素(pivoting)消去法消去法 Gauss-Jordan elimination Square root/improved square

3、 root methods 追赶法追赶法 Jaccobi iteration Gauss-Sidel iteration SOR Existence and uniqueness of the solution？ i i D x D Cramer rule: Computation cost: (n+1)! 0.1.2 算法设计要有“智类之明” 0.1.3 数学思维的化归策略 0.2 直接法的缩减技术 0.2.1 Zeno悖论的启示 0.2.2 Zeno悖论的划归策略 0.2.3 Zeno悖论的算法描述 0.2.4 缩减技术的设计思想 0.2.5 数列求和的累加算法 0.2.6 多项式求值的秦

4、九韶算法 0.2.1 Zeno 悖论的启示 tk Sk-1 Sk V v tk-1 v V 0.2.2 Zeno 悖论的划归策略 tk Sk-1 Sk V v tk-1 v V 0.2.3 Zeno 悖论的算法描述 0.2.4 缩减技术的设计思想 0.2.5 数列求和的累加算法 0.2.6 多项式求值的秦九韶算法 16 通过一次式的反复计算，逐步得出高次多通过一次式的反复计算，逐步得出高次多 项式的值，对于一个项式的值，对于一个n次多项式，只需做次多项式，只需做n次乘次乘 法和法和n次加法即可。次加法即可。 秦九韶算法的特点：秦九韶算法的特点： 17 (1)、算法步骤：、算法步骤： 第一步：输

5、入多项式次数第一步：输入多项式次数n、最高次项的系数、最高次项的系数a0和和x 的值的值. 第二步：将第二步：将v的值初始化为的值初始化为a0，将，将i的值初始化为的值初始化为1. 第三步：输入第三步：输入i次项的系数次项的系数an. 第四步：第四步：v=vx+ai, i=n. 第五步：判断第五步：判断i是否等于是否等于n，若不是，则返回第三步；，若不是，则返回第三步； 否则，输出多项式的值否则，输出多项式的值v。 思考：你能设计程序把“秦九韶算法”表示出来 吗？ 18 例：例： 已知一个五次多项式为已知一个五次多项式为 8 . 07 . 16 . 25 . 325)( 2345 xxxxxx

6、f 用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x = 5的值。的值。 解：解： 将多项式变形：将多项式变形： 8 . 0)7 . 1)6 . 2)5 . 3)25()(xxxxxxf 按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x = 5时的值：时的值： 27255 1 v 5 0 v 5.1385.3527 2 v 9.6896.255.138 3 v 2.34517.159.689 4 v 2.172558.052.3451 5 v 所以，当所以，当x = 5时，多项式的值等于时，多项式的值等于17255.2 你从中看到了 怎样的规律？ 怎么用程序

7、框 图来描述呢？ 19 1、已知多项式、已知多项式f(x)=x5+5x4+10 x3+10 x2+5x+1 用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=-2时的值。时的值。 练习： 2、已知多项式、已知多项式f(x)=2x4-6x3-5x2+4x-6 用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5时的值。时的值。 20 秦九韶算法的另一个好处是求 在 点的值. 由（8）式有 )(x p 其中 对 求导得 ,*)( ,)(*)( )*)()( 12 1 0 n n nnn n bxp bxqxx bbxbxbxxxp ),(*)()()(xqxxxqxp 故 .从而得用秦

8、九韶算法计算 的算法 如下： x *)(xp *x .)( 12 2 1 1 0 nn nn bxbxbxbxq *)(*)(xqxp 21 .49)2()2( ,7542)( ,10)2( 3 23 4 pqc xxxxq pb 此处 例例11 11 设 ， 用秦九韶算法求 和 的值. *).(*)( 1 xpxqcn 则 )2(p ,1,2,1* , 1 00 nibxcc bc iii （*） 4332)( 24 xxxxp )2(p 解解 用（8）和（*）式构造出计算表格（1-2） 22 10 14* 4 )2(49 42* 7 10* 3 21 16* 5 8* 3 8 4* 4 4

9、* 0 2 2 2 2* 2* 常数项系数系数系数系数 系数表 2-1表 4 3 4 3 2 3 2 3 2 1 2 1 2 1 0 1 0 1 0 0 0 1234 b xb a pc xc b xb a c xc b xb a c xc b xb a c b a x x xxxx 0.3 迭代法的校正技术 0.3.1 Zeno悖论的精确解 0.3.2 Zeno悖论的迭代解 0.3.3 Zeno悖论中的“Zeno钟” 0.3.4 校正技术的设计思想 0.3.5 求开方值的迭代公式 0.3.1 Zeno悖论的精确解 0.3.2 Zeno悖论的迭代解法 0.3.3 Zeno 悖论中的“Zeno钟

10、” 0.3.4 校正技术的设计思想 求解校正方程 0 x k x 1k x 0.3.5 求开方值的迭代公式 0.4 算法优化的松弛技术 0.4.1 Zeno算法的升华 0.4.2 松弛技术的设计思想 0.4.3 千古绝技“割圆术” 0.4.1 Zeno 算法的升华 0.4.2 松弛技术的设计思想 0.4.3 千古绝技“割圆术” 33 刘徽用“割圆术”求得 ，如果单纯用“割圆”计算相 当于割到3072边形，计算量是惊人的！ 1416.3 实际上在计算中利用了现代计算方法中的松弛技术，令内接正 边形面积 近似圆周面积 ，取半径 ，计算出 n S 10r n S 用松弛法，令 为松弛参数.),( 9

11、6192192 SSSS , 625 64 314, 625 584 313 19296 SS 若取 ，则得 105 36 34 ,16.314 25 4 314) 625 584 313 625 64 314( 105 36 625 64 314 S 于是 .1416.3 100 16.314 2 r S 与 近似，但由于使用了松弛技术，计算量大大节省 了. S 1590.314 3072 S 松弛技术是计算方法中提高收敛速度的有效方法，设量 为精 确值， 与 为 的两个近似值，其加权平均为 *xx 0 x 1 x*x 35 ,)1()( 01011 xxxxxx 其中 为松弛因子. 通常

12、是比 更接近真值 ，要求 比 更接近 可选 . 1 x 0 x*xx 1 x*,x0 若增量 选得适当， 就可最好地逼近 真值 ，这就产生了选择最优 的问题，割圆术中选择的 ，使 )( 010 xxxx *x 105 36 )( 105 36 96192192 SSSS 是一个接近真值 的近似. S 36 利用松弛技术的方法称为松弛法松弛法，是数值分析中常用的方法. 在近似计算积分的梯形公式中取 分别得2 ,1n . 2 ),()(2)( 4 ),()( 2 2 1 ba cbfcfaf ab T bfaf ab T 为了得到 更精确的近似也可以使用松弛法，令)(fI ,)1()( 121221