一类非线性方程组的改进牛顿算法

Newton Method for Nonlinear Equations Can Be Improved

研究求解非线性方程组的局部算法。提出了LU分解的牛顿步与预优广义共轭梯度步的优化组合的方法(简称LU Newton PGCG)。在保证传统牛顿方法恰二阶收敛的条件下,证明了新算法也具有相同的恰二阶收敛的优点,但在计算量上却有一定的节省。如变量维数n=150时,其计算量可以节省40%,且当变量维数n趋于无穷时,二者的计算量之比以ln2 lnn的速度趋于零。

A local algorithm for nonlinear equations is discussed. The LU factorization Newton step and the preconditioned generalization conjugate gradient(LUNewtonPGCG) step are combined. This new algorithm is proved quadratically convergent exactly under the same conditions ensuring the LUNewton algorithm quadratically convergent exactly . But the cost on computation is less than that on the LUNewton algorithm. The ratio of computation will decrease 40% when n=150,and reduce to zero at the rate of ln 2/ln n when n is infinite.