计算方法非线性方程求根

计算方法非线性方程求根

第十章非线性方程求根

知识点：求根的基本概念，对分法，迭代法，误差，编程停机判断，算法说明

1.概念

（1）根的概念

方程f(x)=0的解叫做方程的根或f(x)的零点。例如

x-cosx=0,x-e x=0

求方程的根是数值计算的任务之一，当不易求得f(x)=0的解析解时，可以考虑求其近似根。求实根问题包括:根的存在性;根的分布;根的精确化.

（2）根的存在性

如果f(x)是[a,b]上的连续函数，且f(a) f(b)<0，则f(x)=0在（a,b）至少有一个根；若单调，则f(x)=0在(a,b)有惟一根。

（3）根的分布

若有根区间的根多于一个，为了得到根的数值解，可以将该有根区间分割若干个子区间，使每个子区间只包含f(x)=0的一个根，这个过程称根的隔离，每个子区间称为隔根区间。

一般情形下，隔根区间内任一点都可作为相应根的近似值，隔根区间越小，近似程度越好。

（4）根的精确化

在隔根区间内得到方程f(x)=0相应根的初步近似值后，为使近似值程度更好、符合预先期望，通常应继续逐步精确化根的近似值，直到满足规定的精度要求为止。精确化方法有很多，常见的有二分法，迭代法等。

2.二分法

二分法是利用隔根区间的两个端点来逐步求得满足预先给定精度的近似根。

（1）基本思想 对分有根区间，判断f(x)的符号，逐步将有根区间缩小，使得在足够小的区间内取得满足预先给定精度要求的近似值。

（2）具体做法

设区间[a,b]为有根区间，记α是f(x)=0在(a,b)的惟一根，二等分区间[a,b]。令

x0=(a+b)/2，如果f(x0)=0,则求得实根α=(a+b)/2。否则，若f(a)f(x0)<0,则α∈[a,x0],取

a1=a,b1=x0；若f(b)f(x0)<0,则α∈[x0,b],取a1=x0,b1=b。

在新的有根区间上重复二等分过程，得有根区间套序列

[a,b]? [a1,b1]? [a2,b2] ?…? [a k,b k] ?…

b-a>b1-a1>b2-a2>…>b k-a k…，a k≤α≤b k

其中每个区间为前一个区间的一半，经过k次二分后，有根区间的长度为

如此无限二等分区间[a,b](k→∞)有

b k- a k→0(k→∞)或lim a k=lim b k=α(k→∞)。

取有根[a k,b k]的中点x k=(a k+b k)/2为α的近似值，则以α为极限的近似值序列为x0，x1，x2，…，x k，…

由于 对于预先给定精度ε>0，只要

便有|α- x k |<ε。这时的x k就是满足精度要求的近似值。

小记：二分法是一个求实根的方法，在“二分”[a,b]的过程中默认了f(x)为[a,b]上的连续函数，f(x)=0在[a，b]内只有一个根，选择[a，b]为“初始”的隔根区间。通过的对分产生自区间套，即隔根子区间套，每次都取隔根子区间“套”的中点作为根的近似值。对于连续函数f(x)，总可以找到区间，使f(x)在该区间上单调有惟一实根，而且这个区间就可以作为隔根区间。

例用二分法求x3+4x2-10=0在(1,2)内的根，要求绝对误差不超过0.5╳10-2

解：因为，f(x)=x3+4x2-10，f(1)=-5,f(2)=14，f(1)f(2)<0，f′(x)=3x2-8x ，函数单调，所以f(x)=0在（1，2）内有唯一根α，取（1，2）为隔根区间。计算列表

事后估计：|x k-α|≤（1.368-1.360）/2=0.004<0.5╳10-2

先验估计：从|x k-α|≤（b-a）/2k+1≤0.5╳10-2，解出对分次数k+1≥8。

近似根x8=1.364（≈α）满足指定精度要求，进行8次对分后终止计算（停机）。（3）采用二分法计算f(x)=0在（a,b）的近似根x*的算法。

1:输入有根区间[a,b]的a、b值及误差精度控制参数ε，定义函数f(x)。

2:IF f(a)f(b)>0 THEN退出，选用其他求根方法.else 转步骤 3

3：while（|a-b|>ε）

计算中点x=(a+b)/2及 f(x)；

if |f(x)|<ε then 停止计算，x*=x，并转步骤 5。else

if f(a)f(x)<0 then 修正[a,x]→[a,b]

else 修正[x,b]→[a,b]

endwhile

4:x*=(a+b)/2

5:输出近似值x*

优点：条件简单，编程容易。缺点：收敛慢，不能求偶数重根和复根。

3.迭代法

迭代法是根据隔根区间内根的初始估计值来逐步求得满足预先给定精度的近似根，二不必考虑根的边界或上下限（隔根区间的两个端点）。

（1） 构造迭代公式

设法将方程f(x)=0改写为等价形式：x = ?( x)（f 和 ?连续）， 构造迭代公式：x n+1= ?(x n )，n=0,12,….

在根邻近任取初始值x 0作为近似根，由迭代公式得一序列

x 0，x 1，x 2，…x n ，…

该序列称为迭代序列，迭代公式中的?称为迭代函数。若迭代序列收敛，则存在α使lim x n =α(n →∞)，有

α就是原方程的根，也称?的不动点。这种求根方法称为一般迭代法，当n 充分大时，x n 可做α近似值，x k 称为方程根的第k 次近似值。如果迭代序列极限存在，则称一般迭代公式收敛，否则称其发散。

（2）收敛性 一般迭代收敛定理：设迭代函数?(x)满足

(x )在[a,b ]连续，（a ，b ）可导；当a ≤x ≤b 时，a

≤?(x )≤b ；?x ∈[a,b ]，|?‵(x )|≤L <1（L 为常数）。则方程x =?(x )在[a,b ]有唯一根α；?x 0∈[a,b ]，x n+1=?(x n )收敛到α.且

教材P211定理10.1及其推论。一般地，L 越小，收敛越快。

（3）举例

求方程 f (x )=x 3-x-1=0 在[1，2]内的近似根。 解：f(1)=-1,f(2)=5，方程在[1，2]有一实根。从

故函数惟有一实根。将方程x 3-x-1=0在[1，2]上改写为等价形式

).()lim ()(lim lim 1αα====∞

→∞

→+∞

→n n n n n n x x x 即α= ?(α)。

满足一般收敛条件，所以方程x = ?1(x)在[1，2]上唯一实根α。?x

∈[1,2]，x k+1= ?1(x k )收敛到α。

继续重复这个近似计算过程，得一系列近似值 因x 7=x 8,可视x 8为满足精度要求的近似根。

值得注意的是，如果解得x = ?2( x)= x 3-1，令x k+1= ?2( x

k )=x k 3-1 。取x 0=1.5作近似初值，代入?2( x)，得x 1=2.375，重复该计算过程，得一发散

的近似值序列。

这个事实表明，不同规则（函数）约束下的近似计算，可能获得不同的结论。

（4）编程停机判断（误差讨论）

在[a,b]任取初值x 0，计算x n+1=

(x n )，当|x n+1-x n |≤ε ，

(5)算法盒图

4.迭代法的收敛阶(收敛速度)(参阅了解)