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