数值计算方法课程设计-计算连分数

文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。目录1：连分数相关知识.................................................................................错误!未定义书签。2：课程设计相关.....................................................................................错误!未定义书签。1：题目：.........................................................................................错误!未定义书签。2：算法设计或算法分析：.............................................................错误!未定义书签。3：算法实现步骤：.........................................................................错误!未定义书签。4：源程序代码：（建立）...............................................................错误!未定义书签。5：计算结果（包括相应的图形）：...............................................错误!未定义书签。6：结果分析（包括误差分析）：...................................................错误!未定义书签。7：心得体会：.................................................................................错误!未定义书签。参考资料：...............................................................................................错误!未定义书签。1：连分数相关知识连分数，它不仅历史悠久，而且是一个有力的工具，解决了不少很深入的问题，更难能可贵的，它还和我们日常生活中的历法有密切的关系。它欧几里德计算法（辗转相除法）有貌异实同之妙，这就是「连分数」法。现在我们先回想一下欧几里德计算法：设a,b为两整数，且b>a，则现在，我们把（甲）组里的式子全写为分式，如下所示：再将乙组中第一式之以第三式之倒数代入，接着以第三式之倒数代入，依次类推，即得上式之右边即所谓的「连分数」（更精确地说，有穷简单连分数）。我们简写为现在考虑一般有穷连分数的几个基本关系式。设为任意一个一般的有穷连分数（也就是说为任意非零之实数），由计算易得一般地1word格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。称为此连分数之第k个渐近分数，我们有公式1：证明：利用归纳法公式2：。证明：利用归纳法，n=1时，pqpqaa10aa-=(+1)x1-x=1010100又公式3：。证明：利用归纳法，n=2时，pqpqaaaaaaaaa-=(++x1-x(+1)=2200221020021又在实际应用中，我们所遭遇的有穷连分数，就像（丙）式一样，其中的a0为整数，a1,a2,…,aN皆为正整数，此种连分数特称为简单有穷连分数。由以上公式，我们可推论出有关此等简单有穷连分数的几个基本性质。推论1：当k>1时，，故。证明：由公式1，，又由归纳法得推论2：。证明：由公式2，两边除以qkqk-1即得。推论3：证明由公式3，两边除以qkqk-1，即得当n=2k为偶数时，右式为正，故得当n=2k+1为奇数时，右式为负，故得2word格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。推论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，则根据假设3word格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。xxx1:=:(1-),即xx+-1=02解出（另一根不合），此数即为黄金比，为一无理数，其近似值为0.618。所以平常也有人说黄金比是3:5=0.6的。现在换一个角度来看x的求法：方程式x2+x-1=0可化为将此式带入其本身右边的x中，便得继续不断此步骤，则得这就是无穷连分数的一个例子。我们看一下它的头几个渐近分数：由此可知利用连分数来求此种二次方程式的无理数是一个非常有价值的办法。一般而言，一个型如的式子称为无穷连分数，简写成通常我们只考虑a0为整数而a1,a2,…为正整数的情形，这又特别叫做简单无穷连分数。每一个实数也都可以用简单无穷连分数表示，其法如下：设ξ为任意一实数，则a0其中为整数而（此种表法为唯一）。若，则a1其中为整数而（此种表法为唯一）。这种步骤反复进行，若ξ非有理数，则程序不终止，而得一简单无穷连分数。无穷连分数之渐近分数推论中所有的性质，我们有：命题：设表无穷连分数之第n个渐近分数，则数列即为ξ之无穷连分数收敛。若其收敛值为ξ，则表示。4word格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。证明：由§2.之推论，已知而且由推论2，所以数列(I)有一上界，而数列(II)有一下界，由单调数列之收敛性，(I)与(II)皆收敛。再由推论2，(I)了渐近分数数列{pn/qn}之收与(II)之收敛值是相同的，这就证明敛性。命题后半之证明从略。事实上，渐近分数是所有分母不超过qn的分数中最接近者，也就是说它们是ξ的最佳渐近分数。（参考《数论导引》pp.270-272）。我们也明白地看出所有偶数次项皆比收敛值小，而奇数次项皆比收敛值大。2：课程设计相关1：题目：28.计算连分数读入n,b,b,,b,a,,a,并输出f的值的值，01n1n5word格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。2：算法设计或算法分析：开始输入数组A与BLength(A)~=Length(B)-1?YNn=length(b);fori=n:-1:2y=b(i-1)+a(i-1)/b(i);%b(i-1)=y;end输出y结束3：算法实现步骤：输入数组A和B；判断数组A和B是否符合要求，否则退出并提示；计算数组B的长度，长度为n；fori=n:-1:2y=b(i-1)+a(i-1)/b(i);%b(i-1)=y;6word格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。end输出y；4：源程序代码：（建立）functiony=fraction(a,b)if(length(b)~=length(a)+1)disp('数组A与数组B维数有错！');return;endn=length(b);fori=n:-1:2y=b(i-1)+a(i-1)/b(i);%注意数组A的维数b(i-1)=y;end5：计算结果（包括相应的图形）：>>a,ba=12b=123>>r=fraction(a,b)r=1.3750>>a1,b1a1=4342312b1=517word格式支持编辑，如有帮助欢迎下载支持。

文档从互联网中收集，已重新修正排版，word格式支持编辑，如有帮助欢迎下载支持。>>r=fraction(a1,b1)r=5.83026：结果分析（包括误差分析）：因为算法只有一个循环，所以算法的时间复杂度为n。在y=b(i-1)+a(i-1)/b(i)的赋值运算中将分数化为小数，有小数精度的损失；且算术量越大时，误差越大。7：心得体会：通过本次数值计算的实验课程设计，我对连分数的历史，运算，应用有了一个通识的了解，它有一些可取的性质：一个数的连分数表示是有限的，当且仅当这个数是有理数。•••“简单”有理数的连分数表示是简短的。任何有理数的连分