《非线性方程的数值求法-二分法和简单迭代法》由会员分享，可在线阅读，更多相关《非线性方程的数值求法-二分法和简单迭代法（52页珍藏版）》请在金锄头文库上搜索。
1、第七章第七章非线性方程与方程组的数值解法非线性方程与方程组的数值解法 引言引言 在在科科学学研研究究和和工工程程设设计计中中, 经经常常会会遇遇到到的的一一大大类类问题是非线性方程问题是非线性方程f(x)=0的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。方程方程f(x)=0的根的根, 亦称为函数亦称为函数f(x)的零点的零点 如如果果f(x)可可以以分分解解成成 , ,其其中中m为为正正整整数数且且 , ,则则称称x x* *是是f(x)f(x)的的m重重零零点点, ,或或称称方方程程f(x)=0的的m重重根根。当当m=1时时称称x x* *为为单单根根。若若f(x)存存
2、在在m阶导数阶导数, ,则则x x* *是方程是方程f(x)的的m重根重根( (m1) 当且仅当当且仅当记笔记记笔记 当当f(x)f(x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为非线性方程。如果为非线性方程。如果f(x)f(x)是多项式函数，则称为代数是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称程等）。一般称n n次多项式构成的方程次多项式构成的方程 为为n n次代数方程次代数方程, ,当当n n1 1时时, ,方程显然是非线性的方程显然是非线性的 一般稍微复杂的一般稍微复
3、杂的3 3次以上的代数方程或超越方程次以上的代数方程或超越方程, ,很难甚至无法求得精确解。本章将介绍常用的求解非很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法线性方程的近似根的几种数值解法 记笔记记笔记 通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有根，有几个根？根，有几个根？确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的初始近似值。初始近似值。根的
4、精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止本章介绍方程的迭代解法，它既可以用来求解代本章介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解超越方程，并且仅限于求数方程，也可以用来解超越方程，并且仅限于求方程的方程的实根。实根。运用迭代法求解方程的根应解决以下两个问题：运用迭代法求解方程的根应解决以下两个问题：n确定根的初值确定根的初值;n将进一步精确化到所需要的精度。将进一步精确化到所需要的精度。记笔记记笔记7.1 二分法二分法 二分法又称二分区间法二分法又称二分区间法, ,是求解
5、非线性方程的近是求解非线性方程的近似根的一种常用的简单方法。似根的一种常用的简单方法。 设函数设函数f(x)f(x)在闭区间在闭区间 a,ba,b上连续上连续, ,且且f(f(a)f()f(b)0,)0,根据连续函数的性质可知根据连续函数的性质可知, , f( (x)= 0)= 0在在( (a,b)a,b)内必有实根内必有实根, ,称区间称区间 a,ba,b为有根区间。为明确为有根区间。为明确起见起见, ,假定方程假定方程f(x)=0f(x)=0在区间在区间 a,ba,b内有惟一实根内有惟一实根x x* *。 二分法的基本思想是二分法的基本思想是: : 首先确定有根区间首先确定有根区间, ,将
6、区将区间二等分间二等分, , 通过判断通过判断f(x)f(x)的符号的符号, , 逐步将有根区间缩逐步将有根区间缩小小, , 直至有根区间足够地小直至有根区间足够地小, , 便可求出满足精度要求便可求出满足精度要求的近似根。的近似根。确定有根区间的方法确定有根区间的方法 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围， 称为称为圈定根或根的隔离圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。 对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（
7、实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲求方程根的问题，就几何上讲,是求曲线是求曲线 y=f (x)与与 x轴交点的横坐标。轴交点的横坐标。 由高等数学知识知由高等数学知识知, 设设f (x)为区间为区间a,b上的单上的单值连续值连续, 如果如果f (a)f (b)0 , 则则a,b中至少有一个中至少有一个实根。如果实根。如果f (x)在在a,b上还是单调地递增或递减，上还是单调地递增或递减，则仅有一个实根。则仅有一个实根。记笔记记笔记n由此
8、可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有： (1) 画图法画图法 (2) 逐步搜索法逐步搜索法y=f(x)abyx(1) 画图法画图法 画出画出y = f (x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的轴交点的 大致位置。大致位置。 也可将也可将f (x) = 0分解为分解为 1(x)= 2(x)的形式，的形式， 1(x) 与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根 区间。区间。例如例如 xlogx-1= 0= 0可以改写为可以改写为logx= =1/x画出对数曲线画出对数曲线y=logx, ,与双曲线与双
9、曲线y= 1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内(1) 画图法画图法023yxn对于某些看不清根的函数，可以扩大一下曲线对于某些看不清根的函数，可以扩大一下曲线y0xy=f(x)y=kf(x)(1) (1) 画图法画图法画图法画图法记笔记记笔记y0xABa1b1a2b2(2) 逐步搜索法逐步搜索法(2) (2) 搜索法搜索法 对于给定的对于给定的f (x),设有根区间为设有根区间为A, ,B,从从x0=A出出发发, ,以步长以步长h=(B-A)/n(n是是正整数正整数),在在A, ,B内取定内取定节点节点: :xi=x0ih (i=0,1,2, ,n),从左
10、至右检查从左至右检查f (xi)的符号的符号, ,如发现如发现xi与端点与端点x0的函数值异号的函数值异号, ,则得到一个则得到一个缩小的有根子区间缩小的有根子区间xi-1, ,xi。例例1 1 方程方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0f(0)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0x=0出发出发, ,取取h=0.5h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索, ,列表如下列表如下x xf(x)f(x)0 0.5 1.0
11、 1.5 20 0.5 1.0 1.5 2 + + + +可以看出，在可以看出，在1.01.0,1.5,1.5内必有一根内必有一根 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当要选择适当h ，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量 又不太大。又不太大。 为获取指定精度要求的初值为获取指定精度要求的初值, ,可在以上隔离根的可在以上隔离根的 基础上采用对分法继续缩小该含根子区间基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。 取有根区间取有根区间a,b之中点之中点, 将
12、它分为两半将它分为两半,分点分点 ,这样就可缩小有根区间这样就可缩小有根区间7.1.2 二分法求根过程二分法求根过程 设设方方程程f(x)=0在在区区间间a,b内内有有根根,二二分分法法就就是是逐逐步步收收缩缩有有根根区区间间，最最后后得得出出所所求求的的根根。具具体体过过程程如如下下 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法, , 即取中点即取中点 , ,将区间将区间 再分为两半再分为两半, ,然然 后再确定有根区间后再确定有根区间 , ,其长度是其长度是 的的 二分之一二分之一 如此反复下去如此反复下去, ,若不出现若不出现 , ,即可得出一即可得出一 系列有根区
13、间序列：系列有根区间序列： 上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半, ,因此因此 的长度的长度 当当k时趋于零时趋于零, ,这些区间最终收敛于一点这些区间最终收敛于一点x x* * 即为即为 所求的根所求的根 。每次二分后每次二分后, ,取有根区间取有根区间 的中点的中点作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x x* *为极限为极限 只要二分足够多次只要二分足够多次( (即即k足够大足够大),),便有便有这里这里为给定精度为给定精度, ,由于由于 , ,则则 当给定精度当给定精度0 0后后, ,要想要想 成立成立
14、, ,只要只要取取k满足满足 即可，亦即当即可，亦即当: 时时, ,做到第做到第k+1次二分次二分, ,计算得到的计算得到的 就是就是满足精度要求的近似根满足精度要求的近似根 。 在程序中通常用相邻的在程序中通常用相邻的 与与 的差的绝的差的绝对值或对值或 与与 的差的绝对值是否小于的差的绝对值是否小于来来决定二分区间的次数。决定二分区间的次数。 二二分分法法算算法法实实现现例例 设设 已知已知 ，求在，求在区间区间1.5,21.5,2内根的近似值内根的近似值. .计算结果列表如下：计算结果列表如下： 取 误差限 例例 证明方程证明方程 在区间在区间2, 3内有一个内有一个根根 使用二分法求误
15、差不超过使用二分法求误差不超过0.510-3 的根要二的根要二 分多少次？分多少次？证明证明 令令 且且f(x)f(x)在在2, 3上连续上连续, ,故方程故方程f(x)=0f(x)=0在在2,32,3内至少内至少有一个根。又有一个根。又 当当时，时， , ,故故f(x)f(x)在在2, 32, 3上是单调递增函数上是单调递增函数, ,从而从而f(x)f(x)在在2, 32, 3上有且仅有一根。上有且仅有一根。 给定误差限给定误差限 0.510-3 , ,使用二分法时使用二分法时 误差限为误差限为 只要取只要取k满足满足 即可，亦即即可，亦即 所以需二分所以需二分1010次便可达到要求。次便可
16、达到要求。 二分法的优点是不管有根区间二分法的优点是不管有根区间 多大多大, ,总总能求出满足精度要求的根能求出满足精度要求的根, ,且对函数且对函数f(x)f(x)的要求不高的要求不高, ,只要连续即可只要连续即可, ,计算亦简单计算亦简单; ;它的局限性是只能用于它的局限性是只能用于求函数的求函数的实根实根, ,不能用于求复根及重根。不能用于求复根及重根。 7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 对于一般的非线性方程对于一般的非线性方程, ,没有通常所说的求根没有通常所说的求根公式求其精确解公式求其精确解, ,需要设计近似求解方法需要设计近似求解方法, ,即迭代法。即迭代法。
17、它是一种逐次逼近的方法它是一种逐次逼近的方法, ,用某个固定公式反复校正用某个固定公式反复校正根的近似值根的近似值, ,使之逐步精确化，最后得到满足精度要使之逐步精确化，最后得到满足精度要求的结果。求的结果。7.2.1 7.2.1 迭代法的基本思想迭代法的基本思想 为求解非线性方程为求解非线性方程f(x)=0f(x)=0的根，先将其写成便于的根，先将其写成便于迭代的等价方程迭代的等价方程 (5.3) (5.3)其中其中 为为x x的连续函数的连续函数即如果数即如果数 使使f(x)=0, 则也有则也有 , 反之反之, 若若 , 则也有则也有 , 称称 为迭代函数为迭代函数 任任取一个初值取一个初
18、值 , 代入式代入式 的右端的右端, 得到得到 再将再将 代入式代入式 的右端的右端, 得到得到 ,依此类推依此类推, 得到一个数列得到一个数列 ， 其一般表示其一般表示 式式( (5.4)5.4)称为求解非线性方程的称为求解非线性方程的简单迭代法简单迭代法。 ( (5.4)5.4)如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛, ,即即 则称迭代法收敛。则称迭代法收敛。 实实际际计计算算中中当当然然不不可可能能也也没没必必要要无无穷穷多多步步地地做做下下去去, , 对预先给定的精度要求对预先给定的精度要求，只要某个只要某个k k满足满足即可结束计算并取即可结束计算并取 当然，迭
19、代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。例.用迭代法求方程 在 内的实根。取 解：对方程进行如下三种变形： 建立迭代格式： 这是一个发散的迭代格式。 建立迭代格式： 该迭代格式收敛。 建立迭代格式： 该迭代格式收敛。 结论：可见，对 的迭代函数 (1) 不唯一(2) 发散或收敛(3) 收敛的快、慢。下面将讨论两个问题：收敛性和收敛速度。 首先，看一下迭代法的几何意义：首先，看一下迭代法的几何意义：迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种, ,有的收敛有的收敛, ,
20、有的不收敛有的不收敛, ,这取决于这取决于 的性态的性态, ,方程方程 的求根问题在几何上就是确定曲的求根问题在几何上就是确定曲线线y= 与直线与直线y=x的交点的交点P*的横坐标的横坐标( (图图7-2所示所示) ) (a)(b)图图7-2 迭代法的几何意义迭代法的几何意义 7.2.4 迭迭代代法法的的算算法法框框图图二、收敛条件二、收敛条件 定理 设函数在有限区间 上满足如下条件： （1）当 , 即 （2）存在正常数 ，对 恒成立 则 在 上的解 存在惟一；任意选取的初始近似值 由迭代过程产生的序列 收敛到 . 证明：由（1）知， 于 连续，令： 则： 故： 在 上至少有一个根. 现证有唯
21、一根.反之，若 均有： 则由(2）有 即： 矛盾.现证收敛.记 由 故： 推论 若条件(2)改为 在 上有界且 当 时 ,则定理1中的结论成立. 例 求 在0，1内的一个实根. 将方程化为等价方程 因为 此时定理1中的条件（1）成立，又 所以定理1中条件（2）也成立，对于0，1中任意初值，迭代序列 收敛，计算结果如下表，取 注注. . 方程方程 也可化为等价方程也可化为等价方程 但此时定理、推论条件不成立，迭代序列不能保证收敛但此时定理、推论条件不成立，迭代序列不能保证收敛。 例例5 5 对方程对方程 , ,构造收敛的迭代格式构造收敛的迭代格式, , 求其最小正根求其最小正根, ,计算过程保留
22、计算过程保留4位小数。位小数。解解 容易判断容易判断1,21,2是方程的有根区间是方程的有根区间, , 且在此区间且在此区间 内内 , ,所以此方程在区间所以此方程在区间1,21,2有有 且仅有一根。将原方程改写成以下两种等价形式。且仅有一根。将原方程改写成以下两种等价形式。 ,即即 不满足收敛条件。不满足收敛条件。 , ,即即 此时迭代公式满足迭代收敛条件。此时迭代公式满足迭代收敛条件。误差估计误差估计 ：在上面定理的条件下，有误差估计式： （7.7） （证明思路:只需证明下列两个结论成立即可。） (1)证明 两边整理后得结论。 (2)以下证明： 事实上，由(1) 即证 存在的困难： 的值很
23、难满足在隔根区间内。 7.2.5 局部收敛性局部收敛性 当迭代函数较复杂时当迭代函数较复杂时, ,通常只能设法使迭代过程通常只能设法使迭代过程在根的邻域在根的邻域( (局部局部) )收敛。收敛。 定理定理 设设 在在 的根的根 的邻域中有连的邻域中有连续的一阶导数续的一阶导数, ,且且 则迭代过程则迭代过程 具有局部收敛性。具有局部收敛性。 证证: :由由于于 , ,存存在在充充分分小小邻邻域域: : , ,使使成成立立 这这 里里 L L为为 某某 个个 定定 数数 , ,根根 据据 微微 分分 中中 值值 定定 理理 由于由于 , ,又当又当时时 , ,故有故有由定理由定理1 1知知 对于
24、任意的对于任意的 都收敛都收敛 例例6 设设 ,要使迭代过程要使迭代过程 局部收敛到局部收敛到 , ,求求 的取值范围。的取值范围。解：解： 由在根由在根 邻域具有局部收敛性时邻域具有局部收敛性时, 收敛收敛 条件条件 所以所以 例例7 7 已知方程 在 内有根 ,且在上满足 ,利用 构造一个迭代函数,使 局部收敛于 。解解: :由由 可得可得, , 故故 , ,迭代公式迭代公式局部收敛局部收敛例.用迭代法求方程 在 内的实根。取 解：对方程进行如下三种变形： 理论分析： 由上述定理知，迭代格式发散，和计算结果吻合。 理论分析： 由定理知，迭代格式收敛，和计算结果吻合。 理论分析：由定理知，迭
25、代格式收敛，和计算结果吻合。而且， ，由（5）式知，和都收敛，但收敛的效果比好。 收敛速度的粗略判别： 值愈小，迭代法收敛得愈快 .若 ，则收敛快； 接近于1，则收敛很慢。 三、迭代过程的收敛速度（收敛阶）三、迭代过程的收敛速度（收敛阶） 定义 设迭代序列收敛于 如果存在实数 和非零常数 使成立 则称序列 是 阶收敛的， 相应的迭代方法称为 阶收敛方法. 收敛速度的阶：判断迭代方法收敛快慢的重要标准。 定理 设 是 的根， 于的邻域 次连续可微 ，又 (*) 则只要初始值 选得充分接近 ，迭代方法 阶收敛，且有 例例 8 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛。证明该迭
26、代公式平方收敛。证证: 迭代公式相应的迭代函数为迭代公式相应的迭代函数为将将 代入，代入，根据定理根据定理7.3可知，迭代公式平方收敛。可知，迭代公式平方收敛。为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提高收敛的速度, 可设法可设法 提高初值的精度以减少迭代的次数提高初值的精度以减少迭代的次数 提高收敛的阶数提高收敛的阶数 p 7. .3 迭代过程的加速迭代过程的加速* * （1 1）加权法）加权法设设 是是根根 的的某某个个近近似似值值, ,用用迭迭代代公公式式校校正正一一次次得得 又又 根据中值定理有根据中值定理有 其中其中 当当 范围不大时范围不大时, ,设设 变化不大变化不
27、大, ,其估计其估计值为值为L L, ,则有则有 可见可见, ,若将迭代值若将迭代值 与与 加权平均加权平均, ,则可得到的则可得到的 是比是比 更好的近似根更好的近似根迭代：迭代： 改进：改进： 或合并写成：或合并写成： 例例9 用加权法加速技术求方程用加权法加速技术求方程 在在0.5附近的一个根。附近的一个根。解：解： 因为在因为在 附近附近 取取L=-0.6，建立如下迭代公式建立如下迭代公式仍取仍取 , ,逐次计算得逐次计算得 =0.56658 =0.56714 。迭代迭代4 4次便可得到精度次便可得到精度 的的结果结果, ,而不用加速技术需迭代而不用加速技术需迭代1818次次, ,效果
28、显著。效果显著。 （2）埃特金（）埃特金（Aitken）方法方法在在加加权权法法中中, 估估计计L的的值值有有时时不不太太方方便便。假假设设在在求得求得 以后以后, 先求出先求出由由 , 利利用用中中值值定定理理可可得得( 在在求求根根区区间间变化不大变化不大, 用某个定值用某个定值L近似地替代之近似地替代之)L 将迭代值将迭代值 再迭代一次再迭代一次, 得新的迭代值得新的迭代值则则 将上述两个方程联立消去常数将上述两个方程联立消去常数L化简可得化简可得 这样得到埃特金加速公式这样得到埃特金加速公式例例 用埃特金方法求方程用埃特金方法求方程 在初值在初值 附近的一个根附近的一个根, 精度要求精度要求 ， 取迭代格式取迭代格式解解 埃特金方法迭代格式为埃特金方法迭代格式为只迭代二次就得到满足精度要求的解。只迭代二次就得到满足精度要求的解。
