代数方程根的近似求解方法多项式方程1 011( )0nn nnnP xa xa xaxa,称为 n次代数方程 ,又称多项式方程 . 其中1 2kna，，，是实系数或复系数 ,00a. 当1n时, 它叫高次代数方程 , 其次数是 n . 多项式的零点就是对应代数方程的根. 当其次数高于四次 时是没有公式解的 , 因此实际的求解方法大多是研究其近似根，这些方法大都可 以在数值分析理论中找到. 要求高次代数方程实根的精确值, 往往是比较困难的 , 因此这就需要寻求方程的近似解. 下面介绍几种近似求解的方法. 将超越方程0fx左端换成多项式( )nPx, 则超越方程就变成了高次代数方程. 超越方程求根的各种方法也适用于代数方程. 求方程的近似解 , 可分两步来 做. (1) 确定根的分布区间,a b, 即使所求的根是位于这个区间内的唯一实根. 此项工作又称根的隔离 , 而区间,a b又称实根的隔离区间 . 具体方法是 : 一方面可用图解法 , 由于方程0fx的实根在几何上表示曲线yfx与 x轴交点的横坐标 , 故可先较精确地画出函数yfx的图形, 然后从图上定出它与x轴交点的大概位置 . 由于作图和读数的误差 , 这种做法得不出根的高精确度的 近似值 , 但一般可确定出根的隔离区间. 另一方面 , 利用连续函数的介值定理来找根的隔离区间, 即若实的连续函数fx在区间,a b的两个端点的值异号 , 则fx在此区间内至少有一个根. ( 2) 以根的隔离区间的一个端点作根的初始近似值, 逐步改善根的近似值的精 确程度 , 直至求得满足精确度要求的近似解. 这里介绍 2种常用方法 : 二分法与牛顿法 1.1二分法这是利用介值定理计算实函数实根的简单可行的方法. 设在区间00,a b上连续, 且000fxfa的函数fx, 取00,a b的二等分点00 02abx, 计算0fx, 若00fx则0x为根; 若000fxfa, 取10aa,10bx作为新的区间端点 ; 若000fxfa, 取10ax,10bb作为新区间端点 ; 若000fxfa, 取10ax,10bb作为新区间端点 .11,a b的二等分点为11 12abx, 计算1fx的值, 并重复以上步骤以确定新区间22,ab, 如此继续下去, 得到区间序,kkab0,1,2k, 它满足0kkfafb, 且001 2kkkbaba , 当达到指定的精度要求时 , 则取2kkbax为方程的近似解 ,且其误差不超过1 1 002kba. 例 1 求方程310fxxx在区间1.0,1.5内的一个实根，要求准确到小数点后的第 2 位. 解：这里1,1.5ab，而0fa，0fb取,a b的中点01.25x.将区间二等分，由于00fx，即0fx与fa同号，故所求的根x必在0x右侧，这时应令101.25ax，11.5bb而得到新的有根区间11,a b。
如此反复二分下去，二分过程无需赘述 .我们现在预估所要二分的次数，按误差估计， 只要二分 6次（6k） ，便能达到预定的精度 . 60.005xx. 二分法的计算结果见表1. k kakbkxkfx符号0 1 2 3 4 5 6 1.0 1.25 1.3125 1.3203 1.5 1.375 1.3438 1.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.32422 - + - + + - - 表1 1.2 牛顿法 牛顿法在非线性方程 (组)近似求解方面 , 具有重要的地位 , 其算法的效率很 高. 牛顿法又称切线法 , 它的基本思想是从一个初始的近似解出发, 过该点作曲线的切线 , 以切线与 x轴交点的横坐标作为下一个更精确的近似解.设已知方程0fx有近似根kx(假定0kfx)，将函数fx在点kx展开，有,kkkfxfxfxxx于是方程0fx可近似的表示0kkkfxfxxx这是个线性方程，记其根为1kx，则1kx的计算公式为1k kk kfxxxfx，0,1,,k这就是牛顿法 .牛顿法有明显的几何解释，方程0xf的根x可解释为曲线xfy与 x轴的交点的横坐标。
设kx是根x的某个近似值， 过曲线xfy上的横坐标为kx的点kP引切线，并将切线与x轴的交点的横坐标1kx作为x的新的近似值 .注意到切线方程为.kkkyfxfxxx这样求的的值1kx必满足0kkkfxfxxx，从而就是牛顿公式1k kk kfxxxfx0,1,,k的计算结果 . 关于牛顿法的收敛性，对1k kk kfxxxfx的迭代函数为fxxxfx由于2,fxfxxx fx假定x是fx的一个单根，即0fx，0fx则由上式可知0x，于是可以判定，牛顿法在根x的邻近是平方收敛的 .又因,fxxfx故我们 可得1 2lim. 2kk kfxxxfxxx下面列出牛顿法的计算步骤：步骤1 准备选定初始近似值0x，计算00ffx，00ffx. 步骤2 迭代按公式010 0fxxf迭代一次，得新的近似值1x，计算11ffx,11ffx．步骤３ 控制如果1x满足1或12f，则终止迭代，以1x作为所求的根；否则转步骤４．此处1，2是允许误差，而10110 1 1xxxCxxxCx，当时，当时其中 c是取绝对误差或相对误差的控制常数，一般可取c=1．步骤４修改如果迭代次数达到预先指定的次数N ， 或者10f， 则方法失败；否则以111,,xff代替000,,xff转步骤 2继续迭代 . 列2 用牛顿法解方程10xxe. 解：这里牛顿公式为11kx k kk kxexxx取迭代初值00.5x，迭代结果列于表 2中. 1.3抛物牛顿法 抛物牛顿法构造定理1 设0fx为非线性的 ,kxx为0fx的一个近似解 , 若fx在kx的某领域内 3阶可导 , 且0kfx则有抛物牛顿迭代公式212kkkkkk kfxfxfxfx xxfx,1,2,k其中, 当0fx时, 取1, 当0fx时, 取1. 抛物牛顿法的解释与收敛性分析1) 抛物牛顿法的几何解释 .从几何上看 , 如果在迭代点所作的抛物线k kx0 1 2 3 4 10 10.750000 10.723837 10.723805 10.723805 22k kkkkfxg xfxfxxxxx与 x 轴相交 , 则抛物牛顿法是将曲线fx上过点,kkP xfx的抛物线22k kkkkfxg xfxfxxxxx与 x 轴的交点来代替fx与x轴的交点 , 抛物线g x与fx在点,kkP xfx相交且具有相同的切线和凹凸性, 从而将抛物线0g x的解作为0fx的一个新的近似解 .2) 抛物牛顿法的代数解释 .从代数的角度看 , 由于fx与g x在迭代点有相同的0 1 2、 、阶导数, 若将 x视为复数 z, 则抛物牛顿法是求在复数域上满足fz的二阶Taylor展式0g z的一个新的近似解 , 由于抛物方程有可能带来复数解, 故抛物牛顿法能迭代到实多项式的近似复解上去.如果获得的 2个近似解是实数1x,2x, 意味着所作的切抛物线与x轴相交于12,xx, 如果获得的 2个近似解是非实数的复数12,zz. 则意味着切抛物线不与x 轴相交而仅是复平面上满足10fz,20fz的两个复数12,zz这是抛物牛顿法与切线牛顿法本质上的区别, 也使牛顿法从实数域推广到复数域 .抛物牛顿法与切线牛顿法共同构架了非线性代数方程在复数域上求近似解的基本方法 , 从而解决了用牛顿法求实多项式全部近似实根和复根的问题.3) 抛物牛顿法收敛性分析 . 抛物牛顿法中迭代式根号前的符号可正可负 , 它对应着近似的抛物线或相应的近似方程在复数域上的2个解, 的取法应使1kx比kx更接近精确解x. 为方便起见 , 也可取定1或1, 一般总会收敛到0fx的解.已知切线牛顿法至少是 2阶收敛的 , 此处抛物牛顿法至少是 3阶收敛的 , 所以 抛物牛顿法比切线牛顿法收敛速度快,抛物牛顿法的另一个用途是当切线牛顿法失效 , 即0kfx而0kfx时, 可用来替代切线牛顿法 , 继续迭代计算 . 例3 求5421683010fxxxxx 的近似根 (精确到-610) 解：一个 5次实多项式在复数域内恰有5个根.该曲线与 x轴只有 3个交点，根 据f()x的性质，它有 3个实根，一对共轭复根，若用切线牛顿法，只能迭代出3个实根，为求出其所有根，采用抛物牛顿法.由于43141212 2fxxxx ，321212fxxx所以抛物牛顿法迭代函数为22fxfxfx fxxxfx4386443231383183412848484857672022035,21212xxxxxxxxxx xxx此处1，取1，010x获得方法的近似解3.025372x，切线法需要 9次，抛物法只需 7次迭代 .抛物牛顿法与切线牛顿法迭代对比如表3所示迭代序数k切线法迭代值kx迭代序数k抛物法迭代值kx0 1 5 7 9 -10 -7.0466 -3.2033 -3.2056 -3.025372 0 1 5 7 -10 -7.2171-2.0873i -3.0106-0.0061i -3.025372 表3 取1初值00x切线牛顿法经过 18次迭代获得与上面相同的实根， 抛物牛顿法经过 5次迭代获得方程的近似复根0.284800 1.831036xi迭代序列如表 3所示迭代序数k切线法迭代值kx迭代序数k抛物法迭代值kx0 1 5 10 15 18 0 -53.1998 -20.8480 -6.1877 -3.0281 -3.025372 0 1 2 3 4 5 0 0.6667+2.1344i 0.2885+1.8515i 0.2848+1.8310i 0.2848+1.8310i 0.284000+1.831036i 表4 二. 劈因子法用 x的二次式2 12Uxu xux除nxp则得商xQ及余式rx =12xr xr，因而有nPxxxr xUQ设xU是一个近似二次因式，修改1u和2u使对应的余式更接近于零.为此，作线性近似，取2 1122xuduxuduUx，使11220rxrdrxrdr，则修正量1du、2du应满足方程组011022rdrrdr即11 121 1222 122 1200rrduduruurrduduruu利用已知关系可求出11ru、21ru、12ru和22ru代入上面方程组， 就能求出1u和2u的校正量1du和2du.而11udu和22udu就是更好的二次因式的两个系数. 三.Bernoulli方法 引理1 对任何的n次代数多项式方程1 011( )0nn nnnP xa xa xaxa，其对应的齐次常系数线性差分方程110knknnkua ua u的特征方程为1 110nn nnxa xaxa. 引理2 如果差分方程110knknnkuaua u的初始条件为0120nuuu，11nu, 则其解可以表示为111,0kk knnuc xc xc，其中：1,2,ixin为方程1 011( )0nn nnnPxa xa xaxa的 n个根．定理 设代数多项式方程1 011( )0nn nnnPxa xa xaxa有一个单重的最大模零点1x，0ku为与之相关联的差分方程的解序列，且差分方程的初始条件为120,nnuuu11u,则1 1limkk kuxu设 E 是使数列kF的下标增加 1 的运算子 , 即1kkEFF, 则齐次常系数线性差分方程1 11nn nknnkP E FEa EaEaF11n kn kFa F110nknkaFa F的特征方程就是代数方程0nPx , 这个代数方程的根12,,,nx xx叫做差分方程的特征根 . 给定11nnFFF，， ，的定值0,0 ， ，1, 即可依次从上式算出nF ,1nF ,, 这样就定出差分方程的一个特解. 如 果特 征 根 各不 相 同 , 则 差 分 方 程 的 一 般 解 是1122kkk knn。