简介
数值求解超越方程时首先需要确定解的分布区域,它可以利用图解法或者根据ƒ(z)的解析性质来确定。当ƒ(x)为实函数时,确定方程实根的分布的最常用方法是应用连续函数的中值定理:如果实的连续函数ƒ(x)在区间
的两个端点的值异号,则在此区间内至少有一个根。二分法 利用中值定理计算实函数实根的简单易行的方法,算法如下:
设区间
满足条件的二等分点为计算的值,若,即为所求解;若,作为新的区间端点;若,取作为新区间的端点。的二分点为计算ƒ(x1)的值并重复上述步骤以确定新的区间,如此继续下去。则得到区间序列(),它满足达到指定的精确度要求时,则取为方程的解,它与精确解的误差不超过迭代法 解超越方程的主要方法,既适用于求实根,也适用于求复根。使用这类方法时一般需要知道根的足够好的近似值。最常用的方法有牛顿法、割线法、二次插值法、双曲插值法、切比雪夫迭代法、艾特肯δ2加速方法和斯梯芬森方法等。
牛顿法 也称切线法,其计算公式为z0为事先选定的根的初始近似。设z为 ƒ(z)的根,若ƒ(z)在z的某邻域内二次可微,且
,则当z0与z充分接近时,牛顿法至少是二阶收敛的,即当k充分大时有估计式成立,C为确定的常数。一般说来,牛顿法只具有局部收敛性,即仅当初始近似与根充分接近时才收敛。但是,当ƒ(x)为实函数,且于上和 ƒ″(x)不变号时,若ƒ(x)于上有根,则只要初始近似x0满足条件,牛顿法就收敛。一般情形,为减弱对初始近似的限制,可利用牛顿下降算法,其算式为为迭代参数,由条件确定,牛顿法的次近似是ƒ(z)在zk处的泰勒展开式的线性部分的根。割线法 又称弦位法,其算式为z0、z1为初始近似。若ƒ(z)于其根z的某邻域二次连续可微,且
则z0、z1与z充分接近时,割线法收敛于z,并当k充分大时有估计式式中C为常数,割线法的次近似是以zk、为插值节点的线性插值函数的根,如果利用更精确的近似表达式则可构造出更高阶的迭代法。二次插值法 亦称缪勒方法,是利用二次插值多项式构造的迭代算法。设已确定了zk、
、,则就取为以zk、、为节点的二次插值多项式两个根中与zk最接近者,其算式为式中“±”号选成使分母的模为最大者,而-式中当分母为0,则
。双曲插值法 利用线性分式插值构造的迭代算法,其算式为式中μk、δk、Δzk和ƒk的意义与二次插值法相同。
若ƒ(z)在其根z的某邻域内三次可微,并且z0、z1、z2与z充分接近,则二次插值法和双曲插值法均收敛。此外,如果
,对充分大的k,有估计式式中C为确定常数,τ为方程式的惟一正根,。切比雪夫迭代法 三阶收敛的方法,其算式为当ƒ(z)在其根z的邻域内三次可微且
时,对充分大的k,有C为确定常数。艾特肯δ2加速方法 提高迭代法收敛速度的有效算法,设
为迭代序列,δ2加速的算式为若ƒ(z)在其根z处充分光滑,且,则对充分大的k,有并且若zk是阶收敛,即C0均为常数。当时也有加速作用。此算法可以循环使用。斯梯芬森方法 不算微商而二阶收敛的方法,其算式为它可由迭代算法循环使用 δ2程序导出。
所有的迭代法用于求重根(即
)时, 其收敛速度将变慢,收敛阶将降低。为求得达到所需精度的解而花费的代价是评价迭代法优劣的依据,效能指数是其重要指标,它定义为p1/宝,p为收敛阶,μ为每步需要计算的函数值和微商值的总数。效能指数越大,说明方法越好。二分法及上述各种迭代法的收敛阶(单根时和重根时)和效能指数如表。只有当初始近似与解充分接近时,迭代法才收敛,这是所述算法的共同特点。减弱对初始近似的限制是提高迭代法有效性的重要措施,例如,牛顿法中引进下降因子。对一些特殊函数类(如单调函数,只有实根的解析函数等)的大范围收敛迭代算法也有一些研究工作。
参考书目
A.Ostrowski,Solutions of Equations in Euclidean and Banach Spaces, 3rd ed., Academic Press, New York, 1973.
J.F.Traub,Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1964.