Numerical Analysis — Homework (Dec 10)

作业：[第二版]习题5.10、5.14、5.15.

Problem 1 (5.10).

证明方程

f(x) = x^3 - 6x - 12 = 0 在区间 [2, 5] 内有唯一实根 p ，并对任意的初始值 x_0 \in [2, 5] ，Newton 序列都收敛于 p 。

证明.

令 f(x) = x^3 - 6x - 12 ，则 f'(x) = 3x^2 - 6 ， f''(x) = 6x 为 f(x) 在 [2, 5] 上的二阶导数。

1. f(2) \cdot f(5) = (8 - 12 - 12)(125 - 30 - 12) < 0 ；

2. f'(x) = 3x^2 - 6 \geq 3 \cdot 2^2 - 6 = 6 > 0 ；

3.

\left| \frac{f(2)}{f'(2)} \right| = \left| \frac{8 - 12 - 12}{3 \cdot 2^2 - 6} \right| = \frac{8}{3} < 3 = 5 - 2,

故由 第二版定理 5.7 知原命题成立。

∎

Problem 2 (5.14).

对 f(x) = 0 的 Newton 法，证明：

\lim{n \to \infty} \frac{xn - x{n-1}}{(x{n-1} - x_{n-2})^2} = -\frac{f''(x^)}{2f'(x^)}.

证明.

设 x^ 是方程 f(x)=0 的最优解，且 f(x) 具有二阶或二阶以上的连续导数，满足 f'(x^) \neq 0。牛顿法得到的迭代序列 {x_k} 收敛到 x^*。

牛顿法的迭代公式为：

x{k+1} = x{k} - \frac{f(x{k})}{f'(x{k})}

对于相邻的两步迭代 x{n-2} \to x{n-1} 和 x{n-1} \to xn，我们有：

x{n-1} - x{n-2} = - \frac{f(x{n-2})}{f'(x{n-2})}

以及：

我们对$f(x_{n-1})$ 在$x_{n-2}$ 处进行泰勒展开。令$h = x_{n-1} - x_{n-2} = - \frac{f(x_{n-2})}{f'(x_{n-2})}$。

代入$h = - \frac{f(x_{n-2})}{f'(x_{n-2})}$：

由牛顿法公式和泰勒展开结果可得：

由于$x_n \to x^*$，当$n \to \infty$ 时，我们有：

• $x_{n-1} \to x^*$

  ，故$f'(x_{n-1}) \to f'(x^*)$

• $x_{n-2} \to x^*$

  ，故$f''(x_{n-2}) \to f''(x^*)$

• $f(x_{n-2}) \to f(x^*) = 0$

  ，故$O \left( \frac{f(x_{n-2})}{f'(x_{n-2})} \right) \to O(0) = 0$

代入极限值：

故：

∎

Problem 3 (5.15).

用 Newton 下山法求方程$x^3 + 4x - 10 = 0$ 在$[0,2]$ 内的根。取初始值$x_0 = 0.1$，并且与 Newton 法进行比较。

解.

我用python来处理，精度到$10^{-15}$.

• Newton 法迭代过程如下：

\caption{Newton 法迭代过程}

|

|$x_k$ |$f(x_k)$ |

| --- | --- | --- |

|

0 | 0.100000000000000 | -9.599000000000000 |

| 1 | 2.481885856079404 | 15.215358198728335 |

| 2 | 1.805024165093047 | 3.101067979966130 |

| 3 | 1.579890422153529 | 0.263053095119627 |

| 4 | 1.556992667702742 | 0.002473038119202 |

| 5 | 1.556773284339790 | 0.000000224799221 |

| 6 | 1.556773264394212 | 0.000000000000002 |

| 7 | 1.556773264394211 | 0.000000000000000 |

| |

Newton 法在 7 次迭代后收敛至近似根$x^* \approx 1.556773264394211$。

• Newton 下山法迭代过程如下：

\caption{Newton 下山法迭代过程}

|

|$x_k$ |$f(x_k)$ |$\lambda_k$ |

| --- | --- | --- | --- |

|

0 | 0.100000000000000 | -9.599000000000000 | 1.0 |

| 1 | 1.290942928039702 | -2.684828466481791 | 1.0 |

| 2 | 1.589270430253988 | 0.371229983740445 | 1.0 |

| 3 | 1.557205211853520 | 0.004869191019477 | 1.0 |

| 4 | 1.556773341695223 | 0.000000871231048 | 1.0 |

| 5 | 1.556773264394214 | 0.000000000000028 | 1.0 |

| 6 | 1.556773264394212 | 0.000000000000002 | 1.0 |

| |

Newton 下山法在 6 次迭代后收敛至近似根$x^* \approx 1.556773264394212$。

∎

PDF

Download the original write-up here.