1、迭代法随想迭代法随想 张 然 吉林大学数学学院老夫聊发少年狂，重操锅盏扮厨娘。未知饮品难调味，不烹虾蟹只烧汤。 蔡大用 2007.07.25 知其然知其所以然； 授之鱼不如授之以渔； know-how no better than “know-why” 教学相长计算数学理论实际应用计算机计算机 根据计算机的特点设计可行的算法； 数值计算方法理论依据：误差分析，收敛性分析，数值稳定性分析给出算法的程序实现： C, C+, Forturne, Matlab, Maple, MathCAD, Mathematica等 没必要专门开数学软件的课迭代法及其应用两个简单例子迭代法理论 非线性方程求解 Ne
2、wton迭代法 高阶迭代法 迭代法应用 两个简单例子例1 已知 0a ，任取 00 x ，则由 11()2nnnaxxx(0,1,2,)n 两个简单例子例2 已知方程 29sin1xx0.4x 在 附近有根. 假定我们已会计算 1 sin x那么我们就能从 0.4x 开始，通过迭代公式 111 sin3nnxx逐步得到所要求的根. 方程 （非线性方程、超越方程）方程组算子方程（微分方程） 迭代法可用于处理 （1） 根的隔离。（2） 近似根的精确化 非线性方程求根求方程的近似根，一般需要解决这样两个问题 二分法且 ( ) , f xC a b( ) ( )0f a f b 优点：简单可靠，易于在
3、计算机上实现，对 f(x) 要求不高，只需连续 缺点：用于计算精度要求较高的近似根时， 所费时较长，且使用范围有局限，不 能用于求复根或偶数根。 function x=nabisect(fname,a,b,e)%用途: 二分法解非线性方程 f(x)=0%格式: x=nabisect(fname,a,b,e) fname 为用函数句柄或内嵌函数表达的% f(x),a,b为区间端点,e为精度(默认值为10-4),x为返回解,程序要求函数在% 两端点值必须异号,中间变量fa,fb,fx引入可以最大限度减少fname调用次数,从而提高速度if nargin0,error(函数在两端点值必须异号);en
4、dx=(a+b)/2while (b-a)(2*e), fx=feval(fname,x); if fa*fx0,b=x;fb=fx;else a=x;fa=fx;end x=(a+b)/2end 二分法Matlab程序 先将方程 简单迭代法( )xx转化为等价方程( )0f x 然后从某个数 出发,通过计算0 x1()nnxx(0,1,2,)n 构造序列 。如果 连续且这个序列收敛于 ,则由上式立即可得nx( )x*x*()xx 问题问题 简单迭代法如何选取迭代函数 ,使迭代过程 1()nnxx(0,1,2,)n 收敛？定理定理1 1（收敛充分条件）（收敛充分条件） 若 满足( )x（1）a
5、,b上 存在, 且|( )|1xL（2）对任意 都有 , xa b( ) , xa b( )x( )x 简单迭代法1()nnxx则（2）（1）对任取初值 ,迭代法 产生的迭代序列 都收敛于方程 在a,b上的唯一实根.0 , xa b nx( )xx（3）*11|;1nnnxxxxL*10|.1nnLxxxxL 简单迭代法定理定理2 2（收敛充分条件）（收敛充分条件） 若存在区间（c,d）,使（1）方程x= (x)在(c,d)内有实根 （2） 在(c,d)内连续且*;x( )x 则迭代法1()nnxx(0,1,2,)n *|()| 1x在*x附近具有局部收敛性. Newton迭代法及其变形New
6、tonNewton迭代法：迭代法：(0,1,2,)n 1()()nnnnf xxxfx拟拟NewtonNewton迭代法：迭代法：(0,1,2,)n 10()()nnnf xxxfx Newton迭代法及其变形NewtonNewton下山法：下山法：(0,1,2,)n 1()()nnnnf xxxfx 弦割法：弦割法：(1,2,)n 111()()()()nnnnnnnf xxxxxf xf x Newton法：求方程单根时，具有二阶收敛速度，但对初值要求苛刻，且需求导 弦割法：针对求导复杂情形, 不需求导，但收敛阶只有1.618阶, 且须提供两个较好的初值.function x=nanewt
7、on(fname,dfname,x0,e,N)%用途: Newton迭代法解非线性方程 f(x)=0%格式: x=nanewton(fname,dfname,x0,e,N) fname 和dfname分别表示f(x)及其导函数的 M % 函数句柄或内嵌函数,x0为迭代初值,e为精度要求(默认值为10-4),x为返回解,% 并显示计算过程设置迭代次数上限N以防发散(默认500)if nargin5,N=500;endif nargin3&kN, k=k+1; x0=x;x=x0-feval(fname,x0)/feval(dfname,x0); disp(x)endif k=N,warning(
8、已达迭代次数上限);endNewton法的推广思考思考按照Taylor展开，将Newton法进一步推广到高阶情形？迭代法的收敛阶定义定义 设序列nx*x收敛于 .若存在常数(1)p p 和(0)c c ,使*1*|limnpnnxxcxx则称序列 是p 阶收敛的nx 三阶迭代法1111(1()1() )()()2nnnnnnxxL xL xfxf x其中2() ()()()nnnnfxf xL xfx01，ChebyshevChebyshev迭代法迭代法 给定一个初值给定一个初值 , ,通过通过 Halley Halley迭代法迭代法 给定一个初值给定一个初值 , ,通过通过0 x111(1()()()2nnnnnxxL xfxf x0 x11111(1()1() )()()22nnnnnnxxL xL xfxf x Super-Halley Super-Halley迭代法迭代法 给定一个初值给定一个初值 , ,通过通过1111(1()1() )()()2nnnnnnxxL xL xfxf x0 xTHIRD-ORDER ITERATIVE METHOD FOR CHOICES OF REGULARIZATION PARAMETERS IN LINEAR INVERSE PROBLEMSOne Task:One Task:
