Accession Number : AD0743914

Title :   A Bound on the Multiplication Efficiency of Iteration.

Descriptive Note : Technical rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Kung,H. T.

Report Date : MAR 1972

Pagination or Media Count : 14

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)

Descriptors :   (*NUMERICAL ANALYSIS, COMPUTER PROGRAMMING), (*ITERATIONS, EFFICIENCY), SEQUENCES(MATHEMATICS), CONVERGENCE, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE