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

1、0.1 算法重在设计0.1.1 科学计算离不开算法设计0.1.2 算法设计要有“智类之明”0.1.3 数学思维的化归策略0.1.1 科学计算离不开算法设计线性方程组：线性方程组：11112211211222221122nnnnnnnnnna xa xa xba xa xaxba xaxaxb1112111212222212nnnnnnnnaaaxbaaaxbaaaxb矩阵形式Homogeneous termCoefficient matrixAxbor1112111212222212,nnnnnnnnaaaxbaaaxbAxbaaaxbUnknown variables线性方程组由增广矩阵唯一

2、确定A b!0solutionA How to get the solution？ Coefficient matrix A低阶稠密阵 高阶稀疏阵small dense matrix large sparse matrixDirect methodsIteration methods Gaussian elimination列列/行行/完全主元素完全主元素(pivoting)消去法消去法Gauss-Jordan eliminationSquare root/improved square root methods追赶法追赶法Jaccobi iterationGauss-Sidel iterat

3、ionSORExistence and uniqueness of the solution？iiDxDCramer 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 多项式求值的秦九韶算法0.2.1 Zeno 悖论的启示tkSk-1SkVvtk-1vV 0.2.2 Zeno 悖论的划归策略tkSk-1SkVvtk-1vV 0.

4、2.3 Zeno 悖论的算法描述0.2.4 缩减技术的设计思想0.2.5 数列求和的累加算法0.2.6 多项式求值的秦九韶算法 16 通过一次式的反复计算，逐步得出高次多通过一次式的反复计算，逐步得出高次多项式的值，对于一个项式的值，对于一个n次多项式，只需做次多项式，只需做n次乘次乘法和法和n次加法即可。次加法即可。秦九韶算法的特点：秦九韶算法的特点：17(1)、算法步骤：、算法步骤：第一步：输入多项式次数第一步：输入多项式次数n、最高次项的系数、最高次项的系数a0和和x的值的值.第二步：将第二步：将v的值初始化为的值初始化为a0，将，将i的值初始化为的值初始化为1.第三步：输入第三步：输入

5、i次项的系数次项的系数an.第四步：第四步：v=vx+ai, i=n.第五步：判断第五步：判断i是否等于是否等于n，若不是，则返回第三步；，若不是，则返回第三步；否则，输出多项式的值否则，输出多项式的值v。思考：你能设计程序把“秦九韶算法”表示出来吗？18例：例： 已知一个五次多项式为已知一个五次多项式为8 . 07 . 16 . 25 . 325)(2345xxxxxxf用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x = 5的值。的值。解：解： 将多项式变形：将多项式变形：8 . 0)7 . 1)6 . 2)5 . 3)25()(xxxxxxf按由里到外的顺序，依此计算一次多项式当按

6、由里到外的顺序，依此计算一次多项式当x = 5时的值：时的值：272551v50v5.1385.35272v9.6896.255.1383v2.34517.159.6894v2.172558.052.34515v所以，当所以，当x = 5时，多项式的值等于时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？191、已知多项式、已知多项式f(x)=x5+5x4+10 x3+10 x2+5x+1用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=-2时的值。时的值。练习：2、已知多项式、已知多项式f(x)=2x4-6x3-5x2+4x-6用秦九韶算法求这个多项式当用

7、秦九韶算法求这个多项式当x=5时的值。时的值。20 秦九韶算法的另一个好处是求 在 点的值.由（8）式有)(xp其中对 求导得,*)(,)(*)()*)()(1210nnnnnnbxpbxqxxbbxbxbxxxp),(*)()()(xqxxxqxp故 .从而得用秦九韶算法计算 的算法如下：x*)(xp*x.)(122110nnnnbxbxbxbxq*)(*)(xqxp21.49)2()2(,7542)(,10)2(3234pqcxxxxqpb此处 例例11 11 设 ， 用秦九韶算法求 和 的值.*).(*)(1xpxqcn则)2(p,1,2,1*,100nibxccbciii（*）4332

8、)(24xxxxp)2(p 解解 用（8）和（*）式构造出计算表格（1-2）221014*4)2(4942*710*32116*58*384*44*02222*2*常数项系数系数系数系数系数表 2-1表4343232321212101010001234bxbapcxcbxbacxcbxbacxcbxbacbaxxxxxx0.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

9、Zeno 悖论中的“Zeno钟”0.3.4 校正技术的设计思想 求解校正方程 0 x kx 1kx 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 实际上在计算中利用了现代计算方法中的松弛技术，令内接正 边形面积 近似圆周面积 ，取半径 ，计算出nS10rnS用松弛法，令 为松弛参数.),(961921

10、92SSSS,62564314,62558431319296SS 若取 ，则得1053634,16.314254314)62558431362564314(1053662564314S于是.1416.310016.3142rS 与 近似，但由于使用了松弛技术，计算量大大节省了.S1590.3143072S 松弛技术是计算方法中提高收敛速度的有效方法，设量 为精确值， 与 为 的两个近似值，其加权平均为*xx0 x1x*x35,)1()(01011xxxxxx其中 为松弛因子. 通常 是比 更接近真值 ，要求 比 更接近 可选 .1x0 x*xx1x*,x0 若增量 选得适当， 就可最好地逼近真值 ，这就产生了选择最优 的问题，割圆术中选择的 ，使)(010 xxxx*x10536)(1053696192192SSSS是一个接近真值 的近似.S36 利用松弛技术的方法称为松弛法松弛法，是数值分析中常用的方法. 在近似计算积分的梯形公式中取 分别得2 ,1n.2),()(2)(4),()(221bacbfcfafabTbfafabT为了得到 更精确的近似也可以使用松弛法，令)(fI,)1()(121221TTT