牛顿法时间复杂度分析

设$y=f(x)$有反函数$x=g(y)$，则在$f(x)=0$的根$a$的邻域内，$g(y)$ 关于点$y_{i}=f(x_{i})$的$Taylor$展开式为:

$$x=g(y)=\sum_{j=0}^{m+1} \frac{\left(y-y_{i}\right)^{j}}{j !} g^{j}\left(y_{i}\right)+\frac{\left(y-y_{i}\right)^{m+2}}{(m+2) !} g^{(m+2)}\left(\eta_{i}\right)$$

其中， $\eta_{i}$ 是介于 $y$ 与$y_{i}$ 之间

因为$a=g(0)$，所以得：

$$a=x_{i}+\sum_{j=1}^{m+1} \frac{(-1)^{j}\left[f\left(x_{i}\right)\right]^{j}}{j!} g^{j}\left(y_{i}\right)+\frac{(-1)^{m+2}}{(m+2) !}\left[f\left(x_{i}\right)\right]^{m+2} g^{(m+2)}\left(\eta_{i}\right)\tag{1}$$ $$a \approx x_{i}-\frac{f\left(x_{i}\right)}{f^{\prime}\left(x_{i}\right)}+\sum_{j=2}^{m+1} \frac{(-1)^{j}\left[f\left(x_{i}\right)\right]^{j}}{j !} g^{j}\left(y_{i}\right)\tag{2}\qquad\qquad\qquad\qquad\qquad$$ $$x_{i+1}=x_{i}-\frac{f\left(x_{i}\right)}{f^{\prime}\left(x_{i}\right)}+\sum_{j=2}^{m+1} \frac{(-1)^{j}\left[f\left(x_{i}\right)\right]^{j}}{j !} g^{j}\left(y_{i}\right)\tag{3}\qquad\qquad\qquad\qquad\quad$$

由式(1)与式(3)可得，式(3)的收敛阶为:

$$\left|\varepsilon_{i+1}\right|=\frac{1}{(m+2) !}\left|f\left(x_{i}\right)\right|^{m+2}\left|g^{(m+2)}\left(\eta_{i}\right)\right|\tag{4}$$

注意到：

$$\varepsilon_{i} = a - x^{i} \\ f(a) = 0 \\$$ $$\because f(x)在\left|a - x_{i}\right| 连续, 由拉格朗日中值定理 \qquad\quad\ \ \\ \therefore \left| f(x_{i})-f(x^{*}) \right|=\left| f^{\prime}(\xi_{i}) \varepsilon_{i}\right| \quad (\xi_{i}\in\left|a - x_{i}\right|)$$

可以将式(4)化为:

$$\left|\varepsilon_{i+1}\right|=\frac{1}{(m+2) !}\left|f^{\prime}\left(\xi_{i}\right)\right|^{m+2}\left|g^{(m+2)}\left(\eta_{i}\right)\right|\left|\varepsilon_{i}\right|^{m+2}\tag{5}$$

若a是单根，则当$\left|f^{\prime}\left(\xi_{i}\right)\right|^{m+2}\left|g^{(m+2)}\left(\eta_{i}\right)\right|$在a的某邻域内是有界的，且当$i \rightarrow+\infty$时,

$$\xi_{i} \rightarrow a, \quad \eta_{i} \rightarrow 0​$$

所以:

$$\lim _{i \rightarrow \infty} \frac{\left|\varepsilon_{i+1}\right|}{\left|\varepsilon_{i}\right|^{m+2}}=\frac{1}{(m+2) !}|f(\mathrm{a})|^{m+2}\left|g^{(m+2)}(0)\right| = C \neq 0$$

由定义3.2：

设$\varepsilon_{k}=x*-xk$为第k次迭代的迭代误差，若

$$\lim _{k \rightarrow \infty} \frac{\left|\varepsilon_{k+1}\right|}{\left|\varepsilon_{k}\right|^{p}}=c \neq 0$$

则称迭代是p阶收敛的。称c为渐近误差常数

可得：牛顿法的收敛阶为 $p = m + 2$

如果设$f(x_{i})$的计算量为1个单位，则计算$f^{(j)}(x_{i})$的计算量设为 $\theta_{j}$，则式子(3)的计算量为:

$$\theta=1+\sum_{j=1}^{m+1} \theta_{j}$$

式子(3)的效率指数为：

$$\mathrm{EI}=\mathrm{p}^{\frac{1}{\theta}}=(m+2)^{1 /\left(1+\sum_{j=1}^{m+1} \theta_{j}\right)}$$

注意到其中只利用到f(x)的一阶导数 $\therefore m = 0$

对比牛顿迭代公式(4)，可得到:

$$\lim _{i \rightarrow \infty} \frac{\left|\varepsilon_{i+1}\right|}{\left|\varepsilon_{i}\right|^{2}}=\frac{1}{2}|f(a)|^{2}\left|g^{(2)}(0)\right|$$

效率指数为:

$$E I=2^{\frac{1}{1+\theta_{1}}}$$