文档介绍：第二章非线性方程的数值解法
/* Numerical Solutions of Nonlinear Equations*/
本章主要内容:
1、二分法
2、不动点迭代的构造及其收敛性判定(重点)
3、Newton和Steffensen迭代(重点)
4、割线法
5、非线性方程组的迭代解法
历史背景
代数方程的求根问题是一个古老的数学问题。理论上, 次代数方程在复数域内一定有个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式,但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解,而对于超越方程就复杂的多,如果有解,其解可能是一个或几个,也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。
求方程几何意义
基本定理
如果函数在上连续,且
则至少有一个数使得,若同时的一阶导数在内存在且保持定号,即(或)则这样的在内唯一。
a
b
x*
§1 二分法/* Bisection Method */
原理:若 f C[a, b],且 f (a) · f (b) < 0,则 f 在(a, b) 上至少有一实根。
基本思想:逐步将区间分半,通过判别区间端点函数值的符号,进一步搜索有根区间,将有根区间缩小到充分小,从而求
出满足给定精度的根的近似值。
以此类推
终止法则?
a
b
x1
x2
a
b
When to stop?
或
不能保证 x 的精度
x*
2
x
x*
二分法算法
给定区间[a,b] ,求f(x)=0 在该区间上的根x.
输入: a和b; 容许误差 TOL; 最大对分次数 Nmax.
输出: 近似根 x.
Step 1 Set k = 1;
Step pute x=f((a+b)/2);
Step 3 While ( k Nmax) do steps 4-6
Step 4 If |x| < TOL , STOP; Output the solution x.
Step 5 If x*f(a)<0 , Set b=x;
Else Set a=x;
Step 6 Set k=k+1; Compute x=f((a+b)/2);Go To Step 3 ;
Step 7 Output the solution of equation: x; STOP.
3、
由二分法的过程可知:
4、对分次数的计算公式:
1、
2、
令
误差分析
解:
例1:用二分法求方程在区间上的根,误差限为,问至少需对分多少次?
①简单;
②对f (x) 要求不高(只要连续即可) .
①无法求复根及偶重根
②收敛慢
注:用二分法求根,最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序,将[a, b]分为若干小区间,对每一个满足 f (ak)·f (bk) < 0 的区间调用二分法程序,可找出区间[a, b]内的多个根,且不必要求 f (a)·f (b) < 0 。
优点
缺点
§2 迭代法的理论/* Theory of Iteration Method*/
f (x) = 0
x = g (x)(迭代函数)
等价变换
思路
从一个初值 x0 出发,计算 x1 = g(x0), x2 = g(x1), …, xk+1 = g(xk), …若收敛,即存在 x* 使得
,且 g 连续,则由可知 x* = g(x* ),即x* 是 g 的不动点,也就是f 的根。
看起来很简单,令人有点不相信,那么问题是什么呢?
如何判定这种方法是收敛的呢?
f (x) 的根
g (x) 的不动点
一、不动点迭代/*Fixed-Point Iteration*/