A bound on the multiplicative efficiency of iteration

✍ Scribed by H.T. Kung

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 290 KB
• Volume: 7
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(73)80027-3

✦ Synopsis

For a convergent sequence {xi} generated by xi+l = ~(x~, xt_ l ,..., Xi_d+l) , define the multiplicative efficiency measure E to be (log~p)/M, where p is the order of convergence and M is the number of multiplications or divisions needed to compute rp. Then, if 9 is any multivariate rational function, E < 1. Since E = 1 for the sequence {xi} generated by x~+l = x~ ~ + xi --~ 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 < 2 M for all positive integers M. Moreover this bound is sharp.