第三章 非线性方程求根

第二章

非线性方程的求根方法

第二章 引言

非线性方程的求根方法

方程求根的二分法 迭代法及其收敛性 Newton迭代法

2.1 引言

方程是在科学研究中不可缺少的工具；

方程求解是科学计算中一个重要的研究对象；几百年前就已经找到了代数方程中二次至五次方程 的求解公式； 但是，对于更高次数的代数方程目前仍无有效的精 确解法； 对于无规律的非代数方程的求解也无精确解法； 因此，研究非线性方程的数值解法成为必然。

非线性方程的一般形式： f(x)=0 代数方程： f(x)=a0+a1x+……+anxn (an 0) 超越方程 ：f(x)中含三角函数、指数函数、或其 他超越函数。 用数值方法求解非线性方程的步骤： (1)找出隔根区间；(只含一个实根的区间称隔根 区间) (2)近似根的精确化。从隔根区间内的一个或多个 点出发，逐次逼近，寻求满足精度的根的近似值。

2.2 方程求根的二分法 定理1(介值定理)设函数f(x)在区间[a,b]连续，

且f(a)f(b)<0,则方程f(x)=0在区间[a,b]内至少有一 个根。

二分法的基本思想：假定f(x)=0在[a,b]内有唯一单实根x*,考察有根区间 [a,b],取中点x0=(a+b)/2,若f(x0)=0,则x*= x0 ,否则， (1)若f(x0)f(a)>0,则x*在x0右侧，令a1=x0, b1=b; (2)若f(x0)f(a)<0,则x*在x0左侧，令a1=a, b1= x0。

以[a1, b1]为新的隔根区间，且仅为[a, b]的一半，对 [a1, b1]重复前过程，得新的隔根区间[a2, b2],如此二分下去，得一系列隔根区间：

[a, b] [a1, b1] [a2, b2] …… [ak, bk] ……其中每个区间都是前一区间的一半，故[ak, bk] 的长度：

1 bk ak k (b a ) 2当k趋于无穷时趋于0。

即若二分过程无限继续下去，这些区间最后必收敛于 一点x*,即方程的根。

每次二分后，取有根区间的中点xk= (ak+bk) /2作 为根的近似值，则可得一近似根序列： x0, x1, x2, … 该序列必以根x*为极限。 实际计算中，若给定充分小的正数 0和允许误差 限 1,当|f(xn)|< 0或bn- an< 1时，均可取x* xn。

二分法性质： f(an)· n)<0; f(b bn – an = (b – a)/ 2n

定理2 设x*为方程f(x)=0在[a, b]内唯一根，且f(x)满足f(a)f(b)<0,则由二分法产生的第n个区间[an, bn] 的 中点xn满足不等式

b a xn x * n 1 2证明：

bn an b a xn x * n 1 2 2

二分法求解非线性方程的优缺点：计算过程简单，收敛性可保证； 对函数的性质要求低，只要连续即可。

收敛速度慢； 不能求复根和重根； 调用一次求解一个[a, b]间的多个根无法 求得。

2.3 迭代法及其收敛性

不动点迭代法不动点的存在性与迭代法的收敛性

迭代收敛的加速方法

迭代法的基本思想：迭代法是一种逐次逼近的方法，用某个固定公式 反复校正根的近似值，使之逐步精确化，最后得到 满足精度要求的结果。例：求方程 x3-x-1=0 在 x=1.5 附近的一个根。 解：将所给方程改写成

x 3 x 1假设初值x0=1.5是其根，代入得x1 3 x0 1 3 1.5 1 1.35721

x1≠x0,再将x1代入得x2 3 x1 1 3 1.35721 1 1.33086

x2≠x1,再将x2代入得x3 3 x2 1 3 1.33086 1 1.32588

如此下去，这种逐步校正的过程称为迭代过程。 这里用的公式称为迭代公式，即

xk 1 3 xk 1

k=0,1,2,……

迭代结果见下表：k0 1 2 3 4

xk1.5 1.35721 1.33086 1.32588 1.32494

k5 6 7 8

xk1.32476 1.32473 1.32472 1.32472

仅取六位数字，x7与x8相同，即认为x8是 方程的根。 x*≈x8=1.32472

2.3.1 不动点迭代法 将连续函数方程f(x)=0改写为等价形式：x= (x)

其中 (x)也是连续函数，称为迭代函数。 不动点：若x*满足f(x*)=0,则x*= (x*);反之，若 x*= (x*) ,则f(x*)=0 ,称x*为 (x)的一个不动点。 不动点迭代： xk 1 ( xk ) (k=0,1,……)

若对任意 x0 [a, b],由上述迭代得序列{xk},有极限

lim xk x *k

则称迭代过程收敛，且x*= (x*)为 (x)的不动点。

几何意义：

x (x)

y x y (x)y=x

y (x)

x2

x1

x0

但迭代法并不总令人满意，如将前述方程x3-x1=0改写为另一等价形式：

x x 133 建迭代公式： xk 1 xk 1

仍取初值x0=1.5, 则有x1=2.375, x2=12.396,x3=1904, 结果越来越大。 此时称迭代过程发散。

y x

y x

y (x ) y (x )

收敛O x * x2 x1

( x)在x * 附近较平缓y x y x

x0

O

x1

x3 x * x2

x0

y (x )

发散y (x )

O

x2

x1

x0 x *

O

x3 x1 x * x0 x2

( x)在x * 附近较陡峭

2.3.2 不动点的存在性与迭代法的收敛性

定理3(存在性) 设 (x) C[a, b]且满足以下 两个条件：

(1)对于任意x [a, b],有a≤ (x)≤b; (2)若 (x)在[a, b]一阶连续，且存在常数 0<L<1,使得对任意x [a, b],成立 | '(x)| ≤L

则 (x)在[a, b]上存在唯一的不动点x*。

不动点的存在性证明：证： 若 (a) a 或 (b) b 显然 (x) 有不动点； 否则，设 (a) a 则有

(b) b

(a) a (b) b (因a≤ (x)≤b)

记 ( x) ( x) x 则有 (a) (b) 0 故存在x*使得 ( x*) 0 即 ( x*) x *

x*即为不动点。

本文来源：https://www.bwwdw.com/article/0u9j.html