计算方法PPT课件第二章非线性方程的数值解

第二章非线性方程的数值解,2020年5月3日星期日,第2页,在许多科学技术和工程计算等实际问题中，常常会遇到求解非线性方程的问题。例如:求n次代数方程的根；或求由三角函数、指数函数和对数函数等组成的超越方程。例如:求超越方程的解。这些都可表示为求非线性方程的根，或称为求非线性方程的解，即求函数的零点。方程的根可以是实数，也可以是复数；,2020年5月3日星期日,第3页,根的概念,给定方程f(x)=0，如果有使得f()=0，则称为f(x)=0的根或f(x)的零点.设有正整数m使得f(x)=(x-)mg(x),且g()0；则当m2时，称为f(x)=0的m重根；当m=1时，称为f(x)=0的单根.本章只讨论实根的求法.,2020年5月3日星期日,第4页,求根一般步骤,（1）确定所给方程存在多少个根.（2）进行根的隔离，找出每个有根区间(参考清华大学出版，靳天飞主编计算方法）。有根区间内的任一点都可看成是该根的一个近似值。（3）逐步把近似根精确化，直到足够精确为止.本章主要讨论单根问题。求根的方法很多，如：二分法（又称对分法）、牛顿法（又称切线法）、双点弦截法（又称快速弦截法）、迭代法等。,2020年5月3日星期日,第5页,2.1二分法,2020年5月3日星期日,第6页,2020年5月3日星期日,第7页,2020年5月3日星期日,第8页,2020年5月3日星期日,第9页,三、二分法的定义、计算步骤与框图1.定义2.0象方法介绍那样，通过将区间a,b对分，逐步缩小根的范围而求出方程f(x)=0的实根的方法称为二分法，也称为对分法。2.计算步骤输入有根区间的端点a、b及预先给定的容许精度e；计算；若f(a)f(b)0,则bx，转向下一步；否则ax,转向下一步；若|b-a|e，则输出方程满足精度要求的值x，否则转向。,2020年5月3日星期日,第10页,3.程序框图与程序实例程序框图图2.2表示了用二分法求方程f(x)=0的根上机实习编制程序的框图。程序实例：我们用C语言编制了用二分法求方程根的程序，程序文本及计算结果可见第八章程序实例2.,2020年5月3日星期日,第11页,2020年5月3日星期日,第12页,2020年5月3日星期日,第13页,2.2迭代法,本节分三步介绍：一.迭代法的基本思想二.迭代法需要解决的两个基本问题（如何选取初值，何时停机）三.迭代法的计算步骤和计算框图,2020年5月3日星期日,第14页,2020年5月3日星期日,第15页,思考：如何选取初值？,2020年5月3日星期日,第16页,2020年5月3日星期日,第17页,二.迭代法需要解决的两个基本问题1.如何选取初始近似值、以及迭代函数g(x)，才能保证按迭代公式求出的迭代序列收敛？2.当迭代序列收敛时，用计算机如何决定迭代过程结束？,2020年5月3日星期日,第18页,2.2.2迭代法的收敛条件（解决第一个问题）定理2.1设迭代函数g(x)在区间a,b上具有一阶导数，且满足：存在正数L1时称为超线性收敛；p=2时称为平方收敛。显然，数p的大小反映了迭代法收敛的快慢，p越大则收敛越快。因此，迭代法的收敛阶是衡量迭代法优劣的重要标志之一。,2020年5月3日星期日,第29页,2020年5月3日星期日,第30页,2020年5月3日星期日,第31页,2020年5月3日星期日,第32页,2020年5月3日星期日,第33页,2.3Newton迭代法（略）,2020年5月3日星期日,第34页,2020年5月3日星期日,第35页,3.Newton迭代法收敛定理（定理2.5）（略）,则Newton迭代法（2.12）产生的数列,收敛到根。,为例证明（其它情况类似）,2020年5月3日星期日,第36页,（略）,2020年5月3日星期日,第37页,例6（略）,解：设,用Newton迭代法求,2020年5月3日星期日,第38页,2020年5月3日星期日,第39页,x,y,xn,Xn+1,Xn+2,tn(x),tn+1(x),0,2.3牛顿（Newton)法解非线性方程f(x)=0的牛顿(Newton)法，就是将非线性方程线性化的一种方法。牛顿法具有实用面广，收敛快等优点。,2.3.1方法介绍所谓牛顿法，就是用f(x)=0的解的近似值xn(n=0,1,2,)的切线方程,图2.4,(2.11),作为f(x)的近似表达式，然后取tn(x)=0的解xn+1作为f(x)=0的解的进一步近似，如图2.4所示。,由式(2.11)，令tn(x)=0就得到了牛顿法的迭代公式,(2.12),2020年5月3日星期日,第40页,由图2.4可以看出，牛顿法实际上是在每一步都使用不同的切线方程去逼近非线性方程。因此，牛顿法也称为切线法，它是一种将非线性方程线性化的方法。由迭代格式(2.12)可知，牛顿法是一种特殊的迭代法，其迭代函数在f(x)及其导数满足一定条件的情况下，通过选择适当的初始值x0，迭代格式(2.12)所产生的迭代序列xn将收敛。,(2.13),2020年5月3日星期日,第41页,2.3.2牛顿法收敛的充分条件定理2.5设函数f(x)在闭区间a,b上存在二阶导数且满足条件：在区间a,b上保号；设且则牛顿迭代格式(2.12)产生的迭代序列收敛于方程f(x)=0的一个解。,（证明P32略）,2020年5月3日星期日,第42页,2020年5月3日星期日,第43页,2020年5月3日星期日,第44页,2020年5月3日星期日,第45页,例6设c为正实数，导出用牛顿法求的公式，并证明迭代序列的误差满足关系式解设；则，所以由于所以f(x)0在区间0,+1内有一正根。又由于在区间内，若取，则在区间内满足定理2.5的条件，所以收敛的牛顿迭代式为,2020年5月3日星期日,第46页,记，则有*由例6中误差满足的关系式(2.14)，可得对上式取极限可得由此可知，在用牛顿法求时是2阶收敛的。,(2.14),2020年5月3日星期日,第47页,2.3.3牛顿法的收敛阶定理2.6设函数f(x)充分光滑，对于方程f(x)=0：若在区间(a,b)内存在单根，则用牛顿法求的近似解时是2阶收敛的。若在区间(a,b)内存在m(2)重根，则用牛顿法求的近似解时是线性收敛的。（证明P35略）写出求,2020年5月3日星期日,第48页,2.3.4计算步骤和程序框图牛顿法的计算步骤为：选定初值，计算按公式迭代，得新的近似值，并计算对于给定的允许精度，如果，则终止迭代，取；否则，再转回步骤计算。图2.6给出了用牛顿法求非线性方程f(x)=0解的程序框图，其中N为设定的最大迭代次数。,2020年5月3日星期日,第49页,1k,输出迭代失败标志,结束,开始,输出x1,输出奇异标志,=,=,图2.6,2020年5月3日星期日,第50页,例7求方程的解。解粗略地绘出函数的草图，如图2.7所示。,图2.7,2020年5月3日星期日,第51页,对函数f(x)求导可得,若取初值x0=3，用牛顿法求解例7的迭代格式为,经计算可得：x1=1.15999,x2=0.189438,x5=0.783595,x6=0.783599.若只需6位有效数字，则x60.783599。,2020年5月3日星期日,第52页,在（2.18)式中，若取初值x0=8，经计算可得：x1=34.778107，x2=865.1519，。继续迭代可知，xn随着n的增大将无限增大，此时迭代格式(2.18)发散。例7说明，使用牛顿法求解非线性方程，初值x0的选择非常重要，选择得不好会引起迭代序列发散，求不出方程的近似解。本例还说明，定理2.5的条件仅是一个充分条件，当条件不满足时，仍有可能收敛。如取x03时，迭代格式收敛；但f(3)=-1.4723660，由式(2.17)知，故不满足定理2.5中的条件。,2020年5月3日星期日,第53页,2.3.5双点弦截法（快速弦截法）在方程f(x)=0的根附近任取两初始近似根x0,x1，由迭代公式(2.20)逐次逼近f(