引 论,0.1 算法重在设计 0.2 直接法的缩减技术 0.3 迭代法的校正技术 0.4 算法设计的松弛技术 小结,0.1 算法重在设计,0.1.1 科学计算离不开算法设计 0.1.2 算法设计要有“智类之明” 0.1.3 数学思维的化归策略,0.1.1 科学计算离不开算法设计,线性方程组：,矩阵形式,Homogeneous term,Coefficient matrix,or,Unknown variables,线性方程组由增广矩阵唯一确定,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 root methods 追赶法,Jaccobi iteration Gauss-Sidel iteration SOR,Existence and uniqueness of the solution？,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 多项式求值的秦九韶算法,0.2.1 Zeno 悖论的启示,0.2.2 Zeno 悖论的划归策略,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,你从中看到了怎样的规律？怎么用程序框图来描述呢？,19,1、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1 用秦九韶算法求这个多项式当x=-2时的值。,练习：,2、已知多项式f(x)=2x4-6x3-5x2+4x-6 用秦九韶算法求这个多项式当x=5时的值。,20,21,此处,例11 设 ， 用秦九韶算法求 和 的值.,则,（*）,解 用（8）和（*）式构造出计算表格（1-2）,22,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钟”,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,这就是计算积分的辛普森公式，比梯形公式精度高.,小 结,算法设计一二三 领悟一条基本原理： 将复杂化归为简单的重复 区分两类数值算法 直接法与迭代法的对立统一 掌握三种设计技术 化大为小的缩减技术 化难为易的校正技术 化粗为精的松弛技术,