- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
弦截法的初始条件是已知2个初始点 x0, x1。
(2.5)
弦截法的几何意义
得与 X 轴的交点 x 作为 x1，即
过两点 ( x0 ,
y = 0（ f(x) = 0)， f ( x0 )),( x1, 作一条直线，令 f ( x1 ))
y f ( x1 ) x x1 , f ( x0 ) f ( x1 ) x0 x1 f ( x1 ) x 2 x x1 ( x1 x0 ) f ( x1 ) f ( x0 )
iii）成立误差估计式
Lk x * xk x1 x 0 1 L
(2.1)
证明 i）存在性 令
( x) x ( x), then from (1) (a) 0, (b) 0.
由介值定理得，存在 x*∈[a, b],使ψ(x*)=0,即x*= φ(x*)。 唯一性 设另有一个 x**≠x*满足x**= φ(x**) ，则有微分 中值定理得
例2.4 写出用牛顿法求 ，并计算 a
。 7
2 f ( x ) x a, in order to compute a , 解 设 i.e. to find the root of f ( x)=0.
2 f ( xk ) xk a xk 1 xk xk f ( xk ) 2 xk
弦截法算法
1. Define f ( x), input e, initial x_k1, x_k 2, (x k 1 , x k ), compute f 1: f ( x_k1) 2. FOR i=0,1,2, ,maxrept f 2 : f ( x_k 2) x _ k x_k 2 f 2( x_k 2 x_k1) /( f 2 f 1) IF (|x_k 2 x_k1|<e) or ( | f ( x_k ) | e) THEN output x_k , end f 1: f 2 x_k1 x_k 2 x_k 2 x_k ENDFOR 3. Output no root near x_k1, x_k 2.
x * x ** ( x*) ( x **) ( )( x * x **) L x * x ** x * x ** (contradiction) x ** x *.
ii） 有条件（1）易知， {xk } [a, b].
xk 1 xk ( xk ) ( xk 1 ) ( )( xk xk 1 ) , [a, b].
1 ( x )
1 1 1, when x [1.5, 2.5], 2/3 3 (2 x 5)
{xk } converges.
2）若将迭代格式写为：
3 xk 5 x3 5 xk 1 , 2 ( x) , 2 2 2 3 x 1, when x [1.5, 2.5], 2 ( x) 2
Again by Taylor at x1 , we have f ( x1 ) x 2 x1 . f ( x1 )
Newton iterative method
f ( xk ) xk 1 x k , k 0,1, 2, f ( xk ) or f ( xk ) xk 1 x k , k 0,1, 2, f ( x0 )
（1）当x∈[a, b],有a≤ φ(x) ≤ b；
（2） φ(x)在[a, b]上可导，且存在正数L<1,使任意的x∈ [a, b],有|φ'(x) | < L. 则 i） 在[a, b]上有唯一的 x* 满足 x*= φ(x*) ； ii）由xk+1 = φ (xk) 产生的{xk+1}收敛到 x*；
ii)
若α为 f(x)的p重根，取
f ( x) ( x) x p , f ( x)
则
( ) 0 。牛顿迭代法可取为 f ( xk ) xk 1 xk p , k 0,1, 2, f ( xk )
• 牛顿法的几何意义
y f ( x0 ) f ( x0 )( x x0 ), setting y f ( x) 0, f ( x0 ) x1 x x0 f ( x0 )
在牛顿迭代法中，用相邻两次迭代值的一阶差商来代 替一阶导数，即取
f ( xk ) f ( xk 1 ) f ( xk ) f [ xk , xk 1 ] xk xk 1
就得到弦截法
f ( xk ) xk 1 xk ( xk xk 1 ), k 1, 2, f ( xk ) f ( xk 1 )
牛顿迭代法对应于 f(x)=0的等价方程：
(2.3)
f ( x) x x f ( x)
f ( x) f ( x) ( x).Then ( x) . 2 ( f ( x))
i) 若α为 f(x)的单根，即 f(α)=0， f '(α)≠0,则 | φ'(α) |=0，因此对充分小的δ>0,当x∈(α-δ, α+δ) 时，有| φ' (x) |<1.所以牛顿迭代法收敛。
第二章 非线性方程的数值解法
2.1 2.2 2.3 二分法 迭代法 牛顿迭代法
求解非线性方程的根，就是求解高次方程或超越方程
(含有指数和对数等)，因为这类方程没有固定的求根公式。
用 f(x)表示方程左端的函数，则一般的非线性方程可表 示为
f (x) = 0.
本章的任务就是上述方程的根或函数的零点。
注1：使用牛顿迭代法存在从一个根跳到另一个根的情况。 注2：如果f(x)=0没有实根，则牛顿迭代序列不收敛。
例2.3 证明：设α是 f(x)=0的单根，则牛顿迭代法是2阶收 敛的。 迭代格式 p 阶收敛的定义 记 ek= xk- α,若存在常数c成立
| ek 1 | lim c. p k | e | k
注 1 对分法对多个零点的情况，只能算出其中一个零点。 注 2 即使 f(x)在[a, b]上有零点，也未必有 f(a) f(b)<0。
2.2 迭 代 法
f ( x) 0 x ( x). For example x x f ( x) ( x). structure xk 1 ( xk ), any initial value x0 .
1 a xk . 2 xk
Take x0 3, we have 1 7 1 7 x1 3 2.667, x 2.667 2.6458 2 2 3 2 2.667 7 2.6457513.
2.3(2) 弦 截 法
If ( x) is continuous,then {x k } converge( lim x k = ),and
k
f ( ) 0. In fact, = lim x k 1 lim ( x k ) (lim x k ) ( ) f ( ).
xk 1 xk ( )( x k x k 1 ) L x k x k 1 L2 x k 1 x k 2
对任意正整数 p，有
Lk 1 x1 x0 .
xk 1 x k
xk p xk xk p xk p 1 xk p 1 xk p 2 Lk p 1 Lk p 2 Lk x1 x0
until f ( xn ) , or b a .
对分法求根算法
1. Input a, b, define f ( x) IF ( f (a) f (b) 0) THEN choose other mathod. 2. WHILE | a b | calculate mid-point x (a b) / 2, and the value of f ( x). IF | f ( x)|< , THEN solution x* x, goto Step 4. IF f (a) f ( x)<0, THEN [a, x] [a, b]; IF f ( x) f (b)<0, THEN [ x, b] [a, b]; ENDWHILE ab 3. x* 2 4. Output x *.
k k k
If |x k 1 x k |< ( 0),then take x k 1 which is zero point of f ( x), i.e. f ( ) 0.
判定迭代格式 xk+1 = φ (xk) 收敛的条件: 定理 1 若定义在[a, b]的φ(x)满足：
xk 1 = 2 ( xk ) does not converge.
2.3 牛顿迭代法
非线性方程：f(x)=0。By Taylor expansion at x0,
f ( x0 ) f ( x) f ( x 0 ) f ( x 0 )( x x 0 ) ( x x0 ) 2 2! f ( x 0 ) f ( x 0 )( x x 0 ) f ( x ) 0 f ( x0 ) f ( x0 ) x x0 ,setting x1 x, then x x0 . f ( x0 ) f ( x0 )
Lk (1 Lp ) x1 x0 0 (k , p ) 1 L
(*)
xk is Cauchy sequence,thus xk converges.
iii） 在（*）式中，令 p ∞，即得（4.1）。证毕。 例2.2 求 x3-2x-5=0在[1.5，2.5]上的根。 解 1） x 3 2 x 5, x 3 2 x 5 1 ( x) x k 1 3 2 x k 5
Calculate middle point x1 (1 2) / 2 1.5, f (1.5) 0.45, [a, b] [1.5, 2]; Calculating x 2 (1.5 2) / 2 1.75, f (1.75) 0.078125, [a, b] [1.5,1.75], , until f ( x n ) , or b a .
