数值分析课件第二章_非线性方程求根

注：试位法每次迭代比二分法多算一次乘法，而且不保证 收敛。
§3 迭代法 /* Fixed-Point Iteration */
等价变换
f (x) = 0 f (x) 的根
x = g (x) g (x) 的不动点
从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), …, x k 0 收敛，即存在 x* 使得 思 xk+1 = g(xk), … 若 k 路 lim x k x * ，且 g 连续，则由 lim x lim g x 可 k 1 k k k k 知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。

x x0 y y=g(x) x1 x* y=x y y=g(x) p0 x0 x*

p1 y=g(x) x x1 y=x
p0 p1

x x0 x*
p1

x
x1 x0 x*
x1
§3 Fixed-Point Iteration
定理 考虑方程 x = g(x), g(x)C[a, b], 若
( I ) 当 x[a, b] 时， g(x)[a, b]； ( II ) 0 L < 1 使得 | g’(x) | L ቤተ መጻሕፍቲ ባይዱ 1 对 x[a, b] 成立。 则任取 x0[a, b]，由 xk+1 = g(xk) 得到的序列 x 收 敛于g(x) 在[a, b]上的唯一不动点。并且有误差估计式：
§2 Bisection Method
试位法 /* Regula Falsi Method */
Is it really better than Bisection Method?

xn1 ( z n yn ) zn z n 2 yn x n
2
改进
2.4 Newton-Raphson Method
设 x*是方程 f(x)=0 的根, x0是x*的近似值. 在 x0 附近,有
f ( x) f ( x0 ) f ( x0 )( x x0 )
f(x ) = 0
| xn1 C | 1 lim 2 n | x C | 2 C n
由此可知,这一序列的收敛阶数为1,即迭代法 是线性收敛.
定理2.6 设x*是 ( x) 的不动点,且 ( p1) ( x*) ( x*) ( x*) 0 而
( p)
( x*) 0 则 xn1 ( xn )
p阶收敛
p
| xn x* | ( p) | xn1 x* || ( xn ) ( x*) | | ( n ) | p! 其中, n 介于xn和x*之间.所以
300 200 100 0 -1 0 0 -2 0 0 -3 0 0 -6 -4 -2
( x) 20 /( x 10)
2
求导数, 得
2 2 ( x) 40x /( x 10)
0 x
2
4
6
显然,在x*附近
| ( x ) | 1 ( x ) 0
利用Lagrange中值定理, 有
| xn1 x* | ( p) ( p) lim lim | ( ) | | ( x*) | n p n | x x* | n n
由Taylor公式
故迭代法p阶收敛.
1阶收敛的数列{xn}的加速收敛算法
yn 2 ( xn 2 xn ) 2 xn 2 xn 2 2 xn1 xn

第2章非线性方程求根§2.1 引言§2.2 二分法§2.3 迭代法2.3.1 迭代格式2.3.2收敛性条件2.3.3迭代法的收敛阶２.4迭代收敛的加速§2.5 牛顿迭代法2.5.1 迭代格式2.5.2 迭代法的收敛阶x yo a b* x*解析解与数值解由推理的方法计算--- 解析解(精确解)。

近似计算（数值计算）---数值解(近似解）常借助于计算机工程实践中遇到最大量的将是数值计算问题。

2.1 引言*数值求解方程（组）的必要性“方程是很多工程和科学工作的发动机”.非线性现象广泛存在于物质世界与社会生活中.在工程和科学计算中，常涉及到非线性方程或非线性方程组的求解问题.例如：(1) 在光的衍射理论（the theory of diffraction of light)中,我们需要求x – tan x = 0 的根(2) 在行星轨道( planetary orbits)的计算中,对任意的a和b，我们需要求x –a sin x = b的根(3) 在数学中，需要求n 次多项式 sin 0,01x t x εε--=<<（4）在天体力学中，有如下开普勒（Kepler ）方程t x x t i t i x 其中 表示时间， 表示弧度，行星运动的轨道 是 的函数.也就是说，对每个时刻 ，上述方程 （运动轨道位置）.（超越方程）有唯一解 1110n n n n x a x a x a --++++=的根。

在非线性方程的求解中，多项式求根是最常见、最简单的情形，例如想通过矩阵的特征多项式求特征根，就会遇到这一问题.20(0) ax bx c a++=≠一元二次方程求根公式30x px q++=242b b acxa-±-⇒=一元三次方程求根公式根据代数基本定理，在复数域内，n 次代数多项式有且只有n个根，而由伽罗华（Galois）理论，5次以上（含5次）的多项式方程无求根公式，例如求代数方程652++--=x x x x632480的根.除了多项式求根之外，更多的是超越方程求根问题.超越方程是指包含指数函数、三角函数等特殊函数的方程.例如前面的几个例子又如求解非线性方程组 {0.7sin 0.2cos ,0.7cos 0.2sin .x x y y x y =+=-*x *()0f x *x f ()f x 上述这些问题，都归结为寻求非线性函数 使 . 称为方程或方程组（ 为向量函数时） 的零点.的根或函数 由于自然现象和实际问题的复杂性，对函数方程和方程组求解问题，没有哪一种方法能求出一般方程的准确解.因此，求其数值解就非常必要了.方程的根，即求本章主要内容：介绍用于实际计算中求 f (x) = 0 的根的近似值的几种常用方法。

解：设最多需要迭代n次。
∵要求精确到小数点后3位，
∴误差限≤ 12×10-3，
∴由定理2.1得：
n=
lg(1
0)
lg( lg 2
1 2
103 )
1
=
0
( lg 2 lg 2
3)
1
=
0.301 0.301
3
1= 10 .97
1
=10，即最多需要迭代10次。
用对分法求f(x)=0在某区间的单根，最多迭代次数与函数f(x)曲线形状无 关。一般情况下，对分法的最多迭代次数比其他的变步长逐步搜索法要 少，因此对分法是用得最多的变步长逐步搜索法。
if(f(b)==0) x=b;
else for(begin=a,end=a+h;begin<b;begin=end,end+=h)
{
if(end>b)end=b;
if(f(begin)==0)
{x=begin;break; }
if(f(begin)*f(end)<0)
{x=(begin+end)/2;break; }}
Y
N
x=begin;
break;
f(begin)*f(end)<0
Y
N
(end－begin)/2<=ε
Y
N
x=(begin+end)/2;
h/=hnumber;
break;
end=begin;
输出方程f(x)=0的根x。
8
2.3 根的搜索
变步长逐步搜索法对应的程序
#include <stdio.h> double f(double x);