文档介绍：目录
1:连分数相关知识 2
2:课程设计相关 10
1:题目: 10
2:算法设计或算法分析: 11
3:算法实现步骤: 11
4:源程序代码:(建立) 12
5:计算结果(包括相应的图形): 12
6:结果分析(包括误差分析): 13
7:心得体会: 13
参考资料: 13
1:连分数相关知识
连分数,它不仅历史悠久,而且是一个有力的工具,解决了不少很深入的问题,更难能可贵的,它还和我们日常生活中的历法有密切的关系。它欧几里德计算法(辗转相除法)有貌异实同之妙,这就是「连分数」法。
现在我们先回想一下欧几里德计算法:
设 a,b 为两整数,且 b>a,则
现在,我们把(甲)组里的式子全写为分式,如下所示:
再将乙组中第一式之以第三式之倒数代入,接着以第三式之倒数代入,依次类推,即得
上式之右边即所谓的「连分数」(更精确地说,有穷简单连分数)。我们简写为
现在考虑一般有穷连分数的几个基本关系式。设
为任意一个一般的有穷连分数(也就是说为任意非零之实数),由计算易得
一般地
称为此连分数之第 k 个渐近分数,我们有
公式 1:
证明:利用归纳法
公式 2: 。
证明:利用归纳法,n=1 时,
p1q0-p0q1 = (a0a1+1) x 1-a0 x a0=1
又
公式 3: 。
证明:利用归纳法,n=2 时,
p2q0-p0q2=(a2a1a0+a2+a0 x 1-a0 x (a2a1+1)=a2
又
在实际应用中,我们所遭遇的有穷连分数,就像(丙)式一样,其中的 a0 为整数,a1,a2,…,aN 皆为正整数,此种连分数特称为简单有穷连分数。由以上公式,我们可推论出有关此等简单有穷连分数的几个基本性质。
推论 1:当 k>1 时, ,故。
证明:由公式 1,,又
由归纳法得。
推论 2:
证明:由公式 2,两边除以 qkqk-1 即得。
推论 3:
证明由公式 3,两边除以 qkqk-1,即得
当 n=2k 为偶数时,右式为正,故得
当 n=2k+1 为奇数时,右式为负,故得
推论 4:对所有,pn 与 qn 互质。
证明:由公式 1 立可得知。
从以上几个推论,我们知道渐近分数的分母一直增大,而两相邻渐近分数之差则愈来愈小。另外,偶数项部分形成单调严格上升数列而奇数项部分形成单调严格下降数列,在第4节讨论无穷连分数时,这些性质对收敛性非常重要。
Aryabhata 的方法是这样的:我们可假设正整数 a 与 b 互质,而且 a>b,将分数展成连分数,假设。令与为最后两个渐近值,则其中
因两者俱为最简分数,故pN=a,qN=b,再由公式2, ,即,(为方便计,可取正号),代入方程式 ax+by=c=c(aqN-1-bpN-1),并展开、移项、化简,得
因而解得
古希腊之神殿 Parthenon 结构之美,叹为观止,常谓之「黄金比」或「黄金分割」,其确实意义如下:
假定有一个长方形,截掉一正方形后,所剩之小长方形与原长方形相似(见图一),则从此小长方形依样再截掉一小正方形,所剩之图形仍与原长方形相似,这种程序可无穷尽地做下去,这就叫做「黄金分割」,而具备此种特性之长方形之长宽比称为「黄金比」。
图一
那黄金分割又怎么和连分数扯上关系呢?
让我们先看一下黄金比的计算:
图二
设图二长方形之长边为单位长 1,而短边长为 x,则根据假设
1:x=x:(1-x),
即
x2+x-1=0
解出(另一根不合),此数即为黄金比,为一无理数,其近似值为 。所以平常也有人说黄金比是 3:5= 的。现在换一个角度来看 x 的求法:方程式 x2+x-1=0 可化为
将此式带入其本身右边的 x 中,便得
继续不断此步骤,则得
这就是无穷连分数的一个例子。我们看一下它的头几个渐近分数:
由此可知利用连分数来求此种二次方程式的无理数是一个非常有价值的办法。一般而言,一个型如
的式子称为无穷连分数,简写成
通常我们只考虑 a0 为整数而 a1,a2,…为正整数的情形,这又特别叫做简单无穷连分数。每一个实数也都可以用简单无穷连分数表示,其法如下:
设ξ为任意一实数,则
其中 a0 为整数而(此种表法为唯一)。
若,则
其中 a1 为整数而(此种表法为唯一)。
这种步骤反复进行,若ξ非有理数,则程序不终止,而得一简单无穷连分数。无穷连分数之渐近分数推论中所有的性质,我们有:
命题:设表无穷连分数之第 n 个渐近分数,则数列收敛。若其收敛值为ξ,则即为ξ之无穷连分数表示。
证明:由§2. 之推论,已知
而且由推论 2, 所以数列(I)有一上界,而数列(II)有一下界,由单