《第6章-非线性方程的计算方法课件.ppt》由会员分享，可在线阅读，更多相关《第6章-非线性方程的计算方法课件.ppt（21页珍藏版）》请在三一办公上搜索。
1、2 Bisection Method,x1,x2,a,b,When to stop?,或,不能保证 x 的精度,x*,2,6.1.1 Bisection Method,误差 分析：,第 k 步产生的 xk 有误差,对于给定的精度,可估计二分法所需的步数 k：,简单;对f(x)要求不高(只要连续即可).,无法求复根及偶重根 收敛慢,注：用二分法求根，最好先给出 f(x)草图以确定根的大概位置。或用搜索程序，将a,b分为若干小区间，对每一个满足 f(ak)f(bk)0 的区间调用二分法程序，可找出区间a,b内的多个根，且不必要求 f(a)f(b)0。,6.1.1 Bisection Method,
2、6.1.1 Bisection Method,6.1.2 迭代法/*Fixed-Point Iteration*/,f(x)=0,x=(x),f(x)的根,(x)的不动点,思路,从一个初值 x0 出发，计算 x1=(x0),x2=(x1),xk+1=(xk),若 收敛，即存在 x*使得，且 连续，则由 可知 x*=(x*)，即x*是 的不动点，也就是f 的根。,So basically we are done!I cant believe its so simple!Whats the problem?,Oh yeah?Who tells you that the method is conv
3、ergent?,6.1.2 Fixed-Point Iteration,6.1.2 Fixed-Point Iteration,定理,k,6.1.2 Fixed-Point Iteration,证明：(x)在a,b上存在不动点？,令,有根,不动点唯一？,反证：若不然，设还有，则,而,当k 时，xk 收敛到 x*？,6.1.2 Fixed-Point Iteration,可用 来控制收敛精度,L 越 收敛越快,小,注：定理条件非必要条件，可将a,b缩小，定义局部收敛性：若在 x*的某 领域 B=x|x x*|有 C1a,b 且|(x*)|1，则由x0B 开始的迭代收敛。即调整初值可得到收敛的结果
4、。,6.1.2 Fixed-Point Iteration,Algorithm:Fixed-Point IterationFind a solution to x=(x)given an initial approximation x0.Input:initial approximation x0;tolerance TOL;maximum number of iterations Nmax.Output:approximate solution x or message of failure.Step 1 Set i=1;Step 2 While(i Nmax)do steps 3-6Ste
5、p 3 Set x=(x0);/*compute xi*/Step 4 If|x x0|TOL then Output(x);/*successful*/STOP;Step 5 Set i+;Step 6 Set x0=x;/*update x0*/Step 7 Output(The method failed after Nmax iterations);/*unsuccessful*/STOP.,当 x 很大时，此处可改为,6.1.3 牛顿法/*Newton-Raphson Method*/,原理：将非线性方程线性化 Taylor 展开/*Taylors expansion*/,取 x0
6、x*，将 f(x)在 x0 做一阶Taylor展开:,，在 x0 和 x 之间。,将(x*x0)2 看成高阶小量，则有：,线性/*linear*/,只要 f C1，每一步迭代都有f(xk)0，而且，则 x*就是 f 的根。,6.1.3 Newton-Raphson Method,定理,（收敛的充分条件）设 f C2a,b，若(1)f(a)f(b)0；则Newtons Method产生的序列 xk 收敛到f(x)在 a,b 的唯一根。,有根,根唯一,产生的序列单调有界，保证收敛。,定理,（局部收敛性）设 f C2a,b，若 x*为 f(x)在a,b上的根，且 f(x*)0，则存在 x*的邻域 使
7、得任取初值，Newtons Method产生的序列 xk 收敛到x*，且满足,6.1.3 Newton-Raphson Method,证明：Newtons Method 事实上是一种特殊的不动点迭代 其中，则,收敛,由 Taylor 展开：,只要 f(x*)0，则令 可得结论。,在单根/*simple root*/附近收敛快,6.1.3 Newton-Raphson Method,注：Newtons Method 收敛性依赖于x0 的选取。,x*,6.1.3 Newton-Raphson Method,重根/*multiple root*/加速收敛法：,Q1:若，Newtons Method
8、是否仍收敛？,设 x*是 f 的 n 重根，则：且。,因为 Newtons Method 事实上是一种特殊的不动点迭代，其中，则,A1:有局部收敛性，但重数 n 越高，收敛越慢。,Q2:如何加速重根的收敛？,A2:将求 f 的重根转化为求另一函数的单根。,令，则 f 的重根=的单根。,6.1.3 Newton-Raphson Method,正割法/*Secant Method*/：,Newtons Method 一步要计算 f 和 f，相当于2个函数值，比较费时。现用 f 的值近似 f，可少算一个函数值。,切线/*tangent line*/,割线/*secant line*/,切线斜率割线斜
9、率,需要2个初值 x0 和 x1。,收敛比Newtons Method 慢，且对初值要求同样高。,6.1.3 Newton-Raphson Method,下山法/*Descent Method*/Newtons Method 局部微调：,原理：若由 xk 得到的 xk+1 不能使|f|减小，则在 xk 和 xk+1 之间找一个更好的点，使得。,注：=1 时就是Newtons Method 公式。当=1 代入效果不好时，将 减半计算。,6.1.3 Newton-Raphson Method,Algorithm:Newtons Descent MethodFind a solution to f(
10、x)=0 given an initial approximation x0.Input:initial approximation x0;f(x)and f(x);minimum step size of xmin;tolerance TOL1 for x;tolerance TOL2 for;maximum number of iterations Nmax.Output:approximate solution x or message of failure.Step 1 Set k=1;Step 2 While(k Nmax)do steps 3-10Step 3 Set=1;Step
11、 4 Set;/*compute xk*/Step 5 If|x x0|TOL2 then GOTO Step 4;/*compute a better xi*/Step 9 Set x0=x0+xmin;/*move forward anyway to avoid deadlock*/Step 10 Set k+;Step 11 Output(Method failed after Nmax iterations);STOP./*unsuccessful*/,计算量未见得减小,精品课件！,精品课件！,6.1.3 Newton-Raphson Method,求复根/*Finding Complex Roots*/Newton 公式中的自变量可以是复数,记 z=x+i y,z0 为初值，同样有,设,代入公式，令实、虚部对应相等，可得,
