Study Notes of "Introduction to MATRIX ALGEBRA": 9. Adequacy of Solutions

PDF format lecture Chapter 9 Adequacy of Solutions

Printable version Study Notes of “Introduction to MATRIX ALGEBRA”

Summary

• Ill-conditional system
  
  • 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.
  • For example, the following system $$\begin{bmatrix} 1& 2\\ 2& 3.999\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4\\ 7.999\end{bmatrix}$$ The solution is $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix} 1& 2\\ 2& 3.999\end{bmatrix} ^{-1}\cdot\begin{bmatrix}4\\ 7.999\end{bmatrix} = \begin{bmatrix}2\\ 1\end{bmatrix}$$ 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}$$ gives $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix} 1& 2\\ 2& 3.999\end{bmatrix} ^{-1}\cdot\begin{bmatrix}4.001\\ 7.998\end{bmatrix} = \begin{bmatrix}-3.999\\ 4.000\end{bmatrix}$$ 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}$$ gives $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix} 1.001& 2.001\\ 2.001& 3.998\end{bmatrix} ^{-1}\cdot\begin{bmatrix}4\\ 7.999\end{bmatrix} = \begin{bmatrix} 6.989016\\ -1.497254\end{bmatrix}$$ We can see that a small change in the coefficient matrix or the right hand side resulted in a large change in the solution vector.
• Well-conditional system
  
  • A system of equations is considered to be well-conditioned if a small change in the coefficient matrix of a small change in the right hand side results in a small change in the solution vector.
  • For example, the following system $$\begin{bmatrix} 1& 2\\ 2& 3\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4\\ 7\end{bmatrix}$$ The solution is $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix} 1& 2\\ 2& 3\end{bmatrix} ^{-1}\cdot\begin{bmatrix}4\\ 7\end{bmatrix} = \begin{bmatrix}2\\ 1\end{bmatrix}$$ 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}$$ gives $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix} 1& 2\\ 2& 3\end{bmatrix} ^{-1} \cdot \begin{bmatrix} 4.001\\ 7.001\end{bmatrix} = \begin{bmatrix}1.999\\ 1.001\end{bmatrix}$$ 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}$$ gives $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix} 1.001& 2.001\\ 2.001& 3.001\end{bmatrix} ^{-1}\cdot\begin{bmatrix}4\\ 7\end{bmatrix} = \begin{bmatrix} 2.003\\ 0.997\end{bmatrix}$$ We can see that a small change in the coefficient matrix or the right hand side resulted in a small change in the solution vector.
• Norm
  
  • Just like the determinant, the norm of a matrix is a simple unique scalar number. For a $m\times n$ matrix $[A]$, the row sum norm of $[A]$ is defined as $$\|A\|_{\infty}=\max_{1\leq i\leq m}\sum_{j=1}^{n}|a_{ij}|$$ that is, find the sum of the absolute value of the elements pf each row of the matrix $[A]$. The maximum out of the $m$ such values is the row sum norm if the matrix $[A]$.
  • For example, we have the following matrix $$[A] = \begin{bmatrix}10& -3& 5\\ -7& 2.099& -1\\ 0& 6& 5\end{bmatrix}$$ The row sum norm of $[A]$ is $$\|A\|_{\infty} = \max_{1\leq i\leq3} \sum_{j=1}^{3}|a_{ij}|$$ $$=\max[(10+7+0), (3+2.099+6), (5,-1,5)]$$ $$=\max[17, 11.099, 11] =17$$
• The relationship between the norm and the conditioning of the matrix
  
  • Example of the ill-conditioned system. $$\begin{bmatrix} 1& 2\\ 2& 3.999\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4\\ 7.999\end{bmatrix}$$ which has the solution $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}2\\ 1\end{bmatrix}$$ Denoting the above system as $AX=B$, and hence we have $$\|X\|_{\infty}=2$$ $$\|B\|_{\infty}=7.999$$ 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}$$ gives $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}-3.999\\ 4.000\end{bmatrix}$$ Denoting the above changed system as $AX'=B'$ and $$\Delta X=X'-X=\begin{bmatrix}-3.999\\ 4.000\end{bmatrix} - \begin{bmatrix}2\\ 1\end{bmatrix} = \begin{bmatrix}-5.999\\ 3.000\end{bmatrix}$$ $$\Delta B=B'-B = \begin{bmatrix}4.001\\ 7.998\end{bmatrix} - \begin{bmatrix}4\\ 7.999\end{bmatrix} = \begin{bmatrix}0.001\\ -0.001\end{bmatrix}$$ Then $$\|\Delta X\|_{\infty} = 5.999$$ $$\|\Delta B\|_{\infty} = 0.001$$ The relative change in the norm of the solution vector is $${\|\Delta X\|_{\infty}\over \|X\|_{\infty}} = {5.999\over2}=2.9995$$ The relative change in the norm of the right hand side vector is $${\|\Delta B\|_{\infty}\over \|B\|_{\infty}} = {0.001\over7.999}=1.25\times10^{-4}$$ That is, the small relative change of $1.25\times10^{-4}$ in the right hand side vector norm results in a large relative change in the solution vector norm of $2.9995$. We can see the ratio of this two norms is $${\|\Delta X\|_{\infty} \big/ \|X\|_{\infty}\over \|\Delta B\|_{\infty} \big/ \| B\|_{\infty}} = 23993$$
  • Example of the well-conditioned system. $$\begin{bmatrix} 1& 2\\ 2& 3\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4\\ 7\end{bmatrix}$$ which has the solution $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}2\\ 1\end{bmatrix}$$ Denoting the above system as $AX=B$, and hence we have $$\|X\|_{\infty}=2$$ $$\|B\|_{\infty}=7$$ Making a small change in the right hand side $$\begin{bmatrix} 1& 2\\ 2& 3\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4.001\\ 7.001\end{bmatrix}$$ gives $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}1.999\\ 1.001\end{bmatrix}$$ Denoting the above changed system as $AX'=B'$ and $$\Delta X=X'-X=\begin{bmatrix}1.999\\ 1.001\end{bmatrix} - \begin{bmatrix}2\\ 1\end{bmatrix} = \begin{bmatrix}-0.001\\ 0.001\end{bmatrix}$$ $$\Delta B=B'-B = \begin{bmatrix}4.001\\ 7.001\end{bmatrix} - \begin{bmatrix}4\\ 7\end{bmatrix} = \begin{bmatrix}0.001\\ 0.001\end{bmatrix}$$ Then $$\|\Delta X\|_{\infty} = 0.001$$ $$\|\Delta B\|_{\infty} = 0.001$$ The relative change in the norm of the solution vector is $${\|\Delta X\|_{\infty}\over \|X\|_{\infty}} = {0.001\over2}=5\times10{-4}$$ The relative change in the norm of the right hand side vector is $${\|\Delta B\|_{\infty}\over \|B\|_{\infty}} = {0.001\over7} = 1.429 \times 10^{-4}$$ That is, the small relative change of $1.429\times10^{-4}$ in the right hand side vector norm results in a small relative change in the solution vector norm of $5\times10^{-4}$. We can see the ratio of this two norms is $${\|\Delta X\|_{\infty} \big/ \|X\|_{\infty}\over \|\Delta B\|_{\infty} \big/ \| B\|_{\infty}} = 3.5$$
• Properties of Norms
  
  • $\|A\| \geq 0$
  • $\|kA\| = |k|\|A\|$ where $k$ is a scalar.
  • $\|A+B\|\leq \|A\| + \|B\|$
  • $\|AB\| \leq \|A\|\cdot\|B\|$
  • For a system $AX=B$, we have $${\|\Delta X\|\over \|X\|} \leq \|A\|\|A^{-1}\|{\|\Delta B\|\over \|B\|}$$ and $${\|\Delta X\|\over \|X + \Delta X\|} \leq \|A\|\|A^{-1}\|{\|\Delta A\|\over \|A\|}$$ where $\|A\|\|A^{-1}\|$ is called the \textbf{condition number}, Cond$(A)$.
• Significant Digits
  
  • The possible relative error in the solution vector norm is no more then Cond$(A)\times\epsilon$, where $\epsilon$ is the machine epsilon which is $2.220446\times10^{-16}$ or $2^{-52}$ here (obtained by R code .Machine$double.eps on 64-bit PC, more details refer to link1 and link2).
    Hence Cond$(A) \times \epsilon$ 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\epsilon$ is less than or equal to $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\end{bmatrix} \begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4\\ 7\end{bmatrix}$$ For $$A=\begin{bmatrix}1& 2 \\ 2& 3\end{bmatrix}$$ and $$A^{-1}= \begin{bmatrix}-3& 2 \\ 2& -1\end{bmatrix}$$ Then $$\|A\|_{\infty}=5,\ \|A^{-1}\|_{\infty}=5\Rightarrow \text{Cond}(A)=\|A\|_{\infty}\|A^{-1}\|_{\infty} = 25$$ Thus $$\text{Cond}(A)\times\epsilon \leq 0.5\times10^{-m}$$ $$\Rightarrow 25\times\epsilon\leq0.5\times10^{-m}$$ $$\Rightarrow \log(25\times\epsilon) \leq \log(0.5\times10^{-m})$$ $$\Rightarrow m\leq13.95459 $$ That is, 13 digits are at least correct in the solution vector.

Selected Problems

1. What factors does the adequacy of the solution of simultaneous linear equations depend on?

Solution:
The product of condition number Cond$(A)=\|A\|\|A^{-1}\|$ and machine epsilon $\epsilon$.

2. If a system of equations $[A][X]=[B]$ is ill-conditioned, then
A. $\det(A)=0$
B. Cond$(A)=1$
C. Cond$(A)$ is large
D. $\|A\|$ is large

Solution:
If the system is ill-conditioned, then the condition number Cond$(A)=\|A\|\|A^{-1}\|$ is large. The correct answer is C.

3. If Cond$(A)=10^{4}$ and $\epsilon=0.119\times10^{-6}$, then in $[A][X]=[B]$, at least how many significant digits are correct in the solution?

Solution:
$$\text{Cond}(A)\times\epsilon \leq 0.5\times10^{-m}$$ $$\Rightarrow 10^{4}\times0.119\times10^{-6} \leq 0.5\times10^{-m}$$ $$\Rightarrow m\leq {\log(0.5)-\log(0.119\times10^{-2})\over \log(10)} = 2.623423$$ Thus at least 2 significant digits are correct in the solution.

4. 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 $${\|\Delta X\|_{\infty} \big/ \|X\|_{\infty}\over \|\Delta A\|_{\infty} \big/ \| A\|_{\infty}}$$
Solution:
The solution of the original system is $$ \begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}2\\ 1\end{bmatrix}$$
Making a small change in the coefficient matrix as $$\begin{bmatrix} 1.001& 2.001 \\ 2.001& 4.000\end{bmatrix} \begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4\\ 7.999\end{bmatrix}$$ and the solution is $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}5999\\ -2999\end{bmatrix}$$ Hence the row sum norms are $$\|X\| = 2,\ \|\Delta X\|=5997,\ \|A\|=5.999,\ \|\Delta A\|=0.002$$ Thus the ratio is $${\|\Delta X\|_{\infty} \big/ \|X\|_{\infty}\over \|\Delta A\|_{\infty} \big/ \| A\|_{\infty}} = {5997 \big/ 2\over 0.002 \big/ 5.999} = 8994001$$ It is a large number. Hence we can conclude that this system is ill-conditioned. On the other hand, we can calculate the condition number of the coefficient matrix, note that $A^{-1} = \begin{bmatrix}-3999& 2000 \\ 2000& -1000 \end{bmatrix}$, and hence $$\|A\|\|A^{-1}\|= 5.999\times5999=35988 $$ which is also a large number.

5. 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 $${\|\Delta X\|_{\infty} \big/ \|X\|_{\infty}\over \|\Delta A\|_{\infty} \big/ \| A\|_{\infty}}$$
Solution:
The solution of the original system is $$ \begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}2\\ 1\end{bmatrix}$$
Making a small change in the coefficient matrix as $$\begin{bmatrix} 1.001& 2.001 \\ 2.001& 3.001\end{bmatrix} \begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}4\\ 7\end{bmatrix}$$ and the solution is $$\begin{bmatrix}x\\ y\end{bmatrix} = \begin{bmatrix}2.003\\ 0.997\end{bmatrix}$$ Hence the row sum norms are $$\|X\| = 2,\ \|\Delta X\|=0.003,\ \|A\|=5,\ \|\Delta A\|=0.002$$ Thus the ratio is $${\|\Delta X\|_{\infty} \big/ \|X\|_{\infty}\over \|\Delta A\|_{\infty} \big/ \| A\|_{\infty}} = {0.003 \big/ 2\over 0.002 \big/ 5} = 3.75$$ It is a small number. Hence we can conclude that this system is well-conditioned. On the other hand, we can calculate the condition number of the coefficient matrix, note that $A^{-1} = \begin{bmatrix}-3& 2 \\ 2& -1\end{bmatrix}$, and hence $$\|A\|\|A^{-1}\|= 5\times5=25$$ which is also a small number.

6. Prove $${\|\Delta X\|\over \|X\|} \leq \|A\|\|A^{-1}\|{\|\Delta B\|\over \|B\|}$$
Solution:
The key point is $\|XY\| \leq \|X\|\|Y\|$. Let $AX=B$, then if $B$ is changed to $B'$, the $X$ is changed to $X'$, such that $$AX'=B'$$ Hence we have $$AX=B,\ AX'=B'$$ $$\Rightarrow \Delta X=X'-X=A^ {-1}B'-A^{-1}B = A^{-1}\Delta B$$ $$\Rightarrow\|\Delta X\|\leq \|A^{-1}\|\|\Delta B\|$$ and $$AX=B\Rightarrow \|B\|=\|AX\| \leq \|A\|\|X\|$$ Multiply the above inequalities and obtain $$\|\Delta X\|\|B\| \leq \|A^{-1}\|\|\Delta B\|\|A\|\|X\|$$ $$\Rightarrow {\|\Delta X\|\over \|X\|} \leq \|A\|\|A^{-1}\|{\|\Delta B\|\over \|B\|}$$
7. Prove $${\|\Delta X\|\over \|X + \Delta X\|} \leq \|A\|\|A^{-1}\|{\|\Delta A\|\over \|A\|}$$
Solution:
Similar to the previous question, we have $$AX=B,\ A'X'=B$$ $$\Rightarrow AX=A'X'=(A+\Delta A)(X+\Delta X)=AX+A\Delta X+\Delta AX + \Delta A\Delta X$$ $$\Rightarrow A\Delta X+\Delta AX + \Delta A\Delta X = [0]$$ $$\Rightarrow \Delta A(X+\Delta X)=-A\Delta X $$ $$\Rightarrow \Delta X= -A^{-1}\Delta A(X+\Delta X) \leq \|A^{-1}\|\|\Delta A\|\|X+\Delta X\|$$ $$\Rightarrow \|A\|\Delta X\leq \|A\|\|A^{-1}\|\|\Delta A\|\|X+\Delta X\|$$ $$\Rightarrow {\|\Delta X\|\over \|X + \Delta X\|} \leq \|A\|\|A^{-1}\|{\|\Delta A\|\over \|A\|}$$
8. Prove that Cond$(A) \geq 1$.

Solution:
$$\text{Cond}(A) = \|A\|\|A^{-1}\| \geq \|AA^{-1}\| = \|I\|=1$$
9. For $$[A] = \begin{bmatrix}10& -7& 0\\ -3& 2.099& 6\\ 5& -1& 5\end{bmatrix}$$ gives $$[A]^{-1} = \begin{bmatrix}-0.1099& -0.2333& 0.2799\\ -0.2999& -0.3332& 0.3999\\ 0.04995& 0.1666& 6.664\times10^{-5}\end{bmatrix}$$ (A) What is the condition number of $[A]$?
(B) How many significant digits can we at least trust in the solution of $[A][X] = B$ if $\epsilon = 0.1192\times10^{-6}$?

Solution:
(A) Cond$(A) = \|A\|\|A^{-1}\| = 17\times1.033 = 17.561$
(B) $$\text{Cond}(A)\times\epsilon \leq 0.5\times10^{-m}$$ $$\Rightarrow 17.561\times0.1192\times10^{-6} \leq 0.5\times10^{-m}$$ $$\Rightarrow m \leq 5.378145$$ Hence 5 significant digits can be trusted in the solution.

10. Let $$[A] = \begin{bmatrix}1& 2+\delta\\ 2-\delta& 1\end{bmatrix}$$ Based on the row sum norm and given that $\delta\rightarrow0$, $\delta > 0$, what is the condition number of the matrix?

Solution:
Recall that the inverse of the matrix $[M]=\begin{bmatrix}a &b\\ c &d \end{bmatrix}$ is $$\begin{bmatrix}{d\over\det(M)} & {-b\over \det(M)}\\ {-c\over\det(M)} &{a\over\det(M)} \end{bmatrix}$$ where $\det(M) = ad-bc$. Thus we have
$$A^{-1} = \begin{bmatrix}{1\over -3+\delta^2}& -{2+\delta\over -3+\delta^2}\\{-2+\delta\over -3+\delta^2}& {1\over -3+\delta^2}\end{bmatrix}$$ The row sum norms are
$$\|A\| = \max(3+\delta, 3-\delta) = 3+\delta$$ and $$\|A^{-1}\| = \max\left({3+\delta\over 3-\delta^2}, {3-\delta \over 3-\delta^2} \right) = {3+\delta\over 3-\delta^2}$$ Hence $$\text{Cond}(A) = \|A\|\|A^{-1}\| = {(3+\delta)^2\over3-\delta^2}$$