第2章:求函数的零点问题 第2章求函数的零点问题 设f(刈)是定义在区间[a,b止上的连麵函数,果X∈[a,b]使 得f(x9)=0则称x是fx)的一个零点。 从几何图形看,函数f(X)的零点就是曲线y=f(x)与x轴的交 点。这个事实对我们求数值解很有启发作用。 提示:函数f(x)的零点其实也就是(非线性)方程f(x)=0的 解,所以求函数的零点问题也就是非线性方程求解的问题。 结论:由高等数学中的界值定理可知,若fa)f(b)<0,方程 f(x)=0在ab]内一定有解。 求函数零点的方法有:对分法,牛顿法和不动点算法 2.1对分法 1.算法原理 直接取区间ab]的中点x=(a+b)/2作为问题的近似解,那么我们可 以估计出绝对误差限仅为区间长的一半,即e=(b-a)/2 如果这个结果能满足精度要求,我们就停止进一步的计算 如果不能,就求出f(刈)结果只能是下面三种情况之 (1)f(a)f(x)<0,此时我们有x∈[a,x]; (2)fx)f(a)<0,此时我们有x∈x,b]
第 2 章：求函数的零点问题 1 第 2 章 求函数的零点问题 设 f(x)是定义在闭区间[a,b]上的连续函数，如果 x *∈[a,b]使 得 f(x0 )=0,则称 x *是 f(x)的一个零点。 从几何图形看，函数 f(x)的零点就是曲线 y=f(x)与 x 轴的交 点。这个事实对我们求数值解很有启发作用。 提示：函数 f(x)的零点其实也就是（非线性）方程 f(x)=0 的 解，所以求函数的零点问题也就是非线性方程求解的问题。 结论：由高等数学中的界值定理可知，若 f(a)·f(b)<0, 方程 f(x)=0 在[a,b]内一定有解。 求函数零点的方法有：对分法，牛顿法和不动点算法。 2.1 对分法 1． 算法原理 直接取区间[a,b]的中点 x=(a+b)/2 作为问题的近似解，那么我们可 以估计出绝对误差限仅为区间长的一半，即 e=(b-a)/2。 如果这个结果能满足精度要求，我们就停止进一步的计算； 如果不能，就求出 f(x),结果只能是下面三种情况之一： (1) f(a)·f(x)<0，此时我们有 x *∈[a,x]； (2) f(x)·f(a)<0，此时我们有 x *∈[x,b]；
第2章:求函数的零点问题 2 (3)f(x)=0,此时ⅹ即为问题的精确解。 上面第三种情况般不会发生可以不予考虑,在前两种情况 下,我们可以用ⅹ分别替换原问题中的b或a,从而把求解的区间 减小了一半。这样我们又可以取新区间[a,b]的中点。 反复进行上述操作即可得到滿任意精度要求的近似解。事 实上,经过N次迭代后,剩下的区间长为ba)2N这也是结果的 绝对误差限 2.算法说明 STEP 0|输入ab, det, eps yO=f(a) STEP1 x=a+b)/2,y=f(x) STEP2判断:(b-a)20则a=x 否则b=x goto step 1 sTFP4输出xy停机 3算法评价
第 2 章：求函数的零点问题 2 (3) f(x)=0，此时 x 即为问题的精确解。 上面第三种情况一般不会发生,可以不予考虑，在前两种情况 下，我们可以用 x 分别替换原问题中的 b 或 a,从而把求解的区间 减小了一半。这样我们又可以取新区间[a,b]的中点。 反复进行上述操作即可得到满足任意精度要求的近似解。事 实上，经过 N 次迭代后，剩下的区间长为(b-a)/2N.这也是结果的 绝对误差限。 2． 算法说明 STEP 0 输入 a,b,det,eps y0=f(a) STEP 1 x=(a+b)/2 ,y=f(x) STEP 2 判断：(b-a)/20,则 a=x, 否则 b=x. goto step 1 STEP 4 输出 x,y,停机 3.算法评价
第2章:求函数的零点问题 算法简单,使用范围很 如果不考虑求函数值f(x)的计算,数值稳定性很好 应该说,收敛速度还是很快的。 如果用计算器来计算,会感觉的收敛速度较慢; 4利用计算器计算的表格形式 如果我们在计算器上利用对分法来求函数的零点,我们建议采用 如下的表格形式来计算 A[k] B[k] X[k] y(k)I RIk k01N §2牛顿法 牛顿法对问题的条件有较高的要求:如果是求f(x)的零点 那么要求f(x)是连续,单调,可微的凸函数。 1.凸函数的定义 定义:设f(x是定义在[ab]上的实函数,如果对任意x,X∈ [a,b]以及任意0≤λ≤1,均有
第 2 章：求函数的零点问题 3 算法简单，使用范围很广； 如果不考虑求函数值 f(x)的计算，数值稳定性很好； 应该说，收敛速度还是很快的。 如果用计算器来计算，会感觉的收敛速度较慢； 4.利用计算器计算的表格形式 如果我们在计算器上利用对分法来求函数的零点，我们建议采用 如下的表格形式来计算： k A[k] B[k] X[k] y(k) R[k] 0 1 … … … … … … N §2 牛顿法 牛顿法对问题的条件有较高的要求：如果是求 f(x)的零点， 那么要求 f(x)是连续，单调，可微的凸函数。 1． 凸函数的定义 定义：设 f(x)是定义在 [a,b]上的实函数，如果对任意 x1,x2∈ [a,b]以及任意 0≤ λ ≤ 1，均有
第2章:求函数的零点问题 fx1+(1-A)x]≤λfx1)+(1-A)f(x2) 则称f(x)是[ab]上的凸函数 提示:如果f(×)是[a,b]上的凸函数,则曲线y=f(x)上任意两 点间的连线上的点都在曲线的上方,也就是“弓在弦下"。 提示:凸函数的另一个重要的几何特征是:过任意点作切线 曲线上的点都在切线的上方。 结论设f(刈)是[a,b]上二次连续可微的实函数如果恒有f"(∞x) ≥0,则f(×)是[ab]上的凸函数。 2.问题的提法 设f()是定义在闭区间[a,b上的二次连续可微函数,且 (1)f(a),f(b)<0 (2)f(x)≠0,对所有的x∈(ab) 3)f"(x)≥0,对所有的X∈(a,b) 试求f(x)=0在ab上的解。 提示:在上述的假设下,条件(1)保证了f(x)=0在[ab]上一定有 解;利用连续性,条件(2)保证了f(×)在[ab]上不变号,从而 得到f(x)是[ab上的单调函数;条件(3)保证了fx×)是ab上的 凸函
第 2 章：求函数的零点问题 4 f[λ x1+(1-λ )x2]≤ λ f(x1)+(1-λ )f(x2) 则称 f(x)是[a,b]上的凸函数。 提示：如果 f(x)是[a,b]上的凸函数，则曲线 y=f(x)上任意两 点间的连线上的点都在曲线的上方，也就是“弓在弦下”。 提示：凸函数的另一个重要的几何特征是：过任意点作切线， 曲线上的点都在切线的上方。 结论：设f(x)是[a,b]上二次连续可微的实函数，如果恒有 f"(x) ≥ 0, 则 f(x)是[a,b]上的凸函数。 2． 问题的提法 设 f(x)是定义在闭区间[a,b]上的二次连续可微函数，且 (1) f(a)·f(b)<0 (2) f'(x)≠ 0 ,对所有的 x∈(a,b) (3) f"(x)≥ 0,对所有的 x∈(a,b) 试求 f(x)=0 在[a,b]上的解。 提示：在上述的假设下，条件（1）保证了 f(x)=0 在[a,b]上一定有 解；利用连续性，条件（2）保证了 f'(x)在[a,b]上不变号，从而 得到 f(x)是[a,b]上的单调函数；条件（3）保证了 f(x)是[a,b]上的 凸函
第2章:求函数的零点问题 3算法原理分析 牛顿法的核心思想是利用曲线上某个初始点X0处的切线与Ⅹ 轴的交点作为曲线与X轴的交点的近似值。在一般情况下这样处 理会产生一些问题,如果f()是单调凸函数,而且f(xo)>0,刘果 非常好 假如x为f(x)的零点,x为任意初始点,满足f(Xo)>0,X 为Ⅺo处的切线与ⅹ轴的交点,它们之间有什么关系呢 通过画草图我们可以看出,无论是Xo>X还是X0,X处切线的零点X1总是比更靠近X从而可以形成 个算法 4.点斜式方程的解(复习) 问题:设f(x)为任意的连续可为函数,对任意给定的X0试求 曲线y=f(x)在xo处的切线与X轴的交点 只要大家稍微动动手,即可求得切线与ⅹ轴的交点Ⅺ1为 1=X0-f(×0)/f(xo) 当然,我么也可以把f(x在Ⅺ处阶泰勒展开,从而得到fX)在 X0处的线性近似函数,x1也就是这个线性函数的零点。 5.算法说明
第 2 章：求函数的零点问题 5 3.算法原理分析 牛顿法的核心思想是利用曲线上某个初始点x0处的切线与X 轴的交点作为曲线与 X 轴的交点的近似值。在一般情况下这样处 理会产生一些问题，如果 f(x)是单调凸函数，而且 f(x0)>0,效果 非常好。 假如 x *为 f(x)的零点，x0为任意初始点，满足 f(x0)>0，x1 为 x0处的切线与 x 轴的交点，它们之间有什么关系呢？ 通过画草图我们可以看出，无论是 x0>x* ,还是 x00，x0处切线的零点 x1总是比 x0更靠近 x * ,从而可以形成一 个算法。 4． 点斜式方程的解（复习） 问题：设 f(x)为任意的连续可为函数，对任意给定的 x0,试求 曲线 y=f(x)在 x0处的切线与 x 轴的交点。 只要大家稍微动动手，即可求得切线与 x 轴的交点 x1为 x1=x0-f(x0)/f / (x0) 当然，我么也可以把 f(x)在 x0处一阶泰勒展开，从而得到 f(x)在 x0处的线性近似函数，x1也就是这个线性函数的零点。 5． 算法说明
第2章:求函数的零点问题 step1:输入a,b,eps 若f(a)>0则x0=a 否则,X0=b yo=fxo),Z0=f(×o) step 2 X1=Xo-yo/zo y1=f(x1) step3判断y<eps否? 若是, goto step5 否则,执行下一步 step 4 0=x1 yo=y1, Zo=f/(Xo) goto step 2 step5输出Ⅺy停机 6利用计算器计算的表格形式 如果我们在计算器上利用牛顿去来求函数的零点,我们建议 采用如下的表格形式来计算 kXIk]kY[k]Z[k]R[k] 1
第 2 章：求函数的零点问题 6 step 1: 输入 a,b,eps 若 f(a)>0,则 x0=a 否则， x0=b y0=f(x0)，z0= f’(x0) step 2 x1=x0-y0/z0 y1=f(x1) step 3 判断 y1<eps 否？ 若是，goto step 5 否则，执行下一步 step 4 x0=x1,y0=y1,z0= f / (x0) goto step 2 step 5 输出 x1,y1,停机 6.利用计算器计算的表格形式 如果我们在计算器上利用牛顿法来求函数的零点，我们建议 采用如下的表格形式来计算： k X[k]k Y[k] Z[k] R[k] 0 1
第2章:求函数的零点问题 7 N 其中YK],zK分别存放函数值和导数值,RK存放第K次迭代 的改进值。 7算法评价 (1)可以证明,牛顿法是收敛的,而且还是单调收敛的,另外, 牛顿法还具有二次终结性质,所以是种理论上很理想的 算法 (2)由于牛顿法去所要求解的函数为二次连续可微的单调的凸函 数,这是很强的条件,所以使用范围受到限制; (3)在迭代过程中由于还要计算导数值f∞,是以实际的计算 量比想象的要大一些 8.一点注释 有些教材中给出应用牛顿法的条件是f(x)不变号,若(x) ≥0,则说明f(x)就是ab止上的凸函数与我们的讨论是一致的 若f(x)≤0,此时f(x)是[ab上的凹函数,从而fx)也就是[ab 上的凸函数,这对于求函数的零点问题来说完全是相同的 9割线法
第 2 章：求函数的零点问题 7 … N 其中 Y[K],Z[K]分别存放函数值和导数值，R[K]存放第 K 次迭代 的改进值。 7.算法评价 (1) 可以证明，牛顿法是收敛的，而且还是单调收敛的，另外， 牛顿法还具有二次终结性质，所以是一种理论上很理想的 算法； (2) 由于牛顿法所要求解的函数为二次连续可微的单调的凸函 数，这是很强的条件，所以使用范围受到限制； (3) 在迭代过程中由于还要计算导数值 f / (x),是以实际的计算 量比想象的要大一些。 8.一点注释 有些教材中给出应用牛顿法的条件是 f //(x)不变号，若 f //(x) ≥ 0，则说明 f(x)就是[a,b]上的凸函数,与我们的讨论是一致的； 若 f //(x)≤ 0，此时 f(x)是[a,b]上的凹函数，从而-f(x)也就是[a,b] 上的凸函数，这对于求函数的零点问题来说完全是相同的。 9.割线法
第2章:求函数的零点问题 在牛顿法中,如果我们保留第k-1次和第k次的计算结果ⅹk-1 f(xk-1);Ⅺk,f(xk),那么我们可用过这两点的弦(割线)的斜率 p=[f(xk)-f(xk-1)1/(xk-Xk-1) 近似替代fx×)在ⅹ处的导数fxx)从而有 Xx+1=Xk-f(x x)/pk 由此不难形成一个算法,而且每一步的计算量差不多只是牛顿 法的一半。 牛顿法还有其它一些变化形式,在特定的情况下也许有效,僬我 们只要理解了牛顿法的原理和上面的割线法的原理,自己也可以 灵活应用牛顿法,但是所有这些方法在理论上却没有二次终结性 质。 23不动点算法 1.压缩映像简介 定义设q(x是定义在闭区间[ab上的实函数,满足下述两 个条件 (1)对任意X∈a,b恒有φ(x)∈[a,b] (2)存在0<L<1使得对任意的x1∈[a,b],恒有 (X2)-q(x)≤Lx2-×x1
第 2 章：求函数的零点问题 8 在牛顿法中，如果我们保留第 k-1 次和第 k 次的计算结果 xk-1， f(xk-1)；xk，f(xk)，那么我们可用过这两点的弦（割线）的斜率 pk=[f(xk)-f(xk-1)]/(xk-xk-1) 近似替代 f(x)在 xk 处的导数 f /(xk),从而有： xk+1=xk-f(xk)/pk 由此不难形成一个算法，而且每一步的计算量差不多只是牛顿 法的一半。 牛顿法还有其它一些变化形式，在特定的情况下也许有效，但我 们只要理解了牛顿法的原理和上面的割线法的原理，自己也可以 灵活应用牛顿法，但是所有这些方法在理论上却没有二次终结性 质。 2.3 不动点算法 1． 压缩映像简介 定义.设φ (x)是定义在闭区间[a,b]上的实函数，满足下述两 个条件： (1) 对任意 x∈[a,b],恒有φ (x)∈[a,b]； (2) 存在 0<L<1,使得对任意的 x1,x2∈[a,b]，恒有 |φ (x2)- φ (x1)|≤ L·| x2-x1|
第2章:求函数的零点问题 则称φ(刈)是闭区间[ab]上的个压缩映像 注释提示:一般地,设A,B是两个集合,定义在A上取值于 B中的函数y=f(×)称为是由A到B的映像,X∈A称为源像点 y=fx.称为是x的像点 提示:y=φ(x)是闭区间[ab]上的一个压缩映像表明,φ(X) 的定义域和值域相同,任意两个像点间的距离都小于源像点间的 距离。 2.判定压缩映像的充分条件 为了方便地利用不动点算法求函数的零点,我们首先给出 个判定压缩映像的充分条件定理。 定理设φ(x)是定义在闭区间[ab]上的连绩可微的实函数,满足定 下述两个条件 (1)对任意X∈ab]恒有φ(x)∈ab] (2)存在0<L<1使得对任意的x∈[a,b],恒有 (×)≤L 则φ(×是闭区间[ab]上的一个压缩映像 提示:利用微分学的 Lagrangian中值公式可以立即证明。 3不动点原理
第 2 章：求函数的零点问题 9 则称φ (x)是闭区间[a,b]上的一个压缩映像。 注释提示：一般地，设 A,B 是两个集合，定义在 A 上取值于 B 中的函数 y=f(x)称为是由 A 到 B 的映像，x∈A 称为源像点， y=f(x)称为是 x 的像点。 提示：y=φ (x) 是闭区间[a,b]上的一个压缩映像表明，φ (x) 的定义域和值域相同，任意两个像点间的距离都小于源像点间的 距离。 2. 判定压缩映像的充分条件 为了方便地利用不动点算法求函数的零点，我们首先给出一 个判定压缩映像的充分条件定理。 定理 设φ (x)是定义在闭区间[a,b]上的连续可微的实函数，满足 下述两个条件： （1）对任意 x∈[a,b],恒有φ (x)∈[a,b]； （2）存在 0<L<1,使得对任意的 x∈[a,b]，恒有 |φ ’(x))|≤ L 则φ (x)是闭区间[a,b]上的一个压缩映像。 提示：利用微分学的 Lagrangian 中值公式可以立即证明。 3.不动点原理
第2章:求函数的零点问题 定理设φ、)是定义在闭区间[ab]上的连续函数,满足下述两个 条件 (1)对任意X∈a,b恒有φ(x)∈[a,b] (2)存在0<L<1使得对任意的ⅪⅪ2∈[a,b],恒有 (x2)-q(x)≤Lx2-×x1 则有 (1)存在唯的x∈ab]使得x=φ(X (2)对任意X∈ab]记xk+1=q(X)k=01,…总有X→x (3)x-Xk(1-)1Xk+1-X4 (4)x-x≤L(1-L)-4x1-Xo 这就是泛函分析中著名的不动点原理,教材中给出了这证 明,很多后继课程中也有这个定理的完整证明,我们目前不作要 求。 4不动点算法 问题:求非线性方程x-φ(x)=0在闭区间[a,b内的解。 条件:φ(刈)是闭区间ab]上的压缩映像 方法:利用迭代格式X1=9求的不动点 算法说明如下
第 2 章：求函数的零点问题 10 定理.设φ (x)是定义在闭区间[a,b]上的连续函数，满足下述两个 条件： (1) 对任意 x∈[a,b],恒有φ (x)∈[a,b]； (2) 存在 0<L<1,使得对任意的 x1,x2∈[a,b]，恒有 |φ (x2)- φ (x1)|≤ L·| x2-x1| 则有 (1) 存在唯一的 x *∈[a,b],使得 x *=φ (x* ); (2) 对任意 x0∈[a,b],记 xk+1=φ (xk),k=0,1,…，总有 xk→x *； (3) |x*-xk|≤ (1-L)-1 ·| xk+1-xk|； (4) |x*-xk|≤ L k ·(1-L)-1 ·| x1-x0|； 这就是泛函分析中著名的不动点原理，教材中给出了这证 明，很多后继课程中也有这个定理的完整证明，我们目前不作要 求。 4.不动点算法 问题：求非线性方程 x-φ (x)=0 在闭区间[a,b]内的解。 条件：φ (x)是闭区间[a,b]上的压缩映像。 方法：利用迭代格式 xk+1=φ (xk)求φ (x)的不动点。 算法说明如下：