Computational Complexity of One-Step Methods for a Scalar Autonomous Differential Equation.

Abstract

The problem is to calculate an approximate solution of an initial value problem for a scalar autonomous differential equation. A generalized notion of a nonlinear Runge-Kutta (NRK) method is defined. We show that the order of any s-stage NRK method cannot exceed 2s-1; hence, the family of NRK methods due to Brent has the maximal order possible. Using this result, we derive complexity bounds on the problem of finding an approximate solution with error not exceeding epsilon. We also compute the order which minimizes these bounds, and show that this optimal order increases as epsilon decreases, tending to infinity as epsilon tends to zero. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1976
Accession Number
ADA035930

Entities

People

  • Arthur G. Werschulz

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Autonomy

DTIC Thesaurus Topics

  • Analytic Functions
  • Arithmetic
  • Coefficients
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Differential Equations
  • Equations
  • Linear Systems
  • Military Research
  • New York
  • Numbers
  • Polynomials
  • Real Numbers
  • Runge Kutta Method
  • Sequences

Fields of Study

  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Computer Programming and Software Development.