《数值分析课件完整版第三章方程组的迭代解法》由会员分享，可在线阅读，更多相关《数值分析课件完整版第三章方程组的迭代解法（97页珍藏版）》请在金锄头文库上搜索。
1、3 方程（组）的迭代解法,3.1 引言,（3-1）,本章主要讨论求解单变量非线性方程,其中 也可以是无穷区间.,如果实数 满足 ，则称 是方程(3-1)的 根，或称 是 的零点.,1根的存在性。方程有没有根？如果有，有几个根？,2根的搜索。这些根大致在哪里？如何把根隔离开？,3根的精确化。,问题:,公元前1700年的古巴比伦人就已有关于一、二次方程的解法。 九章算术(公元前50100年)其中“方程术”有联立一次方程组的一般解法。 1535年意大利数学家尼柯洛 冯塔纳找到了一元三次方程一般形式的求根方法。这个成就，使他在几次公开的数学较量中大获全胜，从此名扬欧洲。但是冯塔纳不愿意将他的这个重要发
2、现公之于世.,当时的另一位意大利数学家兼医生卡尔丹诺，对冯塔纳的发现非常感兴趣。他几次诚恳地登门请教，希望获得冯塔纳的求根公式。 后来，冯塔纳终于用一种隐晦得如同咒语般的语言，把三次方程的解法“透露”给了卡尔丹诺。冯塔纳认为卡尔丹诺很难破解他的“咒语”，可是卡尔丹诺通过解三次方程的对比实践，很快就彻底破译了冯塔纳的秘密。,卡尔丹诺把冯塔纳的三次方程求根公式，写进了自己的学术著作大法中，但并未提到冯塔纳的名字。 由于第一个发表三次方程求根公式的人确实是卡尔丹诺，因此后人就把这种求解方法称为“卡尔丹诺公式”。,后来，卡尔丹诺的学生弗瑞里(Ferrari)又提出了四次方程的解法。 但对于五次方程求根
3、，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。 1828年17岁的法国数学家伽罗华(EGalois 1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的,文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。1830年伽罗华再进科学院递稿，得到泊松院士的判词“完全不能理解”。 后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于1832年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。,十四年后，法国数学家
4、刘维尔(JLiouville)整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。 38年后，即1870年，法国数学家若当(CJordan)在专著论置换与代数方程中阐发了伽罗华的思想，一门现代数学的分支 群论诞生了。 在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。,1.根的存在性,定理1：设函数 f (x) 在区间a, b上连续，如果f (a) f (b) 0， 则方程 f (x) = 0 在a, b内至少有一实根x*。,（3-1）,m重根,若,的 m重根或函数 的m重零点。,（3-1）,2. 根
5、的搜索,(1) 图解法（利用作图软件如 Matlab),(2) 扫描法（逐步搜索法）,(3) 二分法*,（1） (描)做图法,画出 y=f(x) 的草图, 由f(x)与横轴交点的大概位置来确定隔根区间; 或者利用导函数f(x)的正、负与函数f(x)的单调性的关系确定根的大概位置.,若f(x)比较复杂, 还可将方程f(x)=0化为一个等价方程(x)=(x), 则曲线y=(x)与y=(x)之交点A(x*,y*)的横坐标 x*即为原方程之根, 据此也可通过作图求得x*的隔根区间.,如求解方程 的近似根,方法1: 将方程同解变换成 然后画两条曲线,0,2,3,y,x,这两条曲线的交点的横座标大致为x=
6、2.5,x*,f(x),1画出 f(x) 的略图，从而看出曲线与x 轴交点的位置。,2从左端点x = a出发，按某个预先选定的步长h 一步一步地向右跨，每跨一步都检验每步起点x0 和终点x0 + h的函数值，若,那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h 作为根的初始近似。,(2) 扫描法（逐步搜索法）,例1：考察方程,（3） 二分法*（对分法）,设f(x)在区间a, b上连续, f(a)f(b)0, 则在a, b,内有方程的根. 取a, b的中点,将区间一分为二. 若 f (x0)=0, 则x0就是方程的根, 否则判别根 x*在 x0 的左侧还是右侧.,若f(a) f(x
7、0)0, 则x*(a, x0), 令 a1= a, b1=x0;,若f(x0) f(b)0, 则x*(x0 , b), 令 a1=x0, b1=b.,不论出现哪种情况, (a1, b1)均为新的有根区间, 它的长度只有原有根区间长度的一半, 达到了压缩有根区间的目的.,对压缩了的有根区间, 又可实行同样的步骤, 再压缩. 如此反复进行, 即可的一系列有根区间套,由于每一区间都是前一区间的一半，因此区间an , bn的长度为,若每次二分时所取区间中点都不是根，则上述过程将无限进行下去. 当 n 时，区间必将最终收缩为一点x* ，显然x*就是所求的根.,误差 分析：,第 k 步产生的 xk 有误差
8、,对于给定的精度 ,可估计二分法所需的步数 k ：,简单; 对f (x) 要求不高(只要连续即可) .,无法求复根及偶重根 收敛慢,2.由于在偶重根附近曲线 y=f(x) 为上凹或下凸, 即 f(a)与f(b)的符号相同, 因此不能用二分法求偶重根.,注： 1.用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。,二分法的执行步骤,1计算f (x)在有解区间a, b端点处的值，f (a)，f (b)。,2计算f
9、 (x)在区间中点处的值f (x1)。,3判断若f (x1) = 0，则x1即是根，否则检验：,（1）若f (x1)与f (a)异号，则知解位于区间a, x1， b1=x1, a1=a;,（2）若f (x1)与f (a)同号，则知解位于区间x1, b， a1=x1, b1=b。,反复执行步骤2、3，便可得到一系列有根区间：,当,时，,，即这些区间必将收缩于一点，也就是,方程的根。在实际计算中，只要,的区间长度小于预定容,许误差,就可以停止搜索，即,然后取其中点,作为方程的一个根的近似值。,注：,例2 证明方程,存在唯一的实根,用二分法,求出此根，要求误差不超过,。,解：记,，则对任意,，,因而
10、，,是严格单调的，,最多有一个根，,所以，,有唯一实根,又因为,用二分法求解，要使,，只要,解得,，取,。所以只要二等分7次，即可求得满,足精度要求的根。计算过程如下表所示,表3.1,所以，, 问题 虽然二分法计算简单，能够保证收敛，但是它对于方程单根存在区域信息要求太高，一般情况下很难实现，并且不能求偶重根、复根和虚根。在实际应用中，用来求解方程根的主要方法是迭代法。,使用迭代法求解非线性代数方程的步骤为： (1) 迭代格式； (2) 迭代格式的收敛性的构造分析； (3) 迭代格式的收敛速度与误差分析。,3.2 迭代法及其收敛性,3.2.1 不动点迭代法,将方程f(x)=0改写为等价方程形式
11、,x=(x). (3.1),若要求x*满足f(x*)=0，则x*=(x*)；反之亦然，称x*为函数(x)的一个不动点. 求f(x)的零点就等于求(x)的不动点，选择一个初始近似值x0，将它代入(3.1)右端，即可求得,x1=(x0).,可以如此反复迭代计算,xk+1=(xk) (k=0,1,2,). (3.2),(x)称为迭代函数. 如果对任何x0a, b，由(3.2)得到的序列xk有极限,则称迭代方程(3.2)收敛. 且x*=(x*)为(x)的不动点，故称(3.2)为不动点迭代法.,上述迭代法是一种逐次逼近法，其基本思想是将隐式方程(3.1)归结为一组显式的计算公式(3.2)，迭代过程实质上
12、是一个逐步显式化过程.,当(x)连续时，显然x*就是方程x=(x)之根(不动点). 于是可以从数列xk中求得满足精度要求的近似根. 这种求根方法称为不动点迭代法,称为迭代格式, (x)称为迭代函数, x0 称为迭代初值,数列xk称为迭代序列. 如果迭代序列收敛, 则称迭代格式收敛,否则称为发散.,3.2.2 迭代法的几何意义,通常将方程f(x)=0化为与它同解的方程 的方法不止一种,有的收敛,有的不收敛,这取决于 的性态,方程 的求根问题在几何上就是确定曲线y= 与直线y=x的交点P*的横坐标,构造迭代格式,x1 = 0.4771 x2 = 0.3939 x6 = 0.3758 x7 =0.3
13、758,解：,给定初始点,分别按以上三种形式建立迭代公式，并取x0=1进行迭代计算，结果如下：,解 对方程进行如下三种变形：,例3 用迭代法求方程x4+2x2-x-3=0 在区间1, 1.2内的实根.,准确根 x* = 1.124123029, 可见迭代公式不同, 收敛情况也不同. 第二种公式比第一种公式收敛快得多, 而第三种公式不收敛.,例3 表明原方程化为 x= (x) 的形式不同，有的收敛，有的不收敛，有的发散，只有收敛的的迭代过程xk+1= (xk) (k=0,1,2,)才有意义，为此我们首先要研究 (x)的不定点的存在性及迭代法xk+1= (xk)的收敛性.,3.2.3 不动点的存在
14、性与迭代法的收敛性,首先考察(x)在a, b上不动点的存在唯一性.,定理1 设(x)Ca, b满足以下两个条件：,1 对任意xa, b有a(x)b.,2 存在正数L1，使对任意x,ya, b都有,则(x)在a, b上存在唯一的不动点x*.,证明 先证不动点的存在性. 若(a)=a或(b)=b，显然(x)在a, b上存在不动点. 因为a(x)b，以下设(a)a及(b)b定义函数,显然f(x)Ca, b,且满足f(a)=(a)-a0, f(b)=(b)-b0, 由连续函数性质可知存在 x*(a, b) 使 f(x*)=0，即x*=(x*)，x*即为(x)的不动点.,再证不动点的唯一性. 设x1*,
15、 x2*a, b都是(x)的不动点，则由(3.3)得,引出矛盾，故(x)的不动点只能是唯一的. 证毕.,在(x)的不动点存在唯一的情况下，可得到迭代法 xk+1=(xk)收敛的一个充分条件.,定理2 设(x)Ca, b满足定理1中的两个条件，则对任意x0a, b，由xk+1=(xk)得到的迭代序列xk收敛到的不动点x*，并有误差估计式,证明 设x*a, b是(x)在a, b上的唯一不动点,由条件1，可知xka, b，再由(3.3)得,因0L1，故当k时序列xk收敛到x*.,下面证明估计式(3.4)，由(3.3)有,于是对任意正整数p有,上述令p, 注意到limxk+p=x* (p)即得(3.4)式.,又由于对任意正整数p有,上述令p, 及limxk+p=x* (p)即得(3.5)式. 证毕.,迭代过程是个极限过程. 在用迭代法进行时，必须按精度要求控制迭代次数. 误差估计式(3.4)原则上确定迭代次数，但它由于含有信息L而不便于实际应用. 而误差估计式(3.5)是实用的，只要相邻两次计算结果的偏差足够小即可保证近似值xk具有足够精度.,对定理1中的条件2可以改为导数，即在使用时如果(x)Ca, b且对任意xa, b有,则由微
