Lec非线性方程的迭代法.ppt

非线性方程的迭代法向 华武汉大学数学与统计学院(Sumerians, third millennium BC, n>10实际中很少,但在 computer algebra中n>100,且系数高精度)Kepler方程:取x0作为初始近似值，将f(x)在x0做Taylor展开:作为第一次近似值牛顿法及其几何意义基本思路：将非线性方程f(x)=0 线性化重复上述过程  Newton法每一步用不同的切线方程去逼近非线性方程,因 此也称为切线法,它是一种将非线性方程线性化的方法.若定义 ,则可以写成定点迭代的格式何时收敛?局部收敛性思考思考如何判断收敛?收敛的快慢?收敛的阶停机准则设{xk}为收敛于f(x)=0的解x*的序列,记 ek=|xk-x*|为 第k次迭代误差.若存在某个实数 p>=1及正数C,使则称序列{xk}为p 阶收敛.牛顿法的收敛性与收敛速度当p=1且0 0；则由Newton法产生的序列{ xk } 单调地收敛到f (x)=0 在 [a, b] 的唯一根x*,且收敛速度至少是二阶的故可用 作为停机准则 需要一个适当的误差估计作为停机准则。

因为其中 在 与 之间，从而有估计如何判断收敛?(停机准则)直观上希望计算残量很小:Xf(x)注意事项一: 检查连续两次迭代的差, 防止假收敛Xf(x)注意事项二: 检查函数值 f(x), 防止假收敛.(1) 选定初值x0 ,计算f (x0) , f (x0) 计算步骤(2) 按公式 迭代得新的近似值 xk+1 (3) 对于给定的允许精度，如果则终止迭代，取;否则k=k+1，再转步骤(2)计算#include #include #include void main() { float epsilon, x, xb, y, y_derivative, error; void func();printf( “Initial guess ? “ ); scanf( “%f“, epsilon=1.0e-8;error=1.0e10; xb = x; while( error>epsilon ) { func( x, x = x - y/y_derivative; /* finds new x. */error=fabs(x-xb); xb = x;}printf( “\n-----------------------\n“ );printf( “ Final solution = %g \n“, x );printf( “-------------------------\n“ );} void func(x, y, y_derivative) /*Computes y and y_derivative */ float x, *y, *y_derivative; { *y = pow(x, 3) - 5.0*pow(x, 2) + 6.*x;*y_derivative = 3.0*pow(x, 2) - 10.0*x + 6.; return; } 1.已知重数m,用修正的Newton迭代公式:2.未知重数, 定义一个新的函数:把Newton法用于 , 得到对重根仍然二阶收敛的格式:重根的处理3.自适应 Newton 法2. Newton下山法Newton 法的变形1. 简化 Newton法3. 弦截法(割线法)求解非线线性方程组组 的牛顿迭代公式为内迭代要求解线性代数方程组Newton-Krylov方法拟牛顿法(Broyden,DFP,BFS)Inexact Newton methodWhat level of accuracy is required?R.S. Dembo, etc.,SINUM,19(1982),pp.400-Chebyshev-Halley familyChebyshev’s methodHalley methodSuper-Halley methodNewton’s methodNewton法解非线性方程组f=inline('[2*x-y^2+log(x); x^2-x*y-x+1]','x','y'); df=inline('[2+1/x -2*y; 2*x-y-1 -x]','x','y'); x=[1 1]; for i=1:6b=f(x(1),x(2));B=df(x(1),x(2));dx=-B\b;err=norm(dx,'inf')x=x+dx‘ end计算实例例. 用 Newton 法求方程 在 附近的实根021-0.111111.88888888888888888888888888888897.2702 e-02-9.4373 e-0321.87945156695156695156695156695165.0385 e-04-6.6322 e-0531.87938524483667114597854490456462.4801 e-08-3.2649 e-0941.87938524157181677601982169020616.0099 e-17-7.9116 e-1851.87938524157181676810821855464953.5291 e-34-4.6459 e-35迭代格式:最大位移量在x = 201 cm 处, y = -0.11 cmxy例. 性分布的载荷下, 梁的变形 yw0 = 1.75 kN/cm, E = 50,000 kN/cm2, I = 30,000 cm4, L = 450 cm. 例求函数 的正实根 精度要求：Ø初值取为10,计算 的是单根；迭代6 次.Ø初值取为0,计算 的是重根；迭代 22次.用Matlab画图，查看根的分布情形例. 的零点x=1的重数为2,比较用 经典的Newton迭代格式和修正的Newton迭代格式的结果.function y= ff(var ) y = var^3 - 3*var - 1; return;%% fzero(‘ff’,1);fzero:先用三对数据做二次反插值(inverse quadratic interpolation)求出穿过x轴的 ;如果 这三点不能明显分开,用割线法求 ;如果 和 都不在原始有根区间中,则用二分法.Matlab 函数:fzero(),fmin() roots() fsolve()function f=nls(x)f(1)=2*x(1)-x(2)^2+log(x(1));f(2)=x(1)^2-x(1)*x(2)-x(1)+1;>>x0=[1 1];>>alpha=fsolve(‘nls’,x0);#include #include #include #define TRUE 1 void main() { int it_limit, it; float a, b, c, epsilon, Y_a, Y_b, Y_c; float fun_f();printf( “Lower bound: a ? “); scanf( “%f“, printf( “Upper bound: c ? “); scanf( “%f“, epsilon=1e-8;it_limit=100;it = 0;Y_a = fun_f( a ); Y_c = fun_f( c );if( Y_a*Y_c > 0 ) { printf( “ f(a)f(c) > 0, break. \n“ );exit(0);} else { while( TRUE ) { it = it + 1; b = (a + c)/2; Y_b = fun_f( b );if( it > it_limit ) break;if( fabs( b - a ) it_limit ) printf( “Iteration limit exceeded.\n“ );printf( “Final result: Approximate root = %g \n“, b );} } float fun_f(x) /* Definition of Function */ float x; { float f; f = x*x*x - 3*x*x - x + 3; return( f ); 作业:1. 用二分法求解[实验目的]掌握二分法,理解其特点.2. 用不同形式的Newton法求解假设不知道Newton法的收敛阶,如何用数值实验估计?[实验目的]掌握Newton法,对重根的处理,收敛阶的估计.3. 用Newton法解非线性方程组[实验目的]掌握非线性方程组的数值解法,内迭代要求解线性代数方程组 .4. 用Newton法解复数方程在平面上把收敛到不同根的初始值分别标上不同颜色.[实验目的]了解Newton法收敛域的结构和其局部收敛性.Hamming’s Motto“The purpose of computing is insight, not number.”。