第 12 周作业：算法收敛与一维搜索

本周源文件是 Lee 的手写作业，包含第 8 章的闭映射与收敛速度，以及第 9 章的一维搜索计算。下面根据扫描中的题面和数值过程还原，并用参考解核对迭代值。

第 8-1 题：算法映射在 $x=2$ 处不闭

题目给出的点到集映射为

A(x)= \begin{cases} \left[\dfrac32+\dfrac14x,\ 1+\dfrac12x\right], &x\ge2,\\[6pt] \left\{\dfrac12(x+1)\right\}, &x<2. \end{cases}

取

x^{(k)}=2-\frac1k<2,

则

y^{(k)}=\frac12\left(x^{(k)}+1\right) =\frac32-\frac1{2k} \in A(x^{(k)}).

两列序列分别收敛到

x^{(k)}\to2,\qquad y^{(k)}\to\frac32.

但是

A(2)= \left[ \frac32+\frac14\cdot2,\ 1+\frac12\cdot2 \right] =\{2\},

所以

\frac32\notin A(2).

因此映射图像不包含这组图像点的极限：

\boxed{A\text{ 在 }x=2\text{ 处不闭}}.

闭映射检验必须同时跟踪 $x^{(k)}$ 和 $y^{(k)}\in A(x^{(k)})$ ；只看输入序列没有结论。

设极限为 $0$ ，误差就是 $e_k=|\gamma_k|$ 。

\frac{e_{k+1}}{e_k} =\frac{k}{k+1}\to1.

按课件的“收敛阶”记法，它属于 $p=1$ 的情形；但比值极限不是某个 $q<1$ ，所以它不满足通常更强的 Q-线性收敛定义，实际速度是次线性的。写答案时最好把这两个口径同时说明，避免只写“线性”造成误解。

\frac{e_{k+1}}{e_k} =\frac{k^k}{(k+1)^{k+1}} =\left(\frac{k}{k+1}\right)^k\frac1{k+1} \to0.

因此

\boxed{\gamma_k=(1/k)^k\text{ 超线性收敛到 }0}.

f(x)=e^{-x}+x^2,\qquad x\in[0,1],

要求最终区间长度不超过 $0.2$ 。取

\tau\approx0.618,\qquad 1-\tau\approx0.382.

四轮计算如下，函数值保留三位小数：

轮次	当前区间	$\lambda$	$f(\lambda)$	$\mu$	$f(\mu)$	保留区间
1	$[0,1]$	$0.382$	$0.828$	$0.618$	$0.921$	$[0,0.618]$
2	$[0,0.618]$	$0.236$	$0.845$	$0.382$	$0.828$	$[0.236,0.618]$
3	$[0.236,0.618]$	$0.382$	$0.828$	$0.472$	$0.847$	$[0.236,0.472]$
4	$[0.236,0.472]$	$0.326$	$0.828$	$0.382$	$0.828$	$[0.236,0.382]$

最终区间长度

0.382-0.236=0.146<0.2,

所以

\boxed{x^*\in[0.236,0.382]}.

表中第 4 轮的两个三位小数看起来相同，实际未舍入函数值在 $0.326$ 处略小，因此保留左侧区间。黄金分割每轮能复用一个旧试探点，只需新增一次函数计算。

根据作答过程还原目标函数：

f(x)=3x^4-4x^3-12x^2.

导数为

f'(x)=12x^3-12x^2-24x, \qquad f''(x)=36x^2-24x-24.

用

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

从 $x^{(0)}=-1.2$ 出发：

$k$	$x^{(k)}$	$f'(x^{(k)})$	$f''(x^{(k)})$
0	$-1.200$	$-9.216$	$56.640$
1	$-1.037$	$\approx-1.398$	$\approx39.601$
2	$-1.002$	$\approx-0.072$	$\approx36.192$
3	$-1.000$	$\approx0$	$\approx36$

因此

\boxed{x^{(k)}\to-1,\qquad f(-1)=-5}.

不过 $f'(x)=12x(x-2)(x+1)$ 还给出驻点 $0$ 和 $2$ ，且

f(2)=-32<-5.

所以这次 Newton 迭代收敛到的是局部极小点 $-1$ ，不是全局极小点。Newton 法的收敛结果依赖初值，不能看到 $f'(x)\approx0$ 就自动写“全局最优”。