Discretization

 

Discretization[edit]

Furthermore, continuous problems must sometimes be replaced by a discrete problem whose solution is known to approximate that of the continuous problem; this process is called 'discretization'. For example, the solution of a differential equation is a function. This function must be represented by a finite amount of data, for instance by its value at a finite number of points at its domain, even though this domain is a continuum.

Generation and propagation of errors[edit]

The study of errors forms an important part of numerical analysis. There are several ways in which error can be introduced in the solution of the problem.

Round-off[edit]

Round-off errors arise because it is impossible to represent all real numbers exactly on a machine with finite memory (which is what all practical digital computers are).

Truncation and discretization error[edit]

Truncation errors are committed when an iterative method is terminated or a mathematical procedure is approximated and the approximate solution differs from the exact solution. Similarly, discretization induces a discretization error because the solution of the discrete problem does not coincide with the solution of the continuous problem. In the example above to compute the solution of ${\displaystyle 3{�}^3+4=28}$, after ten iterations, the calculated root is roughly 1.99. Therefore, the truncation error is roughly 0.01.

Once an error is generated, it propagates through the calculation. For example, the operation + on a computer is inexact. A calculation of the type ${\displaystyle �+�+�+�+�}$ is even more inexact.

A truncation error is created when a mathematical procedure is approximated. To integrate a function exactly, an infinite sum of regions must be found, but numerically only a finite sum of regions can be found, and hence the approximation of the exact solution. Similarly, to differentiate a function, the differential element approaches zero, but numerically only a nonzero value of the differential element can be chosen.

Numerical stability and well-posed problems[edit]

Numerical stability is a notion in numerical analysis. An algorithm is called 'numerically stable' if an error, whatever its cause, does not grow to be much larger during the calculation.^[13] This happens if the problem is 'well-conditioned', meaning that the solution changes by only a small amount if the problem data are changed by a small amount.^[13] To the contrary, if a problem is 'ill-conditioned', then any small error in the data will grow to be a large error.^[13]

Both the original problem and the algorithm used to solve that problem can be 'well-conditioned' or 'ill-conditioned', and any combination is possible.

So an algorithm that solves a well-conditioned problem may be either numerically stable or numerically unstable. An art of numerical analysis is to find a stable algorithm for solving a well-posed mathematical problem. For instance, computing the square root of 2 (which is roughly 1.41421) is a well-posed problem. Many algorithms solve this problem by starting with an initial approximation x₀ to ${\displaystyle \sqrt{2}}$, for instance x₀ = 1.4, and then computing improved guesses x₁, x₂, etc. One such method is the famous Babylonian method, which is given by x_k+1 = x_k/2 + 1/x_k. Another method, called 'method X', is given by x_k+1 = (x_k² − 2)² + x_k.^{[note 1]} A few iterations of each scheme are calculated in table form below, with initial guesses x₀ = 1.4 and x₀ = 1.42.

Babylonian	Babylonian	Method X	Method X
x0 = 1.4	x0 = 1.42	x0 = 1.4	x0 = 1.42
x1 = 1.4142857...	x1 = 1.41422535...	x1 = 1.4016	x1 = 1.42026896
x2 = 1.414213564...	x2 = 1.41421356242...	x2 = 1.4028614...	x2 = 1.42056...
		...	...
		x1000000 = 1.41421...	x27 = 7280.2284...

Observe that the Babylonian method converges quickly regardless of the initial guess, whereas Method X converges extremely slowly with initial guess x₀ = 1.4 and diverges for initial guess x₀ = 1.42. Hence, the Babylonian method is numerically stable, while Method X is numerically unstable.

Numerical stability is affected by the number of the significant digits the machine keeps. If a machine is used that keeps only the four most significant decimal digits, a good example on loss of significance can be given by the two equivalent functions

${\displaystyle �(�)=�\left(\sqrt{�+1}-\sqrt{�}\right)}$ and ${\displaystyle �(�)=\frac{�}{\sqrt{�+1}+\sqrt{�}}.}$

Comparing the results of

${\displaystyle �(500)=500\left(\sqrt{501}-\sqrt{500}\right)=500\left(22.38-22.36\right)=500(0.02)=10}$

and

by comparing the two results above, it is clear that loss of significance (caused here by catastrophic cancellation from subtracting approximations to the nearby numbers ${\displaystyle \sqrt{501}}$ and ${\displaystyle \sqrt{500}}$, despite the subtraction being computed exactly) has a huge effect on the results, even though both functions are equivalent, as shown below

The desired value, computed using infinite precision, is 11.174755...

• The example is a modification of one taken from Mathew; Numerical methods using MATLAB, 3rd ed.