非线性方程的求根方法优秀PPT.ppt

非线性方程的求根方法1第一页，本课件共有50页Bisection Method方程求根的二分法方程求根的二分法Fixed-Point Iteration迭代法及其收敛性迭代法及其收敛性Newton Method of Nonlinear Equations Newton迭代法迭代法2第二页，本课件共有50页在实际应用中有许多非线性方程的例子，例如在实际应用中有许多非线性方程的例子，例如（1）在光的衍射理论（）在光的衍射理论（the theory of diffraction of light)中中,需要求需要求x-tanx=0的根的根（2）在行星轨道（）在行星轨道（planetary orbits）的计算）的计算中中,对任意的对任意的a和和b，需要求，需要求x-asinx=b的根的根（3）在数学中，需要求在数学中，需要求n次多项式次多项式xn+a1 xn-1+.+an-1 x+an 0的根的根3第三页，本课件共有50页方程求解是科学计算中一个重要的研究对象方程求解是科学计算中一个重要的研究对象;几百年前就已经找到了代数方程中几百年前就已经找到了代数方程中二次至五次方程二次至五次方程的的求解公式求解公式;但是但是,对于更高次数的代数方程对于更高次数的代数方程目前仍无有效的精确解目前仍无有效的精确解法法;对于无规律的非代数方程的求解也无精确解法对于无规律的非代数方程的求解也无精确解法;因此因此,研究非线性方程的数值解法成为必然。研究非线性方程的数值解法成为必然。4第四页，本课件共有50页非线性方程的一般形式：非线性方程的一般形式：f(x)=0代数方程：代数方程：f(x)=a0+a1x+anxn（an 0）超越方程超越方程：f(x)中含三角函数、指数函数、或其他超越中含三角函数、指数函数、或其他超越函数。函数。用用数值方法数值方法求解非线性方程的步骤：求解非线性方程的步骤：（1）找出有根区间；（）找出有根区间；（只含一个实根的区间称隔根区只含一个实根的区间称隔根区间间）（2）近似根的精确化。从隔根区间内的一个或多个）近似根的精确化。从隔根区间内的一个或多个点出发，逐次逼近，寻求满足精度的根的近似值。点出发，逐次逼近，寻求满足精度的根的近似值。5第五页，本课件共有50页Bisection Method 二分法二分法二分法的基本思想：二分法的基本思想：假定假定f(x)=0在在a,b内有内有唯一单实根唯一单实根x*，考察有根，考察有根区间区间a,b，取中点，取中点x0=(a+b)/2，若，若f(x0)=0，则，则x*=x0，否则，否则，（1）若）若f(x0)f(a)0，则，则x*在在x0右侧，令右侧，令a1=x0，b1=b;（2）若）若f(x0)f(a)0，则，则x*在在x0左侧，令左侧，令a1=a，b1=x0。介值定理介值定理 设函数设函数f(x)在区间在区间a,b连续，且连续，且f(a)f(b)0，则方程，则方程f(x)=0在区间在区间(a,b)内至少有内至少有一个根。一个根。6第六页，本课件共有50页以以a1,b1为新的隔根区间，且仅为为新的隔根区间，且仅为a,b的一半，对的一半，对a1,b1重复前过程，得新的隔根区间重复前过程，得新的隔根区间a2,b2，如此二分下去，如此二分下去，得一系列隔根区间：得一系列隔根区间：a,b a1,b1 a2,b2 ak,bk 其中每个区间都是前一区间的一半，故其中每个区间都是前一区间的一半，故ak,bk 的长度：的长度：当当k趋于无穷时趋于趋于无穷时趋于0。即若二分过程无限继续下去，这些。即若二分过程无限继续下去，这些区间最后必收敛于一点区间最后必收敛于一点x*，即方程的根。，即方程的根。7第七页，本课件共有50页性质：f(an)f(bn)0;bn an=(b a)/2nBisection Method每次二分后，取有根区间的中点每次二分后，取有根区间的中点x xk=(=(ak k+b bk k)/2作作为根的近似值，则可得一近似根序列：为根的近似值，则可得一近似根序列：x0,x1,x2,该序列必以根该序列必以根x*为极限。为极限。实际计算中，若给定充分小的正数实际计算中，若给定充分小的正数实际计算中，若给定充分小的正数实际计算中，若给定充分小的正数 0 0和允许误差和允许误差和允许误差和允许误差限限限限 1，当，当，当，当|f(|f(x xn)|)|0 0或或或或b bn n-a an n 1时，均可取时，均可取时，均可取时，均可取x x*x xn n。8第八页，本课件共有50页定理定理 设设x*为方程为方程f(x)=0在在a,b内唯一根，且内唯一根，且f(x)满满足足f(a)f(b)0，则由二分法产生的第，则由二分法产生的第n个区间个区间an,bn 的中点的中点xn满足不等式满足不等式证明：证明：9第九页，本课件共有50页1.1.先验误差估计先验误差估计：利用误差估计定理，令利用误差估计定理，令得得 从而得到对分次数从而得到对分次数k k，取，取x xk k作为根得近似值作为根得近似值x x*。2.2.后验误差估计：后验误差估计：给定给定，每步检查每步检查 ，若成，若成立，则取立，则取 ，否则继续对分。，否则继续对分。10第十页，本课件共有50页 例例例例 用二分法求用二分法求 在在(1,2)(1,2)内的根，要求绝对误差不超过内的根，要求绝对误差不超过 解解解解：f(1)=-50 -(1,2)+f(1.25)0 (1.25,1.375)f(1.313)0 (1.313,1.375)f(1.344)0 (1.344,1.375)f(1.360)0 (1.360,1.368)f(1.5)0 (1,1.5)11第十一页，本课件共有50页计算过程简单，收敛性可保证；计算过程简单，收敛性可保证；对函数的性质要求低，只要连续即可。对函数的性质要求低，只要连续即可。收敛速度慢；收敛速度慢；不能求不能求复根和重根复根和重根；调用一次求解一个调用一次求解一个a,b间的多个根无法间的多个根无法求得。求得。二分法求解非线性方程的优缺点二分法求解非线性方程的优缺点12第十二页，本课件共有50页不动点迭代法不动点迭代法不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性迭代收敛的加速方法迭代收敛的加速方法Fixed-Point Iteration 13第十三页，本课件共有50页迭代法的基本思想迭代法的基本思想迭代法是一种迭代法是一种逐次逼近逐次逼近的方法，用某个的方法，用某个固定公式固定公式反复校正反复校正根的近似值，使之逐步精确化，最后得到满足精度要求的结根的近似值，使之逐步精确化，最后得到满足精度要求的结果。果。例：求方程例：求方程 x3-x-1=0 在在 x=1.5 附近的一个根。附近的一个根。将所给方程改写成将所给方程改写成假设初值假设初值x0=1.5是其根，代入得是其根，代入得x1x0，再将，再将x1代入得代入得x2x1，再将，再将x2代入得代入得14第十四页，本课件共有50页如此下去，如此下去，这种逐步校正的过程称为迭代过程这种逐步校正的过程称为迭代过程。这里用的公。这里用的公式称为式称为迭代公式迭代公式，即，即k=0,1,2,迭代结果见下表。仅取六位数字，迭代结果见下表。仅取六位数字，x7与与x8相同，即认为相同，即认为x8是方程是方程的根。的根。x*x8=1.32472 k xk k xk012341.51.357211.330861.325881.3249456781.324761.324731.324721.3247215第十五页，本课件共有50页将连续函数方程将连续函数方程f(x)0改写为等价形式：改写为等价形式：x=(x)其中其中(x)也是连续函数，称为迭代函数。也是连续函数，称为迭代函数。不动点不动点：若：若x*满足满足f(x*)=0，则，则x*=(x*)；反之，若；反之，若x*=(x*)，则，则f(x*)=0，称，称x*为为(x)的一个不动点。的一个不动点。不动点迭代不动点迭代：(k=0,1,)若对任意若对任意 x0 a,b，由上述迭代得序列，由上述迭代得序列xk，有极限，有极限则称迭代过程收敛，且则称迭代过程收敛，且x*=(x*)为为(x)的不动点。的不动点。Fixed-Point Iteration16第十六页，本课件共有50页迭代法并不总令人满意，如将前述方程迭代法并不总令人满意，如将前述方程x3-x-1=0改写为另改写为另一等价形式：一等价形式：建迭代公式：建迭代公式：仍取初值仍取初值x0=1.5，则有，则有x1=2.375，x2=12.396，x3=1904,结果越来越大。此时称迭代过程发散。结果越来越大。此时称迭代过程发散。x2 x1 x0y=x几何意义几何意义：17第十七页，本课件共有50页xy0 x2Px*P0 x1x0P1P2Q0Q1Q2y=xy=(x)收敛的迭代法收敛的迭代法18第十八页，本课件共有50页发散的迭代法发散的迭代法xy0 x2Px*P0 x1x0P1P2Q0Q1y=xy=(x)19第十九页，本课件共有50页RemarkRemark：可以通过不同的途径将：可以通过不同的途径将f f(x x)=0)=0化为化为x x=(x x)的形式，从而构造不同的迭代公式，得到不同的迭代序的形式，从而构造不同的迭代公式，得到不同的迭代序列。在所有这些构造的迭代公式中形成的序列中，有的列。在所有这些构造的迭代公式中形成的序列中，有的序列是收敛的，而有些是发散的。序列是收敛的，而有些是发散的。问题问题：如何选取合适的迭代函数：如何选取合适的迭代函数(x x)？迭代函数迭代函数(x x)应满足什么条件，序列应满足什么条件，序列 x xk k 收敛收敛？怎样加速序列怎样加速序列 x xk k 的收敛？的收敛？20第二十页，本课件共有50页定理（存在性）定理（存在性）设设(x)Ca,b且满足以下两且满足以下两个条件：个条件：（1）对于任意）对于任意x a,b，有，有a(x)b；（2 2）若）若(x)在在a,b一阶连续，且一阶连续，且存在常数存在常数0 0L1，使得对任意使得对任意x a,b，成立，成立|(x)|L则则(x)在在a,b上存在唯一的不动点上存在唯一的不动点x*。存在性与迭代法的收敛性存在性与迭代法的收敛性21第二十一页，本课件共有50页证证 若若 或或 ,显然显然 有不动点有不动点设设 ,则有则有 ,记记 则有则有所以所以,存在存在x*,使得使得即即 ,x*即为不动点即为不动点.22第二十二页，本课件共有50页唯一性证明唯一性证明：设有设有 x1*x2*,使得使得 ,则则其中其中,介于介于 x1*和和 x2*之间之间.由定理条件由定理条件可得可得,矛盾矛盾,这说明只可能有这说明只可能有 x1*=x2*.23第二十三页，本课件共有50页定理（全局收敛性）定理（全局收敛性）设设(x)Ca,b且满足以下两个且满足以下两个条件：条件：（1）对于任意）对于任意x a,b，有，有a(x)b；（2 2）若）若(x)在在a,b一阶连续，且一阶连续，且存在常数存在常数0 0L1，使得对任意，使得对任意x a,b，成立，成立|(x)|L 则对任意则对任意x0 a,b，由，由xn+1=(xn)得到的迭代序列得到的迭代序列xn 收敛到收敛到(x)的不动点的不动点x*，并有误差估计：，并有误差估计：24第二十四页，本课件共有50页证明：证明：(0L1)所以所以,故迭代格式收敛故迭代格式收敛.25第二十五页，本课件共有50页反复递推，可得误差估计式反复递推，可得误差估计式反复递推，可得误差估计式反复递推，可得误差估计式26第二十六页，本课件共有50页定义定义 设设(x)有不动点有不动点x*，若存在，若存在x*的某邻域的某邻域R：|x-x*|，对任意，对任意x0 R，迭代过程，迭代过程xk+1=(xk)产产生的序列生的序列xk R且收敛到且收敛到x*，则称不动点迭代法，则称不动点迭代法xk+1=(xk)局部收敛局部收敛。注：定理给出的收敛性称全局收敛性，实注：定理给出的收敛性称全局收敛性，实际应用时通常只在不动点际应用时通常只在不动点x*邻近考察其收敛性，邻近考察其收敛性，称局部收敛性。称局部收敛性。27第二十七页，本课件共有50页证明证明：根据连续函数性质，因：根据连续函数性质，因(x)连续，存在连续，存在x*的某邻域的某邻域R：|x-x*|，对任意，对任意x R，|(x)|L1，且，且|(x)-x*|=|(x)-(x*)|=|()|x-x*|L|x-x*|x-x*|即对任意即对任意x R，总有总有(x)R。由全局收敛性定义知，迭代过程由全局收敛性定义知，迭代过程 xk+1=(xk)对于任对于任意初值意初值x0 R均收敛。均收敛。定理（局部收敛性）定理（局部收敛性）设设x*为为(x)的不动点，的不动点，(x)在在x*的某邻域连续，且的某邻域连续，且|(x*)|1，则不动，则不动点迭代法点迭代法xk+1=(xk)局部收敛。局部收敛。28第二十八页，本课件共有50页例例：用不同方法求：用不同方法求 的根的根解解：（：（1）（2）（3）（4）29第二十九页，本课件共有50页取取x0=2，对上述四种方法，计算三步所得结果如下：，对上述四种方法，计算三步所得结果如下：kxk(1)(2)(3)(4)0 x022221x131.51.751.752x2921.734751.7321433x3871.51.7323611.732051注：注：x*=1.732050830第三十页，本课件共有50页例例 用迭代法求方程用迭代法求方程 在在 内内的实根。取的实根。取 解：解：对方程进行如下三种变形：对方程进行如下三种变形：建立迭代格式：建立迭代格式：这是一个发散的迭代格式。这是一个发散的迭代格式。31第三十一页，本课件共有50页建立迭代格式：建立迭代格式：该迭代格式收敛。该迭代格式收敛。建立迭代格式：建立迭代格式：该迭代格式收敛。该迭代格式收敛。32第三十二页，本课件共有50页例例.用迭代法求方程用迭代法求方程 在在 内内的实根。取的实根。取 解：对方程进行如下三种变形：解：对方程进行如下三种变形：理论分析：理论分析：由上述定理知，迭代格式发散，和计算结果吻合由上述定理知，迭代格式发散，和计算结果吻合。理论分析：理论分析：由定理知，迭代格式收敛，和计算结果吻合。由定理知，迭代格式收敛，和计算结果吻合。33第三十三页，本课件共有50页理论分析：理论分析：由定理知，迭代格式收敛，和计算结果吻合。由定理知，迭代格式收敛，和计算结果吻合。而且，而且，和和都收敛，但都收敛，但收敛的效果比收敛的效果比好。好。34第三十四页，本课件共有50页例例 求求 在在00，11内的一个实根内的一个实根.将方程化为等价方程将方程化为等价方程 因为因为 又又 所以对于所以对于00，11中任意初值，迭代序列中任意初值，迭代序列 收敛，计算结果如下表，取收敛，计算结果如下表，取 35第三十五页，本课件共有50页注注.方程方程 也可化为等价方程也可化为等价方程 但此时定理、推论条件不成立，迭代序列不能保证收敛。但此时定理、推论条件不成立，迭代序列不能保证收敛。36第三十六页，本课件共有50页Remark2Remark2：可以证明，若在根可以证明，若在根 的邻域中的邻域中 ，则，则可以以邻域内任何一点可以以邻域内任何一点 为初始值，用迭代过程产生为初始值，用迭代过程产生的序列就一定不会收敛于的序列就一定不会收敛于 。事实上，。事实上，Remark3Remark3：当当 不取在不取在 的邻域为内时可能不收敛。的邻域为内时可能不收敛。Remark1Remark1：全局与局部收敛定理中的条件都是充分全局与局部收敛定理中的条件都是充分条件，条件满足则迭代法收敛，不满足则不能判定，条件，条件满足则迭代法收敛，不满足则不能判定，此时可以用试算来判定迭代法的是收敛性。此时可以用试算来判定迭代法的是收敛性。Remark4Remark4：全局收敛定理中的两个误差估计式实际上全局收敛定理中的两个误差估计式实际上给出了迭代收敛的两个准则：事后误差估计与事先误给出了迭代收敛的两个准则：事后误差估计与事先误差估计（利用估计式可以预先求出迭代次数差估计（利用估计式可以预先求出迭代次数k k）。）。37第三十七页，本课件共有50页一、事先误差估计法一、事先误差估计法二、事后误差估计法二、事后误差估计法有有先计算满足误差要求的迭代次数先计算满足误差要求的迭代次数k k，再进行迭代。，再进行迭代。由由由由因此可以用因此可以用 来控制迭代过程。来控制迭代过程。只要使只要使 ，就可使，就可使 ，对于较为复杂的迭代函数，其导数也较为复杂，对于较为复杂的迭代函数，其导数也较为复杂，使得使得L L难以取得，因而实际中不常用此方法。难以取得，因而实际中不常用此方法。38第三十八页，本课件共有50页Remark1:Remark1:迭代方法的优点是计算程序简单，迭代方法的优点是计算程序简单，并且虽然是以求解非线性方程的实根来讨论并且虽然是以求解非线性方程的实根来讨论的，但类似的结果完全可以推广到求方程的的，但类似的结果完全可以推广到求方程的复数根的情形。复数根的情形。Remark2Remark2：由全局收敛定理知，若由全局收敛定理知，若L L 1 1，则，则 x xk k 必然收敛较慢；若必然收敛较慢；若L L11 r1时称时称时称时称超线性收敛超线性收敛超线性收敛超线性收敛。且且r 越大，收敛越快。越大，收敛越快。迭代收敛阶定义迭代收敛阶定义40第四十页，本课件共有50页例例：线性收敛线性收敛.平方收敛平方收敛.例例：迭代收敛阶举例迭代收敛阶举例41第四十一页，本课件共有50页定理定理 设设x*为为x=(x)的不动点，若的不动点，若(x)满足：满足：（1）(x)在在x*附近是附近是p次连续可微的次连续可微的(p1)；（2）则迭代过程则迭代过程xn+1=(xn)在点在点x*邻近是邻近是p阶收敛的。阶收敛的。得得所以所以故故故故迭代过程迭代过程迭代过程迭代过程xn+1n+1=(x xn n )p)p阶收敛。阶收敛。阶收敛。阶收敛。证：证：由由Taylor公式公式42第四十二页，本课件共有50页 待定参数法：待定参数法：若若|g(x)|1，则将则将 x=g(x)等价地改造为等价地改造为求求K，使得，使得例：例：求求 在在(1,2)的实根。的实根。如果用如果用 进行迭代，则在进行迭代，则在(1,2)中有中有现令现令希望希望，即，即在在 (1,2)上可取任意上可取任意 ，例如，例如K=0.5，则则对应对应 即产生收敛序列。即产生收敛序列。迭代收敛的加速方法迭代收敛的加速方法 accelerating convergence 43第四十三页，本课件共有50页一一 Aitken加速收敛方法加速收敛方法假定假定(x)改变不大，近似取某个近似值改变不大，近似取某个近似值L，则有，则有由微分中值定理，有由微分中值定理，有同理同理两式相比，得两式相比，得44第四十四页，本课件共有50页类推可得类推可得故故上式即为上式即为Aitken加速收敛方法的迭代格式加速收敛方法的迭代格式.45第四十五页，本课件共有50页 分别用简单迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根。(=1.585471802)例例46第四十六页，本课件共有50页 解解 用迭代公式：k简单迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078取x0=/2,计算结果如下:xk+1=1.6+0.99cosxk ，k0，1，2，47第四十七页，本课件共有50页二、二、Steffensen迭代法迭代法或写成或写成将将Aitken加速技巧与不动点迭代法加速技巧与不动点迭代法结合结合,可得可得48第四十八页，本课件共有50页解解：由前知，迭代格式：由前知，迭代格式 xk+1=xk3-1 是发散的。用是发散的。用steffensen迭代法计算。取迭代法计算。取(x)=x3-1，结果如下：，结果如下：k xk yk zk0123451.51.416291.355651.328951.324801.324722.375001.840921.491401.347101.3251812.39655.238882.317281.444351.32714即使不动点迭代法不收敛，用即使不动点迭代法不收敛，用steffensen迭代法仍迭代法仍可能收敛。可能收敛。例：例：用用steffensen迭代法求解方程迭代法求解方程 x3-x-1=0。49第四十九页，本课件共有50页例例：求方程求方程3x2-ex=0在在3,4中的解。中的解。解：解：由由ex=3x2，取对数，取对数 x=ln3x2=2lnx+ln3=(x)构造迭代法构造迭代法 xk+1=2lnxk+ln3故故 (x)=2/x，当，当x 3,4时，时，(x)3,4，且且max|(x)|2/31，据前定理知迭代法收敛。据前定理知迭代法收敛。取取x0=3.5，经计算可得迭代，经计算可得迭代16次后次后x16=3.73307，有，有6位有效数字。位有效数字。若用若用steffensen迭代法加速，结果如下：迭代法加速，结果如下：k xk yk zk03.53.604143.6620213.734443.733813.7334723.7330750第五十页，本课件共有50页