Newton-Raphson法的改进方法

虽然完整的Newton-Raphson法具有平方收敛性和最小的迭代次数，但每次迭代需要很大的计算量。例如，构造完整的Jacobi矩阵需要n²次计算，如果Ja-cobi矩阵是满矩阵，每次迭代对其进行LU分解所需要的运算次数为n³数量级。因此，对Newton-Raphson法的大多数改进着眼在减少构造Jacobi矩阵的计算量或者减少进行LU分解的计算量。

再次考察Newton-Raphson法的迭代格式：

I：x^k+1=x^k-[J（x^k）]^-1f（x^k）

这个迭代格式可以被写成更为一般性的格式：

I：x^k+1=x^k-[M（x^k）]^-1f（x^k） （3.45）(www.xing528.com)

式中，M是一个n×n矩阵，它可以是也可以不是x^k的函数。注意，即使M≠J，如果迭代过程将f（x）驱动到零，这种迭代格式仍然会收敛到正确解。因此，对Newton-Raphson法进行简化的一种做法是，寻找一个比Jacobi矩阵更容易计算的合适的替代矩阵M。一种常用的简化方法是将每个偏导数元素用差商来近似。例如，一种可能的简单近似式为

式中，e^j是第j个单位向量：

式中，1出现在此单位向量的第j行上，而其他元素都为零。标量h_ij的选择可以有无数种方法，但一种常用的选择是令h^k_ij=x_j^k-x_j^k-1。这种h_ij的选择方法可以达到收敛阶为1.62的收敛速度，它居于平方收敛和线性收敛之间。

另一种对Newton-Raphson法的常用改进是令M隔一定的迭代次数等于Ja_- cobi矩阵。例如，每当收敛速度慢下来时对M重新计算一次，或者相隔的迭代次数更加规则，诸如每隔1次或每隔2次等。这种改进被称为“不诚实Newton法”。这种方法的一种极端的推广是令M等于初始的Jacobi矩阵，并在余下的迭代过程中始终保持不变。这种方法通常被称为“极不诚实Newton法”。除了减少与构造矩阵相关的计算量外，这种方法还具有的优势是矩阵M只要被LU分解一次，因为矩阵M是恒定的。这样就可以省去用于LU分解的大量计算时间。类似地，不诚实Newton法也仅仅在矩阵M被重新计算时才需要再进行LU分解。