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:

1972-03-01

Pagination or Media Count:

14.0

Abstract:

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

Descriptors:

• (*NUMERICAL ANALYSIS
• COMPUTER PROGRAMMING)
• (*ITERATIONS
• EFFICIENCY)
• SEQUENCES(MATHEMATICS)
• CONVERGENCE
• THEOREMS

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE