《非线性方程和方程组的数值解法讲解》由会员分享，可在线阅读，更多相关《非线性方程和方程组的数值解法讲解（32页珍藏版）》请在金锄头文库上搜索。
1、第四章 非线性方程和方程组的数值解法教学目标：1.了解并掌握非线性方程的根的相关概念，如m重根、有根区间等概念；2.掌握逐步搜索法和二分法（区间对分法）的基本思想及步骤，了解这两种方法的适用性及缺点，能应用其求解简单的非线性方程；3.了解迭代法的分类，理解并掌握不动点迭代法的概念及相关收敛性定理，掌握全局收敛性及局部收敛性联系及区别，理解收敛阶和计算效率的相关概念的来历及含义；4.了解迭代加速的思想，掌握加权法（松弛法）、Aitken以及Steffensen加速方法的思想及相关理论、计算公式；5.理解并掌握Newton迭代法及求重根的修正Newton迭代法的思想、实现步骤以及相关理论；6.理解
2、Newton迭代法的相关变形方法的提出及实现步骤，如简化Newton法（平行弦法）、Newton下山法、拟Newton法和Steffensen方法；7、理解割线法和Muller法提出的背景及实现步骤，掌握相关的理论。教学重点：1.逐步搜索法和二分法（区间对分法）的基本思想及步骤；2.不动点迭代法的概念及相关收敛性定理；3.迭代加速的思想及三种实现方式；4. Newton迭代法及相关变形或改进的迭代法的思想及步骤。教学难点：1.不动点迭代法的概念及相关收敛性定理；2.迭代加速的思想及三种实现方式；3. Newton迭代法及相关变形或改进的迭代法的思想及步骤。教学方法：教具：4.1 问题的提出非线
3、性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。但是，非线性方程的求根非常复杂。本章重点讨论单个方程的求根方法，对于非线性方程组的解法仅作一些简单的介绍。这是因为单个方程的求根问题比非线性方程组更普遍。另外非线性方程组的求解是个难度比较大的问题，许多近代研究集中在这个问题上。非线性方程和方程组的数值解法主要是迭代法。一般的非线性方程组可以写成，其中和都是维向量。当时就是单个的方程。为了叙述方便，首先引入下述定义：定义4.1 对于一元非线性方程，若为代数多项式，即则称为代数（多项式）方程，否则称为超越方程。例如，为代数方程，而则为超越方程。定义4.2 （1）若存
4、在使，则称是方程的解或根，也称是函数的零点。（2）若函数可分解为 ，其中为正整数，则称是方程的重根，或称是函数的重零点。当时，称是的单根或的单重零点。零点可能是实数，也可能是复数。定理4.1 对于充分可微的函数，是函数的重零点的充分必要条件是：，定义4.3 若方程在区间内至少有一个根，则称为方程的有根区间。通常可用逐步（次）搜索法求方程的有根区间。定理4.2 若函数在区间上连续（即），且，则方程在内至少有一个根。定义4.4 若在区间上只有方程的一个根，则称为方程的隔根区间。定理4.3 若函数在区间上单调连续，且，则方程在内有且仅有一个根。关于根的个数，由代数学基本定理知，高次代数方程的根（包括
5、实根和复根）的个数与代数方程的次数相同；对于超越方程，可能没有根，也可能有一个或若干个根，甚至无穷多个根。理论上已经证明，对于次数的代数方程，它的根可以用根式表示，而次数的代数方程，它的根一般不能用根式表示，亦即不能用解析表达式来表示。因此对于一般的函数方程，一般来说，更不存在根的解析表达式，而在实际应用中，也不一定需要得到求根的解析表达式，只要得到满足精度要求的根的近似值就可以了。求解非线性方程的根的问题大致可分为下面三个方面：（1）根的存在性。即方程有没有根？如果有根，有几个根？（2）根的分布，即求出有根区间。（3）根的精确化。即在已知一个根的近似值后，设法逐步把根精确化，直到满足精度为止
6、。4.2 逐步搜索法和二分法4.2.1 逐步搜索法假设是定义在某区域内的连续函数，在区间有且仅有一个单根，则逐步搜索法的步骤如下：（1）判断的符号：若，则；若，则不妨设。（2）选择适当的步长，搜索一步，看的符号，若，则已找到。若则可知，这时可取或作为的近似值。若，则继续往前搜索一步，看的符号，直到与异号，则可知，其中，这时可取或作为的近似值。逐步搜索法的步长的选择很难恰到好处，若取得较大，则精度较差；若取得足够小，精度提高了，但计算量增加了许多。因此，如果精度要求较高的话，该方法不太经济。例4.1 求方程的有根区间。解：根据有根区间的定义，对方程的根进行搜索计算，结果如下表0123456符号从
7、上表可以得出方程的三个有根区间为，和。4.2.2 二分法二分法（对分法）是逐步搜索法的改进。它的基本思想是逐步将非线性方程的有根区间（或隔根区间）二分，通过判断函数值的符号，逐步对半缩小有根区间（或隔根区间），直到区间缩小到容许误差范围之内，然后取区间的中点为根的近似值。（基本思想：通过计算隔根区间的中点，逐步缩小隔根区间，从而得到方程的近似根）设，且，则在内有根。为明确起见，再设在内仅有一个根。令，计算和。若，则，结束计算。若，则令，否则令，这样得到新的隔根区间。，。再令，若，则，否则类似可得新的隔根区间。这个过程可一直进行下去，仅当出现时过程中断（其中）。记第次过程得到的隔根区间为，则，
8、（4.1）故有 ，因此当充分大时，可作为方程的根的近似值，且有误差估计式 对于预先给定的精度，只要，即 （4.2）便有，这时就是满足精度要求的近似值。（实际中常用来代替，其中为预先给定的小量）分析以上过程不难发现，二分法的收敛速度与公比为的等比级数相同。由于，可知大约二分10次，近似根的精度可提高三位小数位。二分法的思想方法还可以用于搜索一个较大区间内实根的分布情况（不包括偶重实根），实际做法是：取适当的步长，逐一检验小区间（）两端的函数值是否异号，若异号，则按以上二分法求出其中的根；若同号则不作求根运算而转入检查下一个区间，只要选得适当小，则可求出内的所有奇重实根（包括单实根）。选得过大，可
9、能漏掉某些根；选得过小，则计算量增大。二分法的优点是程序简单、方法可靠、易于在计算机上实现，事先估计计算次数容易，收敛速度恒定，对函数的性质要求低，只要连续就可以了；它的局限性是不能求偶数重根，也不能求复根和虚根。另外，二分法在求根过程中，只用到了函数的符号，而未用到计算出的函数值，这总有点浪费。实际应用中这个方法可用于求根的初始近似值，以便使用其它的求根高速迭代法，有时也用来试探实根的分布区间。例4.2 用二分法求方程在区间内的一个实根，要求精确到小数点后第二位（即误差不超过0.005）。解：这里，而，故在区间内有根。由（4.2）式可得故只要二分6次便能达到所要求的精度，具体计算结果见下表：
10、的符号01.01.51.2511.251.37521.3751.312531.31251.343841.34381.328151.32811.320361.32031.3242故为方程的近似根，误差不超过0.005。4.3 迭代法4.3.1 迭代法分类迭代法是一种逐步逼近根的方法，已知方程的一个近似根后，通常使用某个固定公式反复校正根的近似值，使之逐步精确化，一直到满足给定的精度要求为止。迭代法可分为单点迭代法和多点迭代法。设一元函数是连续的，将方程变换为如下的等价形式 （4.3）其中是一个连续函数，这样就得到单点迭代公式， （4.4）给定初值，可得序列。此时称为迭代函数，其只依赖于及上以及的
11、各阶导数值，并称为迭代序列，有时也称（4.4）为迭代方程（过程，格式）。例如，著名的Newton迭代法，就是单点迭代法的一个具体例子。而多点迭代法的一般形式为， （4.5）为产生迭代序列，需要个初始值，。其中迭代函数依赖于及这些点上及其各阶导数值。割线法 ，是多点迭代法的一个最简单的例子。在实践中，有些迭代法其迭代函数是随迭代次数发生改变的，一般称这样的迭代法为非定常迭代。而对应地，上述单点和多点迭代法称为定常迭代。因此，迭代法的最一般形式为 （4.6）我们将要考虑的求的根的方法都属于这种形式。对于定常迭代，而对于单点迭代。 4.3.2 不动点迭代法与全局收敛性定义4.5 若满足，则称为的不动
12、点（或固定点）。此时，我们称（4.4）式为不动点迭代法。显然，若等价于，则的不动点也是方程的根。定义4.6 如果对于任意的，由（4.4）式产生的序列有极限，即，则称迭代方程（4.4）收敛。下面先讨论一般的不动点和不动点迭代法的一些性质。定义4.7 若存在常数，使对任何有则称在上满足Lipschitz（利普希茨）条件，称为Lipschitz常数。 显然，若在上满足Lipschitz条件，则在上连续。若在上一阶导数存在且有界，则在上满足Lipschitz条件。定理4.4（不动点存在性定理） 设满足以下两个条件：（1）对任意，有；（2）在上满足Lipschitz条件，且Lipschitz常数；则在上
13、存在唯一的不动点。证明：先证明不动点的存在性，记，由定理条件有及，若有一等号成立，则或，即有不动点，否则必有，因，则必有使，即为的不动点。再证明唯一性，设都是的不动点，且，则与假设矛盾，这表明，即不动点是唯一的。证毕推论1 若定理4.4中的条件（2）改为，且，则定理结论依然成立。证明：这只要利用下式即可证明，其中，定理4.5（不动点迭代法的全局收敛性定理） 设满足定理4.4中的两个条件，则对任意的，由（4.4）式生成的迭代序列收敛到在上的不动点，且对整数有 （4.7） （4.8） （4.9） （4.10）证明：由定理4.4知在上存在唯一的不动点，下面先证明由（4.4）式生成的迭代序列收敛到的唯
14、一不动点。由于，故，再由Lipschitz条件得因为，故，即。由Lipschitz条件及递推关系得即证得（4.7），再由 及递推可得（4.8），在（4.7）中令即得（4.9），在（4.8）中令即得（4.10）。证毕 推论2 若定理4.5中的条件（2）改为，且，则定理结论依然成立，且有 （4.11）证明：只需证明（4.11）。由微分中值定理及迭代公式有其中介于和之间。从而有，对上式两端取极限，并注意到即得（4.11）式。证毕估计式（4.7），（4.8）和式（4.11），分别被称为误差后验估计式（误差事后估计式）、误差先验估计式（误差事前估计式）和误差渐进估计式。由定理4.5可以看出，的大小与迭代的收敛速度有关。越小，收敛速度越快；若很接近于1，则收敛可能很慢。在实际计算中，对于给
