A Bound on the Multiplication Efficiency of Iteration.
Abstract
For a convergent sequence (x(i)) generated by x(i+1) = phi (x(i),X(i-1),...,x(i-dt1)), define the multiplication efficiency measure E to be (log of p to the base 2)/M, where p is the order of convergence, and M is the number of multiplications or divisions needed to compute phi. Then, if phi is any multivariate rational function, E = or < 1. Since E = 1 for the sequence (x(i)) generated by x(i+1) = (x(i)) squared + x(i) - 1/4 with the limit - 1/2, the bound on E is sharp. Let P(M) denote the maximal order for a sequence generated by an iteration with M multiplications. Then P(M) = or < (2 sup M) for all positive integer M. Moreover this bound is sharp. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1972
- Accession Number
- AD0743914
Entities
People
- H. T. Kung
Organizations
- Carnegie Mellon University