计算方法简明教程王能超-引论分解优秀PPT.ppt

引 论0.1 算法重在设计0.2 干脆法的缩减技术0.3 迭代法的校正技术0.4 算法设计的松弛技术小结0.1 算法重在设计0.1.1 科学计算离不开算法设计0.1.2 算法设计要有“智类之明”0.1.3 数学思维的化归策略0.1.1 科学计算离不开算法设计线性方程组：线性方程组：矩阵形式Homogeneous termCoefficient matrixorUnknown variables线性方程组由增广矩阵唯一确定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 iterationSORExistence and uniqueness of the solution？Cramer rule:Computation cost:(n+1)!0.1.2 算法设计要有“智类之明”0.1.3 数学思维的化归策略0.2 干脆法的缩减技术 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.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.第三步：输入第三步：输入i次项的系数次项的系数an.第四步：第四步：v=vx+ai,i=n.第五步：推断第五步：推断i是否等于是否等于n，若不是，则返回第三步；，若不是，则返回第三步；否则，输出多项式的值否则，输出多项式的值v。思索：你能设计程序把“秦九韶算法”表示出来吗？18例：例：已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：按由里到外的依次，依此计算一次多项式当按由里到外的依次，依此计算一次多项式当x=5时的值：时的值：所以，当所以，当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用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5时的值。时的值。20 秦九韶算法的另一个好处是求 在 点的值.由（8）式有其中对 求导得故 .从而得用秦九韶算法计算 的算法如下：21此处 例例11 11 设 ，用秦九韶算法求 和 的值.则（*）解解 用（8）和（*）式构造出计算表格（1-2）220.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钟”0.3.4 校正技术的设计思想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边形，计算量是惊人的！事实上在计算中利用了现代计算方法中的松弛技术，令内接正 边形面积 近似圆周面积 ，取半径 ，计算出用松弛法，令 为松弛参数.若取 ，则得34于是 与 近似，但由于使用了松弛技术，计算量大大节省了.松弛技术是计算方法中提高收敛速度的有效方法，设量 为精确值，与 为 的两个近似值，其加权平均为35其中 为松弛因子.通常 是比 更接近真值 ，要求 比 更接近 可选 .若增量 选得适当，就可最好地逼近真值 ，这就产生了选择最优 的问题，割圆术中选择的 ，使是一个接近真值 的近似.36 利用松弛技术的方法称为松弛法松弛法，是数值分析中常用的方法.在近似计算积分的梯形公式中取 分别得为了得到 更精确的近似也可以运用松弛法，令若取 ，则得37这就是计算积分的辛普森公式，比梯形公式精度高.小 结 算法设计一二三 领悟一条基本原理：将困难化归为简洁的重复 区分两类数值算法 干脆法与迭代法的对立统一 驾驭三种设计技术 化大为小的缩减技术 化难为易的校正技术 化粗为精的松弛技术