本帖最后由 hbghlyj 于 2023-3-29 11:01 编辑 Painless conjugate gradient
$n$次Chebyshev多项式$$T_n(\omega)=\frac{(\omega+i\sqrt{1-\omega^2})^n+(\omega-i\sqrt{1-\omega^2})^n}2$$
推导设$\omega=\cosθ$得$\omega+i\sqrt{1-\omega^2}=\exp(iθ)⇒\cos(nθ)=\frac{\exp(inθ)+\exp(-inθ)}2=\frac{(\omega+i\sqrt{1-\omega^2})^n+(\omega-i\sqrt{1-\omega^2})^n}2$
在区间$[-1,1]$满足:$$T_n(\omega)=\cos \left(n \cos ^{-1} \omega\right), \quad-1 \leq \omega \leq 1$$
所以$|T_n(\omega)|\le1$, 当$\omega\in[-1,1]$.
在区间$[-1,1]$剧烈振荡:
\begin{alignat*}1
T_n\left(\cos \left(\frac{\frac\pi2+k \pi}n\right)\right)=0 &\quad k=0,\ldots,n-1\\
T_n\left(\cos \left(\frac{k \pi}n\right)\right)=(-1)^{k}&\quad k=0, \ldots, n
\end{alignat*}由罗尔中值定理, 两个零点之间至少有一个极值点, 所以 $T_n(x)$ 的 $n-1$ 个极值点正好落在 $n$ 个根中的相邻两个之间.
在所有最高次项系数为$2^{n-1}$的$n$次多项式$f(x)$中，$T_n(x)$ 是使得 $\max_{[-1,1]}|f(x)|$ 最小的多项式。
类似地, 函数
$$P_n(\lambda)=\frac{T_n\left(\frac{\lambda_{\max }+\lambda_{\min }-2 \lambda}{\lambda_{\max }-\lambda_{\min }}\right)}{T_n\left(\frac{\lambda_{\max }+\lambda_{\min }}{\lambda_{\max }-\lambda_{\min }}\right)}$$
当$\lambda\in\left[\lambda_{\min }, \lambda_{\max }\right]$时在$\pm T_n\left(\frac{\lambda_{\max }+\lambda_{\min }}{\lambda_{\max }-\lambda_{\min }}\right)^{-1}$之间剧烈振荡, 且满足$P_n(0)=1$.
最优性假设$n$次多项式$Q_n(\lambda)$满足$Q_n(0)=1$且$Q_n(λ)$在区间$\left[\lambda_{\min }, \lambda_{\max }\right]$上优于$P_n$, 即$$Q_n(\lambda)<T_n\left(\frac{\lambda_{\max }+\lambda_{\min }}{\lambda_{\max }-\lambda_{\min }}\right)^{-1}$$那么$P_n(0)-Q_n(0)=1-1=0$且在区间$\left[\lambda_{\min }, \lambda_{\max }\right]$上有$n$个根. 因此$P_n-Q_n$次数$≤n$却有$≥n+1$个根, 矛盾. | 
