A bound on the multiplicative efficiency of iteration

摘要

For a convergent sequence {xi} generated by xi+1=(xi, xi−1,…,xi−d+1), define the multiplicative efficiency measure E to be (log2p)/M, where p is the order of convergence and M is the number of multiplications or divisions needed to compute . Then, ifis any multivariate rational function, E≤1. Since E=1 for the sequence {xi} generated by xi+1=xi2+xi−1/4 with the limit −1/2, the bound on E is sharp.Let PM denote the maximal order for a sequence generated by an iteration with M multiplications. Then PM≤2M for all positive integers M. Moreover this bound is sharp.