实验三 最佳分数近似值

./数学实验姓名：康萍学号：4老师：贵仓班级：2013级〔3班时间：2016年4月19日实验三最佳分数近似值实验目的本实验是要研究怎样用分数近似值去对给定的无理数做最佳逼近。而"最佳"就是指既要误差小,又要分母小。我们首先需要对"最佳"定出具体而明确的标准,通过比较各种方法,最终寻找一个求最佳分数近似值的简单易行的算法。二、实验环境基于Windows环境下的Mathematica7.0软件。实验的基本理论和方法、分数对无理数的最佳逼近设是给定的无理数,是分数,如果有一个分数的分母并且误差,或者分母且误差,那么就是比更佳的分数近似值,就不能是"最佳"。反过来,如果的误差比起分母不超过Q的其他分数近似值都小,也就是对所有的以及且成立,就称给出了的最佳逼近。比如,对,分母为1最接近的分数近似值,是最佳分数逼近〔因为根本就没有比他分母更小的分数。分母为2最接近的分数近似值,他的分母比1大,但误差不比小,是比更差的分数近似值,不是最佳。我们也可以将误差小、分母小这两个标准综合起来,以误差与分母的乘积为标准来判定分数近似值的优劣,越小,越优。还可以进一步强化"分母小"这一要求,用做衡量标准,值越小越优。实数的连分数展开仍以为例。先找它的分母为1的最佳近似值,也就是最佳整数近似值,显然是3.在寻找比3的误差更小〔当然分母更大的分数近似值时并不需要依次考虑分母为的分数。因为这时已经有了整数近似值3,则。其中是3的误差,。只要能找到的最佳分数近似值,再加3就得到的最佳分数近似值。为了寻找与接近的分数,先寻找接近的整数,显然是7.于是〔1这就是祖冲之的约率。为了寻找比误差更小的分数近似值,只需寻找比整数7更接近的分数来作为的近似值。由于,其中。先找的最佳整数近似值,显然是16.于是〔2这就得到祖冲之的密率。如果还要进一步提高精确度,就应当再考虑的整数近似值16的误差。取的整数近似值294,取用代替〔1式中的分母16得到的更好的近似值〔3这个过程可以无限进行下去,得到的越来越精确的分数近似值。为了避免上面的分数表达式〔2中出现减号,在取的整数近似值时不取过剩近似值16而取不足近似值15.这样得到的的分数近似值〔然后再对的误差的倒数取整数近似值。这样的过程可以无穷的进行下去,将表示成下面的形式：其中？代表的都是正整数。一般地,对任何一个正整数,都可以用同样的方法进行展开；取设。当时算法终止,此时。否则.<2>一般地,设已经算出了非负整数,正整数及实数使〔4为了书写的方便,将表达式〔4的右边的分式简写为的形式,于是表达式〔4简写为〔5下一步取。当时算法终止,〔5式成为的这个表达式称为有限连分数。当时仍可取的近似值,从而得到一个有限连分数作为a的近似值：〔另一方面,此时可取代入〔5式得〔6如果是无理数,则以上过程可以无限进行下去,被展开成无限连分数：每个称为的一个渐近分数。所有这些渐进分数都是的最佳分数近似值。当是有理数时,以上过程一定在某一步终止,被展开为有限连分数但所有的仍称为的渐近分数,他们都是的最佳分数近似值。而这种求连分数展开式的递推方法适宜用计算机进行。如果用手工进行,则递推过程中由求商,但我们真正的目的并不是求商,而只是求他的整数部分,而对于手工笔算来说,求比求容易得多,就是1除以作带余除法的商,带余的除法的定义如下：带余除法设是实数,是正实数,是使的最大整数,,则称用对作带余除法得到商和余数。〔注：两个整数相除的带余除法是众所周知的,这里只是把它推广到两个实数相除而已。带余除法的商就是准确的商的整数部分。在求的连分数展开式的时候。第一步求很容易。而且可以认为分别是除以1的整数商和余数。下一步是求的整数部分。我们用1除以作带余除法,求出整数商和余数则当时,又可得到再将除以做带余除法,得到整数商和余数于是又有当,这个过程可按照下面的递推法则进行下去；辗转相除法约定,对每个非负整数,设已经得到了和整数。当时,用除以做带余除法,得到整数商和余数递推过程终止。已经求得之后,如何求各个渐近分数有以下递推算法：约定。对每个,有递推关系式二元一次不定方程的整数解设是整数,求二元一次方程的整数解。不妨设都不为0,否则方程很容易解。必要时交换未知数,可化为.利用辗转相除法,可以得到余数数列和商数列使的商为,余数为,〔约定由于是逐步减少的正整数,必然有某个,余数数列和商数列终止。最后一个非零的就是的最大公约数。而分数被展开成有限连分数去掉这个连分数的最后一项,再将所得的连分数化成普通的既约分数,则是的渐近分数近似值：误差于是。如果c不被d整除,则原方程无整数解。否则是整数,。设。则是方程的一组整数解。方程的通解为其中取遍所有整数。四、实验容与步骤及得到的结果分析实验一分数对无理数的最佳逼近实验容让分母q依次取遍1到1000的所有自然数,对每个分母q,取p=[q*Pi+0.5]得到一个最接近Pi的分数p/q,并将所有的这样的分数列出来,同时列出与Pi的误差。实验步骤在Mathematica中输入语句如下：3实验结果结果分析可见,在1到1000之,在给定的近似误差下,最好的一个分数近似值就是祖冲之所找到的密率355/113。实验二实数的连分数展开实验容2、实验步骤在Mathematica中输入语句如下：3、实验结果4、结果分析我们所得的结果已经比较接近,如果将此过程继续往下做,所得的近似值会越来越接近。实验三二元一次不定方程的整数解1、实验容求二元一次方程的最小整数解。2、实验步骤在Mathematica中输入语句如下：3、实验结果4、结果分析实验四"密率"与"约率"的比较1、实验容编程比较"密率"与"约率"的大小实验步骤在Mathematica中输入语句如下：实验结果4、结果分析分数355/113几乎与足够接近,而22