计算方法2方程求根

12学习要点方程求根的三个问题：根的存在性、根的分布、根的精确化；二分法：将有根区间二分，根据函数的符号变化逐步缩短有根区间；迭代法：将方程等价转化为另一种形式，并构造迭代公式；牛顿迭代法与割线法；32.1问题的提出

函数方程f（x）=0若f(x)不是x的线性函数,则称为非线性方程

,特别地若f(x)是n次多项式，则称为n次多项式方程或代数方程；若f(x)是超越函数，则称为超越方程。如果函数f（x）=（x-x*）m

g(x)且g(x*)

0,则称x*是

(x)的m重零点或

(x)=0的m重根。当m=1时，称x*是

(x)的单根或单零点。4理论上已证明:对于次数n<=4的多项式方程，它的根可以用公式表示;而次数大于5的多项式方程，它的根一般不能用解析表达式表示;因此对于f(x)=0的函数方程，只要得到满足精度要求的根的近似值就可以了。常用的求根方法分为区间法和迭代法两大类。5数值求根问题包括：根的存在性根的范围根的精确化6根的存在定理：

假设函数y=f(x)，

xa,b

，且f(a)·f(b)<0，函数图象如图则至少存在一点xa,b

使得

f(x)=0，这就是根的存在定理。yxba7第一步：求根的隔离区间。确定根所在的区间，使方程在这个小区间内有且仅有一个根，这就是根的隔离过程。所得小区间称为方程的根的隔离区间或有根区间。第二步：将根精确化。已知一个根的近似值后，再用一种方法将此近似值精确化，使其满足给定的精度要求。通常分两步来求根8三种方法来求根的隔离区间

作图法

方程等价变换法

搜索法

9例1的有根区间10例2求

的有根区间112.2二分法二分法是求方程近似根的方法中，最直观、最简单的一种方法给定方程f(x)=0，设f(x)在区间[a,b]连续，严格单调，且

f(a)·

f(b)<0，则[a,b]为f(x)=0的一个有根区间。基本思想：用对分区间的方法根据分点处函数f(x)值的符号逐步将有根区间缩小，使在足够小的区间内，方程有且仅有一个根12记a0=a,b0=b。用中点x0=(a0+b0)/2将区间[a0,b0]分成2个小区间：[a0,x0]和[x0,b0]；计算f(x0)，若f(x0)=0，则x0为f(x0)=0的根，计算结束。否则f(a0)f(x0)<0与f(x0)f(b0)<0两式中有且仅有一式成立。若f(a0)f(x0)<0，令a1=a0，b1=x0，若f(x0)f(b0)<0，令a1=x0，b1=b0；于是[a1,b1]为新的有根区间，[a0,b0]

[a1,b1]，且后者长度为前者的一半。具体方法：13对新的有根区间[a1,b1]施行同样的手续，于是得到一系列有根区间[a0,b0]

[a1,b1]

[a2,b2]

……

[ak,bk]其中每一个区间的长度都是前一个区间长度的一半，最后一个区间的长度为bk-ak=（b-a）/2k如果取最后一个区间[ak,bk]的中点xk=(ak+bk)/2作为f(x)=0根的近似值，则有误差估计式 |xk-x*|≤(bk-ak)/2=（b-a）/2k+114abb1a1x015例3

用二分法求方程

在区间[0,1]内的1个实根，要求有3位有效数字。16计算结果kak(f(ak)的符号)xk(f(xk)的符号)bk(f(bk)的符号)00(+)0.5(-)1(-)10(+)0.25(+)0.5(-)20.25(+)0.375(+)0.5(-)30.375(+)0.4375(+)0.5(-)40.4375(+)0.46875(+)0.5(-)50.4375(+)0.453125(-)0.46875(+)60.4375(+)0.4453125(-)0.453125(-)70.4375(+)0.44140625(+)0.4453125(-)80.44140625(+)0.443359375(+)0.4453125(-)90.443359375(+)0.444335937(+)0.4453125(-)100.444335937(+)0.444824218(+)0.444335937(+)17二分法的优点与缺点优点：计算简单，方法可靠缺点：不能求偶数重根；不能求复根；收敛速度慢182.3简单迭代法一迭代格式的构造及其敛散性条件：已知方程

f(x)=0在区间[a,b]内有1个根x*。在区间[a,b]将其改写成同解方程 x=φ(x)

迭代函数迭代法是数值计算中的一种典型方法，不仅用于方程求根，而且用于方程组求解、矩阵求特征值等方面19取x0∈[a,b]，用递推公式xk+1=φ(xk)k=0,1,2,…… 可得到序列x0,x1,x2……。如果k→∞,序列{xk}有极限x*,且φ(x）在x*附近连续，则对上式两边取极限，得x*=φ(x*)因而x*是方程x=φ(x)的解，x*也是方程的根迭代格式迭代序列20例

f（x）=x2–2x-3=0它在区间[2,4]内有唯一根x*。方程可以改写为多种等价形式，如：1）此时取x0=4，得迭代公式当k越来越大，xk趋近精确根x*=3212）此时仍然取x0=4，得迭代公式当k越来越大，xk离精确根越来越远22如何判断所构造的迭代函数x=φ(x)使得迭代序列{xk}收敛或发散？怎样估计误差？问题P0(x0,x1)y2=φ(x)y1=x

x

yoP1(x1,x2)P2P*Q1P0(x0,x1)y2=φ(x)y1=x

x

yoP1(x1,x2)P2P*Q123若迭代法中的迭代函数g(x)在区间[a,b]上具有一阶连续的导数，且满足如下2个条件；对任意x∈[a,b]，a≤g(x)≥b;在区间[a,b]上g’(x)存在，且|g’(x)|≤L<1.则有如下结论：（1）对于任意初始近似值x0∈[a,b]，迭代法xk+1=g(xk)产生的迭代序列{xk}都收敛于方程x=g(x)在区间[a,b]上的唯一实根x*;

（2）定理24拉格朗日中值定理设函数y=f(x)在闭区间

a,b

上连续，在开区间(a,b)内可导，则在(a,b)内至少有一点ξ，使得25二迭代法的收敛速度定义：

设序列{xk}收敛于x*，并记ek=xk-x*(k=0,1,2,…)。如果存在非零常数p，使得

则称序列{xk}是p阶收敛的。当p=1，且0<|c|<1，称为线性收敛；当P>1，称为超线性收敛。特别，当p=2，称为平方收敛262.4牛顿法与割线法一牛顿迭代公式x*xkxk+1xyoy=f(x)(xk,f(xk))27设xk是f(x)=0的一个近似根，把f(x)在xk处作一阶Taylor展开于是：设f’(xk)≠0，则近似解为：取xk+1为原方程新的近似根，得到牛顿迭代公式28定义:

对于方程x=

φ(x)，若在x*的某个邻域S={x|x∈[x*-δ,x*+δ]}内，对任意初始值x0∈S，迭代格式xk+1=φ(xk)k=0,1,2,……（3.14）都收敛，则称该迭代格式在x*的附近是局部收敛的。定理:

设方程x=

φ(x)有根x*，且在x*的某个邻域内φ(x)存在一阶连续的导数，则（1）当|φ’(x)|<1时，迭代格式（3.14）局部收敛（2）当|φ’(x)|>1时，迭代格式（3.14）发散二牛顿法的局部收敛性29二牛顿法的局部收敛性对φ(x)求导牛顿法的迭代函数为由于f’(x*)≠0，因此φ(x*)=0，由局部收敛定理得知，牛顿迭代法是局部收敛的。30而且，无论当x*是f(x)的单根还是重根，牛顿法均为局部收敛。需要注意的是：初值x0需要足够靠近x*31牛顿法的收敛阶数又由牛顿迭代公式得将f’(x*)在xk处泰勒展开，得代入上式，有32牛顿法的收敛阶数即，令k∞，由局部收敛性得知：xkx*时，从而xkx*，所以牛顿迭代法至少为平方收敛33例

用牛顿法求方程f(x)=x(x+1)2-1=0,在0.4附近的根，精确至4位有效数字解: 对f(x)求导得

f’(x)=(x+1)(3x+1)

牛顿迭代格式为取x0=0.4,计算结果为k 0 1 2 3xk 0.4 0.47013 0.46559 0.46557因此 x*≈0.4656341割线法几何意义四割线法x*xk-1xk+1xyoy=f(x)AB35切线斜率

割线斜率割线法用差商代替求导，减少了牛顿法的计算量，但是需要2个初值x