The Big Picture on Numerical Schemes

What is the goal in the design of good numerical schemes? Solving problems EXACTLY is sometimes not possible and/or not even sensible (e.g. a chaotic system). What you want to do is to produce a numerical approximation which will have the property that the more you push it, the ``better'' the answer gets...i.e. the closer it gets (in some norm) to the solution.

The most important qualities of good numerical schemes are:

• Convergence: you want the answer to approach the true solution as the algorithm or calculation is refined.
• Stability: you want your algorithm or calculation to be robust. That is to say, small changes in the input (or parameters) should not lead to large changes in the output.
• Efficiency: roughly speaking, there are two resources you'll use: time (as measured in compute time) and storage (memory). You want to get an answer with reasonable usage of these two resources.

We will discuss these throughout the year in different contexts. Same with stability, but it is appropriate to mention this detail at this point:

Stability:

let $\varepsilon$= initial error, then, after $n$ steps:

$$\begin{eqnarray*} \vert E_n(\varepsilon )\vert\approx Cn\varepsilon \quad \mbox... ...repsilon \quad k>1\quad \mbox { exponential growth is no good.} \end{eqnarray*}$$

See Figure 11.

Figure 11: linear is ok...if you bump a stable system (perturb it) you expect a linearly proportional response to the bump, but not anything polynomial or exponential.

Most problems dealing with continuous variables (derivatives, integrals, etc) cannot be solved, even in principle, in a finite number of steps.

$\Rightarrow$ recast problem so that approximate problem (i.e. solved in a finite number of steps) is ``close enough'' or within error tolerance

    $\Rightarrow$ In most cases we design a method of solution which is ``convergent'' to the solution. In order to assess whether a method is convergent we need to estimate its error and/or we need to define a sensible quantity which estimates its rate of convergence. Convergence may also depend on how system is prepared.

Moreover, if a method is to be useful it should solve the problem efficiently, i.e. in the least amount of time and it must be reasonable with respect to computer resources.

Example Solving a very large $Ax=b\,$ can be

solved by $\left\{\begin{array}{ll} \mbox {direct methods}\\ \mbox {iterative methods. ... ...ble cost in either}\\ \mbox {time or computer resources.} \end{array}\right.$

General Strategy

Replace problem with an approximate one with one with closely related solutions.

For example, replace integrals with finite sums,
replace derivatives with finite differences,
replace matrices $\rightarrow$ matrices with simpler forms
Complicated functions with sequences of polynomials
Differential equations with difference algebraic equations
Nonlinear problems with linearized approximations
High-order differential equations with low order difference equations
Infinite-dimensional spaces with finite-dimensional spaces.

All this while preserving the solution in some sense. What should be preserved? It depends on the problem, as we shall learn.

Sources of Approximations in Scientific Computation

Before Computing:

Modeling (PDE & reality)
Empirical Measurement (Lab data): finite precision, small sample size, random noise, etc.
Approximate prep of model.

At the computing stage

Error Analysis $\left\{\begin{array}{l} \mbox {Approximation: complicated process by simpler p... ...ation of real numbers}\\ \mbox {and arithmetic operators.} \end{array}\right.$

$\star$ THE AIM IN NUMERICAL ANALYSIS COMPUTE EXACTLY. BUT TO BE EXACT ABOUT THE ERROR SOURCES TO MAKE THEIR SIZE AS SMALL AS POSSIBLE. ALTHOUGH WHILE DOING IT WITH REASONABLE EXPENSE.

Example input data errors and approximate computation:

$$\begin{eqnarray*} &&f: R\to R, \mbox {the process } f.\\ &&\mbox {let}x\in R\... ...f\quad \mbox {approximation of process} f. Then, the TOTAL ERROR \end{eqnarray*}$$

Total error $\begin{array}{l} = \widehat f(\hat x)-f(x)\\ = \underbrace{[\widehat f(\wide... ... error}}+\underbrace{[f(\hat x) -f(x)]}_{\mbox {propagated error.}} \end{array}$

Remark: Choice of $\hat f$ representation has no effect on Truncation Error and Rounding Error