Mathematical Preliminaries and Error Analysis

1.1 Introduction

This part examines problems that can be solved by methods of approximation, techniques we call numerical methods. We begin by considering some of the mathematical and computational topics that arise when approximating a solution to a problem.

Nearly all the problems whose solutions can be approximated involve continuous functions, so calculus is the principal tool to use for deriving numerical methods and verifying that they solve the problems. The calculus definitions and results included in the next section provide a handy reference when these concepts are needed later in the book.

There are two things to consider when applying a numerical technique to solve a problem. The first and most obvious is to obtain the approximation. The equally important second objective is to determine a safety factor for the approximation: some assurance, or at least a sense, of the accuracy of the approximation. Sections 1.3 and 1.4 deal with a standard difficulty that occurs when applying techniques to approximate the solution to a problem: Where and why is computational error produced and how can it be controlled?

The final section in this chapter describes various types and sources of mathematical software for implementing numerical methods.

1.2 Review of Calculus

The limit of a function at a specific number tells, in essence, what the function values approach as the numbers in the domain approach the specific number. This is a difficult concept to state precisely. The limit concept is basic to calculus, and the major developments of calculus were discovered in the latter part of the seventeenth century, primarily by Isaac Newton and Gottfried Leibnitz. However, it was not until 200 years later that Augustus Cauchy, based on work of Karl Weierstrass, first expressed the limit concept in the form we now use.

We say that a function $f$ defined on a set $X$ of real numbers has the limit $L$ at $x_{0}$, written $\lim_{x\to0}$$f(x)=L$, if, given any real number $\varepsilon>0$, there exists a real number $\delta>0$ such that $\left|f\left(x\right)-L\right|<\varepsilon$ whenever $0<\left|x-x_{0}\right|<\varepsilon$. This definition ensures that values of the function will be close to $L$ whenever $x$ is sufficiently close to $x_{0}$ . (See Figure 1.1.)

Figure 1.1

A function is said to be continuous at a number in its domain when the limit at the number agrees with the value of the function at the number. So, a function $f$ is continuous at $x_{0}$ if $\lim_{x\to0}f(x)=f\left(x_{0}\right)$, and $f$ is continuous on the set $X$ if it is continuous at each number in $X$. We use $C(X)$ to denote the set of all functions that are continuous on $X$. When $X$ is an interval of the real line, the parentheses in this notation are omitted. For example, the set of all functions that are continuous on the closed interval $[a,b]$ is denoted $C[a,b]$.

The limit of a sequence of real or complex numbers is defined in a similar manner. An infinite sequence $\left\{ x_{n}\right\} _{n=1}^{\infty}$ converges to a number $x$ if, given any $\varepsilon>0$, there exists a positive integer $N\left(\varepsilon\right)$ such that $\left|x_{n}-x\right|<\varepsilon$ whenever $n>N\left(\varepsilon\right)$. The notation $\lim_{n\to\infty}x_{n}=x$, or $x_{n}\to x$ as $n\to\infty$, means that the sequence $\left\{ x_{n}\right\} _{n=1}^{\infty}$ converges to $x$.

[Continuity and Sequence Convergence] If f is a function defined on a set $X$ of real numbers and $x_{0}\in X$, then the following are equivalent:
a. $f$ is continuous at $x_{0}$ ;
b. If $\left\{ x_{n}\right\} _{n=1}^{\infty}$ is any sequence in $X$ converging to $x_{0}$ , then \[\lim_{n\to\infty}f\left(x_{n}\right)=f\left(x_{0}\right)\]

All the functions we will consider when discussing numerical methods will be continuous since this is a minimal requirement for predictable behavior. Functions that are not continuous can skip over points of interest, which can cause difficulties when we attempt to approximate a solution to a problem. More sophisticated assumptions about a function generally lead to better approximation results. For example, a function with a smooth graph would normally behave more predictably than one with numerous jagged features. Smoothness relies on the concept of the derivative.

If $f$ is a function defined in an open interval containing $x_{0}$ , then $f$ is differentiable at $x_{0}$ when \[f'\left(x\right)=\lim_{x\to0}\frac{f\left(x\right)-f\left(x_{0}\right)}{x-x_{0}}\]
exists. The number $f\left(x_{0}\right)$ is called the derivative of f at $x_{0}$ . The derivative of $f$ at $x_{0}$ is the slope of the tangent line to the graph of $f$ at $\left(x_{0},f\left(x_{0}\right)\right)$, as shown in Figure 1.2.

Figure 1.2

A function that has a derivative at each number in a set $X$ is differentiable on $X$. Differentiability is a stronger condition on a function than continuity in the following sense.

[Differentiability Implies Continuity] If the function $f$ is differentiable at $x_{0}$ , then $f$ is continuous at $x_{0}$

The set of all functions that have n continuous derivatives on $X$ is denoted $C^{n}\left(X\right)$, and the set of functions that have derivatives of all orders on $X$ is denoted $C^{\infty}\left(X\right)$ Polynomial, rational, trigonometric, exponential, and logarithmic functions are in $C^{\infty}\left(X\right)$, where $X$ consists of all numbers at which the function is defined.

The next results are of fundamental importance in deriving methods for error estimation. The proofs of most of these can be found in any standard calculus text.

[Mean Value Theorem] If $f\in C\left[a,b\right]$ and $f$ is differentiable on $(a,b)$, then $a$ number $c$ in $(a,b)$ exists such that (see Figure 1.3) \[f'\left(c\right)=\frac{f\left(b\right)-f\left(a\right)}{b-a}\]

Figure 1.3

The following result is frequently used to determine bounds for error formulas.

[Extreme Value Theorem] If $f\in C[a,b]$, then $c_{1}$ and $c_{2}$ in $[a,b]$ exist with $f(c_{1})\leq f\left(x\right)\leq f\left(c_{2}\right)$ for all $x$ in $[a,b]$. If, in addition, $f$ is differentiable on $(a,b)$, then the numbers $c_{1}$ and $c_{2}$ occur either at endpoints of $[a,b]$ or where $f'$ is zero.

As mentioned in the preface, we will use the computer algebra system Maple whenever appropriate. We have found this package to be particularly useful for symbolic differentiation and plotting graphs $\square$
.