实验三最佳分数近似值

1、数 学 实 验姓名：康萍学号：4老师：贵仓班级：2013级（3）班时间：2016年4月19日实验三最佳分数近似值一、实验目的本实验是要研究怎样用分数近似值去对给定的无理数做最佳逼近。而“最佳” 就是指既要误差小，又要分母小。我们首先需要对“最佳”定出具体而明确的标 准，通过比较各种方法，最终寻找一个求最佳分数近似值的简单易行的算法。二、实验环境基于Windows环境下的Mathematica7.0软件。三、实验的基本理论和方法（一）、分数对无理数的最佳逼近是给定的无理数,P是分数，如果有一个分数卫的分母q Q并且误差Qq的分数近似值,，或者分母qQ且误差那么£就是比P更佳2就不能是“

2、最佳”反过来，如果-的误差比起分母不超过Q的其他分数近似值P都小，也就是q对所有的qqQ以及qPp P成立，就称QP给出了的最佳逼近比如，对 3014159265 ，分母为1最接近 的分数近似值-，是 最佳1分数逼近（因为根本就没有比他分母更小的分数）。分母为2最接近 的分数近 似值6，他的分母比1大，但误差不比3小，是比-更差的分数近似值，不是最2 1 1佳。我们也可以将误差小、分母小这两个标准综合起来，以误差 一步强化“分母小”这一要求，用q2做衡量标准，q2值越小越优。母q的乘积q为标准来判定分数近似值P的优劣，q越小，卫越优。还可以进qq（二）实数的连分数展开仍以 为例。先找它的分母为

3、1的最佳近似值，也就是 最佳整数近似值，显然是3.在寻找比3的误差更小（当然分母更大）的分数近似值时并不需要依次考虑 分母为2,3,的分数。因为这时已经有了整数近似值 3,贝U 3为。其中人是3的误差，0人1。只要能找到洛的最佳分数近似值，再加3就得到的最佳分数近似值。1为了寻找与x1接近的分数，先寻找A 7.062513305931 接近的整数，显然是7.于是3 3 22（1）A 77这就是祖冲之的约率。为了寻找比 号误差更小的分数近似值，只需寻找比整数 7更接近A的分数来作为 A的近似值。由于 a 7 x2，其中0 x2 0.0625133059311。先找A 丄 15.996594406

4、685X2的最佳整数近似值，显然是16.于是1113A!7 x2716 16(2)1血空11311316这就得到祖冲之的密率如果还要进一步提高精确度，就应当再考虑A的整数近似值16的误差x216 A20.0034055933 14。取 A3293.6345910144 的整数近x2似值294,取A161代替（1）式中的分母16得到的更好294的近似值1T3 7 一16294(3)为了避免上面的分数表达式（2）中出现减号,在取 A215.996594406 的整数近似值时不取过剩近似值16而取不足近似值15.这样得到的的分数近似c 13333 -7 丄 10615(2)然后再对A215 x2&#

5、39;的误差枕的倒数 A1:取整数近似值。这样的过X2程可以无穷的进行下去，将表示成下面的形式:这个过程可以无限进行下去，得到的越来越精确的分数近似值。其中？代表的都是正整数。般地，对任何一个正整数，都可以用同样的方法进行展开;(1)取a0.（表示不超过的最大整数。）设为ao。当X10时算法终止，此时a0 0否则011,此时X1a0般地，设已经算出了非负整数a°，正整数 a1 ,a2, ak 1及实数a0(4)a1a21 Tak 1为了书写的方便，将表达式（4）的右边的分式简写为ao -ak 1Aka1a2的形式，于是表达式（4）简写为a1111a2ak 1ck 1Ak ak1 0（

6、5）式成为1a0下一步取ak Aj,0当xk 10时算法终止,(5)aoa1a2ak 1 ak的这个表达式称为有限连分数。当Xk 1 0时仍可取ak作为民的近似值，从而得到一个有限连分数作为a的近似值:1(5')a0111a2ak 1ak1另一方面，此时可取Ak 11，Ak1ak代入（5）式得xkAk11(6)a0111 1a2ak 1ak Ak 1如果 是无理数，则以上过程可以无限进行下去,被展开成无限连分数:每个a0limn11 1 a1a2ana0ana 1na011a1Pnqna2an称为的一个渐近分数。所有这些渐进分数都是的最佳分数近似值。当 是有理数时，以上过程一定在某一步

7、终止,被展开为有限连分数但所有的ao 1a1a2an1ka01a1 a2-Pk(0 k n)qkak仍称为的渐近分数，他们都是 的最佳分数近似值。而这种求连分数展开式的递推方法适宜用计算机进行。如果用手工进行, 则递推过程中由k求商Ak，但我们真正的目的并不是求商 Ak，而只是求他的整数部分ak，而对于手工笔算来说，求ak比求Ar容易得多，ak就是1除以Ar作带余除法的商，带余的除法的定义如下:带余除法 设 是实数，是正实数，q是使q的最大整数,，则称用 对 作带余除法得到商q和余数r o（注：两个整数相除的带余除法是众所周知的，这里只是把它推广到两个实 数相除而已。带余除法的商q就是准确的商

8、一的整数部分。）a0很容易。而在求 的连分数展开式的时候。第一步求a0 及1且可以认为a。，1分别是 除以1的整数商和余数。下一步是求A1 -的整数部1分a1再将我们用1除以1作带余除法，求出整数商a1和余数1 a1 1,0 1a1 1 r20,也就是20时，又可得到A2丄：1 23A2a2r2当30时有A 互,这个过程可按照下面的递推法则进行下去;31，对每个非负整数k，设已经得到了ri( 1 i k)和整数ai0 ik 1得到整数商ak和余数|< 1,0k 1已经求得a0, a1,，ak，之后，约定p 11,q 10, P00,q0，r01,有递推关系式对每个k辗转相除法约定r 11

9、 0。当k 0时，用k除以k做带余除法,5；当rk 0时递推过程终止。如何求各个渐近分数 压？有以下递推算法:qkPk qk元一次不定方程的整数解Pk 2 ak pk 11qk 2akqk 1 设a,b,c是整数，求二元一次方程 ax by c的整数解。不妨设a,b都不为0 ,否则方程很容易解。必要时交换未知数x,y，可化为b的情形，并可使a 0.1除以2做带余除法，得到整数商a?和余数31 a22,0 3 2于是又利用辗转相除法，可以得到余数数列a, b,r1,r2,和商数列a0,a1,a2,使ri除以ri的商为a；，余数为口 1 ,（约定a r 1fb r0.）由于口是逐步减少的正整数，必

10、然有某个rk 1 0 rk，余数数列和商数列终止。最后一个非零的rk就a是a,b的最大公约数da,b。而分数三被展开成有限连分数ba0a11a2ak 1 ak去掉这个连分数的最后一项再将所得的连分数化成普通的既约分数u，则akV是f的渐近分数近似值:误差u小1vao11 1a1a2ak 2ak 1a ud于是av bu d,1,a v b u d。如果c不被d整除，则原方程无b,整数解。否则t cd是整数，a tv b tu c。设bXotv, yoyu是方程ax by c的一组整数解。方程的通解为bax xo, y yodd其中 取遍所有整数。四、实验容与步骤及得到的结果分析实验一分数对无理

11、数的最佳逼近1、实验容让分母q依次取遍1到1000的所有自然数，对每个分母q,取p=q*Pi+0.5得到一个最接近Pi的分数p/q，并将所有的这样的分数列出来，同时列出与Pi的误差2、实验步骤在Mathematica中输入语句如下：lnl:=p f q, a, hf 1 ; a = ?Forg lf 皿虫 1000p = Floor gitPi + 1/2;- J. L41 > (ED叽 Continue:H = D;Fori_ lf i Lenqtha； i +,2 -U = It Breakf：If b 0r AendToa, Pi - p /g / &yqU?；sl s S

12、ort -a jfori = 1, 1 i Leii<jtlia, i+,氏丄皿7=52JJ3实验结果355i 1 err = ! +65164 p10-7 Fi =1U- 2816 12 etr = 9.5S#S*xir Pi =69? 上28(2i = 3 err = 9.处俩*4严 Pi =511?4«31=4 err = 0. D0«011t»!09 Pi =7fr»243i 5 err = D. 000011364 Ji =?S421* B 召 err > 0. D00012»!lfl Pi *712152i = 7 er

13、r = D. D00013U5S Pi =«85m 0. 000015927 Pi17 S3958?rr = D.DOOD15739 Ji =179?121M2i ID err - QOOO«1»H63 Pi 45,1JB111 Eir = D. 00011(19 Pi =449缈9i = 12 err = Q.000«2?2532 Pi =80 524411 = 13 err - 0.000*2512 Pi =7?7L0>1i = 14 err 0.10D025B433 Pi =346UM 3i = 15 err - D.IDQ0!e38>

14、5 Pi 312 彗时i = 1( «rt = O.»0DC!ft9rit ?i =叮52774i = 11 err = D, <000297997 Ji =tn1>19i 11 err 轨 DOIOOM Pi 579 1131i = 15 err = I. QD<0H> Pi =551ilili < err > Q.»QD0n»422 Pi H2Wi = 21 ert = d. <00(U21 H =mnili = IS cn = 0,0003525? Ji =91!7»± > 23

15、err > 0. >Q003«2477 Pi 一Z3368富i - M ere > 0. *000401422 Pi 一3192S?3i = S5 ert - 0.10004 辿歸 ti =3085i 26 err = 0.0000447921 Pi 37err . 0.0«0«5M50i1B41121 err = 0.00(»045Sin Pi =58(err = 0.DI0DS133L11354Pi =431I3»1l = 28 err = IL UUUU461261 Pi =M33>err = 0.01003234

16、2M0Pi，713250i = ?9 err = 0. n(l(1047389 Pi 955401109i 于0 err -Fi 514413 (MLerr = O.D«OOSa?2S Pi =9iS "17 err-O.OOODMOOSl Pi =11Q91 = 31 err = 0.00005040 Pi =沾34243err - 0.H0O5526SIerr = 1.0100651783 2994i = 32err = 0.0000!i0651»Pi =mji 一 53err = 0.000053t355Pi -1595倔i - 34err = 0.0000

17、541921Pi -1015251 = 35err = 0.000056(395>1 =14864731 = 36err 0.OOOD5B2«21Pi亠2375754273)Pi£432353444Sis4749err = t.D*OOSt541terr - I.DI007I6242err = 0.9t007Z185»err = I.0100734021Pierr = 1.0100740111 PiZ6S6沾53Q L95613?1294、结果分析可见，在1到1000之，在给定的近似误差下，最好的一个分数近似值就是 祖冲之所找到的密率355/113。实验二实

18、数的连分数展开1、实验容计算335511315 12、实验步骤在Mathematica中输入语句如下：帆住E：= a ；= 3.1415265;pxu:=Modul亡【°打 p = t = (, i, c = a,Do b Floor c ; c-l/Cc-b); AmJemiroCt! h T n>P =； i = b - 1；Wi le(i= tEir>J +1/pr i = i - 1 :Retui-Jip； 3tt>s1 - at Print p"4 J 3、实验结果f r 2.703547f 15, 1|L 1±3Jl4、结果分析我们所得的结果已经比较接近，如果将此过程继续往下做，所得的近似值 会越来越接近 。实验三二元一次不定方程的整数解1、实验容求二元一次方程1234567x 765432" 1的最小整数解。2、实验步骤在Mathematica中输入语句如下：ln5：= LastMinijnLzef(ic +12345 67 x- 7654 351 y = 1, x > y > 0 LIJLtf W3、实验结果4、结果分析