home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14493 < prev    next >
Encoding:
Internet Message Format  |  1992-11-07  |  2.6 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!sdd.hp.com!spool.mu.edu!agate!ames!sun-barr!news2me.EBay.Sun.COM!west.West.Sun.COM!cronkite.Central.Sun.COM!texsun!exucom.exu.ericsson.se!ericom!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: sci.math
  4. Subject: Re: To express Q(x)/P(x) into continued fraction
  5. Message-ID: <1992Nov5.131433.18445@odin.diku.dk>
  6. Date: 5 Nov 92 13:14:33 GMT
  7. References: <1992Nov5.064414.28859@griffin.itc.gu.edu.au>
  8. Sender: torbenm@freke.diku.dk
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 81
  11.  
  12. jchen@sct.gu.edu.au (Jinghong CHEN) writes:
  13.  
  14.  
  15. >Suppose there are two n-th order polynomials Q(x) and P(x), how can we
  16. >express Q(x)/P(x) into a continued fraction, i.e.
  17.  
  18. >      Q(x)             a0
  19. >     ------ = ----------------------
  20. >      P(x)                a1
  21. >               x + -----------------
  22. >                                an
  23. >                    x + ... + ------
  24. >                               x + a
  25.  
  26. Normally, a continued fraction has the form
  27.  
  28. a0 + 1
  29.     ------------
  30.     a1 + 1
  31.     --------
  32.     a2 + 1
  33.         ----
  34.         ...
  35.           --
  36.           an
  37.  
  38. where the ai are polynomia in x.
  39.  
  40. We need not even assume that P and Q have the same order. I assume
  41. that you are familiar with the standard polynomial division algorithm,
  42. and is able to find the quotient and remainder polynomia. That is,
  43. find K(x) and R(x), such that
  44.  
  45.     Q(x)/P(x) = K(x) + R(x)/P(x)
  46.  
  47. where R has a strictly lower order than P.
  48.  
  49. K(x) is the first term (a0) of the continued fraction. The remaining
  50. terms are found by letting a1,... be the continued fraction of
  51. P(x)/R(x).
  52.  
  53. Example:
  54.  
  55. consider Q(x)=2x^3+x^2-3x+1, P(x)=x^3-2x^2-x-4
  56.  
  57. By normal division we get
  58.  
  59. K(x) = 2, R(x) = 5x^2-x+9
  60.  
  61. so a0 = 2. Now we try P(x)/R(x), ad get
  62.  
  63. K'(x) = (1/5)x+(11/25), R'(x) = (-1/5)x-199/25
  64.  
  65. so a1 = (1/5)x+(11/25). Doing R(x)/R'(x) we get
  66.  
  67. K''(x) = -25x+1000, R''(x) = 3969
  68.  
  69. Now we only need to do R'(x)/R''(x) = (-1/19845)x-199/92400
  70.  
  71. Thus our complete continued fraction is
  72.  
  73.     Q(x)        1
  74.     ---- = 2 + ------------------------------------------------
  75.     P(x)       (1/5)x+(11/25) + 1
  76.                    --------------------------------
  77.                    -25x+1000 + 1
  78.                           ---------------------
  79.                           (-1/19845)x-199/92400
  80.  
  81.  
  82. All but the first term is guaranteed to have an order of at least 1.
  83. All quotients of polynomia have finite continud fractions, with n+1
  84. terms (a0,...,an), where n is the order of the polynomium. I think all
  85. C-infinity functions can be written as a (possibly infinite) continous
  86. fraction.
  87.  
  88.     Torben Mogensen (torbenm@diku.dk)
  89.  
  90. P.S.
  91. There is probably a method for constructing a fraction of the form you
  92. memtioned.
  93.