牛顿迭代与预测式迭代的算法复杂性

The Complexity of Algorithm About Newton and Predictor Iteration

从算法复杂性出发，采用Ｏｓｔｒｏｗｓｋｉ给出的“迭代过程有效性指标”的概念，讨论了具有二阶收敛速度的牛顿迭代法和具有三阶收敛速度的预测式迭代法的有效性问题，给出牛顿迭代法的有效性指标为．预测式迭代法的有效性指标为，由此得到牛顿迭代法比预测式迭代法具有更高的有效性。

In view of the complexity of algorithm, the efficiency of algorithm about Newton iteration method with quadratic convergence rate and predictor iteration method with cubic convergence is discussed by using the concept of effective index of iteration process'that was presented by Ostrowski. And the effective indices of iteration process 2 for Newton iteration and 3 for predictor iteration have been given. That proves the Newton iteration has higher efficiency than the predictor iteration.