多项式上的一些逼近理论

Phartial · 2026-04-30 20:19:42 · 算法·理论

因为学某个东西的时候以为要学这个就跑去学了一下，然后发现其实不用学，但是写都写了就发出来了。

我们希望能得到一个和实数上的逼近理论相似的理论，那么我们首先需要一个和实数类似的结构，这给出反形式 Laurent 级数：

定义 1（反形式 Laurent 级数） 一个最高次项为 z^{n_0} 的反形式 Laurent 级数 F(z) 被定义为 \displaystyle\sum_{i=-\infty}^{n_0} f_iz^i，其中 n_0 可以是正数，要求 f_{n_0}\ne 0。

容易看出反形式 Laurent 级数实际上就是形式 Laurent 级数的正次项与负次项反转后的产物，于是它们也构成一个域，记作 \mathbb{A}((z^{-1}))。

反形式 Laurent 级数上每一项的大小关系就和实数上我们的直觉一致了：如果 i<j，那么 z^i 对这一级数的影响也小于 z^j。

其上仍然可以定义 \deg F（\deg F=n_0，容易验证 \deg F^{-1}=-\deg F），我们甚至可以定义 \lfloor F\rfloor 为 F 在删掉所有负次项后得到的多项式，这样一来带余除法也可以定义，F\bmod G 被定义为 F-G\lfloor \frac{F}{G}\rfloor。

这样一来我们又能定义其上的简单连分数（系数均为多项式的连分数）、渐近分数等概念，此处不赘述。

我们真正关心的是其构造与性质，对于反形式 Laurent 级数 F，我们可以按下列步骤构建其连分数展开：

令 A_i=\lfloor F\rfloor，设余项 R_i=F-A_i；
令 F\gets \frac{1}{R_i}，重复上述过程。

则 [A_0,A_1,\dots] 就是 F 的连分数展开。因为 \deg R_i<0，所以 \deg \frac{1}{R_i}>0，因此对所有 i\ge 1 的 A_i 均有 \deg A_i>0。

我们也能根据 A_i 构造渐近分数 \frac{P_k}{Q_k}（其被定义为连分数 [A_0,\dots,A_k] 展开后的结果）。

观察 1 \begin{bmatrix}P_k&P_{k-1}\\ Q_k&Q_{k-1}\end{bmatrix}=\begin{bmatrix}A_0&1\\1&0\end{bmatrix}\cdots\begin{bmatrix}A_k&1\\1&0\end{bmatrix}。

由此不难给出 P_k 与 Q_k 的递推式：

对所有 i\ge 1，P_i=A_iP_{i-1}+P_{i-2}、Q_i=A_iQ_{i-1}+Q_{i-2}。

因为 \forall i\ge 1,\deg A_i>0，所以 \deg Q_k 递增，且 \displaystyle\deg Q_k=\sum_{i=1}^k \deg A_i。

接下来我们对渐近分数进行误差分析。考虑计算 \det\begin{pmatrix}P_k&P_{k-1}\\ Q_k&Q_{k-1}\end{pmatrix}，因为 \det\begin{pmatrix}A_k&1\\1&0\end{pmatrix}=-1，根据观察 1，有：

P_kQ_{k-1}-P_{k-1}Q_k=(-1)^{k+1}

简单改写可以得到另一形式：

\frac{P_k}{Q_k}-\frac{P_{k-1}}{Q_{k-1}}=\frac{(-1)^{k+1}}{Q_{k-1}Q_k}

因此我们有 \displaystyle\frac{P_k}{Q_k}=A_0+\sum_{i=1}^k \frac{(-1)^{i+1}}{Q_{i-1}Q_i}。

定理 1 \displaystyle\deg (Q_kF-P_k)= -\deg Q_{k+1}。

证明：因为 \displaystyle F=\lim_{k\to+\infty} \frac{P_k}{Q_k}，所以 \displaystyle Q_kF-P_k=Q_k\sum_{i=k+1}^{\infty}\frac{(-1)^{i+1}}{Q_{i-1}Q_i}。

同理也可证明 \deg(F-\dfrac{P_k}{Q_k})=-\deg Q_{k+1}-\deg Q_k。

接下来我们就可以着手探究 \mathbb{A}((z^{-1})) 上的最优逼近了，本文只看性质更好的第二类最优逼近。

定义 2（第二类最优逼近） 已知反形式 Laurent 级数 F，我们称有理函数 \dfrac{P}{Q} 是 F 的第二类最优逼近（或简称最优逼近），当且仅当对任意满足 \deg Q'\le \deg Q 且 \dfrac{P'}{Q'}\ne \dfrac{P}{Q} 的 P',Q'，都有 \deg(QF-P)<\deg(Q'F-P')。
定理 2 所有渐近分数都是最优逼近，所有最优逼近也都是渐近分数。

证明：对于前半段话，假设我们现在欲证明 \dfrac{P_k}{Q_k} 是最优逼近。那么因为 \begin{bmatrix}P_k&P_{k-1}\\ Q_k&Q_{k-1}\end{bmatrix} 为幺模矩阵，方程组：
\begin{cases} uP_k+vP_{k-1}=P\\ uQ_k+vQ_{k-1}=Q \end{cases}
对任意多项式 P,Q 都有唯一多项式解 u,v。于是 QF-P 可改写为 u(Q_kF-P_k)+v(Q_{k-1}F-P_{k-1})。

假设 \deg Q\le \deg Q_k 且 \dfrac{P}{Q}\ne\dfrac{P_k}{Q_k}，那么为了让 Q=uQ_k+vQ_{k-1}，只有两种情况可以出现：
在第一种情况中，因为 \deg Q_k<\deg Q_{k+1}，故显然有 \deg(QF-P)=\deg v-\deg Q_k> -\deg Q_{k+1}=\deg(Q_kF-P_k)。

在第二种情况中，我们考察 \deg u-\deg Q_{k+1} 与 \deg v-\deg Q_k 之间的大小关系，显然有 \deg v-\deg Q_k=\deg u-\deg Q_{k-1}>\deg u-\deg Q_{k+1}，所以仍然有 \deg(QF-P)=\deg v-\deg Q_k>-\deg Q_{k+1}=\deg(Q_kF-P_k)。故 \dfrac{P_k}{Q_k} 的确是最优逼近。

接下来我们希望证明：如果有理函数 \dfrac{P}{Q} 是最优逼近，则一定存在 k 使得 \dfrac{P}{Q}=\dfrac{P_k}{Q_k}。

找到首个满足 \deg Q_k\le \deg Q<\deg Q_{k+1} 的 k（因为 \deg Q_k 单调递增，这样的 k 一定存在），我们断言 \dfrac{P}{Q}=\dfrac{P_k}{Q_k}，并使用反证法证明。

如果断言不成立，则多项式 P_kQ-PQ_k\ne 0，即 \deg(P_kQ-PQ_k)\ge 0，对其变形可得 \deg(Q(P_k-Q_kF)-Q_k(P-QF))\ge 0，左半部分 \deg Q+\deg(P_k-Q_kF)=\deg Q-\deg Q_{k+1}<0，因此为了让原多项式 \ne 0，右半部分必须有 \deg Q_k+\deg(P-QF)\ge 0。

这导出 \deg(P-QF)\ge -\deg Q_k=\deg(P_{k-1}-Q_{k-1}F)，与 \dfrac{P}{Q} 是最优逼近这一前提矛盾，故断言成立。

这一定理告诉了我们最优逼近实际上就是渐近分数。于是我们成功地把实数上的逼近理论迁移到了多项式上。