Series solutions of algebraic and differential equations: a comparison of linear and quadratic algebraic convergence

ABSTRACT

Speed of convergence of Newton-like iterations in an algebraic domain can be affected heavily by the increasing cost of each step, so much so that a quadratically convergent algorithm with complex steps may be comparable to a slower one with simple steps. This note gives two examples: solving algebraic and first-order ordinary differential equations using the MACSYMA algebraic manipulation system, demonstrating this phenomenon. The relevant programs are exhibited in the hope that they might give rise to more widespread application of these techniques.

REFERENCES

• 1: M. Anderson. An implementation of the Newton polygon procedure, Term Project for CS 292s, Winter, 1980 (University of California, Berkeley), 1980.
• 2: Jean Della Dora , Giovanni Di Crescenzo , Evelyne Tournier, An Algorithm to Obtain Formal Solutions of a Linear Homogeneous Differential Equation at an Irregular Singular Point, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.273-280, April 05-07, 1982
• 3: W. G. Dubuque. Series Solution of Functional Equations:Taylor-solve, MACSYMA Newsletter 3 no. 3 July, 1986, 18-19.
• 4: R. Fateman. Some comments on series solutions, Proc. 1977 Macsyma Users' Conf., NASA CP- 2012 (July 1977) 43-52.
• 5: Keith O. Geddes, Convergence behavior of the Newton iteration for first order differential equations, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.189-199, June 01, 1979
• 6: H. T. Kung , J. F. Traub, All Algebraic Functions Can Be Computed Fast, Journal of the ACM (JACM), v.25 n.2, p.245-260, April 1978 [doi>10.1145/322063.322068]
• 7: John D. Lipson, Newton's method: a great algebraic algorithm, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.260-270, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806344]
• 8: Y-M Shen. SOODESIS, Term Project for CS 292s, Winter, 1980 (University of California, Berkeley) 20 pp.
• 9: M. F. Singer. Liouvillian solutions of n-th order homogeneous linear differential equations, Amen J. Math. 103, (1981) 661-681.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Boundary value problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Iterative methods

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory