📂Algorithm

Stability in Numerical Algorithms

Definition ¹

Relative Error and Closeness

1. Suppose an algorithm operating in a given floating-point system takes data $a$ as input and outputs a computed solution $\bar{w}$. Then, with respect to the exact solution $w$, the quantity $\left| w - \bar{w} \right| / \left| w \right|$ is called the relative error.
2. With respect to the machine epsilon $\epsilon$, if the relative error is less than or equal to $c \epsilon$, the product of $\epsilon$ and a not-too-large constant $c$ as shown below, then $\bar{w}$ is said to be close to $w$.
   $$ {\frac{ \left| w - \bar{w} \right| }{ \left| w \right| }} \le c \epsilon $$

Forward Stability

3. If the computed solution is close to the exact solution, the algorithm is said to be forward stable.

Backward Stability

4. If the computed solution $\bar{w}$ of data $a$ is the exact solution for some $\tilde{a}$ that is close to $a$, the algorithm is said to be backward stable.

Backward Stability in Numerical Matrix Algebra

5. Let $\mathcal{A}$ be a class of some matrices. A numerical algorithm for solving the linear system $A \mathbf{x} = \mathbf{b}$ for each $A \in \mathcal{A}$ and vector $\mathbf{b}$ is said to be backward stable if, when $\bar{A} \in \mathcal{A}$ and $\bar{\mathbf{b}}$ are close to $A \in \mathcal{A}$ and $\mathbf{b}$, the computed solution $\bar{\mathbf{x}}$ of $A \mathbf{x} = \mathbf{b}$ satisfies $\bar{A} \bar{\mathbf{x}} = \bar{\mathbf{b}}$.

Explanation

The so-called $\tilde{a}$ is said to be slightly perturbed, and saying that an algorithm is backward stable means that a solution can be obtained stably even when there is a slight change in the data. If this explanation is a bit difficult, it is better to understand it via backward stability in numerical matrix algebra: although $\bar{\mathbf{x}}$ was computed from $A$ and $\mathbf{b}$, it becomes the exact solution of $\bar{A} \bar{\mathbf{x}} = \bar{\mathbf{b}}$. Here, the expression backward means that we do not merely consider whether the solution is similar, but also whether it properly functions as the solution of the original problem when we go back.

The difference between general backward stability and backward stability in numerical linear algebra is that we consider a class of matrices such as $A \in \mathcal{A}$. Although it sounds difficult, it suffices to understand it as meaning that the conditions on whether the numerical matrix-algebraic algorithm is for invertible matrices or for positive definite matrices, etc., must be consistently maintained. If no restriction on the class is imposed, one could violate the very conditions the algorithm requires in the first place and then insist that it is not backward stable.