{'fraction_non_alphanumeric': 0.04318963663728231, 'fraction_numerical': 0.011261019135669749, 'mean_word_length': 3.9878016085790886, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Equivalence Theorems in Numerical Analysis : Integration, Differentiation and Interpolation

We show that if a numerical method is posed as a sequence of operators acting on data and depending on a parameter, typically a measure of the size of discretization, then consistency, convergence and stability can be related by a Lax-Richtmyer type equivalence theorem -- a consistent method is convergent if and only if it is stable. We define consistency as convergence on a dense subspace and stability as discrete well-posedness. In some applications convergence is harder to prove than consistency or stability since convergence requires knowledge of the solution. An equivalence theorem can be useful in such settings. We give concrete instances of equivalence theorems for polynomial interpolation, numerical differentiation, numerical integration using quadrature rules and Monte Carlo integration.


Introduction
For a numerical method the three most important aspects are its consistency, convergence and stability. These three were related in the well known equivalence theorem of Lax and Richtmyer for finite difference methods for certain partial differential equations [13]. We show that in a very general setting of numerical methods, in which a numerical method is posed as a family of operators acting on data, there is a Lax-Richtmyer type equivalence theorem : a consistent method is convergent if and only if it is stable. After proving the theorem in two general settings (Theorem 3.3 and Theorem 3.5), we prove it in specific instances of numerical integration using quadrature, numerical integration using Monte Carlo methods, numerical differentiation and polynomial interpolation.
Consistency is a measure of how good the discretization is. Roughly, it says that the discretization is close to the smooth operator in some sense. If the discrete solution converges to the smooth solution then the numerical method is said to be convergent. Note that for discussing consistency and convergence one needs some information about the smooth problem and the smooth solution. However, numerical stability is purely a property of the discrete scheme. Roughly, stability means that the propagated error is controlled by the error in the data. Hence there is a similarity between numerical stability and well-posedness.
In practice, convergence can be the hardest to prove among consistency, convergence and stability, since the actual solution is usually not known. Hence equivalence theorems can be useful in such situations. Equivalence theorems essentially say that we need not worry about the convergence while solving a problem numerically as long as its discretization is consistent with the smooth problem and the discrete scheme is stable. In addition, such theorems also show that unstable schemes will not converge for some data. These are the same advantages that are often appreciated in the setting of the classical Lax-Richtmyer equivalence theorem for finite difference schemes (see [16], page 32).
After the preliminaries in the next section, in Section 3 we define consistency, convergence and stability in a general context of operators acting on data and we then prove equivalence theorems in this setting. The three sections that follow specialize these notions to specific classes of basic numerical methods. The convergence and stability theory for these example areas are well understood, but equivalence theorems have not been discussed in these areas in the literature.
As given here, the equivalence theorems in these example areas serve only as concrete instances for illustration of the main ideas. We make no claims that these examples have direct practical importance in numerical analysis. However, with proper generalizations, the ideas might be of use in practical situations. For example, convergence of multidimensional interpolation can be related to its stability and consistency, as we sketch in Section 6. Until now the advantages of equivalence theorem have been limited to finite difference methods. We suggest that similar benefits may be possible in many areas of numerical analysis.

Preliminaries
For the convenience of the reader, we state some definitions and theorems used later on in the paper. Uniform boundedness principle is one of the fundamental building blocks of functional analysis and it is useful for proving equivalence theorems in the linear operator setting. It says that a sequence of pointwise bounded continuous linear operators defined on a complete normed linear space are uniformly bounded.
Theorem 2.1 (Uniform Boundedness Principle). Let {F i∈I } be a set of bounded linear operators from a Banach space V to a normed linear space W , where I is an arbitrary set. Assume for every v ∈ V , the set {F i (v)} is bounded. Then sup i∈I F i < ∞.
Proof. See [1] or [6]. The main ingredient of the proof is Baire category theorem.
The next lemma will be used in Section 6 for proving that polynomial interpolation operators are bounded. Lemma 2.2. Let V and W be normed linear spaces over R, where W is finite dimensional. Let T : V → W be a surjective linear operator with a closed kernel. Then T is continuous.
Proof. Since K = T −1 (0) is closed, V /K is a normed linear space (see for instance Theorem 4.2 on page 70 in [6]). For v ∈ V the norm in V /K is defined as usual to be v + K V /K := inf{ v + k s.t. k ∈ K}, which is the distance of v from K. Let T : V /K → W be the unique linear map such that T = T •π, where π : V → V /K is the quotient map. Recall that the quotient map is continuous. Note also that T is a bijection. Then since T is a linear bijection between V /K and W , and W is finite dimensional, we have that V /K is finite dimensional. Thus T is continuous (see page 56 of [1]). Hence T is continuous since it is the composition of two continuous functions. Remark 2.3. Note that all that one needs above is that the image of T in W be finite dimensional and the kernel be closed. The surjectivity of T is not required in that case.
The remaining part of this section deals with some basic facts about probability theory which are needed when we discuss Monte Carlo integration. These are not needed for the general equivalence theorems of Section 3 or other sections with the exception of Section 4.2. Let (Ω, Σ, P ) denote a probability space [19] where Ω is the space of outcomes, Σ is a σ-algebra of subsets of Ω, and P is a countably additive probability measure on Σ.
The probability measure α = P X −1 defined on R is called the distribution of X. We will assume that the random variable X is continuous, i.e., there exists a nonnegative function f (x), called the probability density function (pdf) of the random variable X, defined on R such that for all Borel sets A ⊂ R

The mean or the expectation of the random variable
for all Borel sets A, B.
Theorem 2.6 (Strong Law of Large Numbers). Let X 1 , X 2 , . . . , X n , . . . be a sequence of independent and identically distributed random variables with finite mean µ. Then Proof. See [3].
Theorem 2.7. Let X,Y be two independently and identically distributed random variables. If f is a Borel measurable function [15] on R, then the random variables f (X),f (Y ) are independent and identically distributed.
Proof. Let A, B be any Borel sets in R.
Remark 2.8. We need the condition of Borel measurability on f because for every Borel set A, we want f −1 A to be a Borel set so that Otherwise, if f is not a Borel measurable function, then f −1 A need not be a Borel measurable set and then X −1 (f −1 A) would not be in Σ.

Consistency, Convergence and Stability
If a smooth problem can be formulated as an operator applied to data, then the discretization can usually be formulated as a family of operators depending on some discretization parameter, typically a measure of the mesh size. For example, the parameter might be a measure of the distance between nodes in quadrature, or between interpolation points in polynomial interpolation, etc.
The smooth and discrete operators can be made to act on the same space. In some cases this may be done for example, by considering continuous functions instead of discrete data. We then define the discrete scheme to be convergent if the discrete operators converge to the smooth operator pointwise on the entire space. We define consistency to be convergence on a dense subspace. If the discrete operators are bounded linear then the definition of stability is uniform boundedness of the family of discrete operators. However, when the discrete operators are general nonlinear operators, we define stability as asymptotic pointwise boundedness of the family of operators. The precise definitions are given below in Definition 3.1 and 3.4.
The two definitions of stability lead to two different proofs for the equivalence theorem, both of which appear in this section. Theorem 3.3 is a Lax-Richtmyer type equivalence theorem applicable to general numerical analysis problems when the discrete operators involved are bounded linear. When this condition is dropped, we get Theorem 3.5. Specific incarnations of the linear case theorem are proved later in the context of numerical integration (Theorems 4.3), numerical differentiation (Theorem 5.2), and polynomial interpolation (Theorem 6.5). We treat the general problem of Monte Carlo integration without the assumption of linearity. This leads to a proof of an equivalence theorem (Theorem 4.8) analogous to the nonlinear case but with a probabilistic flavor.
In the classical Lax-Richtmyer equivalence theorem for partial differential equations, the main ingredient in the proof of stability implying convergence is essentially triangle inequality and a density argument [13]. Similarly, to prove the equivalence theorems in this paper, the main tools we use are uniform boundedness principle, triangle inequality and some density arguments.
Let V be a Banach space and W a normed linear space. Let h ∈ (0, 1). The upper limit of h is not relevant because we will be considering limits as h → 0. Let T, T h : V → W be set of bounded linear operators.
Our definition of consistency is motivated by the definition of consistency for finite difference schemes for certain PDEs. For a partial differential equation P u = f , where u is the unknown, and a finite difference scheme P k,h v = f , the finite difference scheme is called consistent if for any smooth function φ(t, x), P φ − P k,h φ → 0 as k, h → 0. Here k and h are a measure of the space and time meshes respectively. The convergence is pointwise convergence at every (t, x). This definition is from [16]. Although density is not explicitly mentioned in this definition, note that smooth functions are dense in the typical function spaces in which the solutions live.
Remark 3.2. Observe that by our definition of consistency, convergence implies consistency. However, there are other definitions of consistency under which there exist inconsistent schemes which converge. See for instance, [21] and Example 1.4.3 in [16] in the context of finite difference schemes for PDEs.
The stability definition above is equivalent to discrete well-posedness, i.e., wellposedness of the discrete problems which is that for any h and for any Proof. Suppose the family is convergent, i.e., lim Since V is complete, by uniform boundedness principle we have uniform boundedness of T h , i.e., sup h T h ≤ K, for some K ≥ 0, and hence stability.
Conversely, suppose that T h is consistent and stable.
Therefore we have convergence.
For the case when the discrete operators are nonlinear we give a different definition of stability since uniform boundedness is unlikely. This allows us to prove an equivalence theorem in this case as well. Most of the examples we give in later sections are linear ones. The proof of the equivalence theorem in the case of nonlinear discrete operators (Theorem 3.5) is different from the linear case.
Let T n be a sequence of operators (not necessarily linear or continuous) from V to W , where V and W are normed linear. Let T : V → W be a bounded linear operator.
Definition 3.4 (Nonlinear Discrete Operator Case). The discrete operator T n is said to converge to T if, for any given v ∈ V , the sequence T n v converges to T v in W , i.e., for each v ∈ V , given ǫ > 0 there exists n 0 ∈ N, such that for all n ≥ n 0 , Remark 3.2 about convergence implying consistency that was made earlier about the linear case is also valid for the nonlinear case covered in Definition 3.4 since the consistency and convergence definitions are the same in both cases.

Theorem 3.5 (Equivalence Theorem for Nonlinear Discrete Operators).
A consistent family of operators T n is convergent if and only if it is stable.
We need to find an n 0 ∈ N and a δ > 0 such that for a given Conversely, suppose we assume stability and consistency. We'll show convergence at v 0 . Thus we need to find an By the choice of v ′ 0 the first and last terms on the right hand side of the above inequality are already at most ǫ/3. By consistency, there exists n 2 ∈ N such that T n v ′ 0 − T v ′ 0 ≤ ǫ/3 whenever n ≥ n 2 . Choose n 0 = max(n 1 , n 2 ). Then for all n ≥ n 0 we have T n v 0 − T v 0 ≤ ǫ. Hence we have convergence at v 0 . Since v 0 was arbitrary, we have that stability implies convergence.
In the linear case above (Definition 3.1 and Theorem 3.3), we used a real parameter h. Typically this will be a measure of size of discretization, such as the maximum distance between adjacent nodes in the partition of an interval. In the nonlinear case (Definition 3.4 and Theorem 3.5) we chose to use a natural number n as the parameter. This might stand, for example, for the number of times sampling is done in Monte Carlo integration. This change from real h to natural number n was done to give both flavors of the definitions and proofs. Each can be written using either h or n.
Remark 3.6. Note that in the proofs of both the equivalence theorems above, we did not assume consistency to show that convergence implies stability. It would have been redundant anyway, to assume consistency when we already have convergence (see Remark 3.2).
Remark 3.7. In [2] (page 67) consistency, convergence and stability are defined in a general setting of linear operators. The problem setting is the solution of equation Lv = w, where L is a bounded linear operator. This is discretized as L n v n = w.
Here the unknown is v and v n and w is known. Under their definitions they show one side of the equivalence theorem, that a consistent method is convergent if it is stable. Our setting however is that of "direct" problems. In our case the object being approximated discretely is T f which is approximated by T h f where f is known data. In [2] an inverse of the operator L is required. In our case T may go from the space of continuous functions to reals (as in Section 4) so that an inverse may not exist.

Numerical Integration
As the first application of the ideas of Section 3 we now discuss the notions of consistency, convergence and stability of numerical integration. We only address definite integrals of continuous functions on the real line. The two most successful methods for numerical integration are quadrature rules and Monte Carlo integration and these are covered below in Sections 4.1 and 4.2. The definitions and proof of theorem for quadrature are identical to the linear case in Section 3. For Monte Carlo integration however, the notions of consistency, convergence and stability need to be put into a probabilistic setting and the equivalence theorem proof uses some probabilistic reasoning. Otherwise, the pattern of the proof follows that of Theorem 3.5. In the quadrature case we apply the theorem to infer convergence of Gaussian quadrature from a simple proof of its stability and we also discuss composite trapezoidal rule and the instability of Newton-Cotes quadrature. In the case of Monte Carlo integration we discuss the Sample Mean method as an example. 4.1. Quadrature. The numerical approximation of definite integrals is often done using quadrature rules [11].
The points x i are called nodes. These nodes are not necessarily equally spaced or progressive. (In progressive quadrature if the number of nodes is increased from n 1 to n 2 then only n 2 − n 1 nodes are new.) The real linear functional I : V → R is a bounded linear operator and I = b − a.
Each I n : V → R is also a linear functional on V and , and so each I n is also a bounded linear functional. With these preliminaries, we can define the stability, consistency and convergence of quadrature rules in exactly the same way as was done in Definition 3.1.
Thus sup n n i=0 w (n) i < ∞ gives discrete well-posedness, i.e., stability. Now we prove an equivalence theorem for quadrature whose statement and proof is exactly the same same as the general linear equivalence theorem proved earlier (Theorem 3.3). We have decided to use the natural number n as a parameter here instead of the real parameter h of Theorem 3.3, because this is the natural setting for quadrature (n + 1 is the number of nodes). Proof. Suppose I n converges to I, i.e., I n (f ) → I(f ) for every f in V . This implies that for any given f in V , the sequence {I n (f )} is bounded. Since each I n is a bounded linear functional, we can apply the uniform boundedness principle which gives us that sup n I n < ∞ which is the definition of stability.
Conversely assume stability and consistency. By definition of consistency then I n (f ) → I(f ) for all f in V 0 where V 0 is a dense subspace of V . Stability means that sup n I n < ∞. By the density of Hence By consistency, there exists n 0 ∈ N such that I(f 0 ) − I n (f 0 ) ≤ ǫ/3 for all n ≥ n 0 . Hence Now we use the equivalence theorem to show convergence of Gaussian quadrature rules and of the composite trapezoidal rule, followed by the non convergence and instability of Newton-Cotes rules.    [17], page 208). This function also appears in the polynomial interpolation section in Example 6.6. By Theorem 4.3 Newton-Cotes should also be unstable. Indeed it is known that in Newton-Cotes rules some of the weights have negative sign and that this leads to instability, i.e., it is known that sup n I n = sup n n i=0 |w (n) i | = ∞ (see page 350 of [11]). 4.2. Monte Carlo Integration. For well behaved functions, i.e., functions with continuous derivatives, the deterministic quadrature rule is very efficient at least in one dimension. However, if the function fails to be well behaved or in the case of multidimensional integrals, other techniques can be competitive. In this section we will define convergence, consistency and stability for Monte Carlo integration. For simplicity, this is done for functions in C[a, b]. The notation and results from probability theory that are needed were reviewed in Section 2.
Let V = (C[a, b], · ∞ ) and for an f ∈ V , let I : V → R be defined as I(f ) = b a f . Let (W, · ∞ ′ ) denote the space all of bounded random variables defined on a probability space (Ω, Σ, P ), where X ∞ ′ = ess. sup ω∈Ω |X(ω)|. Let M n : V → W be a sequence of maps, not necessarily bounded linear. For a specific Monte Carlo integration method see Example 4.9 below. In that example the discrete operators M n are bounded linear. We have chosen to state and prove the equivalence theorem for Monte Carlo integration (Theorem 4.8) without this assumption. This is done to illustrate how the nonlinear case proof of an equivalence theorem works in a probabilistic setting such as this.
We can look upon I as a map from V to W by defining I(f ) to be the constant random variable, i.e., I(f ) : Ω → R is defined as I(f )(ω) = I(f ) for all ω ∈ Ω. It is consistent if there is a dense subspace V 0 of V such that for any f ∈ V 0 , it is convergent. It is said to be stable at f 0 ∈ V if for any ǫ > 0 there exists a δ > 0 such that for each f ∈ V with f − f 0 ∞ ≤ δ, there exists n 0 ∈ N such that for all n ≥ n 0 , It stable if it is stable at every f 0 ∈ V . Now we state and prove an equivalence theorem for which the proof is similar to Theorem 3.5, but with a probabilistic flavor. Proof. Suppose it is convergent. To show stability, we need to find an n 0 ∈ N and δ > 0 such that for a given f ∈ V with f − f 0 ∞ ≤ δ, and for all n ≥ n 0 , we have P [ω : |M n (f )(ω) − M n (f 0 )(ω)| ≤ ǫ] = 1. Outside a set of P -measure 0 in Ω and for all n ∈ N, we have the following inequality By convergence, there are n 1 and n 2 such that for all n ≥ n 1 , and for all n ≥ n 2 , Since I(f )(ω) = I(f ) for all ω ∈ Ω and by the boundedness of the integral operator, for an appropriately chosen δ > 0, we have |I It is easy to see that Ω 2 = Ω. Let Ω ′ = 3 i=1 Ω i . Let n 0 = max(n 1 , n 2 ). For all n ≥ n 0 , P (Ω i ) = 1 for 1 ≤ i ≤ 3. Since P is countably additive, measure of a countable union of sets of measure zero is zero. Therefore P (Ω ′ ) = 1. Thus for all ω ∈ Ω ′ , except for set of P -measure zero we have |M n (f )(ω) − M n (f 0 )(ω)| ≤ ǫ for all n ≥ n 0 . Hence P [ω : |M n (f )(ω) − M n (f 0 )(ω)| ≤ ǫ] = 1 for all n ≥ n 0 . Since f 0 was arbitrary the Monte Carlo integration is stable if it is convergent.
Conversely, suppose we assume stability and consistency. Therefore, given f 0 and ǫ > 0, there exists δ > 0, such that for each f ∈ V with f − f 0 ∞ ≤ δ, there exists an n 0 ∈ N such that for all n ≥ n 0 , By the density of V 0 in V , we can choose g ∈ V 0 such that g − f 0 ∞ ≤ δ. By the boundedness of I, for an appropriately chosen δ, we have |I(g) − I(f 0 )| ≤ ǫ/3. Again, outside a set of P -measure 0 in Ω and for all n ∈ N, we have the following inequality Stability at f 0 means that there exists δ > 0 such that for each g ∈ V 0 with g − f 0 ∞ ≤ δ there exists n 1 ∈ N with for all n ≥ n 1 . By consistency, there is an n 2 such that for all n ≥ n 2 , . By an identical argument as in the previous half of the proof, on a subset Ω ′ of Ω with P -measure one, we have for all n ≥ n 0 = max(n 1 , n 2 ). Hence we have convergence at f 0 . Since f 0 was arbitrary we have that stability implies convergence.
As an example of numerical integration using Monte Carlo methods we will examine the Sample-Mean Monte Carlo method and discuss its convergence and stability. We prove both convergence and stability separately. An alternative would have been to prove consistency and one of the other two properties and infer the third from Theorem 4.8.
Then there exists some random variable X with range in [a, b], such that g(x) is the pdf of X [18]. Then, consider the random variable Y = f (X)/g(X). Therefore, Now, choose a sequence of independent and identically distributed random variables X = X 1 ,X 2 , . . .,X n , . . . Since f, g are continuous, they are Borel measurable. Since g = 0, f /g is Borel measurable. Hence the sequence of random variables Y = f (X)/g(X) = f (X 1 )/g(X 1 ) = Y 1 , Y 2 = f (X 2 )/g(X 2 ), . . . , Y n = f (X n )/g(X n ), . . . are independently and identically distributed by Theorem 2.7. Hence for the chosen pdf g, we can define M n : V → W as By Theorem 2.6, Thus we have the convergence of M n . Since M n is linear in f , we can check for the boundedness of this linear operator To get the estimate on the norm of M n we have used the fact that h(X) ∞ ′ ≤ h ∞ , where h = f /g. This is true because h(X) ∞ ′ = ess. sup ω∈Ω |h(X(ω))| = inf{M : P [ω ∈ Ω : |h(X(ω))| ≥ M ] = 0} , and hence the bound on h(X) is controlled by the bound on h.
The bound on M n is independent of n and depends only on g. To exhibit stability we have to show that given ǫ > 0 there exists δ > 0, n 0 ∈ N such that for all n ≥ n 0 But outside a set of P -measure zero and for all n ∈ N, we have Therefore, for an appropriately chosen δ > 0 and for all n ∈ N, we have The random variables X n are not necessarily unique for a given g. However, it does not matter as the Sample Mean Monte Carlo method is stable and convergent if we choose a positive pdf g ∈ C[a, b].

Numerical Differentiation
If sufficiently differentiable functions are considered and a sum of sup norms on the function and its derivatives is used as the norm then smooth differentiation is bounded linear. Numerical differentiation can be posed as a parameterized collection of linear operators. If they are assumed to be bounded as well then the definitions and equivalence theorem from Section 3 apply here. We show in this section, and it is no surprise, that the equivalence theorem is actually not needed for proving convergence or stability for the usual finite difference formulas for the first derivative such as forward, backward and central difference formulas. We also give the example of the lowest order, 3 points finite difference formula for second derivative, for which equivalence theorem is also not required. For these and similar simple formulas, the proofs of stability and convergence can be done directly and independently of each other and are easy.
Thus there is no practical benefit of an equivalence theorem in the context of such simple finite difference formulas for numerical differentiation in one dimension. However the equivalence theorem might be of benefit in proving stability or convergence for formulas of high order accuracy for arbitrary derivatives on non equally spaced grids such as the finite difference formulas in [8,9]. The mesh size parameter h appears as h k in the denominator of these and similar formulas and stability proofs might be tedious. Here k is the order of the derivative. We do not discuss these formulas further in this paper. For h and D (k) are the discrete and smooth differentiation operators respectively. Here h ∈ (0, 1), is a parameter of the discrete operators and is a measure of how far apart the points used in, say, a finite difference formula are. In the chosen norms, D (k) is a bounded linear operator. In addition, assume also that D   Example 5.3 (Forward Difference). As an example we now consider the basic forward difference approximation to the first derivative which we will show to be stable and convergent. The equivalence theorem is not required in this case although using it would reduce the work required in proving stability and convergence. It is easy enough to prove convergence and stability separately in an elementary way. Consider a point x ∈ [a, b − h]. Let h ∈ (0, 1) such that x + h < b. We will show that the forward difference approximation to the first derivative is both convergent and stable. First note that for some 0 < θ < 1. Thus D (1) h is stable. Moreover, by Mean Value Theorem we have which means that D (1) h converges to D (1) . The convergence and stability of the other commonly used finite difference schemes like backward difference and central difference schemes can be similarly proved.
The stability proved above means that a slight perturbation of f ∈ V 1 does not drastically change the computed numerical derivative. Note however that if the C 1 norm is replaced by the sup norm, i.e., if the space V 1 is replaced by (C 1 [a, b], · ∞ ), then the finite difference schemes above are highly sensitive to small perturbations, leading to instability. This can be seen in the following example.
Example 5.4 (Unboundedness in sup Norm). Define a sequence g h (x) = sin(2πx/h) in C 1 [0, 1], · ∞ . Note that g h ∞ = 1. However, for some c ∈ (0, 1 − h) and so This implies that D (1) h ∞ > 1/h for all h ∈ (0, 1). Example 5.5 (Second Derivative). We now discuss the convergence and stability of the most basic finite difference operator for second derivative. We will show that the finite difference approximation for second derivative is both convergent and stable. The operators D (2) h are consistent and so it is actually enough to prove just stability or convergence due to Theorem 5.2. But as in the first derivative case, we will prove stability and convergence separately, since both are easy to prove. To prove stability, note that By two applications of the Mean Value Theorem, we have that for some 0 < α, β < 1, the above is equal to Hence the D h is stable. Moreover, once again by the Mean Value Theorem, for some 0 < α, β, γ < 1 we have which means convergence. Again, if the C 2 norm is replaced by the C 1 norm or the sup norm, the operator D h fails to be stable. Examples similar to Example 5.4 above can be constructed to exhibit the unboundedness of the operator D (2) h .

Polynomial Interpolation
The interpolation problem is to find a function that takes on prescribed values at specified points. In one dimension the data is given as (x i , y i ) for i = 0, . . . , n, with x 0 < x 1 < · · · < x n , and we look for a function f : R → R called interpolating function such that f (x i ) = y i for all i. In order to define the notions of consistency, convergence and stability it is convenient to pose the interpolation problem as interpolation of continuous functions. For any given data which is to be interpolated, there is the obvious unique piecewise linear continuous function that interpolates the data. Stability with respect to changes in the given values or the locations of the values are both captured by stability with respect to changes in the piecewise linear continuous function. We will only address interpolation of continuous functions by polynomials. It is easy to show the existence and uniqueness of the interpolant polynomial in the case of one dimensional interpolation, i.e., when the dimension of the domain of the function is one [11,20].
Let {p n } be a sequence of polynomials of degree at most n, interpolating a function f in V = (C[a, b], · ∞ ) on a set of interpolation points x We can define polynomial interpolation as a map P n : V → P n ⊂ V , where P n is the space of polynomials of degree at most n and P n f is defined as the unique polynomial p ∈ P n which interpolates f at the given nodes. A basic fact about error in polynomial interpolation is given by the following lemma.
, and let a ≤ x 0 < x 1 < · · · < x n ≤ b be a partition of [a, b]. Then for all x ∈ (a, b), there exists ξ ∈ (min{x 0 , x}, max{x n , x}) such that Proof. The proof requires repeated use of Rolle's Theorem. See page 119 of [2] for details.
The following Lemma 6.2 shows that the P n operators are linear, and Lemma 6.3 shows that they are bounded. The corresponding smooth operator is the identity map which is bounded linear. Thus the linear case definitions of consistency, convergence and stability given in Definition 3.1 apply here as well.
Lemma 6.2 (Linearity). The interpolation operator P n : V → P n ⊂ V is linear.
Proof. Let P n (f ) = p 1 and P n (g) = p 2 , where f, g ∈ V and p 1 , p 2 are the unique polynomials in P n such that f (x i ) = p 1 (x i ) and g(x i ) = p 2 (x i ) for 0 ≤ i ≤ n. Hence (f + g)(x i ) = (p 1 + p 2 )(x i ). By uniqueness of polynomial interpolation P n (f + g) = p 1 + p 2 . Hence P n (f + g) = P n f + P n g. Similarly using uniqueness we can show that P n (cf ) = cP n (f ), for any c ∈ R. Lemma 6.3 (Boundedness). Each interpolation operator P n is bounded, i.e., Proof. By Lemma 6.1, P n (f ) = f , where f is any polynomial of degree ≤ n. Hence P n maps onto P n . Let f m be a sequence in P −1 n (0) converging to f in V . Since f m (x i ) = 0 for all 0 ≤ i ≤ n and lim m→∞ f m (x) = f (x) for all x ∈ [a, b], we have f (x i ) = 0 for all 0 ≤ i ≤ n. Therefore f ∈ P −1 n (0). Hence the kernel of P n is closed. Therefore, by Lemma 2.2, P n is continuous and hence bounded. Definition 6.4. Interpolation is convergent if for any given f ∈ V the sequence of interpolant polynomials P n f converges to f in V . It is consistent if there is a dense subspace V 0 of V such that for any f in V 0 , the sequence of interpolant polynomials P n f converges to f in V . Interpolation is said to be stable if sup n P n < ∞.
If the function being interpolated is a polynomial then the interpolant is exact. This follows from Lemma 6.1. Since polynomials are dense in V (Weierstrass Approximation Theorem) this implies that interpolation of continuous functions by polynomials is consistent.
We now prove an equivalence theorem for polynomial interpolation. In the notation of Theorem 3.3 the discrete operators T n of the theorem correspond to the polynomial interpolation operator P n and the smooth operator T corresponds to the identity operator. Proof. The proof is identical to the one given for the general linear equivalence theorem (Theorem 3.3) with discretization parameter h replaced by n. Thus the proof of the equivalence theorem for quadrature (Theorem 4.3) can be used here with appropriate modifications. Example 6.6 (Runge's Function). It is well known that for the Runge's function f (x) = 1/(1 + 25x 2 ) in the interval [−1, 1] the polynomial interpolants do not converge if the interpolation points are uniformly spaced. See for example [12]. As we noted earlier, interpolation of continuous functions by polynomials is consistent. However, the method is not stable if equispaced points are used for interpolation. In light of the equivalence theorem above (Theorem 6.5) this agrees with the lack of convergence. To see the lack of stability, let p(x) be any polynomial which is arbitrarily close to the Runge's function. Existence of p(x) is guaranteed by the Weierstrass approximation Theorem. Now, the interpolating polynomials for p(x) are exact as we increase the number of interpolating points. However, the interpolating polynomial for the Runge's function is not close to p(x). This shows that polynomial interpolation of continuous functions using equispaced points is not discretely well-posedness, i.e., it is not stable.
Interpolating real valued functions whose domain has dimension greater than one is a much harder problem, unlike the one dimensional case where polynomial interpolant always exists and is unique. For example, in 2 variable interpolation, if data is specified at 3 points that are collinear, then there are infinitely many linear interpolants. The geometry of the point locations becomes an important factor in existence and uniqueness of the interpolant. For a result of this type in the 2 variable case see, for example, [14]. We need the existence and uniqueness of interpolant so that there is a well defined operator P n .
There does exist a generalization, called Ciarlet's error formula [5,4,10], of Lemma 6.1 to the multivariable case. Moreover, multivariate polynomials are dense in the sup norm, in the space of multivariate continuous functions on compact subsets of R n (Stone-Weierstrass Theorem) [7]. Thus when multivariate polynomial interpolation does exist and is unique, we get consistency as before. Consistency, stability and convergence can be defined as described in the univariate case and thus an equivalence theorem exists for the multivariate polynomial interpolation of continuous functions. Of course the conditions for stability and convergence are more complicated in the multivariate case and we do not address those here.
In contrast with interpolation, approximation methods do not require agreement with data at specific points. For example one might seek a polynomial p such that min p∈Pn f − p ∞ is attained. In this particular case one can show existence and uniqueness. See for instance Theorem 7.5.6 in [7]. One can define the notion of convergence, consistency and stability for approximation problems in an identical fashion as for interpolation and prove a theorem like Theorem 6.5. In the particular case considered above, the approximation always converges (Theorem 7.6.1 of [7]) and hence is stable.

Conclusions and Future Work
We have shown that equivalence theorems can be proved in a general setting in numerical analysis. As in the classical Lax-Richtmyer equivalence theorem in PDEs, these theorems state that a consistent method is convergent if and only if it is stable. The notion of stability we used was that of discrete well posedness and we defined consistency to be convergence on a dense subspace. The discretizations of the smooth problems were considered to be linear or nonlinear operators on normed linear spaces and depending on some parameter which measures the discretization size. We showed that our general equivalence theorems require basic tools like uniform boundedness principle, triangle inequality, and density arguments. Convergence implying stability was always obtained independent of consistency.
In this paper, we have studied stability with respect to perturbation of input data of the discrete operators. However, one could also study stability with respect to locations of points, shape of domain etc. One can also investigate equivalence theorems in other numerical analysis contexts. Some examples are, multidimensional quadrature rules, multidimensional Monte Carlo integration, optimization, eigenvalue problems in PDEs, formulas for numerical differentiation of any order and accuracy, such as those given in [9].
We defined consistency as convergence on a dense subspace. In our examples, many times the dense subspace was polynomials in continuous functions. It may be worthwhile to study if and how the choice of particular dense subspace affects the theory and applications of equivalence theorems.