On efficient approximation of quadratic irrationals

技术摘要：二次无理数的有效逼近

问题陈述
本文探讨了计算二次无理数简单连分数展开收敛项（$p_n/q_n$）的计算挑战。虽然拉格朗日定理保证了这些展开最终是周期的，但使用标准迭代方法计算大索引 $n$ 的特定收敛项需要 $O(n)$ 次操作。作者寻求能够将这种复杂度降低至 $O(\log n)$ 的算法，特别是在伽罗瓦对拉格朗日定理进行改进（特别是针对有理数的平方根及某些复数）适用的场景下。

方法论与理论框架
作者建立了二次无理数的收敛项序列与各类切比雪夫多项式家族之间的深层联系。

1. 多项式定义： 本文引入并关联了几种多项式序列：

   • 标准第一类（$T_k$）和第二类（$U_k$）切比雪夫多项式。
   • 扩张变体（$\tilde{T}_k, \tilde{U}_k$），满足 $T_{k+2} = xT_{k+1} - T_k$。
   • 符号改变变体（$\hat{T}_k, \hat{U}_k$），满足 $T_{k+2} = xT_{k+1} + T_k$。
   • “带符号”切比雪夫多项式（$T^l_k, U^l_k$），其取决于周期长度 $l$ 的奇偶性，满足形式为 $T^l_{k+2} = 2xT^l_{k+1} - (-1)^l T^l_k$ 的递推关系。

2. 矩阵表示： 作者利用连分数的矩阵表示，其中矩阵乘积 $\begin{pmatrix} c_i & 1 \\ 1 & 0 \end{pmatrix}$ 产生收敛矩阵 $\Psi_n$。他们利用凯莱-哈密顿定理（Cayley–Hamilton theorem）证明，这些矩阵幂的迹对应于所定义的切比雪夫多项式。

3. 抽取（Decimation）与周期性： 对于具有纯周期或对称周期结构（特别是具有对称结构的有理数平方根）的二次无理数，作者证明了收敛项序列的特定抽取项（索引为 $kl-1$）是由这些带符号的切比雪夫多项式生成的。

核心贡献与算法
本文提供了四种不同的算法来计算大 $m$ 的收敛矩阵 $\Psi_m$，所有算法均实现了 $O(\log m)$ 的复杂度。

• 理论结果（定理 3.1）： 推导出了一个线性递推关系，用于处理间隔为周期 $l$ 倍数的收敛矩阵。该关系利用由带符号切比雪夫多项式导出的系数 $t_{2ik}$，将 $\Psi_{n+2ikl}$ 表示为 $\Psi_{n+2ikl}$ 和 $\Psi_n$ 的函数。
• 算法 3.1（二进制，加法型）： 使用周期乘数的二进制表示。它依赖于线性递推关系 (3.1)，涉及矩阵乘法以及矩阵的线性组合。作者指出，在最坏情况下，线性组合的数量随 $\log h$ 呈二次方增长。
• 算法 3.2（嵌套二进制，加法型）： 使用嵌套二进制表示（类似于霍纳法则/Horner's method）来最小化线性组合的数量。这被呈现为首选的加法方法，因为它通过减少线性组合的计算成本，优化了算法 3.1。
• 算法 3.3： 一个辅助算法，用于高效计算加法方法所需的切比雪夫系数（$t_k$）。
• 算法 3.4 与 3.5（乘法型）： 这些方法仅依赖于矩阵平方（乘法），而不计算中间系数。虽然它们避免了确定系数的过程，但相比加法变体，它们需要更多的矩阵乘法次数（$n_q + q + 3$）。

关于豪斯霍尔德（Householder）方法的结果
本文的一个重要理论贡献是证明了这些抽取的收敛项序列可以通过迭代豪斯霍尔德方法生成。

• 定理 5.1： 对 $\sqrt{N}$ 的第 $(l-1)$ 项收敛项应用 $d$ 阶豪斯霍尔德方法，会得到第 $(kl-1)$项收敛项，其中$k = d+1$。
• 特定情况：
  • $d=1$（牛顿法/巴比伦法）产生第 $2l-1$ 项收敛项。
  • $d=2$（哈雷法/Halley's method）产生第 $3l-1$ 项收敛项。
• 这确立了豪斯霍尔德迭代在应用于具有特定周期结构的二次无理数时，充当了一个“跳跃”算子，可以直接跳跃到连分数序列中的特定项。

意义与主张
本文声称提供了一种“高效算法”来计算二次无理数的收敛项，特别是在伽罗瓦定理成立的设定下优化了计算。

• 效率： 其主要意义在于将计算复杂度从相对于收敛项索引的线性降低到了对数级。
• 统一性： 该工作统一了连分数理论、切比雪夫多项式与迭代求根方法（豪斯霍尔德法）。它表明“带符号切比雪夫序列”不仅是数学上的奇趣现象，而且是二次无理数逼近结构的内在组成部分。
• 普适性： 虽然研究重点是具有对称结构（周期为 $1.4$）的有理数平方根，但作者指出，即使在严格的对称形式不成立的情况下，只要已知周期长度$l$，算法（3.1–3.5）对于复数和其他二次无理数仍然适用。

作者并未提出超出其所呈现的数学框架之外的新实验应用或未来研究方向，而是专注于所提出的高效计算方法的理论推导与算法实现。