Ill-conditioning and instability

Two more concepts that are related to well-posedness need to be clearly stated when we move from the continuous setting to the discrete (numerical) setting. The first we would like to discuss is “ill-conditioning”. The “condition” of a problem is a property of the mathematical problem (not of the numerical scheme used to solve it) and can be stated intuitively as follows:

Definition 1.11 (Ill-conditioning). A mathematical problem is said to be ill-conditioned if small per-turbations on the data cause large variations of the solution.

The definition is problem specific, but a simple example related to linear algebra can be illuminating.

Example 1.12. Consider the following 2× 2 system of linear equations:

3x + 2y = 2 (1.21)

2x + 6y = −8. (1.22)

-7 -5 -3 -1 1 3 5

FIGURE 1.4: Geometric interpretation of a “well-conditioned” (left) and an “ill-conditioned” linear system (right).

The mathematical problem can be stated as follows:

Problem 1.13. find the pair of real values (x, y) such that examples 1.12 and 1.12 are satisfied simul-taneously.

The solution to this problem is evidently P = (x, y) = (2,−2). We can rewrite the linear system as:

y = −3

2x + 1 (1.23)

y = −1 3x− 4

3. (1.24)

This reformulation, allows to change the problem into an equivalent formulation:

Problem 1.14. find the point P = (x, y) ∈ R² that represents the intersection between the two lines identified by examples 1.12 and 1.12 (see fig. 1.4).

Now we want to analyze the conditioning of this problem. To do this we specify a small perturbation to the data of our problem and look at how its solution changes. In our case we can, for example, change the right hand side of the second equation by a quantity δ, yielding a downward translation of the line (fig. 1.4, left). The point of intersection between the two lines has now moved by a quantity

 ≈ δ. This problem is well-condition and the ratio /δ measures somehow the conditioning of our problem.

Now, if the two lines have almost equal slopes, the situation is different (fig. 1.4, right). A small perturbation δ to one if the right hand side values yield a large movement of the solution (the point of

intersection), by a quantity   δ. The conditioning is measured again by the quantity /δ which is now much larger than one. The problem is thus “ill-conditioned”.

We note that both problems are actually “well-posed” as they admit a unique solution which is con-tinuously dependent upon the data. But the numerical solution may loose accuracy.

The second concept is called stability. Unlike conditioning, stability is a property of the numerical scheme used to solve a mathematical problem.

Definition 1.15 (Stability). A numerical scheme is stable if errors in initial data remain bounded as the algorithm progresses.

As an example, consider the following numerical algorithm given by the linear recursion:

u^(k)= Au^(k−1), k = 1, 2, . . .

where u^(k) ∈ Rⁿ, A is a constant n× n matrix, and the recursion is initiated with a given (possibly arbitrary) initial guess u⁽⁰⁾. The representation u⁽⁰⁾_h of the values of u⁽⁰⁾ in the computer is not exact, so the actual algorithm involves the numerical approximation u^(k)_h :

u^(k)_h = Au^(k−1)_h , k = 1, 2, . . . (1.25)

Stability of the algorithm requires that the errors with which we represent u⁽⁰⁾_h are not magnified by the algorithm process. More formally, we define the error as e^(k) = u^(k)− u^(k)h , k = 1, 2, . . .. From this last equation we have that u^(k) = u^(k)_h + e^(k), and after substitution in eq. (1.25) we obtain the error propagation equation:

e^(k) = Ae^(k−1).

Stability of the scheme is achieved if the norm of the error remains bounded as k increases, i.e. (using compatible norms):

e^(k) ≤

Ae^(k−1)

≤ kAk

e^(k−1)

≤ kAk^k e⁽⁰⁾

which implieskAk ≤ 1.

Finally we would like to mention the following famous and completely general result known as the Lax-Richtmeyer equivalence theorem:

Theorem 1.1 (Lax-Richtmeyer equivalence theorem). A consistent numerical scheme for the solution of a well posed problem is convergent if and only it is stable.

2 Hyperbolic Equations

An intuitve, although empirical, definition of a hyperbolic equation is as follows. Given x ∈ R^d, the PDE

F (x, u,∇ u) = 0

is hyperbolic at the point x if it is possible to transform it into an Ordinary Differential Equa-tion (ODE) with respect to one of the d variables (say x_d) as a function of the remaining ones x₁, x₂, . . . , x_d−1.

2.1 Some examples

Notice that in the above statement one of the components of the vector x is take as time (we will do this often in the sequel). Thus, for example, we can set t := x1 and x := x2, and consider the simple one-dimensional equation:

u_t+ u_x = 0.

This equation can be transformed into an ODE if we write it along the lines (called “characteristics”):

ξ = x− t.

To see this, we make a simple change of variable x = ξ + t, so that we can write u(x, t) = u(x(t), t) as:

u(x, t) = u(ξ + t, t); x = ξ + t; dx

dt = 1; dx dξ = 1, so that:

d

dtu(ξ + t, t) = ∂u

∂x dx dt + ∂u

∂t = u_t+ u_x= 0.

From this we see that our original equation is an ODE with respect to time t as a function of space, x (i.e. along the characteristic lines of equation x = ξ + t). Thus, we are mainly interested in looking at solutions of a Cauchy problem, although we will be looking at the effects of boundary conditions as well. However, it is intuitive to think that any auxiliary condition on the boundary can be transformed into an auxiliary condition at t = 0, and vice-versa. Another picture for this statement can be envisioned by stating that we can revert the sign of the time variable, and go backwards in time, i.e., we can find the solution at an earlier time given the solution at a later time. We will see that indeed this is the case, contrary to e.g. a parabolic PDE. In other words, a hyperbolic equation governs a reversible phenomenon, while a parabolic equation governs a irreversible (or dissipative) phenomenon.

t

x

−x λ

ξ

x− λt = ξ

y

x^∗ x t = 0

x^∗+ λt1

t = t1

FIGURE 2.1: Characteristic line for equation (2.1) in the (x, t) plane (left). Graph of the solution u(x, t) at t = 0 and t = t₁ in the (u, x) plane. A wave of form f (x) (here f (x) = e^−a(x−b)2) propagates to the right with speedλ without changing shape.

To study the behavior of a hyperbolic equation, we need to study the geometry of the solution function in the space of its dependent variables, i.e., z = u(t, x), which represents a surface in R^d+1, if x∈ R^d. This will help us acquiring an understanding of the type of solutions we may expect from a hyperbolic partial differential equation. This is what we are trying to do in the next few sections We start this task with some simple examples.