第6章非线性方程(组)的数值解法n

13
数值分析
上面两个定理指出了迭代函数在满足一定的条件下，迭代序列 收敛到方程的根，在迭代求根过程中，x*未知的，因此不可能 用|ek|<ε来作为迭代结束的条件。那么，如何估计误差ek呢？
定理6.2.3
设定理6.2.1条件成立，则
Lk | x k x* | 1 L | x1 x0 |
12
数值分析
③ 当k 时， xk 收敛到 x* ？
Hale Waihona Puke | x * xk | | ( x*) ( xk 1 ) | | (ξ k 1 ) | | x * xk 1 |
L | x * xk 1 | ...... Lk | x * x0 | 0
方程(x)=0在区间[a，b]上根多于1个时，也只能求出其中的一个根。
科大研究生学位课程 数值分析
6
①简单; 可靠、易于在计算机上实现 ② 对f (x) 要求不高(只要连续即可) . ①无法求复根及偶重根 ② 收敛慢 一般不单独使用,而多用于为其他方法提供一个比较好的 初始近似值.
7
数值分析
6.2 迭代法
4
数值分析
例1
用二分法求x3+4x-10=0在区间[1,2]内根的近似值,并估计误差.
解 这里(x)=x3+4x-7， (1)(2)=-18<0,而且 (x)=3x2+4>0,所以
(x)=0在[1,2]区间有唯一根. 取x0=1.5,由于(x0)=2.375,得新有根区间[1,1.5], x1=1.25,由于(x1)=-0.0468,得新有根区间[1.25,1.5], x2=1.375,由于(x2)=1.0996,得新有根区间[1.25,1.375], x3=1.3125,由于(x3)=0.511,得新有根区间[1.25,1.3125],
………………………………………………….
x9=1.254882813,得有根区间[1.254882813,1.255859375], x10=1.255371094, (x10)=-0.000105285 取x*x10=1.255371094作为方程根的近似值,且有
b10 a10 1.255859375 1.254882813 | x10 | 0.00049 2 2
f (x) = 0
f (x) 的根
等价变换
x = ( x)
(x) 的不动点
思 路
从一个初值 x0 出发，计算 x1 = (x0), x2 = (x1), …, xk+1 = (xk), … 若 xk k 0 收敛，即存在 x* 使得
lim x k x * ，且
k
lim x k 1 lim x k 连续，则由 k k 可知 x* = (x* )，即x* 是 的不动点，也就
5
数值分析
如果取精度=10-5,则要使
| x k | ba 1 5 10 2 k 1 2 k 1
只需k>5ln210-115.61.即需取x*x16. 二分法要求函数在区间[a，b]上连续，且在区间两端点函数值符 号相反，二分法运算简便、可靠、易于在计算机上实现。但是，若 另外，若方程(x)=0在区间[a，b]有重根时，也未必满足(a)(b)<0. 而且由于二分法收敛的速度不是很快,一般不单独使用,而多用于为 其他方法提供一个比较好的初始近似值.
先验估计
证明：
L | x k x k 1 | | x k x* | 1 L
事后估计
xk 1 xk L xk xk 1 Lk x1 x0 于是，对于任意正整数p，有
x k p x k x k p x k p 1 x k p 1 x k p 2 x k p 2 x k
第6章 非线性方程(组)的数值解法
非线性科学是当今科学发展的一个重要研究方向，而非 线性方程（组）的求根也成了一个不可缺的内容。但是，非 线性方程（组）的求根非常复杂。 所谓非线性方程就是指次数>1的代数方程和所有的超越方程。 先讨论求非线性方程(x)=0的根的问题. (x)=3x5-2x4+8x2-7x+1， (x)=e2x+1-xln(sinx)-2 因此，通常我们用迭代法解非线性方程 看迭代法之前，先看看一种简单直观的方法
k ln
(1 L)
x1 x 0
ln L
例6.2.2 求方程xex-1=0在0.5附近的根,精度要求=10-3. 解 可以验证方程xex-1=0在区间[0.5,0.6]内仅有一个根. 改写方程为x=e-x ,建立迭代格式
x k 1 e x
取初值x0=0.5,计算得 k 0 xk 0.5
|xk-xk-1| 0.06129 0.03446 0.01964 0.01111 0.00631
k 7 8 9 10
xk 0.56844 0.56641 0.56756 0.56691
|xk-xk-1| 0.00358 0.00203 0.00115 0.00065
所以,取近似根x*x10=0.56691满足精度要求. 如果精度要求为=10-5, 则由
g ( x ) 有根
故x*=(x*)
② 不动点唯一？ ~ g( x ~ )，则 反证：若不然，设还有 x ~ ( x*) ( ~ ~ 之间。 x* x x ) (ξ ) ( x * ~ x ), 在 x * 和 x ( x* ~ x )(1 (ξ )) 0 而 | (ξ ) | 1 x* ~ x
a 0 b0 , 2
若(x0)=0 ,则取x*=x0 ;否则,若 (a0)(x0)<0,取a1=a0,b1=x0 ;若
0 a
x1 x* x0
b
x
(a0)(x0)>0,取a1=x0,b1=b0 ,得到新的有根区间[a1,b1],
而且有根区间[a1,b1]长度是有根区间[a0,b0]长度的一半, 再对有根区间[a1,b1]重复上面运算, 即: 计算 x1 1 1 , 2 若(x1)=0, 则取x*=x1; 否则,若(a1)(x1)<0,取a2=a1 , b2=x1 ;若 (a1)(x1)>0, 取a2=x1 ,b2=b1,得到新的有根区间[a2,b2]. 数值分析
可见,k趋向无穷大时, xk收敛于x* . 而且,若要|xk-x*|< ,只要
2
ba k 1 2
或者
k log 2
ba

1
此时可取近似根x*xk .
3
数值分析
算法6.1（二分法）：
(1) 输入 : 有根区间 [a, b]的a, b值及精度控制量 ;
(2)置x:=(a+b)/2, (3)若f(x)=0，输出x，停算；否则，转步(4); (4)若f(a)f(b)<0，则置b:=x ；否则，置a:=x ; (5)置x:=(a+b)/2,若|b-a|< ,输出x，停算，否则，转 步(3).
0.4 10 5 k ln ln L ln ln 0.6 19.95 x1 x 0 0.10653
(1 L)
可知,需要迭代20次.
科大研究生学位课程 数值分析 16
6.2.3 迭代法的加速
定义6.2.1： 设由某方法确定的序列{xk}收敛于方程的根x*， 如果存在正实数p，使得
( 2 ) 对 x[a, b], 0 <L < 1 使得 | '(x) | L < 1 成立。 x 则任取 x0[a, b]，由 xk+1 = g(xk) 得到的序列 k k 0 收 敛于(x) 在[a, b]上的唯一不动点。

证明：① (x) 在[a, b]上存在不动点？ 令 g ( x) ( x) x g (a) (a) a 0 , g (b) (b) b 0
1
数值分析
6.1
二 分 法
设(x)在区间[a,b]上连续且(a)(b)<0,根据连续函数的介值定理,
区间[a,b]上必有方程(x)=0的根,称[a,b]为方程(x)=0的有根区间. 设(x)在区间[a,b]上连续且 y=(x)
(a)(b)<0 .
记a0=a,b0=b,计算 x0
是f 的根。
称 ( x)为迭代函数，
xk 1 ( x k )为迭代格式
称为xk第k次迭代近似解，
数值分析
ek xk x 为第k次迭代误差.
*
8
迭代法需解决的四个问题
• 迭代函数的合适选取， • 由迭代函数产生的解序列的收敛性 • 近似解的误差估计问题？ • 序列的收敛速度问题？
y=x
迭代法的几何意义
yx x ( x) y ( x)
交点的横坐标 为了保证x= (x)在[a,b]内 的根存在，还必须假定 (x)在[a,b]上连续.
数值分析
x * x2
x1
x0
9
6.2.2 收敛性和误差分析 3 例 试用迭代法求方程 f ( x) x x 1 0 在区间(1,2)内的实根。 3 建立迭代格式 解： 由 x x 1 xk 1 3 xk 1 k=0,1,2,3…….
xk 1 x * lim c k ( x x * ) p k
x k p x k p 1 x k p 1 x k p 2 x k 1 x k
(L
k p 1
L
k p 2
L ) x1 x0
k
Lk (1 LP ) x1 x0 1 L
14
科大研究生学位课程 数值分析