文档介绍：第6章方程和方程组的迭代法
现代科技领域或工程技术的许多实际问题,常常可以归结为求解函数方程:
上述方程可能是代数方程,也可能是超越方程。
①当f(x) 为代数方程(多项式)时,理论上已经证明,
大于五次的多项式一般没有代数解法。
②当f(x) 为超越方程时,一般不能用代数方法求其根。
所以,对于一般的方程(6-1),只能用数值方法求解。
本章主要介绍二分法、切线法、弦切法、迭代法。
(6-1)
§ 方程求根数值法
二分法
二分法是方程求根最常用而且也是最保险的方法之一。
一、基本思想
将区间对分,保留有根的区间,舍去无根的区间。如此往复,以逐步逼近方程的根。
二、算法分析
第一步:将[a, b]对分,即[a, x0]和[x0, b],x0=(a+b)/2。若 f(a)f(x0)<0,则根x*∈(a, x0),并令 a1=a, b1=x0;若 f(x0)f(b)<0, 则根x*∈( x0,b),并令 a1 =x0, b1 =b 。
第二步:将[a1, b1]再对分,即[a1, x0]和[x0, b1],x1=(a1 + b1)/2。若 f(a1)f(x1)<0,则根x*∈(a1, x1),并令 a2 = a1, b2 =x1;若 f(x0)f(b1)<0,则根x*∈( x1, b1)并令a2 =x1, b1= b1
…。直到满足精度要求为止,这样便得到一系列的对分结果系列:
§ 方程求根数值法
三、程序框图与程序语言设计
subroutine bisect
a1=a,b1=b
x0=a1+b1/2
comp f(a1),f(b1)
f(a1)f(b1)<0?
end sub
abs(f(x0))<E?
comp f(a1),f(x0)
f(a1)f(x0))<0?
end sub
b1=x0
a1=x0
N
Y
Y
N
N
Y
图6-1 二分法程序框图
§ 方程求根数值法
10 subroutine bisect(a,b,E,x0)
20 a1=a;b1=b
30 if(f(a1)*f(b1)<0) then
40 x0=(a1+b1)/2
50 if(abs(f(x0)>E) then
60 if (f(a1)*f(x0)<0) then
70 b1=x0
80 else
90 a1=x0
100 endif
110 goto 40
120 endif
130 endif
140 end subroutine bisect
§ 方程求根数值法
简单迭代法
一、算法分析
将方程(6-1)改写成等价形式,则自然希望使用相同的公式
若给定根的一个初始近似值,则由迭代式(6-2)式可以计算得一系列的值: 。利用(6-2)式求根近似值的方法称为简单迭代法。称为迭代序列, 称为迭代函数,上式称为迭代格式。显然,如果极限存在,那么必定有成立,即就是方程(6-1)式的根。
(6-2)
§ 方程求根数值法
例6-1 用简单迭代法求方程在1附近的根。
解:将原方程变形为如下的等价形式:
作迭代格式
取,迭代得
§ 方程求根数值法
可见经过四次迭代,方程的根的近似值已经精确到小数点后第六位,第五次以后的迭代值则不在改变。所以原方程的近似根为。
对于本题,若作迭代格式
取,迭代得
随着k的增大也增大,而且不不趋向于任何极限值,这时迭代过程是发散的。
§ 方程求根数值法
从以上2种解法来看,迭代序列是否收敛或收敛快慢的问题与选取迭代函数g(x)有关。下面研究如何相关。
先看迭代法的几何意义。
图6-2 迭代法几何意义
在直解坐标系中同时作y=x 和y=g(x)两条曲线,如图6-2所示,则这两条曲线的交点的横坐标就是方程式(6-2)式的根。也就是方程式()式的根。迭代法(6-2)由求,相当于过曲线上作水平线与直线y=x相交,过
§ 方程求根数值法
交点作x轴的垂线,此时垂足至原点距离等于,故垂足横坐标为。由图可见,曲线斜率时迭代序列收敛,且越小收敛越快;反之,若,则迭代序列发散。于是有如下条件。
设迭代函数g(x)为定义在区间[a,b]上的连续函数,且对任意属于该区间内的x都有g(x)也属于该区间,即
成立→也成立,那么在区间[a,b]内必有下式成立:
式(6-3)就是迭代函数g(x)收敛的充分必要条件。
(6-3)
§ 方程求根数值法
二、程序框图与程序语言设计
subroutine suppo
i=i+1
comp g(x),f(x)
abs(f(x))>E?
end sub
N
Y
10 subroutine suppo(x0,E,x)