数值分析方程求根的迭代法

数值分析方程求根的迭代法第1页，课件共43页，创作于2023年2月远在公元前1700年的古巴比伦人就已有关于一、二次方程的解法。《九章算术》(公元前50~100年)其中“方程术”有联立一次方程组的一般解法。1535年意大利数学家坦特格里亚(TorTaglia)发现了三次方程的解法，卡当(H·Cardano)从他那里得到了这种解法，于1545年在其名著《大法》中公布了三次方程的公式解，称为卡当算法。后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。第2页，课件共43页，创作于2023年2月1799年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理n次代数方程必有n个实根或复根。但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到18世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。但求解五次方程时未能如愿,开始意识到有潜藏其中的奥妙,用现代术语表示就是置换群理论问题。在继续探索5次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔(N·Abel1802-1829)1824年阿贝尔发表了“五次方程代数解法不可能存在”的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。第3页，课件共43页，创作于2023年2月1828年17岁的法国数学家伽罗华(E·Galois1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。1830年伽罗华再进科学院递稿，得到泊松院士的判词“完全不能理解”。后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于1832年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。第4页，课件共43页，创作于2023年2月十四年后，法国数学家刘维尔(J·Liouville)整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。38年后，即1870年，法国数学家若当(C·Jordan)在专著《论置换与代数方程》中阐发了伽罗华的思想，一门现代数学的分支—群论诞生了。在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。第5页，课件共43页，创作于2023年2月

在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。第6页，课件共43页，创作于2023年2月4.1方程求根与二分法4.1.1引言（1.1）单变量非线性方程的一般形式其中也可以是无穷区间.f(x)是高次多项式函数或超越函数（1.2）

如果函数是多项式函数，即其中为实数，则称方程(1.1)为次代数方程.超越函数不能表示为多项式的函数如(x)=3x5-2x4+8x2-7x+1(x)=e2x+1-xln(sinx)-2高次代数方程超越方程第7页，课件共43页，创作于2023年2月

若是的重零点，且充分光滑，则

次方程在复数域有且只有个根（含重根，重根为个根）.超越方程它在整个轴上有无穷多个解，若取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调的定义域，即的求解区间

如果实数满足，则称是方程(1.1)的根，或称是的零点.若可分解为其中为正整数，且则称为方程(1.1)的重根，或为的重零点，时为单根.结论第8页，课件共43页，创作于2023年2月通常方程根的数值解法大致分为三个步骤进行：非线性问题一般不存在直接的求解公式，要使用迭代法.本章将介绍常用的求解非线性方程的近似根的几种数值解法①

判定根的存在性。即方程有没有根？如果有根，有几个根？②确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。③根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止.第9页，课件共43页，创作于2023年2月如何求方程的有根区间？

设f(x)∈C[a,b],且

f(a)f(b)<0,存在ξ∈(a,b)，使f(ξ)=0.根的存在性定理——闭区间上连续函数的介值定理有根区间如果f(x)在[a,b]上还是单调递增或递减的，则f(x)=0仅有一个实根。(1)描图法

画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0等价变形为g1(x)=g2(x)的形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所在的子区间即为含根区间。例1

求方程3x-1-cosx=0的有根区间。方程等价变形为3x-1=cosx，y=3x-1与y=cosx的图像只有一个交点位于[0.5，1]内。第10页，课件共43页，创作于2023年2月对的根进行搜索计算，

例2

求方程的有根区间.由此可知方程的有根区间为(2)逐步搜索法

先确定方程f(x)=0的所有实根所在的区间为[a,b],从x0=a出发,以步长

h=(b-a)/n

其中n是正整数，在[a,b]内取定节点：

xi=x0＋ih(i=0,1,2，……，n)

计算f(xi)的值,依据函数值异号及实根的个数确定有根区间,通过调整步长，总可找到所有有根区间。

解

第11页，课件共43页，创作于2023年2月4.1.2二分法求解方程f(x)=0的近似根的一种常用的简单方法。原理基本思想设函数f(x)在闭区间[a,b]上连续,且f(a)f(b)<0,则f(x)=0在(a,b)内必有实根区间。逐步将区间二等分,通过判断区间端点f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。具体做法第12页，课件共43页，创作于2023年2月以此类推由二分法的过程知(1)(2)(3)作为根的近似可得一个近似根的序列

第13页，课件共43页，创作于2023年2月（1.3）且(4)只要二分足够多次（即充分大），便有这里为预定的精度.要使解：例3用二分法求方程在区间上的根，误差限为，问至少需对分多少次？第14页，课件共43页，创作于2023年2月二分法的算法

步骤1准备

计算在有根区间端点处的值

步骤2二分

计算在区间中点处的值

步骤3判断

若，则即是根，计算过程结束，否则检验.

若，则以代替，否则以代替.此时中点即为所求近似根.误差，

反复执行步骤2和步骤3，直到区间长度小于允许第15页，课件共43页，创作于2023年2月第16页，课件共43页，创作于2023年2月例4

求方程在区间内的一个实根，要求准确到小数点后第2位.欲使只需，即只要二分6次，便能达到预定的精度.

解得到新的有根区间第17页，课件共43页，创作于2023年2月二分法对多个零点的情况，只能算出其中一个零点。

即使f(x)在[a,b]上有零点，也未必有f(a)f(b)<0。

不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单。优点缺点注：用二分法求根，最好先给出f(x)

草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。第18页，课件共43页，创作于2023年2月迭代法的基本思想基本思路同解迭代公式给定初值存在等价于迭代函数？转换是否唯一几何意义第19页，课件共43页，创作于2023年2月转换例子(1)x=1(x)=x3-6x2+10x-2;(2)

;(3)

;(4)

;例：已知方程

x3-6x2+9x-2=0

在

[3,4]

内有一根，考虑迭代？哪种转换方法好第20页，课件共43页，创作于2023年2月几何含义xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1第21页，课件共43页，创作于2023年2月几何含义xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1第22页，课件共43页，创作于2023年2月压缩映像定理定理设(x)C[a,b]

且可导，若(2)0L<1，使得|’(x)|L

对x[a,b]

成立(1)a(x)b对一切x[a,b]

都成立则有(a)对任意x0[a,b]，由

xk+1

=

(xk)

产生的迭代序列均收敛到(x)在[a,b]

中的唯一不动点x*。(b)有如下的误差估计可用|xk+1-xk

|来控制收敛精度L

越小收敛越快第23页，课件共43页，创作于2023年2月压缩映像定理证明(a)由压缩映像定理可知，不动点x*

存在且唯一。第24页，课件共43页，创作于2023年2月压缩映像定理证明(b)又第25页，课件共43页，创作于2023年2月全局收敛与局部收敛

定理的条件保证了不动点迭代的全局收敛性。即迭代的收敛性与初始点的选取无关。

这种在x*的邻域内具有的收敛性称为局部收敛性。定理中的条件|’(x)|L

<1可以适当放宽(2’)’(x)

在x*

的某个邻域内连续，且|’(x*)|<1由’(x)

的连续性及|’(x*)|<1即可推出：存在x*的某个

邻域

N(x*)

=[x*-,x*+],

使得对

xN(x*)都有|’(x)|L

<1,则由x0N(x*)开始的迭代都收敛。第26页，课件共43页，创作于2023年2月迭代过程的收敛速度定义则称该迭代为r阶收敛。(1)当r=1时称为线性收敛，此时C<1；(2)当r=2时称为二次收敛，或平方收敛；(3)当r>1时称为超线性收敛。

二分法线性收敛

不动点迭代中，若

’(x*)0，则取极限得(C为常数)线性收敛第27页，课件共43页，创作于2023年2月P阶收敛设迭代xk+1=(xk)

，若(p)(x)

在x*的某邻域内连续，则该迭代法具有p阶收敛的充要条件是定理并且有证明：充分性.根据泰勒展开有第28页，课件共43页，创作于2023年2月必要性的证明必要性.设迭代xk+1=(xk)是p阶收敛。迭代两边取极限

，由(x)的连续性可知x*=(x*)

。设p0是满足的最小正整数。由充分性的证明过程可知迭代p0阶收敛。又若

p0<p，

与迭代p

阶收敛矛盾p0=p第29页，课件共43页，创作于2023年2月迭代过程的加速

设有不动点迭代：设：缺点：每次迭代需计算第30页，课件共43页，创作于2023年2月埃特金算法设：Aitken加速当x

收敛到x*时，修正项分子趋于零。

第31页，课件共43页，创作于2023年2月一点注记第32页，课件共43页，创作于2023年2月Newton迭代

基本思想：将非线性方程线性化设xk

是f(x)=0

的近似根，将f(x)

在

xk

一阶Taylor展开:，在xk

和x

之间。xyx*xkxk+1条件：

f’(x)0第33页，课件共43页，创作于2023年2月Newton迭代

Newton法可以看作下面的不动点迭代：其中’(x*)=0Newton法至少二阶局部收敛定理

设f(x)

在其零点x*的某个邻域内二阶连续可导且f’(x)0，则存在

x*的某个

邻域

N(x*)

=[x*-,x*+],

使得对

x0N(x*)，Newton法产生的序列以不低于二阶的收敛速度收敛到x*

。第34页，课件共43页，创作于2023年2月Newton迭代

Newton法也可以看作一类特殊的加速迭代取(x)=x+f(x)第35页，课件共43页，创作于2023年2月收敛性定理定理设f

C2[a,b]，且

f

满足(1)f(a)f(b)<0(2)对

x[a,b]，f’(x)0

且f”(x)

0

；(3)初始点x0

[a,b]

满足f(x0)f”(x0)>0；则Newton法产生的序列收敛到f在[a,b]

的唯一零点x*。第36页，课件共43页，创作于2023年2月全局收敛性定理定理设f

C2[a,b]，且

f

满足(1)f(a)f(b)<0(2)对

x[a,b]，f’(x)0

且f”(x)

0

；则对任意初始点x0

[a,b]，Newton法产生的序列收敛到f在[a,b]

的唯一零点x*。(3)第37页，课件共43页，创作于2023年2月举例（一）例：设计一个二阶收敛算法计算(a>0)。解：转化为求x2-a=0的正根Newton迭代：二阶收敛第38页，课件共43页，创作于2023年2月重根情形

设x*

是f(x)

的m(m2)

重根，Newton法是否收敛？Tay