第2章 非线形方程及其非线性方程组解法

数值分析课件

第二章 方程(组)的迭代解法§1 §2 §3 §4 §5 §6 引言 迭代解法 迭代公式的改进 联立方程组的迭代解法 联立方程组的延拓解法 联立方程组的牛顿解法

数值分析课件

§11.1 涉及到的概念

引言

求 f (x) = 0 的根

如三角函数, 指数函数的 复合函数等

f (x)既可以是代数多项式,也可以是超越函数f(x)=a0xn+a1xn-1+ … + an-1x+ an (a0≠0)

方程的根: 满足f(x)=0的x 重根和单根:如果f(x)=(x- )mg(x)且g( )≠0, 则称 为f(x)=0的m重根.m=1称为单根,m>1称 2 为重根.

数值分析课件

§1

引言

1.2 本章重点 介绍求方程实根的迭代解法(适用于求解代 数方程和超越方程)

代数方程:根的个数与其最高次数相同,有 成熟的圈定根的方法 超越方程:可能有一个,几个根或者无解,无 固定的圈定根的方法3

数值分析课件

§2

迭代解法

1 本节重点(关键问题) 根的初值的确定方法； 迭代法的求解过程

迭代法的收敛性 迭代序列的误差估计

数值分析课件

§2 迭代解法2.1 根的初值确定方法 求根的具体步骤为: 确定根的初值x0 将x0进一步精确到所需要的精度求方程根的几何意义:求曲线y=f (x)与x轴交点 的横坐标。5

数值分析课件

2.1 根的初值确定方法定理2.1 设f (x)为区间[a,b]上的单值连续函数

如果: f (a)· (b)<0 f (2.1) 则: [a,b]中至少有一个实根。 如果:f (x)在[a,b]上还是单调地递增或递减，则:仅有一个实根(有单根的条件)

a

b

数值分析课件

2.1 根的初值确定方法2.1.1 画图法 1.具体步骤 画出y = f (x)的略图,从而看出曲线与x轴 交点的大致位臵。 也可将f (x) = 0分解为 1(x)= 2(x)的形式, 1(x)与 2(x)两曲线交点的横坐标所在的子 区间即为含根区间.

数值分析课件

2.1 根的初值确定方法2.1.1 画图法 2.实例 已知:f (x)=x㏒x –1 = 0;求根的初值范围

解:(1)可以改写为:㏒x=1/x (2)画出对数曲线y=㏒x,与双曲线y= 1/x, 它们交点的横坐标位于区间[2,3]内

数值分析课件

2.1 根的初值确定方法2.1.1 画图法yy 1 x

y gx0

1

2 3

x9

数值分析课件

2.1 根的初值确定方法2.1.2 扫描法 1.原理对于给定的f (x),设有根区间为[A,B],从x0=A出发， 以步长h=(B-A)/n(n是正整数),在[A,B]内取定节点： xi=x0+ih (i=0,1,2,…,n),从左至右检查f (xi)的 符号，如发现xi与端点xi-1的函数值异号，则得到一个 缩小的有根子区间[xi-1,xi]。 关键是选取步长h h太小，资源耗费大； h过大，可能遗漏根。10

数值分析课件

2.1 根的初值确定方法2.1.3 对分(二分)法 1.具体步骤设[xk-1,xk]为含根子区间，初值对于根的误差要 求为ε,令a= xk-1,b= xk,计算出f (a),f (b)后,进行如下: Begin: 取[a,b]的中点r=(a+b)/2,计算f(r) 若f(r)· f(a)>0,取a=r;否则取b=r 若b-a>ε,转向Begin;否则结束

数值分析课件

2.1 根的初值确定方法2.1.3 对分(二分)法

a

x1 x* a x2 b

b

数值分析课件

2.1 根的初

值确定方法2.1.3 对分(二分)法

数值分析课件

误差 分析：第1步产生的x1

a b 2

有误差

|x 1 x*|

b a 2k

第 k 步产生的 xk 有误差 ε k

|x k x*|

b a 2

对于给定的精度 ,可估计二分法所需的步数 k : ln b a ln ε b a2k

ln 2

①简单; ② 对f (x) 要求不高(只要连续即可) .①无法求复根及偶重根 ② 收敛慢 注：用二分法求根，最好先给出 f (x) 草图以确定根的大 概位臵。或用搜索程序，将[a, b]分为若干小区间，对每一 个满足 f (ak)· (bk) < 0 的区间调用二分法程序，可找出区 f 14 间[a, b]内的多个根，且不必要求 f (a)· (b) < 0 。 f

数值分析课件

2.2 迭代法的求解过程思路:f (x) = 0f (x) 的根 等价变换

x = φ(x)φ(x) 的不动点迭代函数

2.2.1 建立迭代公式

由公式f(x)=0出发将其分解为等价形式x=φ(x) 例如：f(x)=x3+2x2-4=0 可以分解为:

x=x+ f(x) =x3+2x2+x-4;x=2(1/(2+x))1/2

x=x-(x3+2x2-4)/(3x2-4x)

数值分析课件

2.2 迭代法的求解过程2.2.2 迭代解法(简单迭代法)由初值x0出发,按迭代函数xn+1= φ(xn) (n=0,1,2,…) 进行计算 x0 , x1,x2,…,xn ,称为迭代序列； 迭代公式 迭代序列的值相应地称为根的0次,1次,2次,…,n次 近似值； 序列的计算过程称为迭代过程； 如果序列x0 , x1 , x2 ,… 收敛于 ,即 lim x n n 则 为方程的根. 证明： lim x n 1 lim ( x n ) ( lim x n ) n n n ( )16

数值分析课件

2.2 迭代法的求解过程例2.2:用迭代法求方程 f(x)=x3-x-1=0 在x=1.5附近 的根，要求根的近似值稳定至小数点后5位.

解: (1)将方程改写为 x=(1+x)1/3

x0=1.5

(2)按上式建立迭代公式 xn+1=(1+xn)1/3 (3)取x0=1.5逐次迭代得: x1=1.35721,x2=1.33086, x3=1.32588, x4=1.32494,x5=1.32476,x6=1.32473, x7=1.32472,x8=1.32472 (4)最后取稳定至小数后5位的迭代值 x8 =1.32472为方程的根17

数值分析课件

y p1 p0

y=x y= φ(x)

y p0

y=x

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

p1 y= φ(x) x x1 y=x

p0 p1

x x0 x*

p1

x 18

x1 x0 x*

x1

数值分析课件

2.3 迭代法的收敛性1.影响迭代法收敛性的要素 迭代函数在根附近的性态 初值的选取范围 局部收敛方法 比大范围收敛 方法收敛得快

2. 迭代法收敛的类型

大范围收敛:从任何可取的初值出发都能保证 收敛 局部收敛:为了保证收敛性必须选取初值充分 接近于所要求的根 注：这里讨论迭代法的收敛性时，均指的是局部 收敛性19