9: Adequacy of Solutions
- Page ID
- 104161
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)After reading this chapter, you should be able to:
- know the difference between ill-conditioned and well-conditioned systems of equations,
- define and find the norm of a matrix
- define and evaluate the condition number of an invertible square matrix
- relate the condition number of a coefficient matrix to the ill or well conditioning of the system of simultaneous linear equations, that is, how much can you trust the solution of the simultaneous linear equations.
What do you mean by ill-conditioned and well-conditioned system of equations?
A system of equations is considered to be well-conditioned if a small change in the coefficient matrix or a small change in the right hand side results in a small change in the solution vector.
A system of equations is considered to be ill-conditioned if a small change in the coefficient matrix or a small change in the right hand side results in a large change in the solution vector.
Is this system of equations well-conditioned?
\[\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}\ \nonumber \]
Solution
The solution to the above set of equations is
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber \]
Make a small change in the right-hand side vector of the equations
\[\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.998 \\ \end{bmatrix}\ \ \nonumber \]
gives
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} - 3.999 \\ 4.000 \\ \end{bmatrix} \nonumber \]
Make a small change in the coefficient matrix of the equations
\[\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 3.998 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}\ \ \nonumber \]
gives
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 3.994 \\ 0.001388 \\ \end{bmatrix} \nonumber \]
This last systems of equation “looks” ill-conditioned because a small change in the coefficient matrix or the right hand side resulted in a large change in the solution vector.
Is this system of equations well-conditioned?
\[\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix}\ \ \nonumber \]
Solution
The solution to the above equations is
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber \]
Make a small change in the right-hand side vector of the equations.
\[\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.001 \\ \end{bmatrix}\ \ \nonumber \]
gives
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 1.999 \\ 1.001 \\ \end{bmatrix} \nonumber \]
Make a small change in the coefficient matrix of the equations.
\[\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 3.001 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix}\ \ \nonumber \]
gives
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2.003 \\ 0.997 \\ \end{bmatrix} \nonumber \]
This system of equation “looks” well-conditioned because small changes in the coefficient matrix or the right-hand side resulted in small changes in the solution vector.
So, what if the system of equations is ill conditioned or well-conditioned?
Well, if a system of equations is ill-conditioned, we cannot trust the solution as much. Revisit the velocity problem, Example 5.1 in Chapter 5. The values in the coefficient matrix \(\lbrack A\rbrack\) are squares of time, etc. For example, if instead of \(a_{11} = 25,\) you used \(a_{11} = 24.99,\) would you want this small change to make a huge difference in the solution vector. If it did, would you trust the solution?
Later we will see how much (quantifiable terms) we can trust the solution in a system of equations. Every invertible square matrix has a condition number and coupled with the machine epsilon, we can quantify how many significant digits one can trust in the solution.
To calculate the condition number of an invertible square matrix, I need to know what the norm of a matrix means. How is the norm of a matrix defined?
Just like the determinant, the norm of a matrix is a simple unique scalar number. However, the norm is always positive and is defined for all matrices – square or rectangular, and invertible or noninvertible square matrices.
One of the popular definitions of a norm is the row sum norm (also called the uniform-matrix norm). For a \(m \times n\) matrix \(\lbrack A\rbrack\), the row sum norm of \(\lbrack A\rbrack\) is defined as
\[\left\| A \right\|_{\infty} = \begin{matrix} \max \\ 1 \leq i \leq m \\ \end{matrix}\sum_{j = 1}^{n}\left| a_{ij} \right| \nonumber \]
that is, find the sum of the absolute value of the elements of each row of the matrix \(\lbrack A\rbrack\). The maximum out of the \(m\) such values is the row sum norm of the matrix \(\lbrack A\rbrack\).
Find the row sum norm of the following matrix [A].
\[A = \begin{bmatrix} 10 & - 7 & 0 \\ - 3 & 2.099 & 6 \\ 5 & - 1 & 5 \\ \end{bmatrix} \nonumber \]
Solution
\[\begin{split} \left\| A \right\|_{\infty} &= \begin{matrix} \max \\ 1 \leq i \leq 3 \\ \end{matrix}\sum_{j = 1}^{3}\left| a_{ij} \right|\\ &= max\left\lbrack \left( \left| 10 \right| + \left| - 7 \right| + \left| 0 \right| \right),\left( \left| - 3 \right| + \left| 2.099 \right| + \left| 6 \right| \right),\left( \left| 5 \right| + \left| - 1 \right| + \left| 5 \right| \right) \right\rbrack\\ &= max\left\lbrack \left( 10 + 7 + 0 \right),\left( 3 + 2.099 + 6 \right),\left( 5 + 1 + 5 \right) \right\rbrack\\ &= max\left\lbrack 17,\ 11.099,\ 11 \right\rbrack\\ &= 17 \end{split} \nonumber \]
How is the norm related to the conditioning of the matrix?
Let us start answering this question using an example. Go back to the ill-conditioned system of equations,
\[\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix} \nonumber \]
that gives the solution as
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber \]
Denoting the above set of equations as
\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]
\[\left\| X \right\|_{\infty} = 2 \nonumber \]
\[\left\| C \right\|_{\infty} = 7.999 \nonumber \]
Making a small change in the right-hand side,
\[\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.998 \\ \end{bmatrix} \nonumber \]
gives
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} - 3.999 \\ 4.000 \\ \end{bmatrix} \nonumber \]
Denoting the above set of equations by
\[\left\lbrack A \right\rbrack\left\lbrack X' \right\rbrack = \left\lbrack C' \right\rbrack \nonumber \]
right hand side vector is found by
\[\left\lbrack \Delta C \right\rbrack = \left\lbrack C' \right\rbrack - \left\lbrack C \right\rbrack \nonumber \]
and the change in the solution vector is found by
\[\left\lbrack \Delta X \right\rbrack = \left\lbrack X' \right\rbrack - \left\lbrack X \right\rbrack \nonumber \]
then
\[\begin{split} \left\lbrack \Delta C \right\rbrack &= \begin{bmatrix} 4.001 \\ 7.998 \\ \end{bmatrix} - \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}\\ &= \begin{bmatrix} 0.001 \\ - 0.001 \\ \end{bmatrix} \end{split} \nonumber \]
and
\[\begin{split} \left\lbrack \Delta X \right\rbrack &= \begin{bmatrix} - 3.999 \\ 4.000 \\ \end{bmatrix} - \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix}\\ &= \begin{bmatrix} - 5.999 \\ 3.000 \\ \end{bmatrix} \end{split} \nonumber \]
then
\[\left\| \Delta C \right\|_{\infty} = 0.001 \nonumber \]
\[\left\| \Delta X \right\|_{\infty} = 5.999 \nonumber \]
The relative change in the norm of the solution vector is
\[\frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}} = \frac{5.999}{2} \nonumber \]
\[\ = 2.9995 \nonumber \]
The relative change in the norm of the right-hand side vector is
\[\frac{\left\| \Delta C \right\|_{\infty}}{\left\| C \right\|_{\infty}} = \frac{0.001}{7.999} \nonumber \]
\[\ = 1.250 \times 10^{- 4} \nonumber \]
See the small relative change of \(1.250 \times 10^{- 4}\) in the right-hand side vector norm results in a large relative change in the solution vector norm of 2.9995.
In fact, the ratio between the relative change in the norm of the solution vector and the relative change in the norm of the right-hand side vector is
\[\begin{split} \frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta C \right\|_{\infty}/\left\| C \right\|_{\infty}} &= \frac{2.9995}{1.250 \times 10^{- 4}}\\ &= 23993 \end{split} \nonumber \]
Let us now go back to the well-conditioned system of equations.
\[\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\ \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix} \nonumber \]
gives
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} \nonumber \]
Denoting the system of equations by
\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber \]
\[\left\| X \right\|_{\infty} = 2 \nonumber \]
\[\left\| C \right\|_{\infty} = 7 \nonumber \]
Making a small change in the right-hand side vector
\[\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4.001 \\ 7.001 \\ \end{bmatrix} \nonumber \]
gives
\[\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 1.999 \\ 1.001 \\ \end{bmatrix} \nonumber \]
Denoting the above set of equations by
\[\left\lbrack A \right\rbrack\left\lbrack X' \right\rbrack = \left\lbrack C' \right\rbrack \nonumber \]
the change in the right-hand side vector is then found by
\[\left\lbrack \Delta C \right\rbrack = \left\lbrack C' \right\rbrack - \left\lbrack C \right\rbrack \nonumber \]
and the change in the solution vector is
\[\left\lbrack \Delta X \right\rbrack = \left\lbrack X' \right\rbrack - \left\lbrack X \right\rbrack \nonumber \]
then
\[\begin{split} \left\lbrack \Delta C \right\rbrack &= \begin{bmatrix} 4.001 \\ 7.001 \\ \end{bmatrix} - \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix}\\ &= \begin{bmatrix} 0.001 \\ 0.001 \\ \end{bmatrix} \end{split} \nonumber \]
and
\[\begin{split} \left\lbrack \Delta X \right\rbrack &= \begin{bmatrix} 1.999 \\ 1.001 \\ \end{bmatrix} - \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix}\\ &= \begin{bmatrix} - 0.001 \\ 0.001 \\ \end{bmatrix} \end{split} \nonumber \]
then
\[\left\| \Delta C \right\|_{\infty} = 0.001 \nonumber \]
\[\left\| \Delta X \right\|_{\infty} = 0.001 \nonumber \]
The relative change in the norm of solution vector is
\[\begin{split} \frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}} &= \frac{0.001}{2}\\ &= 5 \times 10^{- 4} \end{split} \nonumber \]
The relative change in the norm of the right-hand side vector is
\[\begin{split} \frac{\left\| \Delta C \right\|_{\infty}}{\left\| C \right\|_{\infty}} &= \frac{0.001}{7}\\ &= 1.429 \times 10^{- 4} \end{split} \nonumber \]
See the small relative change in the right-hand side vector norm of \(1.429 \times 10^{- 4}\) results in the small relative change in the solution vector norm of \(5 \times 10^{- 4}\).
In fact, the ratio between the relative change in the norm of the solution vector and the relative change in the norm of the right-hand side vector is
\[\begin{split} \frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta C \right\|_{\infty}/\left\| C \right\|_{\infty}} &= \frac{5 \times 10^{- 4}}{1.429 \times 10^{- 4}}\\ &= 3.5 \end{split} \nonumber \]
What are some of the properties of norms?
- For a matrix \(\lbrack A\rbrack\), \(\left\| A \right\| \geq 0\)
- For a matrix \(\lbrack A\rbrack\) and a scalar k, \(\left\| {kA} \right\| = \left| k \right|\left\| A \right\|\)
- For two matrices \(\lbrack A\rbrack\) and \(\lbrack B\rbrack\) of same order, \(\left\| A + B \right\| \leq \left\| A \right\| + \left\| B \right\|\)
- For two matrices \(\lbrack A\rbrack\) and \(\lbrack B\rbrack\) that can be multiplied as \(\lbrack A\rbrack\ \lbrack B\rbrack\), \(\left\| {AB} \right\| \leq \left\| A \right\|\left\| B \right\|\)
Is there a general relationship that exists between \(\left\| \mathbf{\Delta}\mathbf{X} \right\|\mathbf{/}\left\| \mathbf{X} \right\|\) and \(\left\| \mathbf{\Delta}\mathbf{C} \right\|\mathbf{/}\left\| \mathbf{C} \right\|\) or between \(\left\| \mathbf{\Delta}\mathbf{X} \right\|\mathbf{/}\left\| \mathbf{X} \right\|\) and \(\left\| \mathbf{\Delta}\mathbf{A} \right\|\mathbf{/}\left\| \mathbf{A} \right\|\)? If so, it could help us identify well-conditioned and ill conditioned system of equations.
If there is such a relationship, will it help us quantify the conditioning of the matrix? That is, will it tell us how many significant digits we could trust in the solution of a system of simultaneous linear equations?
There is a relationship that exists between
\[\frac{\left\| \Delta X \right\|}{\left\| X \right\|}\text{and}\frac{\left\| \Delta C \right\|}{\left\| C \right\|} \nonumber \]
and between
\[\frac{\left\| \Delta X \right\|}{\left\| X \right\|}\text{and}\frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber \]
These relationships are
\[\frac{\left\| \Delta X \right\|}{\left\| X \right\|} \leq \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\frac{\left\| \Delta C \right\|}{\left\| C \right\|} \nonumber \]
and
\[\frac{\left\| \Delta X \right\|}{\left\| X + \Delta X \right\|}\leq \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber \]
The above two inequalities show that the relative change in the norm of the right-hand side vector or the coefficient matrix can be amplified by as much as \(\left\| A \right\|\left\| A^{- 1} \right\|\).
This number \(\left\| A \right\|\left\| A^{- 1} \right\|\) is called the condition number of the matrix and coupled with the machine epsilon, we can quantify the accuracy of the solution of \(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack\).
Prove for
\(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack\)
that
\[\frac{\left\| \Delta X \right\|}{\left\| X + \Delta X \right\|} \leq \ \ \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber \]
Proof
Let
\[\left\lbrack A \right\rbrack{\ \ }\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \;\;\;\;\;\;\;(1) \nonumber \]
Then if \(\lbrack A\rbrack\) is changed to \(\left\lbrack A' \right\rbrack\), the \(\lbrack X\rbrack\) will change to \(\left\lbrack X' \right\rbrack\), such
that
\[\left\lbrack A' \right\rbrack{\ \ }\left\lbrack X' \right\rbrack = \left\lbrack C \right\rbrack\;\;\;\;\;\;\;(2) \nonumber \]
From Equations (1) and (2),
\[\left\lbrack A \right\rbrack{\ \ }\left\lbrack X \right\rbrack = \left\lbrack A' \right\rbrack\left\lbrack X' \right\rbrack \nonumber \]
Denoting change in \(\lbrack A\rbrack\) and \(\lbrack X\rbrack\) matrices as \(\left\lbrack \Delta A \right\rbrack\) and \(\left\lbrack \Delta X \right\rbrack\), respectively
\[\left\lbrack \Delta A \right\rbrack = \left\lbrack A' \right\rbrack - \left\lbrack A \right\rbrack \nonumber \]
\[\left\lbrack \Delta X \right\rbrack = \left\lbrack X' \right\rbrack - \left\lbrack X \right\rbrack \nonumber \]
then
\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \ \ \left( \left\lbrack A \right\rbrack + \left\lbrack \Delta A \right\rbrack \right)\ \left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber \]
Expanding the above expression
\[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \ \left\lbrack A \right\rbrack\left\lbrack X \right\rbrack + \left\lbrack A \right\rbrack\left\lbrack \Delta X \right\rbrack + \left\lbrack \Delta A \right\rbrack\left\lbrack X \right\rbrack + \left\lbrack \Delta A \right\rbrack\left\lbrack \Delta X \right\rbrack \nonumber \]
\[\lbrack 0\rbrack = \left\lbrack A \right\rbrack\left\lbrack \Delta X \right\rbrack + \left\lbrack \Delta A \right\rbrack\left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber \]
\[- \left\lbrack A \right\rbrack\left\lbrack \Delta X \right\rbrack = \left\lbrack \Delta A \right\rbrack\left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber \]
\[\left\lbrack \Delta X \right\rbrack = - \left\lbrack A \right\rbrack^{- 1}\left\lbrack \Delta A \right\rbrack\left( \left\lbrack X \right\rbrack + \left\lbrack \Delta X \right\rbrack \right) \nonumber \]
Applying the theorem of norms, that the norm of multiplied matrices is less than the multiplication of the individual norms of the matrices,
\[\left\| \Delta X \right\|\leq \left\| A^{- 1} \right\| \left\| \Delta A \right\| \left\| X + \Delta X \right\| \nonumber \]
Multiplying both sides by \(\left\| A \right\|\)
\[\left\| A \right\|\ \left\| \Delta X \right\|\leq \left\| A \right\| \left\| A^{- 1} \right\| \left\| \Delta A \right\|\left\| X + \Delta X \right\| \nonumber \]
\[\frac{\left\| \Delta X \right\|}{\left\| X + \Delta X \right\|}\leq \left\| A \right\|\ \left\| A^{- 1} \right\|\ \frac{\left\| \Delta A \right\|}{\left\| A \right\|} \nonumber \]
How do I use the above theorems to find how many significant digits are correct in my solution vector?
The relative error in a solution vector norm is \(\leq\) Cond (A) \(\times\)relative error in right hand side vector norm.
The possible relative error in the solution vector norm is \(\leq\) \(Cond(A) \times \in_{mach}\)
Hence \(Cond(A) \times \in_{mach}\) should give us the number of significant digits, m that are at least correct in our solution by finding out the largest value of m for which \(Cond(A) \times \in_{mach}\) is less than \(0.5 \times 10^{- m}\).
How many significant digits can I trust in the solution of the following system of equations?
\[\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\ \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ \end{bmatrix} \nonumber \]
Solution
For
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\ \nonumber \]
it can be shown
\[\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} - 3999 & 2000 \\ 2000 & - 1000 \\ \end{bmatrix}\ \nonumber \]
\[\left\| A \right\|_{\infty} = 5.999 \nonumber \]
\[\left\| A^{- 1} \right\|_{\infty} = 5999 \nonumber \]
\[\begin{split} {Cond}\left( A \right) &= \left\| A \right\|\left\| A^{- 1} \right\|\\ &= 5.999 \times 5999.4\\ &= 35990 \end{split} \nonumber \]
Assuming single precision with 23 bits used in the mantissa for real numbers, the machine epsilon is
\[\begin{split} \in_{mach} &= 2^{- 23}\\ &= 0.119209 \times 10^{- 6} \end{split} \nonumber \]
\[\begin{split} {Cond}(A) \times \in_{mach} &= 35990 \times 0.119209 \times 10^{- 6}\\ &= 0.4290 \times 10^{- 2} \end{split} \nonumber \]
For what maximum positive value of m, would \({Cond}(A) \times \in_{mach}\) be less than or equal to \(0.5 \times 10^{- m}\)
\[0.4290 \times 10^{- 2} \leq 0.5 \times 10^{- m} \nonumber \]
\[0.8580 \times 10^{- 2} \leq 10^{- m} \nonumber \]
\[log(0.8580 \times 10^{- 2}) \leq log(10^{- m}) \nonumber \]
\[- 2.067 \leq - m \nonumber \]
\[m \leq 2.067 \nonumber \]
\[m \leq 2 \nonumber \]
So, two significant digits are at least correct in the solution vector.
How many significant digits can I trust in the solution of the following system of equations?
\[\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\ \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7 \\ \end{bmatrix} \nonumber \]
Solution
For
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\ \nonumber \]
it can be shown
\[\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} - 3 & 2 \\ 2 & - 1 \\ \end{bmatrix}\ \nonumber \]
Then
\[\left\| A \right\|_{\infty} = 5, \nonumber \]
\[\left\| A^{- 1} \right\|_{\infty} = 5. \nonumber \]
\[\begin{split} Cond\ (A) &= \left\| A \right\|{\ \ }\left\| A^{- 1} \right\|\\ &= 5 \times 5\\ &= 25 \end{split} \nonumber \]
Assuming single precision with 23 bits used in the mantissa for real numbers, the machine epsilon
\[\begin{split} \in_{mach} &= 2^{- 23}\\ &= 0.119209 \times 10^{- 6} \end{split} \nonumber \]
\[\begin{split} {Cond}(A) \times \in_{mach} &= 25 \times 0.119209 \times 10^{- 6}\\ &= 0.2980 \times 10^{- 5} \end{split} \nonumber \]
For what maximum positive value of m, would \({Cond}(A) \times \in_{mach}\) be less than or equal to \(0.5 \times 10^{- m}\)
\[0.2980 \times 10^{- 5} \leq 0.5 \times 10^{- m} \nonumber \]
\[m \leq 5 \nonumber \]
So, five significant digits are at least correct in the solution vector.
Adequacy of Solutions Quiz
The row sum norm of the matrix
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 6 & - 7 & 3 & 13 \\ 19 & - 21 & 23 & - 29 \\ 41 & 47 & - 51 & 61 \\ \end{bmatrix} \nonumber \] is
(A) \(29\)
(B) \(61\)
(C) \(98\)
(D) \(200\)
The adequacy of the solution of simultaneous linear equations \[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack \nonumber \] depends on
(A) the condition number of coefficient matrix \(\left\lbrack A \right\rbrack\)
(B) the machine epsilon
(C) the condition number for matrix \(\left\lbrack A \right\rbrack\)and the machine epsilon
(D) norm of the coefficient matrix \(\left\lbrack A \right\rbrack\)
Given a set of equations in matrix form \[\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack, \nonumber \] \[\left\| A \right\| = 250,\left\| A^{- 1} \right\| = 40 \;\;and \nonumber \] \[\varepsilon_{mach} = 0.119 \times 10^{- 6}, \nonumber \] then the number of significant digits you can at least trust in the solution are
(A) \(1\)
(B) \(2\)
(C) \(3\)
(D) \(4\)
The solution to a set of simultaneous linear equations
\[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 44 \\ 94 \\ 138 \\ \end{bmatrix} \nonumber \] is given as
\[\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ 7 \\ \end{bmatrix} \nonumber \] The solution to another set of simultaneous linear equations is given by (note the coefficient matrix is the same as above)
\[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 43.99 \\ 93.98 \\ 138.03 \\ \end{bmatrix} \nonumber \]
is given as
\[\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 214.01 \\ - 208.01 \\ 60 \\ \end{bmatrix} \nonumber \]
Based on the row sum norm, the condition number of the coefficient matrix is greater than (choose the largest possible value)
(A) \(1\)
(B) \(138\)
(C) \(4500\)
(D) \(139320\)
The condition number of the \(n \times n\) identity matrix based on the row sum norm is
(A) \(0\)
(B) \(1\)
(C) \(n\)
(D) \(n^{2}\)
Let \(\left\lbrack A \right\rbrack = \begin{bmatrix} 1 & 2 + \delta \\ 2 - \delta & 1 \\ \end{bmatrix}\). Based on the row sum norm and given that \(\delta \rightarrow 0\),\(\delta > 0\), the condition number of the matrix is
(A) \(\displaystyle \frac{3 - \delta}{3 + \delta}\)
(B) \(\displaystyle \frac{9 - \delta^{2}}{3 - \delta^{2}}\)
(C) \(\displaystyle \frac{(3 + \delta)^{2}}{3 - \delta^{2}}\)
(D) \(\displaystyle \frac{3 - 2\delta - \delta^{2}}{3 - \delta^{2}}\)
Adequacy of Solutions Exercise
The adequacy of the solution of simultaneous linear equations depends on
- Condition number
- Machine epsilon
- Product of condition number and machine epsilon
- Norm of the matrix.
- Answer
-
C
If a system of equations \(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack\) is ill conditioned, then
- \(det(A) = 0\)
- \(Cond(A) = 1\)
- \(Cond(A)\) is large.
- \(\left\| A \right\|\) is large.
- Answer
-
C
If \(Cond(A) = 10^{4}\) and \(\in_{mach}\)= 0.119 \(\times\) 10-6, then in \(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack\), at least these many significant digits are correct in your solution,
- \(0\)
- \(1\)
- \(2\)
- \(3\)
- Answer
-
C
Make a small change in the coefficient matrix of \(\begin{bmatrix} 1 & 2 \\ 2 & 3.999 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \\ 7.999 \\ \end{bmatrix}\)
and find
\[\frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta A \right\|_{\infty}/\left\| A \right\|_{\infty}} \nonumber \]
Is it a large or small number? How is this number related to the condition number of the coefficient matrix?
- Answer
-
Changing \(\lbrack A\rbrack\) to
\[\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 4.000 \\ \end{bmatrix} \nonumber \]
Results in solution of
\[\begin{bmatrix} 5999 \\ -2999 \\ \end{bmatrix} \nonumber \]
\[\frac{\frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}}}{\frac{\left\| \Delta A \right\|_{\infty}}{\left\| A \right\|_{\infty}}} = \frac{\frac{5999.7}{2}}{\frac{0.002}{5.999}} \nonumber \]
4\(= 8.994 \times 10^{6}\)$
Make a small change in the coefficient matrix of
\(\begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}\begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 4 \ 7 \\ \end{bmatrix}\)
and find
\[\frac{\left\| \Delta X \right\|_{\infty}/\left\| X \right\|_{\infty}}{\left\| \Delta A \right\|_{\infty}/\left\| A \right\|_{\infty}}. \nonumber \] Is it a large or a small number? Compare your results with the previous problem. How is this number related to the condition number of the coefficient matrix?
- Answer
-
Changing \(\lbrack A\rbrack\) to
\[\begin{bmatrix} 1.001 & 2.001 \\ 2.001 & 3.000 \\ \end{bmatrix} \nonumber \]
Results in solution of
\[\begin{bmatrix} 2.003 \\ 0.9970 \\ \end{bmatrix} \nonumber \]
\[\frac{\frac{\left\| \Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}}}{\frac{\left\| \Delta A \right\|_{\infty}}{\left\| A \right\|_{\infty}}} = \frac{\frac{0.003}{2.000}}{\frac{0.002}{5}} \nonumber \]
\[= 3.75 \nonumber \]
Prove
\[\frac{\left\| \Delta X \right\|}{\left\| X \right\|}\ \ \left\| A \right\|\ \left\| A^{- 1} \right\|\ \frac{\left\| \Delta C \right\|}{\left\| C \right\|} \nonumber \]
- Answer
-
Use theorem that if \(\lbrack A\rbrack\lbrack B\rbrack = \lbrack C\rbrack\)then \(\left\| A \right\|\left\| B \right\| \geq \left\| C \right\|\)
For
\[\left\lbrack A \right\rbrack = \begin{bmatrix} 10 & - 7 & 0 \\ - 3 & 2.099 & 6 \\ 5 & - 1 & 5 \\ \end{bmatrix} \nonumber \]
gives
\[\left\lbrack A \right\rbrack^{- 1} = \begin{bmatrix} - 0.1099 & - 0.2333 & 0.2799 \\ - 0.2999 & - 0.3332 & 0.3999 \\ 0.04995 & 0.1666 & 6.664 \times 10^{- 5} \\ \end{bmatrix} \nonumber \]
- What is the condition number of \(\lbrack A\rbrack\)?
- How many significant digits can we at least trust in the solution of \(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack\) if \(\in_{mach} = 0.1192 \times 10^{- 6}\)?
- Without calculating the inverse of the matrix \(\lbrack A\rbrack\), can you estimate the condition number of \(\lbrack A\rbrack\) using the theorem in problem#6?
- Answer
-
A. \(\left\| A \right\| = 17\)
\(\left\| A^{- 1} \right\| = 1.033\)
\({Cond}(A)=17.56\)B. 5
C. Try different values of right hand side of \(C = \lbrack \pm 1\ \ \pm 1\ \ \pm 1\rbrack^{T}\) with signs chosen randomly. Then \(\left\| A^{- 1} \right\| \leq \left\| X \right\|\) obtained from solving equation set \(\lbrack A\rbrack\ \lbrack X\rbrack = \lbrack C\rbrack\) as \(\left\| C \right\| = 1\).
Prove that the \({Cond}(A) \geq 1\).
- Answer
-
We know that
\[\left\| A\ B \right\| \leq \left\| A \right\|\left\| B \right\| \nonumber \]
then if
\[\lbrack B\rbrack = \lbrack A\rbrack^{- 1}, \nonumber \]
\[\left\| A\ A^{- 1} \right\| \leq \left\| A \right\|\left\| A^{- 1} \right\| \nonumber \]
\[\left\| I \right\| \leq \left\| A \right\|\left\| A^{- 1} \right\| \nonumber \]
\[1 \leq \left\| A \right\|\left\| A^{- 1} \right\| \nonumber \]
\[\left\| A \right\|\left\| A^{- 1} \right\| \geq 1 \nonumber \]
\[{Cond}(A) \geq 1 \nonumber \]