连分数中的矩阵运算
Matrix Operations in Continued Fractions
DOI: 10.12677/PM.2023.135120, PDF, HTML, XML, 下载: 308  浏览: 619  国家自然科学基金支持
作者: 朱 林:上海理工大学,理学院,上海;王 冰*:上海立信会计金融学院,统计与数学学院,上海
关键词: 欧几里得算法连分数矩阵Euclidean Algorithm Continued Fractions Matrices
摘要: 本文旨在探究矩阵运算在连分数中的应用。本文通过欧几里得算法自然地引出连分数的概念,探究了矩阵运算在连分数中的若干应用,利用矩阵运算技巧证明了连分数的部分性质,通过实例展示矩阵在连分数中的巧妙应用。矩阵运算在连分数中有着广泛而深入的应用,为我们深入理解和研究连分数提供了新的视角和工具。
Abstract: This article aims to explore the application of matrix operations in continued fractions. This article naturally introduces the concept of continued fractions through Euclidean algorithm, explores several applications of matrix operations in continued fractions, proves some properties of con-tinued fractions using matrix operation techniques, and demonstrates the ingenious application of matrices in continued fractions through examples. Matrix operations have extensive and in-depth applications in continued fractions, providing us with new perspectives and tools for in-depth un-derstanding and research of continued fractions.
文章引用:朱林, 王冰. 连分数中的矩阵运算[J]. 理论数学, 2023, 13(5): 1151-1156. https://doi.org/10.12677/PM.2023.135120

1. 引言

连分数是数学领域中一个重要的概念,它在数论、代数、数值分析、密码学、数字图像处理、天文、历法、乐律等方面都有广泛的应用。在数论中,连分数被用于解决无理数的最佳有理逼近、二次无理数和求解不定方程等问题(参见 [1] )。在数值计算中,连分数被用于连分式插值与逼近理论,以及微分方程数值解的研究(参见 [2] )。在信息安全领域,连分数在攻击RSA密码系统中发挥着重要作用(参见 [3] [4] )。

随着现代数学的发展,连分数的研究得到了广泛的关注和不断深入的拓展。目前,学者们在连分数的理论研究、计算机数值计算及其他领域中的应用进行了不断的探索和研究。文献 [5] 提出并研究了一种可以在任意虚二次环中实现的广义连分数算法,且不限制于欧几里得的情形,经典连分数的许多标志性特性被证明是可以保留的。文献 [6] 研究了p-adic域中的一族拟周期p-adic Ruban连分数。这些新的理论成果的发现,进一步推动了连分数理论的发展和应用的广泛化。

在实际应用中,我们通常要对连分数进行计算和处理,因此需要寻找一些有效的计算方法和工具。欧几里得算法是一种古老的算法,它可以用于寻找两个数的最大公约数。通过欧几里得算法,我们可以很自然地引出连分数的概念。矩阵是数学中的重要工具,它可以用于描述线性变换和解决一些代数和几何问题。本文的主题是探究矩阵运算在连分数中的应用,本文研究的方法和结果在数学理论和应用领域都具有广泛的应用价值。

本文的结构如下:首先介绍扩展的欧几里得算法,用矩阵技巧处理扩展的欧几里得算法中的迭代关系式;然后,由欧几里得算法自然地引出连分数的概念,并探究矩阵运算在连分数中的应用。在此基础上,利用矩阵运算技巧证明连分数的渐近分数的一些性质,并通过实例展示矩阵运算在连分数中的巧妙应用。最后,对本文的结论进行总结和展望。

2. 欧几里得算法

欧几里得算法与连分数关系密切。利用欧几里得算法(参见 [1] )可以快速地求整数a,b的最大公因子 ( a , b ) 。设整数 a b > 0 ,令 r 0 = a r 1 = b 。如果连续做带余除法得到 r j = r j + 1 a j + 1 + r j + 2 0 < r j + 2 < r j + 1 0 j n 2 且有 r n + 1 = 0 ,那么 ( a , b ) = r n ,即最后一个非零余数 r n 为a,b的最大公因子。若沿着欧几里得算法的反方向递推,最终可将 ( a , b ) 表示成 r 0 = a r 1 = b 的线性组合,即得Bezout定理的构造性证明。

定理1 (Bezout定理)如果a,b均为整数,那么存在整数k,l使得 k a + l b = ( a , b )

方程 k a + l b = ( a , b ) 称为Bezout等式,k,l称为Bezout系数。下面用矩阵运算的技巧给出 d : = ( a , b ) 表示成a,b的线性组合的解释(参见 [7] )。将行向量 ( a , b ) 作为矩阵的第一行,下面写一个2阶单位矩阵,构成3行2列整数矩阵A。只对A进行第三类初等列变换(且所乘系数均为整数),当A的第一行变成 ( d , 0 ) ( 0 , d ) 时,得到矩阵B或 B ,其中k,l,u,v为整数。

A = ( a b 1 0 0 1 ) a , b B = ( d 0 k u l v ) B = ( 0 d u k v l ) .

由此得到的k,l满足Bezout等式 k a + l b = ( a , b ) 。Bezout系数不是唯一的,可以递归地求出。下面定理给出了另一种计算Bezout系数的方法(参见 [3] )。

定理2 (扩展的欧几里得算法)令a,b是正整数,那么

( a , b ) = s n a + t n b ,

其中 s n t n 是下面定义的递归序列的第n项,

s 0 = 1 , t 0 = 0 , s 1 = 0 , t 1 = 1 ,

s j = s j 2 a j 1 s j 1 , t j = t j 2 a j 1 t j 1 .

其中 2 j n + 1 a j 是欧几里得算法 r j = r j + 1 a j + 1 + r j + 2 0 < r j + 2 < r j + 1 中每一步的商。

在扩展的欧几里得算法中,由递推序列有

( s j t j s j 1 t j 1 ) = ( a j 1 1 1 0 ) ( a j 2 1 1 0 ) ( a 1 1 1 0 ) ( 0 1 1 0 ) (1)

( r j r j 1 ) = ( s j t j s j 1 t j 1 ) ( a b ) (2)

计算 s n t n ,即可得到关于a,b的Bezout等式 ( a , b ) = s n a + t n b 。利用(2)式可将任一余数 r j 表示为a,b的线性组合。反之,a,b也可由任意一对相邻的余数线性表示:

( a b ) = ( a 1 1 1 0 ) ( a 2 1 1 0 ) ( a j 1 1 0 ) ( r j r j + 1 ) , 1 j n .

命题3 在扩展的欧几里得算法中,系数 s n t n 满足如下性质:

s j t j 1 s j 1 t j = ( 1 ) j s j t j 2 s j 2 t j = ( 1 ) j 1 a j 1

s j t j 2 j n + 1 为既约分数;

a b = t n + 1 s n + 1 | s n + 1 | = b d | t n + 1 | = a d

证明 对 式左右两边同时取行列式即得 s j t j 1 s j 1 t j = ( 1 ) j 。对

( s j t j s j 2 t j 2 ) = ( 1 0 1 a j 1 ) ( s j t j s j 1 t j 1 )

左右两边同时取行列式即得 s j t j 2 s j 2 t j = ( 1 ) j 1 a j 1 。第2条性质 s j t j 为既约分数是第1条性质的直接推论。由 式知, 0 = r n + 1 = s n + 1 a + t n + 1 b ,则 a b = t n + 1 s n + 1 。又 t n + 1 s n + 1 互素,则 | s n + 1 | = b d | t n + 1 | = a d ,证毕。

注意到, s n t n 的这些性质与定理6中渐近分数的性质有相似之处。

3. 连分数中的矩阵技巧

连分数由欧几里得算法引入十分自然,我们有时用数的整数部分近似代替这个数,为了再精确一点,就再给出小数部分的倒数的整数部分,如此连续进行,得到连分数。首先将欧几里得算法中的辗转相除式改写,设a,b为正整数:

a b = r 0 r 1 = a 1 + r 2 r 1 , r j r j + 1 = a j + 1 + r j + 2 r j + 1 ( 0 j n 2 ) , r n 1 r n = a n .

依次将后式的倒数代人前式,则

a b = a 1 + r 2 r 1 = a 1 + 1 r 1 r 2 = a 1 + 1 a 2 + r 3 r 2 = = a 1 + 1 a 2 + 1 a 3 + + 1 a n 1 + 1 a n

上述等式的最后一项就是 a b 的连分数展开式。

连分数是具有以下形式的表达式(记为 α ):

a 0 + b 0 a 1 + b 1 a 2 +

其中 a i b i 是任意数。如果 a 0 为整数, a k ( k > 0 ) 为正整数, b i = 1 ( i 0 ) ,则称表达式为简单连分数,简记为 [ a 0 , a 1 , a 2 , ] 。止于有限步时,则为有限连分数,记为

α n = [ a 0 , a 1 , a 2 , , a n ] = p n q n

这称为无限连分数 [ a 0 , a 1 , a 2 , ] 的第n个渐近分数。

连分数的渐近分数在无理数的有理逼近中有非常重要的应用,下面的定理4是关于渐近分数的基本结论(参见 [1] [3] [8] )。

定理4 设正实数 α 展开连分数为 [ a 0 , a 1 , a 2 , ] ,则

渐近分数 [ a 0 , a 1 , a 2 , , a n ] = p n q n 满足

{ p 0 = a 0 , p 1 = a 0 a 1 + 1 , p n = a n p n 1 + p n 2 , q 0 = 1 , q 1 = a 1 , q n = a n q n 1 + q n 2 .

事实上,对任何x,有 [ a 0 , a 1 , , a n 1 , x ] = x p n 1 + p n 2 x q n 1 + q n 2

渐近分数 p n q n 收敛于原实数 α ,而且是 α 的最佳逼近分数,即分母不大于 q n 的分数中, p n q n α 最接近,且 p 2 n q 2 n p 2 n + 1 q 2 n + 1 分别单调递增和单调递減地趋于 α

命题5 设正实数 α 展开连分数为 [ a 0 , a 1 , a 2 , ] ,则其渐近分数 p n q n 满足如下等式:

p n q n 可以用行列式表达

p n = | a 0 1 1 a 1 1 1 a 2 1 1 a n 1 1 1 a n | , q n = | 1 0 0 a 1 1 1 a 2 1 1 a n 1 1 1 a n | (3)

( p n q n p n 1 q n 1 ) = ( a n 1 1 0 ) ( a n 1 1 1 0 ) ( a 0 1 1 0 )

( p n p n 1 q n q n 1 ) = ( a 0 1 1 0 ) ( a 1 1 1 0 ) ( a n 1 1 0 )

利用上述矩阵等式可以简洁地证明一些关于渐近分数的性质。

定理6 设正实数 α 展开连分数为 [ a 0 , a 1 , a 2 , ] ,则其渐近分数 p n q n 满足如下性质:

p n q n 1 p n 1 q n = ( 1 ) n 1 p n q n 2 p n 2 q n = ( 1 ) n a n

p n q n 为既约分数;

[ a 0 , a 1 , , a n ] [ a n , a n 1 , , a 0 ] 的第n个渐近分数的分子必相等。

证明 第1、2条性质与命题3中的证明类似。利用 式和行列式的性质即得第3条性质,证毕。

利用渐近分数的矩阵等式还可以比较方便地计算连分数的渐近分数,从而得到无理数的最佳有理逼近。

例7 圆周率 π 的连分数为

π = [ 3 , 7 , 15 , 1 , 292 , 1 , 1 , 1 , 21 , 31 , 14 , 2 , 1 , 1 , 2 , 2 , ] .

利用关于渐近分数的矩阵等式有

( p 1 p 0 q 1 q 0 ) = ( a 0 1 1 0 ) ( a 1 1 1 0 ) = ( 22 3 7 1 )

( p 3 p 2 q 3 q 2 ) = ( 22 3 7 1 ) ( 15 1 1 0 ) ( 1 1 1 0 ) = ( 355 333 113 106 )

π 的前几个渐近分数为

3 1 , 22 7 , 333 106 , 355 113 , 103993 33102 , 104348 33215

其中 22 7 355 113 分别称为疏率和密率。密率是分母小于16,604的分数中最接近 π 的。

例8 贵金属数是二次方程式 x 2 m x 1 = 0 (整数 m > 0 )的正根

m + m 2 + 4 2 .

贵金属数的连分数表示是 [ m , m , m , ] 。利用命题5中关于渐近分数的矩阵等式有

( p n p n 1 q n q n 1 ) = A n + 1 , A = ( m 1 1 0 ) .

A的特征多项式 φ A ( λ ) = λ 2 m λ 1 有两个不相等的特征值

λ 1 = m + m 2 + 4 2 , λ 2 = m m 2 + 4 2 .

分别解出属于特征值 λ 1 λ 2 的特征向量 X 1 = ( λ 1 , 1 ) T X 2 = ( λ 2 , 1 ) T 。依次以 X 1 X 2 为列向量组成可逆方阵P,则

A = P ( λ 1 λ 2 ) P 1

A n + 1 = 1 λ 1 λ 2 ( λ 1 λ 2 1 1 ) ( λ 1 n + 1 λ 2 n + 1 ) ( 1 λ 2 1 λ 1 ) = 1 m 2 + 4 ( λ 1 n + 2 λ 2 n + 2 λ 1 n + 1 λ 2 n + 1 ) .

所以,贵金属数的渐近分数为

p n q n = λ 1 n + 2 λ 2 n + 2 λ 1 n + 1 λ 2 n + 1 .

特别地, m = 1 时, 1 + 5 2 是黄金分割数,同时也是斐波那契数列相邻两项之比的极限。当 m = 2 时, 1 + 2 是白银分割数,同时也是佩尔数列相邻两项之比的极限。

4. 结论

矩阵运算在连分数中具有广泛而深入的应用,为我们深入理解和研究连分数提供了很好的工具和有益的指导。本文利用矩阵运算技巧证明了连分数的一些性质,通过实例展示了矩阵在求圆周率、贵金属数的渐近分数等问题时的巧妙应用。然而,本文的研究范围存在一定的局限性,未来的研究可以充分利用矩阵的强大性质,深入探究矩阵在连分数的逼近理论、求解不定方程、数值分析等方面的应用。

基金项目

感谢国家自然科学基金(批准号11901390),上海高校青年教师培养资助计划(“互联网+”背景下课程思政融入《高等数学》的路径研究)的支持。

NOTES

*通讯作者。

参考文献

[1] 张贤科. 初等数论[M]. 北京: 高等教育出版社, 2016.
[2] 檀结庆, 等. 连分式理论及其应用[M]. 北京: 科学出版社, 2007.
[3] Rosen, K.H. (2011) Elementary Number Theory and Its Applications. 6th Edition, Pearson, Bos-ton.
[4] 江宝安. 一种基于连分数逼近Legendre定理的RSA攻击算法[J]. 信息安全研究, 2021, 7(11): 1037-1040.
[5] Martin, D.E. (2023) Continued Fractions over Non-Euclidean Imaginary Quadratic Rings. Journal of Number Theory, 243, 688-714.
https://doi.org/10.1016/j.jnt.2022.06.004
[6] Ammous, B., Ben Mahmoud, N. and Hbaib, M. (2022) On the Quasi-Periodic P-Adic Ruban Continued Fractions. Czechoslovak Mathematical Journal, 72, 1157-1166.
https://doi.org/10.21136/CMJ.2022.0409-21
[7] 王琳. 关于最大公约数的一个问题[J]. 数学通报, 1992(1): 33-35.
[8] Hardy, G.H. and Wright, E.M. (2008) An Introduction to the Theory of Numbers. Oxford University Press, Oxford.