非线性方程求根.ppt

1、非线性方程求根,何国良 ,数学科学学院,参考文献,1李庆扬 关治 白峰杉, 数值计算原理(清华) 2蔡大用 白峰杉, 现代科学计算 3 李庆扬 等, 数值分析 4Numerical Analysis (Seventh Edition) 数值分析 （第七版 影印版） 5David Kincaid,数值分析(第三版) 6 John H. Mathews,数值方法(MATLAB版),模型误差: 建立数学模型时所引起的误差；,误差分类：,舍入误差:计算机表示的数的位数有限，通常用四舍五入的办法取近似值，由此引起的误差.,截断误差:求解数学模型时，用简单代替复杂,或者用有限过程代替无限过程所引起的误差,

2、观测误差:测量工具的限制或在数据的获取时随机因素所引起的物理量的误差；,数值计算中的一些基本概念,假设某一数据的准确值为 x*,其近似值 为 x，则称,而称,为 x 的相对误差,误差的有关概念,e(x)= x - x* 为 x 的绝对误差。,避免绝对值小的数作除数,这一原则主要指尽量避免除数绝对值远远小于被除数绝对值的除法。,设 （ x0），如果 x 的绝对值远小于 y 的绝对值，由于,二、数值计算中的一些基本原则,避免两个相近的数据相减,如果 y x，现分析两个数的近似数作减法所得结果的误差. 设 z= y x，则利用误差估计,有相对误差估计,当 y x 时，有 z0，计算结果的相对误差限可

3、能很大，导致数值计算结果的有效数字位数减少。,要防止大数“吃掉”小数,一个绝对值很大的数和一个绝对值很小的数直接相加时，很可能发生所谓“大数吃小数”的现象。,例如，a= 1013，b= 4，设想这两个数在具有12位浮点数计算机系统（12位有效位数系）中相加,a + b= 1013 + 4=1. 0000000000000 1013,+0. 0000000000004 1013,实际加法操作如下,尽量减少计算工作量,在考虑算法时应注意简化计算步骤，减少运算次数 。,计算工作量小的算法不仅节约运行时间，而且使误差积累小。,算法一： S 0= a0 ， Sk= Sk1 + ak xk ，（ k= 1

4、，2，n ） Pn（x）= Sn,例2 设计算法用于计算多项式,计算一个 n 次多项值需要用 2n 次乘法。,尽量减少计算工作量,算法二： Sn= an， Sk1= a k 1+ xSk，（k= n，n1，1）， Pn（x）= S0,另一种典型算法是秦九韶算法,计算一个 n 次多项值需要用 n 次乘法。,选用数值稳定性好的算法,不同的算法在执行过程中对数据误差的影响是不一样的。舍入误差对计算结果影响不大的算法被称为数值稳定的算法.,例3 利用递推式计算定积分 ( n= 0， 1， 2， ， 20 )的值。,得递推关系式,算法一：,其中,利用递推式可得20个数据如下表：,对积分值有估计式：,算法

5、二：,有,由递推公式,由In 的估计式,取,有,利用递推式可得20个数据如下表：,在算法执行过程中,舍入误差对计算结果影响不大的一类算法被称为数值稳定算法;否则称为不稳定算法.,初始误差在算法执行过程中不断减小,这种算法称为数值稳定算法。,结论,一、 非线性方程数值方法,数值方法就是非常实用和有效的方法,在求解非线性方程的方法中，迭代技术是一种常用技术,是利用逐次逼近过程求解非线性方程的一类数值方法。,基本思想,计算机求解分为两步：,第一步，对方程 f（x）= 0的根进行隔离。,第二步，利用迭代法计算满足一定精度的根近似值。,方法：,近似根,xn,二、二分法,定理2.1 设函数f（x）在区间a

6、，b上连续，且 f（a）f（b） 0，则方程f（x）= 0 在区间（a，b）内至少有一个根。,基本思想：,对有根区间a，b逐次分半，直到满足精度要求 。,二分法计算过程中产生区间序列 ak，bk (k= 1，2，3，),显然有,a，b a1，b1 a2，b2 an，bn,有如下性质,（1）bn an= （b a）/ 2n； （2）an+1 an，bn+1 bn ； （3）f（an）f（bn） 0.,当n充分大时,令,定理2.2 设x*为方程f（x）= 0在区间a，b内的唯一根，f（x）满足f（a）f（b） 0，则二分法计算过程中第n个区间an，bn的中点xn满足不等式,证明自己练习,算法(二分

7、法求解非线性方程),第一步：输入误差限0，1，计算 y1 f（a），y2 f（b）；,第二步：计算x0 0.5（a+b），y0f（x0），若 |y0 y1 | 0，则输出x0，结束。否则转第三步；,第三步：若 y0 y1 0，则置b x0，y2 y0；否则a x0，y1 y0，转第四步；,第四步：若|b a|1则转第二步；否则，输出x0结束。,例2.1 用二分法求 在区间0，1内的一个根，要求误差不超过 .,解：令 ,计算得,所以函数 f（x）在区间0,1上确有且只有一个根.,计算结果如下表2.1,取x4= 0.5( 0.4375 + 0.5)= 0.4688 作为x*的近似值,误差不超过1/

8、 25.,牛顿迭代法,Newton迭代格式 Newton迭代法的收敛性 弦截法迭代格式 数值实验题介绍,基本思想：,将方程 f(x)=0中函数 f(x)线性化,以线性方程的解逼近非线性方程的解.,设函数 f(x)在有根区间a,b二次连续可微,则 f(x)在x0处的泰勒展开式为:,只取关于x线性项，有,设 ，其解记为,(*),迭代格式(*)称为牛顿迭代法.,牛顿迭代法的几何意义,牛顿迭代法在单变量情况下又称为切线法.,Newton迭代法的局部收敛性,定理 2.7 设 f(x) 在点x*的某邻域内具有二阶连续导数,且设 f(x*)=0, f (x*) 0, 则对充分靠近点x*的初值x0, Newt

9、on迭代法至少平方收敛.,所以, Newton迭代法至少平方收敛。,例2. 求 f(x)=xex 1= 0 在 x0=0.5 附近的根,解: 迭代格式为,(n = 0, 1, ),f=inline(x*exp(x)-1); f1=inline(x+1)*exp(x); x0=0.5;er=1;k=0; while er0.00001 x=x0-f(x0)/f1(x0); er=abs(x-x0) x0=x;k=k+1 end,x = 0.5671 k=4 er=1.2347e-010,缺陷,1.被零除错误,2.程序死循环,方程: f(x)=x3 3x + 2 = 0 在重根x*=1附近,f(x

10、)近似为零,对 f(x) = arctan x 存在 x0,Newton迭代法陷入死循环,例4 用牛顿迭代法解方程 f（x）= x e x=0.,初值取x0= 2 ，,x1= 4， x2= 5.33333， ， x15= 19.72354943， ,f（x15）=0.0000000536,设x*是方程 f(x)=0 的根, x0和x1是x*附近的两个点.,Newton迭代法的变形弦截法,曲线 y=f(x) 在点(x0, f(x0)和点 (x1,f(x1)处的割线与X轴交点,f(x) = 0 ,( n =1,2, ),f=inline(u.*cosh(50/u)-u-10); a0=120;a=150;k=1; y0=f(a0);y=f(a); while abs(a0-a)0.0001 t=a-y*(a-a0)/(y-y0); a0=a;y0=y; a=t;y=f(a); k=k+1; end,Ans K=6, a=126.6324,f=inline(u.*cosh(50/u)-u-10