第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 对分法算法原理直接取区间[a,b]的中点x=(a+b)/2作为问题的近似解，那么我们可以估计出绝对误差限仅为区间长的一半，即e=(b-a)/2。
如果这个结果能满足精度要求，我们就停止进一步的计算；如果不能，就求出f(x),结果只能是下面三种情况之一：
f(a)·f(x)<0，此时我们有x*∈[a,x]；
f(x)·f(a)<0，此时我们有x*∈[x,b]；
f(x)=0，此时x即为问题的精确解。
上面第三种情况一般不会发生,可以不予考虑，在前两种情况下，我们可以用x分别替换原问题中的b或a,从而把求解的区间减小了一半。这样我们又可以取新区间[a,b]的中点。
反复进行上述操作即可得到满足任意精度要求的近似解。事实上，经过N次迭代后，剩下的区间长为(b-a)/2N.这也是结果的绝对误差限。
算法说明
STEP 0
输入a,b,det,eps
y0=f(a)
STEP 1
x=(a+b)/2,y=f(x)
STEP 2
判断：(b-a)/2<det否若是，goto step 4
否则，执行下一步
STEP 3
若y.y0>0,则a=x,
否则 b=x.
goto step 1
STEP 4
输出x,y,停机
3.算法评价算法简单，使用范围很广；
如果不考虑求函数值f(x)的计算，数值稳定性很好；
应该说，收敛速度还是很快的。
如果用计算器来计算，会感觉的收敛速度较慢；
4.利用计算器计算的表格形式如果我们在计算器上利用对分法来求函数的零点，我们建议采用如下的表格形式来计算：
k
A[k]
B[k]
X[k]
y(k)
R[k]
0
1
…
…
…
…
…
…
N
§2 牛顿法牛顿法对问题的条件有较高的要求：如果是求f(x)的零点，那么要求f(x)是连续，单调，可微的凸函数。
凸函数的定义定义：设f(x)是定义在 [a,b]上的实函数，如果对任意x1,x2∈[a,b]以及任意0≤λ≤1，均有
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]上的凸函数。
问题的提法设f(x)是定义在闭区间[a,b]上的二次连续可微函数，且
f(a)·f(b)<0
f'(x)≠0,对所有的x∈(a,b)
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]上的凸函。
3.算法原理分析牛顿法的核心思想是利用曲线上某个初始点x0处的切线与X轴的交点作为曲线与X轴的交点的近似值。在一般情况下这样处理会产生一些问题，如果f(x)是单调凸函数，而且f(x0)>0,效果非常好。
假如x*为f(x)的零点，x0为任意初始点，满足f(x0)>0，x1为x0处的切线与x轴的交点，它们之间有什么关系呢？
通过画草图我们可以看出，无论是x 0>x*,还是x0<x*,只要f(x0)>0，x0处切线的零点x1总是比x0更靠近x*,从而可以形成一个算法。
点斜式方程的解（复习）
问题：设f(x)为任意的连续可为函数，对任意给定的x 0,试求曲线y=f(x)在x0处的切线与x轴的交点。
只要大家稍微动动手，即可求得切线与x轴的交点x1为
x1=x0-f(x0)/f/(x0)
当然，我么也可以把f(x)在x0处一阶泰勒展开，从而得到f(x)在x0处的线性近似函数，x1也就是这个线性函数的零点。
算法说明
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
…
N
其中Y[K],Z[K]分别存放函数值和导数值，R[K]存放第K次迭代的改进值。
7.算法评价可以证明，牛顿法是收敛的，而且还是单调收敛的，另外，牛顿法还具有二次终结性质，所以是一种理论上很理想的算法；
由于牛顿法所要求解的函数为二次连续可微的单调的凸函数，这是很强的条件，所以使用范围受到限制；
在迭代过程中由于还要计算导数值f/(x),是以实际的计算量比想象的要大一些。
8.一点注释有些教材中给出应用牛顿法的条件是f//(x)不变号，若f//(x)≥0，则说明f(x)就是[a,b]上的凸函数,与我们的讨论是一致的；若f//(x)≤0，此时f(x)是[a,b]上的凹函数，从而-f(x)也就是[a,b]上的凸函数，这对于求函数的零点问题来说完全是相同的。
9.割线法在牛顿法中，如果我们保留第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 不动点算法压缩映像简介定义.设φ(x)是定义在闭区间[a,b]上的实函数，满足下述两个条件：
对任意x∈[a,b],恒有φ(x)∈[a,b]；
存在0<L<1,使得对任意的x1,x2∈[a,b]，恒有
|φ(x2)- φ(x1)|≤L·| x2-x1|
则称φ(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.不动点原理定理.设φ(x)是定义在闭区间[a,b]上的连续函数，满足下述两个条件：
对任意x∈[a,b],恒有φ(x)∈[a,b]；
存在0<L<1,使得对任意的x1,x2∈[a,b]，恒有
|φ(x2)- φ(x1)|≤L·| x2-x1|
则有存在唯一的x*∈[a,b],使得x*=φ(x*);
对任意x0∈[a,b],记xk+1=φ(xk),k=0,1,…，总有xk→x*；
|x*-xk|≤(1-L)-1·| xk+1-xk|；
|x*-xk|≤Lk·(1-L)-1·| x1-x0|；
这就是泛函分析中著名的不动点原理，教材中给出了这证明，很多后继课程中也有这个定理的完整证明，我们目前不作要求。
4.不动点算法问题：求非线性方程x-φ(x)=0在闭区间[a,b]内的解。
条件：φ(x)是闭区间[a,b]上的压缩映像。
方法：利用迭代格式xk+1=φ(xk)求φ(x)的不动点。
算法说明如下：
step 0:输入x0,eps
step 1:x1=φ(x0)
step 2:判断|x1-x0|<eps否？
若是，goto step 4
否则，执行下一步
step 3,x0=x1,goto step 1
step 4:输出x0,x1,停机结论：不动点算法是很简单的。
不动点方法的表格形式假如我们求f(x)=0在[a,b]内的解，并且利用数学方法得到了与f(x)=0同解的方程x=T(x),其中T(x)是[a,b]上的压缩映像。那么我们可以按下面的表格进行计算。
K
X[K]
Y[K]
R[K]
0
1
…
N
其中Y[K]用于存放第K次的f(x)的值。
6.不动点方法举例：最基本的方法问题：求f(x)=0在[a,b]内的解。
条件：在[a,b]内0<m≤f/(x)≤M
格式：T(x)=x-f(x)/(m+M)
例：设f(x)=x3-7,求f(x)=0在[1,3]内的解。
解：f/(x)=3x2,所以在区间[1,3]内，我们有
3≤f/(x) ≤27
取λ=1/(3+27)=1/30,令T(x)=x-λf(x),则有
x=T(x)与f(x)=0同解。
T(x)是[1,3]上的压缩映像。
从而问题得到解决。
7.不动点方法讨论对于求函数的零点问题来说，在许多情况下，我们可根据实际问题的数学形式把它转化为求不动点的问题，从而可用简单的跌代方法来求解。
在许多情况下，我们可以根据f(x)的具体形式，采用具体的办法把求解f(x)=0的问题转化为求不动点问题，成功的关键还是要把方程的根所在的区间尽可能估计得小一些。
注意到指数函数，次数大于1式的幂函数得到数值通常都大于1，我们可以通过取反函数得到有效的压缩映像；正弦函数和余弦函数的导数都不超过1，所以也比较容易处理。
不动点算法主要是用于一些特别场合，特别是求微分方程数值解，实际问题本身就给出了很好的迭代格式。
8.不动点算法的几何解释注意到求方程x=T(x)的解就是求曲线y=T(x)和直线y=x的交点，利用这种几何特征，我们不难得到各种形式的加速迭代法。
与牛顿法类似，我们也可以求y=T(x)的切线与y=x的交点作为下一个近似解，也可以求y=T(x)的割线与y=x的交点作为下一个近似解等等。明白这个道理，大家也可以搞出加速算法。没有什么了不起的。
关于不动点算法的几何解释可以阅读p20-p21
关于迭代过程的加速方法可以阅读p29-30
埃特金加速算法可以阅读p30-31
学习本章的基本要求三种方法的算法原理，使用条件，迭代格式；
会用计算器按要求的表格形式计算；
在此基础上比较三种方各自的法优缺点；
能理解割线法和加速收敛方法的几何背景；
还有能力，可研究一下牛顿法的收敛速率和不动点原理的证明。
从几何图形看，函数f(x)的零点就是曲线y=f(x)与x轴的交点。这个事实对我们求数值解很有启发作用。
提示：函数f(x)的零点其实也就是（非线性）方程f(x)=0的解，所以求函数的零点问题也就是非线性方程求解的问题。
结论：由高等数学中的界值定理可知，若f(a)·f(b)<0,方程f(x)=0在[a,b]内一定有解。
求函数零点的方法有：对分法，牛顿法和不动点算法。
2.1 对分法算法原理直接取区间[a,b]的中点x=(a+b)/2作为问题的近似解，那么我们可以估计出绝对误差限仅为区间长的一半，即e=(b-a)/2。
如果这个结果能满足精度要求，我们就停止进一步的计算；如果不能，就求出f(x),结果只能是下面三种情况之一：
f(a)·f(x)<0，此时我们有x*∈[a,x]；
f(x)·f(a)<0，此时我们有x*∈[x,b]；
f(x)=0，此时x即为问题的精确解。
上面第三种情况一般不会发生,可以不予考虑，在前两种情况下，我们可以用x分别替换原问题中的b或a,从而把求解的区间减小了一半。这样我们又可以取新区间[a,b]的中点。
反复进行上述操作即可得到满足任意精度要求的近似解。事实上，经过N次迭代后，剩下的区间长为(b-a)/2N.这也是结果的绝对误差限。
算法说明
STEP 0
输入a,b,det,eps
y0=f(a)
STEP 1
x=(a+b)/2,y=f(x)
STEP 2
判断：(b-a)/2<det否若是，goto step 4
否则，执行下一步
STEP 3
若y.y0>0,则a=x,
否则 b=x.
goto step 1
STEP 4
输出x,y,停机
3.算法评价算法简单，使用范围很广；
如果不考虑求函数值f(x)的计算，数值稳定性很好；
应该说，收敛速度还是很快的。
如果用计算器来计算，会感觉的收敛速度较慢；
4.利用计算器计算的表格形式如果我们在计算器上利用对分法来求函数的零点，我们建议采用如下的表格形式来计算：
k
A[k]
B[k]
X[k]
y(k)
R[k]
0
1
…
…
…
…
…
…
N
§2 牛顿法牛顿法对问题的条件有较高的要求：如果是求f(x)的零点，那么要求f(x)是连续，单调，可微的凸函数。
凸函数的定义定义：设f(x)是定义在 [a,b]上的实函数，如果对任意x1,x2∈[a,b]以及任意0≤λ≤1，均有
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]上的凸函数。
问题的提法设f(x)是定义在闭区间[a,b]上的二次连续可微函数，且
f(a)·f(b)<0
f'(x)≠0,对所有的x∈(a,b)
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]上的凸函。
3.算法原理分析牛顿法的核心思想是利用曲线上某个初始点x0处的切线与X轴的交点作为曲线与X轴的交点的近似值。在一般情况下这样处理会产生一些问题，如果f(x)是单调凸函数，而且f(x0)>0,效果非常好。
假如x*为f(x)的零点，x0为任意初始点，满足f(x0)>0，x1为x0处的切线与x轴的交点，它们之间有什么关系呢？
通过画草图我们可以看出，无论是x 0>x*,还是x0<x*,只要f(x0)>0，x0处切线的零点x1总是比x0更靠近x*,从而可以形成一个算法。
点斜式方程的解（复习）
问题：设f(x)为任意的连续可为函数，对任意给定的x 0,试求曲线y=f(x)在x0处的切线与x轴的交点。
只要大家稍微动动手，即可求得切线与x轴的交点x1为
x1=x0-f(x0)/f/(x0)
当然，我么也可以把f(x)在x0处一阶泰勒展开，从而得到f(x)在x0处的线性近似函数，x1也就是这个线性函数的零点。
算法说明
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
…
N
其中Y[K],Z[K]分别存放函数值和导数值，R[K]存放第K次迭代的改进值。
7.算法评价可以证明，牛顿法是收敛的，而且还是单调收敛的，另外，牛顿法还具有二次终结性质，所以是一种理论上很理想的算法；
由于牛顿法所要求解的函数为二次连续可微的单调的凸函数，这是很强的条件，所以使用范围受到限制；
在迭代过程中由于还要计算导数值f/(x),是以实际的计算量比想象的要大一些。
8.一点注释有些教材中给出应用牛顿法的条件是f//(x)不变号，若f//(x)≥0，则说明f(x)就是[a,b]上的凸函数,与我们的讨论是一致的；若f//(x)≤0，此时f(x)是[a,b]上的凹函数，从而-f(x)也就是[a,b]上的凸函数，这对于求函数的零点问题来说完全是相同的。
9.割线法在牛顿法中，如果我们保留第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 不动点算法压缩映像简介定义.设φ(x)是定义在闭区间[a,b]上的实函数，满足下述两个条件：
对任意x∈[a,b],恒有φ(x)∈[a,b]；
存在0<L<1,使得对任意的x1,x2∈[a,b]，恒有
|φ(x2)- φ(x1)|≤L·| x2-x1|
则称φ(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.不动点原理定理.设φ(x)是定义在闭区间[a,b]上的连续函数，满足下述两个条件：
对任意x∈[a,b],恒有φ(x)∈[a,b]；
存在0<L<1,使得对任意的x1,x2∈[a,b]，恒有
|φ(x2)- φ(x1)|≤L·| x2-x1|
则有存在唯一的x*∈[a,b],使得x*=φ(x*);
对任意x0∈[a,b],记xk+1=φ(xk),k=0,1,…，总有xk→x*；
|x*-xk|≤(1-L)-1·| xk+1-xk|；
|x*-xk|≤Lk·(1-L)-1·| x1-x0|；
这就是泛函分析中著名的不动点原理，教材中给出了这证明，很多后继课程中也有这个定理的完整证明，我们目前不作要求。
4.不动点算法问题：求非线性方程x-φ(x)=0在闭区间[a,b]内的解。
条件：φ(x)是闭区间[a,b]上的压缩映像。
方法：利用迭代格式xk+1=φ(xk)求φ(x)的不动点。
算法说明如下：
step 0:输入x0,eps
step 1:x1=φ(x0)
step 2:判断|x1-x0|<eps否？
若是，goto step 4
否则，执行下一步
step 3,x0=x1,goto step 1
step 4:输出x0,x1,停机结论：不动点算法是很简单的。
不动点方法的表格形式假如我们求f(x)=0在[a,b]内的解，并且利用数学方法得到了与f(x)=0同解的方程x=T(x),其中T(x)是[a,b]上的压缩映像。那么我们可以按下面的表格进行计算。
K
X[K]
Y[K]
R[K]
0
1
…
N
其中Y[K]用于存放第K次的f(x)的值。
6.不动点方法举例：最基本的方法问题：求f(x)=0在[a,b]内的解。
条件：在[a,b]内0<m≤f/(x)≤M
格式：T(x)=x-f(x)/(m+M)
例：设f(x)=x3-7,求f(x)=0在[1,3]内的解。
解：f/(x)=3x2,所以在区间[1,3]内，我们有
3≤f/(x) ≤27
取λ=1/(3+27)=1/30,令T(x)=x-λf(x),则有
x=T(x)与f(x)=0同解。
T(x)是[1,3]上的压缩映像。
从而问题得到解决。
7.不动点方法讨论对于求函数的零点问题来说，在许多情况下，我们可根据实际问题的数学形式把它转化为求不动点的问题，从而可用简单的跌代方法来求解。
在许多情况下，我们可以根据f(x)的具体形式，采用具体的办法把求解f(x)=0的问题转化为求不动点问题，成功的关键还是要把方程的根所在的区间尽可能估计得小一些。
注意到指数函数，次数大于1式的幂函数得到数值通常都大于1，我们可以通过取反函数得到有效的压缩映像；正弦函数和余弦函数的导数都不超过1，所以也比较容易处理。
不动点算法主要是用于一些特别场合，特别是求微分方程数值解，实际问题本身就给出了很好的迭代格式。
8.不动点算法的几何解释注意到求方程x=T(x)的解就是求曲线y=T(x)和直线y=x的交点，利用这种几何特征，我们不难得到各种形式的加速迭代法。
与牛顿法类似，我们也可以求y=T(x)的切线与y=x的交点作为下一个近似解，也可以求y=T(x)的割线与y=x的交点作为下一个近似解等等。明白这个道理，大家也可以搞出加速算法。没有什么了不起的。
关于不动点算法的几何解释可以阅读p20-p21
关于迭代过程的加速方法可以阅读p29-30
埃特金加速算法可以阅读p30-31
学习本章的基本要求三种方法的算法原理，使用条件，迭代格式；
会用计算器按要求的表格形式计算；
在此基础上比较三种方各自的法优缺点；
能理解割线法和加速收敛方法的几何背景；
还有能力，可研究一下牛顿法的收敛速率和不动点原理的证明。
