home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 2 / DATAFILE_PDCD2.iso / fractals / fractal107 / userfunc / 3rootdoc next >
Encoding:
Text File  |  1992-03-25  |  4.2 KB  |  118 lines
  1. CubeRoot Documentation   16 March 1992, by Steve Markham
  2. ======================
  3.  
  4. This document describes the CubeRoot module for inclusion with the AFG
  5. !Fractal application.
  6.  
  7. Overview
  8. ========
  9.  
  10. CubeRoot is a plotting routine which maps the cube roots of 1 onto the
  11. complex plane. It uses Newton's algorithm of successive approximation to map
  12. the way in which the three roots attract points on the complex plane.
  13.  
  14. The three basins of attraction surrounding the roots are presented in
  15. colour, the tint of the colour representing the number of iterations that
  16. the routine takes before the initial point converges to one of the roots. 
  17.  
  18. A fractal boundary exists between the basins of attraction which has the
  19. curious property that wherever two colours try to come together, the third
  20. colour intervenes.
  21.  
  22.  
  23. The algorithm
  24. =============
  25.  
  26. The number "1" has three cube roots. In complex notation they are at:
  27.  
  28.  1+i0; -0.5+i.8666..; -0.5-0.8666.. where 0.86666...is SQR(3)/2.
  29.  
  30. For real numbers Newton's method successively iterates:
  31.  
  32. Let x=a be an approximation to the solution of equation f(x)=0.
  33. Let x=a+h be the accurate solution i.e. f(a+h)=0.
  34. If x=a is a good approximation then h will be small.
  35.  
  36. Thus     f(a+h) is approximately equal to f(a)+hf'(a),
  37. i.e.          0 is approximately equal to f(a)+hf'(a),
  38.                h is approximately equal to -f(a)/f'(a)
  39.  
  40. where f'(a) represents the first derivative of f(a). If x=a is a reasonably
  41. good approximate root of an equation f(x)=0, then x=a-f(a)/f'(a) is a closer
  42. one. The iteration process is repeated until the value of f(a)/f'(a) reaches
  43. an arbitrarily small value i.e. the error between the current of x and the
  44. exact root is very small.
  45.  
  46. The process above can be applied equally well to complex numbers (although
  47. the algebra gets more complicated!), and by using the computer to do the
  48. calculations the initial approximations do not have to be at all close to
  49. the roots.
  50.  
  51. From the above it should(?) be clear that approximations close to the roots
  52. will converge quickly and this is the case. For other values, the iteration
  53. process bounces around chaotically before finally converging. 
  54.  
  55. The implementation
  56. ================== 
  57.                    
  58. The initial equation is:     (rx+iy)^3=1      where r and i are the
  59.                       or     (rx+iy)^3-1=0    coefficients of the real
  60.                                               and imaginary components x,y.
  61.  
  62. Expanding (rx+iy)^3 for the coefficients yields:
  63.  
  64. Real part                 M=2i(r^2)+i(r^2-i^2)
  65. Imaginary part            N=r(r^2-3i^2)-1
  66. 1st derivative, real      T=3(r^2-i^2)
  67. 1st derivative, imaginary U=6ir,
  68.  
  69. and for the error calculation  f(x)/f'(x):
  70.  
  71. numerator real            nr=NT-MU
  72. numerator imaginary       ni=TM-NU
  73. denominator              den=T^2-U^2,
  74.  
  75. hence error(real)        err=nr/den
  76.       error(imaginary)   eri=ni/den
  77.  
  78. For the next iteration    r(next)=r-err
  79.                           i(next)=i=eri
  80.  
  81. During the iteration process, some of the numbers become very large, due to
  82. the fact that the initial values are a long way from the root, or the guess
  83. may lie on the fractal boundary.
  84.        
  85. For this reason integer arithmetic of the int_27 type is not applicable.
  86. CubeRoot uses double precision floating point arithmetic throughout. (If you
  87. can think of a better way let me know!)
  88.  
  89. The routine takes about 6 minutes with an ARM 3 to plot (about twice as fast
  90. as BASIC).
  91.  
  92. The number of iterations taken to converge is presented as a variation in
  93. the tint of the colour of the point. The colour is the same as the main
  94. field where the root lies. The presentation of the tints is cyclic; there
  95. are only four tints available. No doubt this could be improved. 
  96.  
  97. Other points
  98. ============
  99.  
  100. The CubeRoot plotter includes some error checking for initial values.
  101. Although the routine will cope with very large values for r and i, the
  102. interesting area lies around the roots. For this reason, r and i and limited
  103. to +/- 4.
  104.  
  105. The resolution of the plot is controlled by the value assigned to the error.
  106. A minimum value of 1E-15 is the smallest I have tested, and is set as the
  107. minimum allowable.
  108. ==========================================================================
  109.  
  110. This module was written by
  111.  
  112. S.Markham
  113. 28,High Street,
  114. Over,
  115. CAMBRIDGE CB4 5ND
  116.  
  117. For the AFG.
  118.