数值分析教案-非线性方程的数值解法.doc

第七章 非线性方程和方程组的数值解法教学目标：1.了解并掌握非线性方程的根的相关概念，如n重根、有根区间等概念；2.掌握二分法的基本思想及步骤，了解该方法的适用性及缺点，能用其求解简单的非线性方程；3.理解并掌握不动点迭代法的概念及相关收敛性定理，掌握全局收敛性及局部收敛性联系及区别，理解收敛阶、收敛速度等相关概念；4.理解并掌握Newton迭代法及求重根的修正Newton迭代法的思想、实现步骤以及相关理论，理解Newton迭代法的相关变形方法的提出及实现步骤，如简化Newton法、Newton下山法、弦截法与抛物线法等教学重点：1.二分法的基本思想及步骤；2.不动点迭代法的概念及相关收敛性定理；3. Newton迭代法及相关变形或改进的迭代法的思想及步骤教学难点：1..不动点迭代法的概念及相关收敛性定理；2. Newton迭代法及相关变形或改进的迭代法的思想及步骤教学过程（主要教学环节、教法、学法）修改批注7.1 方程求根与二分法1.1 引言对于一元非线性方程，若为代数多项式，即则称为代数（多项式）方程，否则称为超越方程例如，为代数方程，而则为超越方程若存在使，则称是方程的解或根，也称是函数的零点。

若函数可分解为 ，其中为正整数，则称是方程的重根，或称是函数的重零点当时，称是的单根或的单重零点零点可能是实数，也可能是复数若方程在区间内至少有一个根，则称为方程的有根区间通常可用逐步（次）搜索法求方程的有根区间求解非线性方程的根的问题大致可分为下面三个方面：（1）根的存在性即方程有没有根？如果有根，有几个根？（2）根的分布，即求出有根区间3）根的精确化即在已知一个根的近似值后，设法逐步把根精确化，直到满足精度为止2.2 二分法二分法的基本思想是逐步将非线性方程的有根区间（或隔根区间）二分，通过判断函数值的符号，逐步对半缩小有根区间（或隔根区间），直到区间缩小到容许误差范围之内，然后取区间的中点为根的近似值设，且，则在内有根为明确起见，再设在内仅有一个根令，，计算和若，则，结束计算若，则令，，否则令，，这样得到新的隔根区间再令，若，则，否则类似可得新的隔根区间这个过程可一直进行下去，仅当出现时过程中断（其中）记第次过程得到的隔根区间为，则， 故有 ，因此当充分大时，可作为方程的根的近似值，且有误差估计式 对于预先给定的精度，只要，即便有，这时就是满足精度要求的近似值。

分析以上过程不难发现，二分法的收敛速度与公比为的等比级数相同由于，可知大约二分10次，近似根的精度可提高三位小数位例2 用二分法求方程在区间内的一个实根，要求精确到小数点后第二位（即误差不超过0.005）解：这里，，而，，故在区间内有根由二分法的误差估计可知故只要二分6次便能达到所要求的精度，具体计算结果见下表：的符号01.01.51.2511.251.37521.3751.312531.31251.343841.34381.328151.32811.320361.32031.3242故为方程的近似根，误差不超过0.0057.2 不动点迭代法及其收敛性2.1 不动点与不动点迭代法若满足，则称为的不动点（或固定点）此时，我们称 (2.1)为不动点迭代法显然，若等价于，则的不动点也是方程的根如果对于任意的，由（2.1）式产生的序列有极限，即，则称迭代方程（2.1）收敛2.2 不动点的存在性与迭代法的收敛性定义 若存在常数，使对任何有则称在上满足Lipschitz（利普希茨）条件，称为Lipschitz常数 显然，若在上满足Lipschitz条件，则在上连续。

若在上一阶导数存在且有界，则在上满足Lipschitz条件定理1（不动点存在性定理） 设满足以下两个条件：（1）对任意，有；（2）在上满足Lipschitz条件，且Lipschitz常数；则在上存在唯一的不动点证明：先证明不动点的存在性，记，由定理条件有及，若有一等号成立，则或，即有不动点，否则必有，因，则必有使，即为的不动点再证明唯一性，设都是的不动点，且，则与假设矛盾，这表明，即不动点是唯一的证毕定理2（不动点迭代法的全局收敛性定理） 设满足定理1中的两个条件，则对任意的，由（2.1）式生成的迭代序列收敛到在上的不动点，且有, （2.2）. （2.3）证明：由定理1知在上存在唯一的不动点，下面先证明由（2.4）式生成的迭代序列收敛到的唯一不动点由于，故，再由Lipschitz条件得因为，故，即由Lipschitz条件及递推关系得.再由 及递推可得（2.3），令即得（2.2）证毕 推论1 若定理2中的条件（2）改为，且，则定理结论依然成立，且有. （2.4）证明：由微分中值定理及迭代公式有其中介于和之间。

从而有，对上式两端取极限，并注意到即得（2.4）式证毕定理2可以看出，的大小与迭代的收敛速度有关越小，收敛速度越快；若很接近于1，则收敛可能很慢例2 解方程解：不难验证方程在有一个根用不同的方法构造形式的等价方程，从而就有不同的迭代公式方法1：方程变换为，迭代公式为设，则，由定理4.6知迭代式发散的方法2：方程变换为，迭代公式为设，可以验证，，对所有成立取，有，，方法3：取，对所有，有，，取，有，，，2.3 局部收敛性和收敛阶定理1和2讨论了迭代法在区间上的收敛性，我们称之为全局收敛性，全局收敛性也包括在无穷区间上收敛的情形但是很多情况下全局收敛的情形不容易检验，为此我们通常考察在根附近的收敛性问题定义1设在区间内有不动点，若存在的某个邻域，对任意初值，迭代公式产生的迭代序列，且收敛到，则称迭代法局部收敛定理3（不动点迭代法的局部收敛性定理） 设为的不动点，且在的某个邻域内，存在一阶连续的导数，则当时，迭代法局部收敛证明：由于在附近是连续的，对于，存在适当小的，当时，有由上式得 又对如上选择的，对一切有 因而在区间内定理4.4的两个条件满足，因而迭代法是局部收敛的。

定理3对初值的要求较高如果已知的大概位置，为的一个较好的近似值，则可用代替，用代替，然后应用定理3判断迭代法的局部敛散性迭代法产生的迭代序列的收敛速度是衡量方法好坏的重要标志之一，为此我们引入收敛阶的概念定义2 设序列收敛到，记误差，若存在常数和，使得则称为阶收敛，称为渐进误差常数当时分别称线性收敛和平方收敛，当时称为超线性收敛需要指出的是，收敛阶的概念仍是一个局部性质，它刻画了方法接近于收敛时的误差下降的快慢一般来说，越大，收敛就越快定理4（收敛阶定理） 设为的不动点，整数，在的某邻域上连续，其满足，, （2.5）则由产生的序列在的某邻域内是阶收敛，且有 . （2.6）证明：由及定理3可知迭代法是局部收敛的将在处作泰勒（Taylor）展开，得 亦即 其中在和之间由于，，于是由此得（）由收敛阶的定义即得定理结论证毕例3 考察例2的方法二和方法三的收敛阶解：（1）方法二中，则，，所以它是一阶收敛的2）方法三中，解得，，所以它也是一阶收敛的7.4 牛顿法用迭代法求方程的根时，首先要把它写成等价形式，而迭代函数构造的好坏，不仅影响收敛速度，而且迭代过程也有可能发散。

那么怎样选择一个迭代函数才能够保证迭代序列一定收敛呢？构造迭代函数的一条重要途径是用近似方程来代替原方程求根因此如果能将非线性方程用线性方程来代替，那么求近似根问题就容易解决了Newton迭代法就是把非线性方程线性化的一种方法4.1 牛顿法及其收敛性牛顿法的基本思路是将非线性方程逐步线性化而形成的迭代公式设是的一个近似根，将函数在处作一阶Taylor展开，即若上式右端最后一项忽略不计，则得到如下近似方程 设，则可解得取作为原方程新的近似根，即令， （4.1）称（4.1）为Newton迭代过程（方程或格式），用Newton迭代过程求方程根的方法称为Newton迭代法，简称为Newton法Newton迭代法的几何意义是作曲线在点的切线方程该方程与轴交点的横坐标就是方程根的新的近似值，所以Newton法又常称为（Newton）切线法将Newton迭代法写成一般的不动点迭代的形式，有, （4.2）. （4.3）从而有，即Newton迭代法是超线性收敛的。

一般地，关于Newton法的收敛性有以下的局部收敛定理定理5 设，，在附近二阶导数连续，则Newton迭代法至少是二阶收敛的，且有. （4.4）证明：由（4.3）式可知，而，由收敛阶定理4可知，Newton迭代法至少二阶收敛，由（2.6）式立即可得（4.4）式证毕例4 用Newton法求方程的根解：，，Newton迭代为，取，得，，，即为根的近似，与例3相比，它表明Newton法收敛很快例5 用Newton迭代法建立求平方根的迭代式并分析收敛性解：作函数，则的正根就是，可得 （4.5）这是在计算机上做开方运算的一个实际有效的方法，它每步迭代只作一次除法和一次加法在做一次移位即可，计算量少，收敛又快当时有，，故由定理4.12知，对任意的初值，迭代（4.5）均收敛于事实上，若，则不难验证有，即，一般地可证明，即从起是一个单调递减有下届的数列，从而必有极限，在（4.33）中令可得4.2 求重根的修正Newton法设是的重根，即，其中，有二阶导数，，计算的导数可得从而有当时，，这样Newton法只是线性收敛的若重数已知，将迭代函数改为，则，故迭代法， （4.6）至少二阶收敛。

在实际使用中，由于根的重数一般是未知的令，可以证明若为的重根，则为的单根对用Newton法，迭代函数为 （4.7）从而可构造迭代法 ， （4.8）可证明上述方法至少二阶收敛例6 方程的根是二重根，使用Newton法及（4.6）、（4.8）各计算三步解：，，（1）Newton法：，（2）迭代法（4.6）：，（3）迭代法（4.8）：，三种方法均取，计算结果如下表：。