Proof That the Condition Number in Numerical Matrix Algebra Is Proportional to the Upper Bound of Relative Error
Definition 1
For a given matrix $A \in \mathbb{R}^{m \times n}$, the condition number $\kappa (A)$ is defined as follows. $$ \kappa(A) = \left\| A \right\| \left\| A^{\dagger} \right\| = {\frac{ \sigma_{1} }{ \sigma_{r} }} $$ Here, $\left\| \cdot \right\|$ is the Frobenius norm, and $A^{\dagger}$ is the pseudoinverse of $A$. $\sigma_{k}$ is the $k$-th largest singular value of $A$, and $r \le \min (m, n)$ is the rank of $A$. If $\kappa (A)$ is large, $A$ is called an ill-conditioned matrix, and if it is small, a well-conditioned matrix.
Theorem
The upper bound of the relative error of an algorithm that solves the linear system $A \mathbf{x} = \mathbf{b}$ is proportional to the condition number. $$ \frac{\left\| \bar{\mathbf{x}} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \varepsilon c \kappa(A) $$ Here, $\varepsilon > 0$ is a sufficiently small constant; more specifically, it may be regarded as the machine epsilon $\epsilon$. $c = c(A, \mathbf{b})$ is determined by $A$ and $\mathbf{b}$.
Explanation
At first glance, the general condition number and the condition number in numerical matrix algebra appear to have completely different definitions. Why the condition number for a matrix is defined that way can only be understood by examining the following proof.
Proof 2
$$ A \mathbf{x} = \mathbf{b} $$ Suppose there is an algorithm that solves a linear system as above for $A \in \mathbb{R}^{m \times n}$ and $\mathbf{b} \in \mathbb{R}^{m}$. Unless $m = n$ and $A$ is an invertible matrix, the least squares method is used, and one must assume that small perturbations $\varepsilon F$ and $\varepsilon \mathbf{f}$ are applied to $A$ and $\mathbf{b}$ respectively. $$ \left( A + \varepsilon F \right) \mathbf{x} = \mathbf{b} + \varepsilon \mathbf{f} $$ The solution in this case depends on $\varepsilon$, so it can be written as $\mathbf{x} = \mathbf{x}(\varepsilon)$, with $\mathbf{x} (0) = \mathbf{x}$. $\mathbf{x}(\varepsilon)$ is differentiable in a neighborhood of $\varepsilon = 0$, and its Taylor expansion is as follows. $$ \mathbf{x}(\varepsilon) = \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) $$ Here, $\mathbf{x} ' (0)$ can be obtained as the derivative with respect to $\varepsilon$. $$ \begin{align*} \left( A + \varepsilon F \right) \mathbf{x} \left( \varepsilon \right) =& \mathbf{b} + \varepsilon \mathbf{f} \\ \implies A \mathbf{x} ' \left( \varepsilon \right) + F \mathbf{x} \left( \varepsilon \right) + \varepsilon F \mathbf{x} ' \left( \varepsilon \right) =& \mathbf{f} \\ \implies A \mathbf{x} ' \left( 0 \right) + F \mathbf{x} \left( 0 \right) =& \mathbf{f} \\ \implies \mathbf{x} ' \left( 0 \right) =& A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \left( 0 \right) \right] \end{align*} $$ Trying to express this in terms of the relative error, by the triangle inequality of the norm $|a-b| \le |a| + |b|$ we obtain the following inequality. $$ \begin{align*} \mathbf{x}(\varepsilon) =& \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) \\ \implies \mathbf{x}(\varepsilon) - \mathbf{x} =& \varepsilon A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \end{align*} $$
Generalized Cauchy–Schwarz inequality: $$ \left\| \mathbf{x} \right\| \left\| \mathbf{y} \right\| \ge \left< \mathbf{x} , \mathbf{y} \right> $$
By the generalized Cauchy–Schwarz inequality, we obtain the following auxiliary inequality. $$ \begin{align*} \left\| \mathbf{b} \right\| \le& \left\| A \right\| \left\| \mathbf{x} \right\| \\ \implies {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} \le & {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} \end{align*} $$ Therefore, the relative error with respect to $\mathbf{x}$ is as follows. $$ \begin{align*} {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} + \left\| A \right\| {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A \right\| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{b} \right\| }} + {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \end{align*} $$ Here, $\left\| F \right\| / \left\| A \right\|$ and $\left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$ are themselves the relative errors with respect to $A$ and $\mathbf{b}$ respectively, so setting $c = \left\| F \right\| / \left\| A \right\| + \left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$ and, for sufficiently small $\varepsilon$, neglecting $O \left( \varepsilon^2 \right)$, we obtain the desired result.
■