5 第二章 非线性方程组的数值解法

y
线性
x*
x2 x1
x
x0
f ( x0 ) f ( x0 ) f ( x0 ) = ⇒ x1 = x0 − ' x0 − x1 f ( x0 )
'
xk +1
f ( xk ) = xk − f ′( x k )
k = 0,1, 2, L
只要 f ∈C1，每一步迭代都有 f ′( xk ) ≠ 0 x k = x ∗，则 x*就是 f 的根 而且 lim k→∞
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=(a+b)/2; STOP.
10 ⎛ 10 ⎞ − 4x x = ⎜ − 4x ⎟ 3、 x = x ⎝ x ⎠
1 2
1 2
⎛ 10 ⎞ − 4x ⎟ 即 g ( x) = ⎜ ⎝ x ⎠
1 2
1 2
⎛ 10 ⎞ ⎛ 10 ⎞ x = 4、 ⎜ 4+ x ⎟ 即 g ( x) = ⎜ ⎟ 4 + x ⎝ ⎠ ⎝ ⎠ f ( x) x 3 + 4 x 2 − 10 = − g ( x ) x 5、x = x − 即 2 f ′( x ) 3x + 8x
ξ
使得 f (ξ ) = 0 ，若同时 f ( x ) 的一阶导数 f ′( x )
§2.2.1 二分法
原理：若 x∈C[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上至 少有一实根 基本思想：逐步将区间分半，通过判别区间端点函数值的符号， 进一步搜索有根区间，将有根区间缩小到充分小，从而求 出满足给定精度的根 x 的近似值。
例：1写出求 2写出求
1
a (a > 0)的Newton迭代格式；
( a > 0)的Newton迭代格式,要求公式中既
a 无开方运算，又无除法运算。
解： 1等价于求方程 f ( x ) = x 2 − a = 0 ( a > 0) 的正根 f ′( x ) = 2 x
2 f ( xk ) xk −a 1 a = xk − = ( xk + ) k = 0,1, 2,L xk + 1 = xk − f ′( x k ) 2 xk 2 xk 1 2 2解法一： 等价于求方程 f ( x ) = ( x − ) = 0 (a > 0) 的正根 a 1 2 ( xk − ) 1 f ( xk ) a f ′( x ) = 2( x − ) xk + 1 = xk − = xk − 1 f ′( xk ) a 2( xk − )
输入: a和b ; 容许误差 TOL; 最大对分次数 Nmax. 输出: 近似根 x. Step 1 Set k = 1; Step 2 Compute x=f((a+b)/2); Step 3 While ( k ≤ Nmax) do steps 4-6 Step 4 If
|x| < TOL , STOP; Output the solution x.
判定收敛方法：
xk +1 − xk < ε
几何意义
y p1 p0 y=x y=g(x)
x = g (x)
y p0 y=x
9
x0 y x1 x*
9
p1 y=g(x) x0 y y=g(x) p0 x* x1 y=x x
y = f (x) x
y=x
y=g(x)
p0 p1 x1 x0 x*
U
x x0 x*
选择(2)计算 k 0 1 xk 1.5 1.481 2 1.473 3 1.469 4 1.467
x = 1.46
§2.2.3 牛顿法 /* Newton - Raphson Method */
使用最多的求 根方法 一、牛顿迭代公式的推导 Taylor展开法 原理：将非线性方程线性化 取 xk ≈ x*，将 f (x)在 xk 做一阶Taylor展开:
本节主要内容： 1、二分法 2、不动点迭代的构造 3、Newton迭代法 4、割线法 5、非线性方程组的迭代解法
（1）Newton迭代法 （2）最速下降法
求方程 f ( x ) = 0几何意义
y
y = f ( x)
a
o
x* b
x
基本定理 如果函数 f ( x ) 在 [a , b] 上连续，且 f ( a ) f ( b ) < 0 则至少 有一个数 在 [a , b] 内存在且保持定号，即 f ′( x ) < 0 (或 f ′( x ) > 0 ) 则这样的 ξ 在 [a , b] 内唯一
x − x0 < TOL x
Step 7 Output (The method failed after Nmax iterations); /*不成功 */
例：已知方程 x3 − x2 − 1 = 0 在1.5附近有根，把方程写成三
种不同的等价形式(1) x = 1 +
3 2
1 x2
xn+1 = 1 + 对应迭代格式；
≈ 4.64
∴ n=5
求运动员的质量： 由图估计根位于 140～150 kg之间
v(t ) = gm gc tanh( t) c m
gm gc tanh( t ) - v(t ) c m
1 0 -1 -2 -3 -4 -5
根
f (m ) =
解为 m=142.7376 kg 调用二分法程序:
50
100
1 2
法3
x1 = 1.34840 x2 = 1.36738 x3 = 1.36496 x4 = 1.36526 x4 = 1.37517 x5 = 1.365225
法4
x4 = 1.0275×10 x4 = 1.37517
法5
x1 = 1.37333 x2 = 1.36526
9
x3 = 1.365230014 x11 = 1.365137821 x4 = 1.365230013 L
§2.2.2 迭代法的理论
一、不动点迭代 /*Fixed-Point Iteration*/
等价变换
f (x) = 0 f (x) 的根 x
x = g (x)（迭代函数）
∗ x g (x) 的不动点 xk +1 = g ( xk ) k = 0,1, 2, L
∗
思 路
从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), …, ∞ { } x xk+1 = g(xk), … 若 k k=0 收敛，即存在 x* 使得 lim xk = x *，且 g 连续，则由 lim x k 1 = lim g ( x k ) 可 + k →∞ k→∞ k→∞ 知 x* = g(x* )，即x* 是 0
m=HalfInterval('sqrt(9.81*m/0.25)*tanh(sqrt(9.81*0.25/m)*4)-36', 40, 200, 0.001)
优点
①简单; ② 对f (x) 要求不高(只要连续即可)
缺点
①无法求复根及偶重根; ②收敛慢
1. 最好先给出 f (x) 草图以确定根的大概位置 2. 或用搜索程序，将[a, b]分为若干小区间，对每一个满足 f (ak)·f (bk) < 0 的区间调用二分法程序，可找出区间[a, b]内 的多个根
a+b x1 = 2
误差 分析
ak + bk 1 ∗ , 且 x − xk +1 ≤ k +1 ( b − a ) , k = 1, 2,L 3、 xk +1 = 2 2
4、对分次数的计算公式： x ∗ − x ≤ 1 ( b − a ) 令 <ε k +1 k +1 2 ln ( b − a ) − ln ε
取 x 0 = 1 .5 计算结果如下：
x1 = −0.875 x2 = 6.732 x3 = −469.720
8
法1
x1 = 1.28695 x2 = 1.40254 x3 = 1.34546 x4 = 1.37517 x5 = 1.37517 L
法2
x1 = 0.81650 x2 = 2.99691 x3 = (−8.65086)
f ′′( x k ) f ( x ) = f ( x k ) + f ′( x k )( x − x k ) + ( x − xk )2 2!
将 (x* − xk)2 看成高阶小量，则有：
0 = f ( x*) ≈ f ( xk ) + f ′( xk )( x * − xk )
⇒ x* ≈ x k − f ( xk ) f ′( x k )
由二分法的过程可知：
对分k次
y = f ( x)
a
x
∗
•
1、
[ a , b] ⊃ ⎡ ⎣a1 , b1 ⎤ ⎦⊃L⊃ ⎡ ⎣ak , bk ⎤ ⎦⊃L f ( ak ) f ( bk ) < 0, x ∗ ∈ ⎡ ⎣ak , bk ⎤ ⎦
b
1 1 2、 bk − a k = ( bk −1 − a k −1 ) = L = k ( b − a ) 2 2
第二章 方程的数值解法
§2.2 非线性方程数值解法
代数方程的求根问题是一个古老的数学问题。 理论上，n 次代数方程在复数域内一定有n个根(考虑重数)。 早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪 才证明大于等于五次的一般代数方程式不能用代数公式求解， 而对于超越方程就复杂的多，如果有解，其解可能是一个或几个， 也可能是无穷多个。一般也不存在根的解析表达式 需要研究数值方法求得满足一定精度根的近似解