第四章 方程求根的迭代法

数值分析

第 四 章

方程求根的迭代法

第四章 方程求根的迭代法引言 在科学研究和工程设计中, 经常会遇到的一大类问题是非 线性方程 f(x)=0 (4.1) 的求根问题，其中f(x)为非线性函数。 方程f(x)=0的根, 亦称为函数f(x)的零点 如果f(x)可以分解成 f ( x) ( x x * ) m g ( x) ,其中m为正整数 且 g ( x * ) 0 ,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。 当m=1时称x*为单根。若f(x)存在m阶导数,则是方程f(x)的m重 根(m>1) 当且仅当

f ( x * ) f ( x * ) fSchool of Automation Engineering

( m 1)

( x * ) 0, f

( m)

( x* ) 0

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

当f(x)不是x的线性函数时，称对应的函数方程为非线性方 程。如果f(x)是多项式函数，则称为代数方程，否则称为超越

方程(三角方程，指数、对数方程等)。一般称n次多项式构 成的方程

a n x n a n 1 x n 1 a1 x a0 0

(a n 0)

为n次代数方程,当n>1时,方程显然是非线性的。 一般稍微复杂的3次以上的代数方程或超越方程,很难甚至 无法求得精确解。本章将介绍常用的求解非线性方程的近似 根的几种数值解法 。

School of Automation Engineering 记笔记

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

通常方程根的数值解法大致分为三个步骤进行 ① 判定根的存在性。即方程有没有根？如果有根，有几个根？ ② 确定根的分布范围。即将每一个根用区间隔离开来，这 个过程实际上是获得方程各根的初始近似值。 ③ 根的精确化。将根的初始近似值按某种方法逐步精确化， 直到满足预先要求的精度为止

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

本章介绍方程的迭代解法，它既可以用来求解代数方程， 也可以用来解超越方程，并且仅限于求方程的实根。

运用迭代法求解方程的根应解决以下两个问题：

确定根的初值;

将进一步精确化到所需要的精度。

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章 4.1 二分法

方程求根的迭代法

二分法又称二分区间法,是求解方程(4.1)的近似根的一种 常用的简单方法。 设函数f(x)在闭区间[a,b]上连续,且f(a)f(b)<0,根据连续函 数的性质可知, f(x)= 0在(a,b)内必有实根,称区间[a,b]为有根区 间。为明确起见,假定方程f(x)=0在区间[a,b]内有惟一实根x*。 二分法的基本思想是: 首先确定有根区间,将区间二等分, 通过判断f(x)的符号, 逐步将有根区间缩小, 直至有根区间足够 地小, 便可求出满足精度要求的近似根。

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章4.1.1确定有根区间的方法

方程求根

的迭代法

为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。 对于代数方程，其根的个数(实或复的)与其次数

相同。至于超越方程，其根可能是一个、几个或无解，并没有什么固定的圈根方法。

求方程根的问题，就几何上讲,是求曲线 y=f (x)与

x轴交点的横坐标。School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

由高等数学知识知, 设f (x)为区间[a,b]上的单值连续, 如果 f (a)· (b)<0 , 则[a,b]中至少有一个实根。如果f (x)在[a,b]上 f 还是单调地递增或递减，则仅有一个实根。 y y=f(x) a b x

由此可大体确定根所在子区间，方法有： (1) 画图法 (2) 逐步搜索法 记笔记自 动 化 工 程 学 院

School of Automation Engineering

数值分析

第 四 章(1) 画图法

方程求根的迭代法

画出y = f (x)的略图，从而看出曲线与x轴交点的大致位臵。 也可将f (x) = 0分解为 1(x)= 2(x)的形式， 1(x) 与 2(x)两曲线交点的横坐标所在的子区间即为含根 区间。 例如 xlogx-1= 0 可以改写为logx=1/x 画出对数曲线y=logx,与双曲线y= 1/x,它们交点的横坐标 位于区间[2,3]内

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章(1) 画图法

方程求根的迭代法

y

1 y x

y gx0 2 3 x自 动 化 工 程 学 院

School of Automation Engineering

数值分析

第 四 章(1) 画图法

方程求根的迭代法

对于某些看不清根的函数，可以扩大一下曲线

y y=kf(x) y=f(x)

0

x

School of Automation Engineering

记笔记

自 动 化 工 程 学 院

数值分析

第 四 章 (2) 逐步搜索法

方程求根的迭代法

对于给定的f (x),设有根区间为[A,B],从x0=A出发,以步长 h=(B-A)/n(n是正整数),在[A,B]内取定节点:xi=x0+ih (i=0,1,2,…,n),从左至右检查f (xi)的符号,如发现xi与端点x0的函 数值异号,则得到一个缩小的有根子区间[xi-1,xi]。y

0

A

B a1 b1 a2 b2

x

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

例4.1 方程f(x)=x3-x-1=0 确定其有根区间 解：用试凑的方法，不难发现 f(0)<0 f(2)>0 在区间(0,2)内至少有一个实根 设从x=0出发,取h=0.5为步长向右进行根的

搜索,列表如下0 0.5 – – 1.0 – 1.5 + 2 +

f(x)

可以看出，在[1.0,1.5]内必有一根。School of Automation Engineering

x

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

用逐步搜索法进行实根隔离的关键是选取步长h。 要选择适当h ,使之既能把根隔离开来，工作量 又不太大。

为获取指定精度要求的初值,可在以上隔离根的 基础上采用对分法继续缩小该含根子区间。

二

分法可以看作是搜索法的一种改进。

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

4.2.2 二分法求根过程 设方程f(x)=0在区间[a,b]内有根,二分法就是逐步收缩有根 区间，最后得出所求的根。具体过程如下 :① 取有根区间[a,b]之中点, 将它分为两半,分点x0 a b ,这样就 2

可缩小有根区间y y=f(x)

y=f(x)

x* a a1 a2 x1 x* x0 b1 b2 b a x0 a1 x1 a2 b b1 b2

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

② 对压缩了的有根区间 a1 , b1 施行同样的手法, 即取中点 a b x1 1 1 ,将区间 a1 , b1 再分为两半,然后再确定有根区间 2 a2 ,b2 ,其长度是 a1 , b1 的二分之一。 ③ 如此反复下去,若不出现 f ( xk ) 0 ,即可得出一系列有根 区间序列：

a, b a1 , b1 a 2 , b2 ak , bk 上述每个区间都是前一个区间的一半,因此 ak , bk 的长度1 1 bk a k (bk 1 a k 1 ) k (b a ) 2 2

当k→∞时趋于零,这些区间最终收敛于一点x* 即为所求的根 。

School of Automation Engineering

自 动 化 工 程 学 院

数值分析

第 四 章

方程求根的迭代法

每次二分后,取有根区间 ak , bk 的中点 xk 1 (ak bk )作为根的近似值，得到一个近似根的序列2

x0 , x1 , x 2 , , x k , 该序列以根x*为极限。* 只要二分足够多次(即k足够大),便有 x x k

x * a k , bk ,则 这里ε为给定精度,由于

x xk*

bk a k b a bk 1 a k 1 k 1 2 2School of Automation Engineering

bk a k b a k 1 2 2

自 动 化 工 程 学 院