A Bound on the Multiplication Efficiency of Iteration.
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
For a convergent sequence xi generated by xi1 phi xi,Xi-1,...,xi-dt1, define the multiplication efficiency measure E to be log of p to the base 2M, 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 xi generated by xi1 xi squared xi - 14 with the limit - 12, the bound on E is sharp. Let PM denote the maximal order for a sequence generated by an iteration with M multiplications. Then PM or 2 sup M for all positive integer M. Moreover this bound is sharp. Author
- Theoretical Mathematics