第一章非线性方程和方程组的数值解法

非线性方程根的概念给定非线性方程f(x)=0 如果有α使得f(α)=0,则称α为f(x)=0的根 或f(x)的零点. 设有正整数m使得f(x)=(x-α)mg(x) 且g(α) 0 ,则当m 2时，称α为f(x)=0的m 重根；当m=1时，称α为f(x)=0的单根. 若α为f(x)=0的m重根，则 f(α)=f (α)= =f (m-1)(α)=0, f (m)(α) 0 这里只讨论实根的求法.

求根步骤

(1)根的存在性. (2)根的隔离. (3)根的精确化.

非线性方程求根的数值方法

二分法 迭代法单点迭代法(不动点迭代，Newton迭代法) 多点迭代法(弦截法)

迭代法是一种逐次逼近的方法，它的基 本思想是通过构造一个递推关系式 (迭 代格式) ,计算出根的近似值序列,并要 求该序列收敛于方程的根.

迭代法的一般理论

单点迭代法将方程f(x)=0改写成等价形式 x= (x) (1) 建立迭代公式 xk+1= (xk) (2) 在根的附近任取一点x0,可得一序列 xk k 0 .若 xk ,且 (x)连续，则对(2)两 xk k 0 收敛，即 klim 端取极限有α = (α) ,从而α为方程(1)的根， 也称为 (x)的不动点，这种求根算法称为不动点 迭代法(Picard迭代法). (x) 称为迭代函数.

多点迭代法

建立迭代公式 xk+1= (xk-n+1, ,xk-2, xk-1, xk)

(3)

对于迭代法需要考虑一下几个主要问题 收敛性 收敛速度 计算效率

迭代法的局全收敛性

定义1 设 为f(x)=0的根，如果x0 [a, b], 由迭代法产生的序列都收敛于根 ,则 称该迭代法是全局收敛的。

迭代法的局部收敛性

定义2 设方程x= (x) 根α, 如果存在α 的某个邻域 : x-α ,对任意初值 x0 ,迭代过程所产生的序列均收敛 于根α ,则称该迭代法是局部收敛的.

迭代过程的收敛速度

定义3 记 ek = α- xk ,若k

lim

ek 1 ekp

C 0

则称迭代过程是p阶收敛的. 特别地，当p=1时，称为线性收敛； 当p>1时，称为超线性收敛， 当p=2时，称为平方收敛. p越大，收敛越快.

效率指数

定义3 称1

EI p 为效率指数. 其中p表示迭代的收敛阶， 表示 每步迭代的计算量. EI越大，计算效率越高.

不动点迭代法

不动点迭代法的整体收敛性

定理1.1 设 (x)满足 (1)当x [a, b]时， (x) [a, b] ; (2) x1, x2 [a, b] ,有 (x1)- (x2) L x1-x2 , L<1 则对任意初值x0 [a, b], 迭代过程 xk+1= (xk)收敛于 x= (x)的惟一根 ，且有误差估计式L xk xk xk 1 1 L Lk xk x1 x0 1 L

证 根的存在性 由(2)知 (x)连续. 令f(x)=x- (x), f(a) 0, f(b) 0, 从而 f(x)=0在[a, b] 上有根，即x= (x)在[a, b] 上有根. 根的唯一性 设x= (x)在[a

, b] 上有两根α1, α2, α1 α2 , α1- α2 = (α1)- (α2) L α1- α2 与 L<1矛盾.故α1= α2 序列的收敛性 xk+1-α = (xk)- (α) L xk-α , xk+1-α Lk+1 x0-α 由0 L<1有k

lim xk