Return to computing page for the first course APMA0330
Return to computing page for the second course APMA0340
Return to computing page for the fourth course APMA0360
Return to Mathematica tutorial for the first course APMA0330
Return to Mathematica tutorial for the second course APMA0340
Return to Mathematica tutorial for the fourth course APMA0360
Return to the main page for the first course APMA0330
Return to the main page for the second course APMA0340
Return to the main page for the fourth course APMA0360
Return to Part II of the course APMA0360
Introduction to Linear Algebra with Mathematica

Glossary

Preface

Definition of well-posed problem was first proposed in 1902 by the French mathematician Jacques Hadamard (1865--1963) in the framework on partial differential equations. Problems that are not well-posed in the sense of Hadamard are termed ill-posed. The main motivation for their study were inverse problems that are often ill-posed, including the derivative operator, inverse Laplace and Fourier transforms, convolution, and many others.

It was already understood in early work that in order to have any chance of computing meaningful solutions of ill-posed problems, they need to be approximated by well-posed ones, usually by a family parametrized with the regularization parameter. This approach was first developed by the famous Russian mathematician Andrey Nikolayevich Tikhonov (1906--1993) who seems to be the first to introduce the regularization method term in the literature. The methods of the regularization parameter choice in dependence on the noise level were further developed in the Russian mathematical community by formulating in the 1960s its concepts in a much more general way. Although it is now common to identify the regularization approach for solving ill-posed problems with the pioneering work of Tikhonov, the first practical regularization was proposed by the French mathematician Augustin-Louis Cauchy (1789--1857) who introduced principal value method for assigning values to certain improper sums and integrals that would otherwise be undefined.

Introduction

Imagine you have a bow and arrow, and you are given instructions to shoot the arrow with the intial velocity, v0, and with the intial angle, α, at position, (x0, y0). There is no air resistance present.

You are asked to solve the problem of finding out where the arrow would land before verifying it by shooting the arrow. Since there only exists one unique solution to this problem we can solve it by laws of mechanics. A small change in the angle or velocity yields a small change to the arrows landing. These types of problems are referred to as direct problems and are commonly known to be well-posed.

Now, consider the following problem. The only information you know is the initial velocity v0 and the angle α the arrow had. You are now asked to find out at what point, (x0, y0), the arrow was shot from by just studying the arrow’s orientation and placement on the field. Since there exists multiple ways this arrow could have gotten to this position, the initial point is nearly impossible to find out. This problem is called an inverse problem and happens to be ill-posed because no unique solution exists to this problem.

Now we shall mathematically define every important term that was used. According to Hadamard, the mathmatical definition of a well-posed problem is given by the following.

Hadamard’s definition of well-posedness occurs if and only if a problem has the following characteristics:
  1. For all admissible data, a solution exists.
  2. For all admissible data, the solution is unique.
  3. The solution depend continuously on the data.

To understand this definition, we must further examine the well-posedness characteristics. Suppose a linear operator T is given in the form

\[ T x = y , \]
where T : X → Y is a bounded linear operator between the normed vector spaces X and Y. The first condition is met if all y ∈ Y are also in R(T), the range of the operator T. The second condition is met if and only if the null space N(T) = {0}. In other words we need to provide sufficient evidence that the solution is unique. Suppose that x₁ − x₂ = 0. By applying operator T, we get Tx₁ − Tx₂ = 0 and through linearity we obtain
\[ T \left( x_1 - x_2 \right) = 0 \qquad \iff \qquad x_1 - x_2 = 0. \]
Thus the solution is unique if N(T) = {0}. If the linear operator T satisfies the first two conditions of Hadamard’s definition, then the inverse operator T−1 exists.

Let X and Y be normed vector spaces and T : D(T) −→ Y a linear operator, where D(T) ⊊ X is the domain of T (the set of all x for which T(x is finite). The operator T is said to be bounded if there is a real number c such that for all x ∈ D(T
\[ \| T\, x \| \le c\,\| x \| . \]

Well-posed Problems

Let us consider the initial value problem for an n-th order linear differential equation.
\[ \begin{split} \left( \texttt{D}^n + p_{n-1}(x)\, \texttt{D}^{n-1} + \cdots + p_{1}(x)\, \texttt{D} + p_0 (x)\, \texttt{I} \right) y = f(x), \qquad \texttt{D} = \frac{\text d}{{\text d}x} , \\ y(x_0 ) = v_0 , \quad y' (x_0 ) = v_1 , \quad \ldots \quad y^{(n-1)} (x_0 ) = v_{n-1} . \end{split} \]
Since the general solution to the differential equation is a linear combination of the n homogeneous solutions plus the particular solution
\[ y = y_p + c_1 y_1 + c_2 y_2 + \cdots + c_n y_n , \]
he problem to find the constants ci (i = 1, 2, … ,n) can be written
\[ \begin{bmatrix} y_1 (x_0 ) & y_2 (x_0 ) & \cdots & y_n (x_0 ) \\ y'_1 (x_0 ) & y'_2 (x_0 ) & \cdots & y'_n (x_0 ) \\ \vdots & \vdots & \ddots & \vdots \\ y_1^{(n-1)} (x_0 ) & y_2^{(n-1)} (x_0 ) & \cdots & y_n^{(n-1)} (x_0 ) \end{bmatrix} \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix} + \left( \begin{array}{c} y_p (x_0 ) \\ y'_p (x_0 ) \\ \vdots \\ y_p^{(n-1)} (x_0 ) \end{array} \right) = \begin{pmatrix} v_0 \\ v_1 \\ \vdots \\ v_{n-1} \end{pmatrix} \]
From linear algebra, we know that this system of equations has a unique solution only if the determinant of the matrix is nonzero. Note that the determinant of the matrix is just the Wronskian evaluated at x0. Thus if the Wronskian vanishes at x0, the initial value problem for the differential equation either has no solutions or infinitely many solutions. Such problems are said to be ill-posed. From Abel’s formula for the Wronskian
\[ W(x) = C\,\exp \left\{ -\int p_{n-1} (x)\,{\text d} x \right\} , \]
we see that the only way the Wronskian can vanish is if the value of the integral goes to +∞ or constant multiple C = W(x0) = 0.
Example 1: Consider the initial value problem
\[ y'' - \frac{2}{x}\, y' + \frac{2}{x^2}\, y = 0, \qquad y(0) = y' (0) = 1 . \]
The Wronskian
\[ W(x) = C\,\exp \left\{ \int \frac{2}{x}\,{\text d} x \right\} = C\,x^2 \]
vanishes at x = 0. Thus this problem is not well-posed.

The general solution of the differential equation is

\[ y = c_1 x + c_2 x^2 . \]
We see that the general solution cannot satisfy the initial conditions. If instead we had the initial conditions y(0) = 0, y' (0) = 1, then there would be an infinite number of solutions.

Example 2: Consider the initial value problem
\[ y'' - \frac{2}{x^2}\, y = 0, \qquad y(0) = y' (0) = 1 . \]
The Wronskian is just a constant, which must be zero at the origin. Why? Because the solution y(x) must approach the origin as x² in order to satuisfy the Euler equation that contain the term y(x)/x². Correspondingly, its derivative will vanish as x at the origin. Therefore, the Wronskian is identically zero and this problem is not well-posed.

The general solution,

\[ y = c_1 x^{-1} + c_2 x^2 , \]
cannot satisfy the initial conditions.

Regularization

Recall the “bow and arrow” problem in the previous section. Imagine now that we try to transform this ill-posed problem into a well-posed problem. To do this we must adjust the problem itself. Let’s say we introduce an adjustable constant that makes the impenetrable surface more rough as the constant gets larger. It is still the same problem, only now when the arrow hits the surface it will reveal the direction from whence it came. By doing so the problem has potentially become well-posed.

This type of idea, where an adjustment can make ill-posed problems become well-posed by applying Tikhonov’s regularization to the inverse operator for the inverse problem of Helmholtz equation with certain boundary data.

 

  1. Benning, M. and Burger, M., Modern regularization methods for inverse problems, Acta Numerica, 2018, >Volume 27, pp. 1--111.