Numerical Analysis — Homework (Dec 3)

作业：[第二版]习题5.1、5.2、5.6.

Problem 1 (习题5.1).

方程

x^3 - x - 1 = 0 在 [1,2] 内有唯一的根。用二分法求此根，误差不超过 10^{-2}。若要误差不超过 10^{-3} 或 10^{-4}，问要作多少次二分？

解.

1. 设 f(x) = x^3 - x - 1。因为 f(1) = -1 < 0，f(2) = 5 > 0，且 f'(x) = 3x^2 - 1 > 0 在 [1,2] 上恒成立，所以 f(x) 在 [1,2] 内严格单调增加，存在唯一实根 x^* \in (1,2)。

2. 下面我们给出二分法求根（误差不超过10^{-2}）的结果：

由上表结果可知，我们需进行8次二分即可得到符合误差范围内的结果，最后解出来的根x\approx1.32421875.

3. 二分法每次迭代将区间长度减半，我们取区间中点为近似根 x_n，则误差满足

|x_n - x^*| \le \frac{L_n}{2} = \frac{1}{2^{n}}。

要求误差不超过 \varepsilon，即需

\frac{1}{2^{n}} \le \varepsilon \Longrightarrow 2^{n} \ge \frac{1}{\varepsilon}。

n \ge \log2 \left( \frac{1}{\varepsilon} \right) = -\log2 \varepsilon，

f\left(\frac{\pi}{2}\right) = \sin\frac{\pi}{2} - \frac{\pi}{4} = 1 - \frac{\pi}{4} \approx 0.2146 > 0,

且$f'(x) = \cos x - \frac{1}{2}$，在$\left[\frac{\pi}{2}, \pi\right]$ 上$f'(x) \le \cos\frac{\pi}{2} - \frac{1}{2} = -\frac{1}{2} < 0$，故$f(x)$ 在该区间上严格单调递减，因此存在唯一实根$x^* \in \left(\frac{\pi}{2}, \pi\right)$。

二分法迭代时，第$k$ 次二分后区间长度$L_k = \frac{\pi - \frac{\pi}{2}}{2^k} = \frac{\pi}{2^{k+1}}$，取中点$x_k$ 作为近似根，误差满足

要求$|x_k - x^*| < 10^{-4}$，即

取对数得

故满足误差要求至少需要$k \ge 14$ 次迭代。

我们的二分从初始区间$[\frac{\pi}{2},\pi]=[1.5707963268, 3.1415926536]$ 开始，结果如下：

我们由表格结果可知，实际上在进行第$12$次二分时，我们就有$|f(x_{12})|\leq10^{-4}$，故只要执行$12$次二分就能得到符合误差的结果：$x\approx1.895616758629681$.

另外，由表格结果我们也能发现：在进行第$15(>14)$次二分时，区间长度满足$\leq10^{-4}$，和我们上面的估计相符合.

∎

Problem 3 (习题5.6).

为求方程$x^3 - x^2 - 1 = 0$ 在$x_0 = 1.5$ 附近的一个根，现将方程改为下列的等价形式，且建立相应的迭代公式：

1. $x = 1 + \frac{1}{x^2}$

   ，迭代公式为$x_{k+1} = 1 + \frac{1}{x_k^2}$；

2. $x^3 = 1 + x^2$

   ，迭代公式为$x_{k+1} = (1 + x_k^2)^{1/3}$；

3. $x^2 = \frac{1}{x-1}$

   ，迭代公式为$x_{k+1} = \frac{1}{\sqrt{x_k - 1}}$。

试分析每一种迭代公式的收敛性，任选一种收敛的迭代公式计算$1.5$ 附近的根，要求$|x_{k+1} - x_k| < 10^{-5}$。

解.

方程$f(x) = x^3 - x^2 - 1 = 0$ 在$x_0 = 1.5$ 附近有唯一实根$x^*$。取初始区间$[1.4, 1.6]$ 考察：

且$f'(x) = 3x^2 - 2x = x(3x-2) > 0$ 在$[1.4, 1.6]$ 上成立，故根$x^* \in (1.4, 1.6)$。

要验证迭代公式是否收敛我们只需验证：在根$x^*$ 的某个邻域内$|\varphi'(x)| < 1$。 下面分析三种迭代公式在区间$[1.4, 1.6]$ 上的收敛性：

1. $x_{k+1} = 1 + \frac{1}{x_k^2}$ 设$\varphi_1(x) = 1 + \frac{1}{x^2}$，则$\varphi_1'(x) = -\frac{2}{x^3}$。 在区间$[1.4, 1.6]$ 上，$|\varphi_1'(x)| = \frac{2}{x^3}$ 单调递减，因此

故在$[1.4, 1.6]$ 上，$|\varphi_1'(x)| \le 0.728 < 1$，满足局部收敛条件。

2. $x_{k+1} = (1 + x_k^2)^{1/3}$ 设$\varphi_2(x) = (1 + x^2)^{1/3}$，则

故在$[1.4, 1.6]$ 上，$|\varphi_2'(x)| \le 0.514 < 1$，满足局部收敛条件。

3. $x_{k+1} = \frac{1}{\sqrt{x_k - 1}}$ 设$\varphi_3(x) = \frac{1}{\sqrt{x-1}}$，则$\varphi_3'(x) = -\frac{1}{2}(x-1)^{-3/2}$，所以

在$[1.4, 1.6]$ 上，$x-1 \in [0.4, 0.6]$，$(x-1)^{-3/2}$ 单调递减，因此

在$[1.4, 1.6]$ 上$|\varphi_3'(x)| \ge 1.078 > 1$，不满足收敛条件，因此该迭代公式在$x^*$ 附近不收敛。

下面我们选择收敛的迭代公式 (2)$x_{k+1} = (1 + x_k^2)^{1/3}$ 进行计算，取$x_0 = 1.5$.

迭代的结果如下表所示：

其中：

因此，我们取近似根$x^* \approx 1.465577183742211$，满足精度要求。

∎

PDF

Download the original write-up here.