Toward Abstract Numerical Analysis

ABSTRACT

This paper deals with a technique for proving that certain problems of numerical analysis are numerically unsolvable. So that only methods which are natural for dealing with analytic problems may be presented, notions from recursive function theory have been avoided. Instead, the number of necessary function evaluations is taken as the measure of computational complexity. The role of topological concepts in the study of computability is examined. Last, a topological result is used to prove that a simple initial-value problem is numerically unsolvable.

REFERENCES

• 1: Oliver Aberth, Analysis in the Computable Number Field, Journal of the ACM (JACM), v.15 n.2, p.275-299, April 1968 [doi>10.1145/321450.321460]
• 2: ABERTn, O. The concept of effective method apphed to computational problems of hnear algebra. J. Comput. Syst. Sc~. 5 (1971), 17-25,
• 3: CLEAVE, J. The primitive recursive analysis of ordinary differential equations and the complexity of their solutions j. Comput. Syst. Sc~ 8 (1969), 447-455
• 4: CODDINGTON, E., AND LEVINSON, N. Theory of Ordsnary D~fferent2al Equations. McGraw-Hill, New York, 1955.
• 5: l)u6usDJI, J. Topology. Allyn and Bacon, Boston, 1966.
• 6: HENmCI, PD~screte Variable Methods In Ordinary D~fferential Equations. Wiley, New York, 1962.
• 7: MILLER, WToward abstract numerical analysis Ph D. Dlss., U of Washington, Seattle, 1969.
• 8: MILLER, W.Recursive function theory and numemcal analysis. J. Comput. Syst Sct. $ (1970), 465-472.
• 9: MILLER, W.Unsolvable problems with differentiability hypotheses Proc. Fourth Ann. Pranceton Conf on information Sciences and Systems, 1970, pp 480-482.
• 10: REINGOLD, E M. Review of {2} Comput~l~g Remews 12 (Dec 1971), 22,350.
• 11: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 12: TaAUB, J.F. Computational complexity of lteratlve processes. S~am J. Comput. I (1972), 167- 179.
• 13: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Performance, Theory, Verification