数值分析二分法迭代法及收敛性

数值分析二分法迭代法及收敛性第一页，共三十二页，编辑于2023年，星期六3.1.1引言本章主要讨论单变量非线性方程

f(x)=0

(1.1)的求根问题，这里x∈R,f(x)∈C[a,b].在科学与工程计算中有大量方程求根问题，其中一类特殊的问题是多项式方程其中系数ai(i=0,1,,n)为实数.3.1方程求根与二分法第二页，共三十二页，编辑于2023年，星期六

n=1,2时方程的根是大家熟悉的，n=3,4时虽有求根公式但比较复杂，可在数学手册中查到，但已不适合数值计算，而n≥5时就不能用公式表示方程的根.因此，通常对n≥3的多项式方程求根与一般连续函数方程(1.1)一样都可采用迭代法求根.第三页，共三十二页，编辑于2023年，星期六方程f(x)=0的根x*，又称为函数f(x)的零点，它使得f(x*)=0，若f(x)可分解为f(x)=(x-x*)mg(x)，其中m为正整数，且g(x*)≠0.当m=1时，则称x*为单根，若m>1称x*为(1.1)的m重根，或x*为函数f(x)的m重零点.若x*是f(x)的m重零点，则注：第四页，共三十二页，编辑于2023年，星期六3.1.2二分法如果f(x)在区间[a,b]上连续,f(a)·f(b)<0,则在[a,b]

内有方程的根.（BisectionMethod）二分法原理第五页，共三十二页，编辑于2023年，星期六二分法的实施过程取[a,b]的中点

将区间一分为二.若f(x0)=0,则x0就是方程的根,否则判别根x*在x0

的左侧还是右侧.若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)均为新的有根区间,它的长度只有原有根区间长度的一半,达到了压缩有根区间的目的.第六页，共三十二页，编辑于2023年，星期六如此反复进行,即可的一系列有根区间套

由于每一区间都是前一区间的一半，因此区间[an,bn]的长度为若每次二分时所取区间中点都不是根，则上述过程将无限进行下去.当

n→∞

时，区间必将最终收缩为一点x*

，显然x*就是所求的根.第七页，共三十二页，编辑于2023年，星期六

若取区间[an,bn]的中点作为x*的近似值，则有下述误差估计式只要

n

足够大,(即区间二分次数足够多)，误差就可足够小.二分法的误差估计第八页，共三十二页，编辑于2023年，星期六例1用二分法求方程

f(x)=x3-x-1=0在(1,1.5)的实根,要求误差不超过0.005.

解由题设条件，即：则要|x*-xn|≤0.005由此解得取n=6,按二分法计算过程见下表,x6=1.3242

为所求之近似根.第九页，共三十二页，编辑于2023年，星期六nanbnxnf(xn)说明01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3242-+-++--(1)f(a)<0,

f(b)>0(2)根据精度要求，取到小数点后四位即可.

二分法的优点是算法简单，且总是收敛的，缺点是收敛的太慢，故一般不单独将其用于求根，只是用其为根求得一个较好的近似值.第十页，共三十二页，编辑于2023年，星期六二分法的计算步骤:

步骤1准备计算函数f(x)在区间[a,b]端点处的值f(a),

f(b).

若f(a)·f((a+b)/2)<0,则以(a+b)/2代替b

，否则以(a+b)/2代替a.

步骤2二分计算函数f(x)在区间中点(a+b)/2处的值f((a+b)/2).

步骤3判断若f((a+b)/2)=0，则(a+b)/2即是根，计算过程结束，否则检验.

反复执行步骤2和步骤3，直到区间[a,b]长度小于允许误差ε，此时中点(a+b)/2即为所求近似根.第十一页，共三十二页，编辑于2023年，星期六3.2迭代法及其收敛性3.2.1不动点迭代法

将方程f(x)=0改写为等价方程形式

x=(x).(2.1)若要求x*满足f(x*)=0，则x*=(x*)；反之亦然，称x*为函数(x)的一个不动点.求f(x)的零点就等于求(x)的不动点，选择一个初始近似值x0，将它代入(2.1)右端，即可求得

x1=(x0).第十二页，共三十二页，编辑于2023年，星期六可以如此反复迭代计算xk+1=(xk)

(k=0,1,2,).(2.2)

(x)称为迭代函数.如果对任何x0∈[a,b]，由(2.2)得到的序列{xk}有极限则称迭代方程(2.2)收敛.且x*=(x*)为(x)的不动点，故称(2.2)为不动点迭代法.第十三页，共三十二页，编辑于2023年，星期六当(x)连续时，显然x*就是方程x=(x)之根(不动点).于是可以从数列{xk}中求得满足精度要求的近似根.这种求根方法称为不动点迭代法,称为迭代格式,(x)称为迭代函数,x0

称为迭代初值,数列{xk}称为迭代序列.如果迭代序列收敛,则称迭代格式收敛,否则称为发散.第十四页，共三十二页，编辑于2023年，星期六分别按以上三种形式建立迭代公式，并取x0=1进行迭代计算，结果如下：

解对方程进行如下三种变形：例2

用迭代法求方程x4+2x2-x-3=0

在区间[1,1.2]内的实根.第十五页，共三十二页，编辑于2023年，星期六准确根x*

=1.124123029,可见迭代公式不同,收敛情况也不同.第二种公式比第一种公式收敛快得多,而第三种公式不收敛.第十六页，共三十二页，编辑于2023年，星期六xyoy=(x)y=x解x=(x)求y=x

与y=(x)的交点的横坐标x*x0(x0,x1)(x1,x2)(x1,x1)x1x2迭代法的几何意义第十七页，共三十二页，编辑于2023年，星期六xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1第十八页，共三十二页，编辑于2023年，星期六注：迭代法的研究涉及四个问题：(1)迭代公式的选取；(2)迭代公式收敛性的判定；(3)在收敛情况下，如何比较收敛速度；(4)迭代停止的条件。第十九页，共三十二页，编辑于2023年，星期六3.2.2不动点的存在性与迭代法的收敛性

首先考察(x)在[a,b]上不动点的存在唯一性.

定理1

设(x)∈C[a,b]满足以下两个条件：

1º对任意x∈[a,b]有a≤(x)≤b.

2º存在正数L<1，使对任意x,y∈[a,b]都有则(x)在[a,b]上存在唯一的不动点x*.

证明

先证不动点的存在性.

若(a)=a或(b)=b，显然(x)在[a,b]上存在不动点.因为a≤(x)≤b，以下设(a)>a及(b)<b定义函数第二十页，共三十二页，编辑于2023年，星期六显然f(x)∈C[a,b],且满足f(a)=(a)-a>0,f(b)=(b)-b<0,由连续函数性质可知存在x*∈(a,b)使f(x*)=0，即x*=(x*)，x*即为(x)的不动点.

再证不动点的唯一性.设x1*,x2*∈[a,b]都是(x)的不动点，则由(2.4)得引出矛盾，故(x)的不动点只能是唯一的.

证毕.第二十一页，共三十二页，编辑于2023年，星期六

定理2

设(x)∈C[a,b]满足定理1中的两个条件，则对任意x0∈[a,b]，由(2.2)得到的迭代序列{xk}收敛到不动点x*，并有误差估计式

证明设x*∈[a,b]是(x)在[a,b]上的唯一不动点,由条件1º，可知{xk}∈[a,b]，再由(2.4)得因0<L<1，故当k→∞时序列{xk}收敛到x*.第二十二页，共三十二页，编辑于2023年，星期六下面证明估计式(2.5)，由(2.4)有于是对任意正整数p有上述令p→∞,注意到limxk+p=x*(p→∞)即得(2.5)式.第二十三页，共三十二页，编辑于2023年，星期六又由于对任意正整数p有上述令p→∞,及limxk+p=x*(p→∞)即得(2.6)式.证毕.注：误差估计式(2.5)原则上确定迭代次数，但它由于含有信息L而不便于实际应用.而误差估计式(2.6)是实用的，只要相邻两次计算结果的偏差足够小即可保证近似值xk具有足够精度.第二十四页，共三十二页，编辑于2023年，星期六注：

对定理1和定理2中的条件2º可以改为导数，即在使用时如果(x)∈C[a,b]且对任意x∈[a,b]有则由微分中值定理可知对任意x,y∈[a,b]有故定理中的条件2º是成立的.

第二十五页，共三十二页，编辑于2023年，星期六例如，在前面例2中采用的三种迭代公式，在有根区间(1,1.2)内，有故前两个迭代公式收敛，第三个迭代公式不收敛.第二十六页，共三十二页，编辑于2023年，星期六3.2.3局部收敛性与收敛阶

上面给出了迭代序列{xk}在区间[a,b]上的收敛性,通常称为全局收敛性.有时不易检验定理的条件，实际应用时通常只在不动点x*的邻近考察其收敛性，即局部收敛性.

定义1

设(x)有不动点x*，如果存在x*的某个邻域U:|x-x*|≤δ，对任意x0∈U，迭代公式(2.2)产生的序列{xk}∈U，且收敛到x*，则称迭代法(2.2)局部收敛.

第二十七页，共三十二页，编辑于2023年，星期六

定理3

设x*为(x)的不动点，在x*的某个邻域连续，且，则迭代法(2.2)局部收敛.

证明由连续函数的性质，存在不动点x*的某个邻域U:|x-x*|≤δ，使对于任意x∈U成立此外，对于任意x∈U，总有(x)∈U，这是因为于是依据定理2可以断定迭代过程xk+1=(xk)对于任意初值x0∈U均收敛.证毕.第二十八页，共三十二页，编辑于2023年，星期六

例3

用不同迭代法求方程x2-3=0的根.

解

这里f(x)=

x2-3，可以改写为各种不同的等价形式x=(x)，其不动点为，由此构造不同的迭代法.第二十九页，共三十二页，编辑于2023年，星期六取x0=2,对上式4