关于共轭梯度法复杂度相关平凡不等式的推导疑问：最速下降法迭代次数上界的证明求助
嗨，我来帮你搞定这最后一步推导！其实你已经走完了最核心的流程，就差一个关键的经典不等式来衔接啦～
首先得夸夸你：前面的推导步骤完全正确！从收敛界出发，通过取自然对数、翻转不等号（因为$\ln\left(\frac{\kappa-1}{\kappa+1}\right)$是负数，毕竟$\frac{\kappa-1}{\kappa+1} < 1$），你得到了：
$$i \ge \frac{\ln\left(\frac{1}{\epsilon}\right)}{\ln\left(\frac{\kappa+1}{\kappa-1}\right)}$$
接下来的关键，就是证明当$\kappa > 1$（条件数必然大于1）时，$\ln\left(\frac{\kappa+1}{\kappa-1}\right) \ge \frac{2}{\kappa}$。只要这个不等式成立，我们就能把它代入上面的式子，推导出目标上界。
证明这个关键不等式
我们做个变量替换：令$t = \frac{1}{\kappa}$，因为$\kappa > 1$，所以$0 < t < 1$。此时原不等式转化为：
$$\ln\left(\frac{1+t}{1-t}\right) \ge 2t$$
我们用函数单调性来证这个式子：
定义函数$f(t) = \ln\left(\frac{1+t}{1-t}\right) - 2t$，其中$t \in (0,1)$。对$f(t)$求导：
$$f'(t) = \frac{1-t}{1+t} \cdot \frac{(1-t)+(1+t)}{(1-t)^2} - 2 = \frac{2}{1-t^2} - 2 = \frac{2t2}{1-t2}$$
因为$0 < t < 1$，所以$f'(t) > 0$，这说明$f(t)$在$(0,1)$上是严格单调递增的。又因为$f(0) = 0$，所以当$t > 0$时，$f(t) \ge 0$，也就是：
$$\ln\left(\frac{1+t}{1-t}\right) \ge 2t$$
把$t = \frac{1}{\kappa}$代回去，就得到我们需要的：
$$\ln\left(\frac{\kappa+1}{\kappa-1}\right) = \ln\left(\frac{1+\frac{1}{\kappa}}{1-\frac{1}{\kappa}}\right) \ge \frac{2}{\kappa}$$
代入推导目标上界
现在把这个不等式代入你得到的式子：
因为$\ln\left(\frac{\kappa+1}{\kappa-1}\right) \ge \frac{2}{\kappa}$，所以它的倒数满足$\frac{1}{\ln\left(\frac{\kappa+1}{\kappa-1}\right)} \le \frac{\kappa}{2}$。
因此：
$$i \ge \frac{\ln\left(\frac{1}{\epsilon}\right)}{\ln\left(\frac{\kappa+1}{\kappa-1}\right)} \le \frac{\kappa}{2}\ln\left(\frac{1}{\epsilon}\right)$$
这里的逻辑是：我们要找最小的$i$使得误差满足要求，而$\frac{\kappa}{2}\ln\left(\frac{1}{\epsilon}\right)$是这个最小$i$的一个上界——也就是说，只要迭代次数取到这个值的向上取整（$\lceil \frac{1}{2}\kappa \ln\left(\frac{1}{\epsilon}\right) \rceil$），就一定能保证$\lVert e_{(i)} \rVert_A \le \epsilon \lVert e_{(0)} \rVert_A$，这就是题目里说的“maximum number of iterations required”的含义啦。
这样就完成了整个推导，是不是一下子就通了😉
备注：内容来源于stack exchange，提问作者nalzok
