Condition number - Relative error

[mathmari]

Hey!

Let $\gamma\in \mathbb{R}$ and $A=\begin{pmatrix}1 & \gamma \\ 0 & 1\end{pmatrix}$.

I want to calculate the condition numbers $\text{cond}_1(A) , \text{cond}_2(A) ,\text{cond}_{\infty}(A) $.

The determinant of the matrix $A$ is equal to $\det (A)=1\neq 0$, so the matrix $A$ is invertible.

The inverse matrix is $A^{-1}=\frac{1}{\det (A)}\begin{pmatrix}1 & -\gamma \\ 0 & 1\end{pmatrix}=\begin{pmatrix}1 & -\gamma \\ 0 & 1\end{pmatrix}$.

• \begin{equation*}\text{cond}_1(A) = \|A\|_1 \cdot \|A^{-1}\|_1\end{equation*}
  
  The norm is defined by \begin{equation*}\|A\|_1:=\max_{1\leq k\leq 2}\sum_{j=1}^2|a_{jk}|\end{equation*}
  
  We have the following norms: \begin{align*}&\|A\|_1=\max \{|1|+|0|, |\gamma|+|1|\}=\max\{1, |\gamma|+1\}=|\gamma|+1 \\ &\|A^{-1}\|_1=\max \{|1|+|0|, |-\gamma|+|1|\}=\max\{1, |\gamma|+1\}=|\gamma|+1\end{align*}
  
  So, the condition number is $\text{cond}_1(A) = \|A\|_1 \cdot \|A^{-1}\|_1=\left (\gamma|+1\right )\cdot \left (|\gamma|+1\right )=\left (|\gamma|+1\right )^2$.
  
• \begin{equation*}\text{cond}_2(A) = \|A\|_2 \cdot \|A^{-1}\|_2\end{equation*}
  
  The norm is defined by \begin{equation*}\|A\|_2:=\max\left \{\sqrt{\lambda} : \lambda \text{ ist Eigenwert von } \overline{A}^TA\right \}\end{equation*} right? (Wondering)
  
  Since we have only real numbers, it is $\overline{A}^T=A^T$.
  
  We have that \begin{equation*}A^TA=\begin{pmatrix}1 & 0\\ \gamma & 1\end{pmatrix}\begin{pmatrix}1 & \gamma \\ 0 & 1\end{pmatrix}=\begin{pmatrix}1 & \gamma \\ \gamma & \gamma^2+1\end{pmatrix} \ \text{ and } \ (A^{-1})^TA^{-1}=\begin{pmatrix}1 & 0\\ -\gamma & 1\end{pmatrix}\begin{pmatrix}1 & -\gamma \\ 0 & 1\end{pmatrix}=\begin{pmatrix}1 & -\gamma \\ -\gamma & \gamma^2+1\end{pmatrix}\end{equation*}
  
  The eigenvalues are $\frac{\gamma^2-2\pm \sqrt{\gamma^4-4\gamma^2}}{2}$, or not? So is \begin{equation*}\|A\|_2=\|A^{-1}\|_2=\sqrt{\frac{\gamma^2-2+ \sqrt{\gamma^4-4\gamma^2}}{2}}\end{equation*} ? (Wondering)
• \begin{equation*}\text{cond}_{\infty}(A) = \|A\|_{\infty} \cdot \|A^{-1}\|_{\infty}\end{equation*}
  
  The norm is defined by \begin{equation*}\|A\|_{\infty}:=\max_{1\leq j\leq 2}\sum_{k=1}^2|a_{jk}|\end{equation*}
  
  We have the following norms: \begin{align*}&\|A\|_{\infty}=\max \{|1|+|\gamma|, |0|+|1|\}=\max\{1+|\gamma|, 1\}=1+|\gamma| \\ &\|A^{-1}\|_{\infty}=\max \{|1|+|-\gamma|, |0|+|1|\}=\max\{1+|\gamma|,1\}=1+|\gamma|\end{align*}
  
  So, the condition number is $\text{cond}_{\infty}(A) = \|A\|_{\infty} \cdot \|A^{-1}\|_{\infty}=\left (1+\gamma|\right )\cdot \left (1+|\gamma|\right )=\left (1+|\gamma|\right )^2$.

Then for $Ax=\begin{pmatrix}1+\delta_1 \\ 1+\delta_2\end{pmatrix}$ where $\delta_1, \delta_2$ are small errors, we have to discuss with $\|\cdot \|_{\infty}$ how $\gamma$ affects the relative error of the result $x$. Do we use here the relation \begin{equation*}\frac{\|\Delta x\|_{\infty}}{\|x\|_{\infty}}\leq \text{cond}_{\infty}(A)\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}\end{equation*} ? (Wondering)

 

[I like Serena]

• \begin{equation*}\text{cond}_2(A) = \|A\|_2 \cdot \|A^{-1}\|_2\end{equation*}
  
  The norm is defined by \begin{equation*}\|A\|_2:=\max\left \{\sqrt{\lambda} : \lambda \text{ ist Eigenwert von } \overline{A}^TA\right \}\end{equation*} right? (Wondering)

Hey mathmari!

That's an equivalent definition.
The proper definition is:
\begin{equation*}\|A\|_2:=\sup_{x\ne 0} \frac{\|Ax\|_2}{\|x\|_2}\end{equation*}
(Nerd)

• Since we have only real numbers, it is $\overline{A}^T=A^T$.
  
  We have that \begin{equation*}A^TA=\begin{pmatrix}1 & 0\\ \gamma & 1\end{pmatrix}\begin{pmatrix}1 & \gamma \\ 0 & 1\end{pmatrix}=\begin{pmatrix}1 & \gamma \\ \gamma & \gamma^2+1\end{pmatrix} \ \text{ and } \ (A^{-1})^TA^{-1}=\begin{pmatrix}1 & 0\\ -\gamma & 1\end{pmatrix}\begin{pmatrix}1 & -\gamma \\ 0 & 1\end{pmatrix}=\begin{pmatrix}1 & -\gamma \\ -\gamma & \gamma^2+1\end{pmatrix}\end{equation*}
  
  The eigenvalues are $\frac{\gamma^2-2\pm \sqrt{\gamma^4-4\gamma^2}}{2}$, or not? So is \begin{equation*}\|A\|_2=\|A^{-1}\|_2=\sqrt{\frac{\gamma^2-2+ \sqrt{\gamma^4-4\gamma^2}}{2}}\end{equation*} ?

Yep. (Nod)

Then for $Ax=\begin{pmatrix}1+\delta_1 \\ 1+\delta_2\end{pmatrix}$ where $\delta_1, \delta_2$ are small errors, we have to discuss with $\|\cdot \|_{\infty}$ how $\gamma$ affects the relative error of the result $x$. Do we use here the relation \begin{equation*}\frac{\|\Delta x\|_{\infty}}{\|x\|_{\infty}}\leq \text{cond}_{\infty}(A)\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}\end{equation*} ?

Yep. (Thinking)

 

[mathmari]

Hey mathmari!

That's an equivalent definition.
The proper definition is:
\begin{equation*}\|A\|_2:=\sup_{x\ne 0} \frac{\|Ax\|_2}{\|x\|_2}\end{equation*}
(Nerd)

We have that $$Ax=\begin{pmatrix}1 & \gamma \\ 0 & 1\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}=\begin{pmatrix}x_1+\gamma \ x_2 \\ x_2\end{pmatrix}$$
Then $$\|Ax\|_2=\sqrt{\left (x_1+\gamma \ x_2\right )^2+x_2^2} \ \text{ and } \ \||x\|_2=\sqrt{x_1^2+x_2^2}$$

So \begin{equation*}\|A\|_2:=\sup_{x\ne 0} \frac{\|Ax\|_2}{\|x\|_2}=\sup_{x\ne 0} \frac{\sqrt{\left (x_1+\gamma \ x_2\right )^2+x_2^2}}{\sqrt{x_1^2+x_2^2}}\end{equation*} Is everything correct so far? How could we continue? I got stuck right now. (Wondering)

Yep. (Thinking)

We have that $\text{cond}_{\infty}(A)=\left (1+|\gamma|\right )^2$. Do we get from $Ax$ that $b=\begin{pmatrix}1 \\ 1\end{pmatrix}$ and $\Delta b=\begin{pmatrix}1+\delta_1 \\ 1+\delta_2\end{pmatrix}$ ? If so, we have that $\|b\|_{\infty}=1$ and $\|\Delta b\|_{\infty}=\max \{1+\delta_1, 1+\delta_2\}$, right?

What do we get from that? (Wondering)

 

[I like Serena]

We have that $$Ax=\begin{pmatrix}1 & \gamma \\ 0 & 1\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}=\begin{pmatrix}x_1+\gamma \ x_2 \\ x_2\end{pmatrix}$$
Then $$\|Ax\|_2=\sqrt{\left (x_1+\gamma\right )^2+x_2^2} \ \text{ and } \ \||x\|_2=\sqrt{x_1^2+x_2^2}$$

So \begin{equation*}\|A\|_2:=\sup_{x\ne 0} \frac{\|Ax\|_2}{\|x\|_2}=\sup_{x\ne 0} \frac{\sqrt{\left (x_1+\gamma\right )^2+x_2^2}}{\sqrt{x_1^2+x_2^2}}\end{equation*} Is everything correct so far? How could we continue? I got stuck right now.

What you had was already correct.
The typical way to calculate $\|A\|_2$ is by taking the square root of the largest eigenvalue of $\overline A^T A$. (Thinking)After all, the definition you gave is equivalent.
The proof starts with:
\begin{equation*}\|Ax\|_2 = \sqrt{\overline{(Ax)}^T Ax} =\sqrt{\overline x^T \overline A^T A x}
=\sqrt{\overline x^T \left(\overline A^T A\right) x}\end{equation*}
The matrix $\overline A^T A$ is Hermitian, meaning we can diagonalize it as $VD\overline V^T$, where $D$ is a diagonal matrix with real values on its diagonal, and $V$ is a unitary matrix that consists of the normalized eigenvectors (Spectral theorem).
Taking this forward we will find that those definitions are indeed equivalent, and it gives us a method to calculate $\|A\|_2$.
(Nerd)

We have that $\text{cond}_{\infty}(A)=\left (1+|\gamma|\right )^2$. Do we get from $Ax$ that $b=\begin{pmatrix}1 \\ 1\end{pmatrix}$ and $\Delta b=\begin{pmatrix}1+\delta_1 \\ 1+\delta_2\end{pmatrix}$ ? If so, we have that $\|b\|_{\infty}=1$ and $\|\Delta b\|_{\infty}=\max \{1+\delta_1, 1+\delta_2\}$, right?

What do we get from that?

That should be $\|\Delta b\|_{\infty}=\max \{|\delta_1|, |\delta_2|\}$, shouldn't it?

Can we solve $x$ from $Ax=b$? And find its norm as well? (Wondering)

 

[mathmari]

What you had was already correct.
The typical way to calculate $\|A\|_2$ is by taking the square root of the largest eigenvalue of $\overline A^T A$. (Thinking)

Ah ok! So the condition number is equal to $\frac{\gamma^2-2+ \sqrt{\gamma^4-4\gamma^2}}{2}$, isn't it? (Wondering)

After all, the definition you gave is equivalent.
The proof starts with:
\begin{equation*}\|Ax\|_2 = \sqrt{\overline{(Ax)}^T Ax} =\sqrt{\overline x^T \overline A^T A x}
=\sqrt{\overline x^T \left(\overline A^T A\right) x}\end{equation*}
The matrix $\overline A^T A$ is Hermitian, meaning we can diagonalize it as $VD\overline V^T$, where $D$ is a diagonal matrix with real values on its diagonal, and $V$ is a unitary matrix that consists of the normalized eigenvectors (Spectral theorem).
Taking this forward we will find that those definitions are indeed equivalent, and it gives us a method to calculate $\|A\|_2$.
(Nerd)

Ahh ok! (Nerd)

That should be $\|\Delta b\|_{\infty}=\max \{|\delta_1|, |\delta_2|\}$, shouldn't it?

Oh yes, you're right!

Can we solve $x$ from $Ax=b$? And find its norm as well? (Wondering)

We have that $$x=A^{-1}b=\begin{pmatrix}1 & -\gamma \\ 0 & 1\end{pmatrix}\begin{pmatrix}1 \\ 1\end{pmatrix}=\begin{pmatrix} 1-\gamma\\ 1\end{pmatrix}$$

Therefore $\|x\|_{\infty}=\max \{|1-\gamma|, 1\}$, right? (Wondering)

We have that $\|\Delta x\|_{\infty}\leq \text{cond}_{\infty}(A)\cdot \|x\|_{\infty}\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}=\left (1+|\gamma|\right )^2\cdot \max \{|1-\gamma|, 1\}\cdot \max \{|\delta_1|, |\delta_2|\}$ .

How could we continue? Do we just say that this is an upper bound of the relative error that it dependent of $\gamma$ ? (Wondering)

 

[I like Serena]

Ah ok! So the condition number is equal to $\frac{\gamma^2-2+ \sqrt{\gamma^4-4\gamma^2}}{2}$, isn't it?

Yes... although... shouldn't it be $\frac{\gamma^2+2+ \sqrt{\gamma^4+4\gamma^2}}{2}$?
I think that's what the biggest eigenvalue is. (Thinking)

We have that $$x=A^{-1}b=\begin{pmatrix}1 & -\gamma \\ 0 & 1\end{pmatrix}\begin{pmatrix}1 \\ 1\end{pmatrix}=\begin{pmatrix} 1-\gamma\\ 1\end{pmatrix}$$

Therefore $\|x\|_{\infty}=\max \{|1-\gamma|, 1\}$, right? (Wondering)

We have that $\|\Delta x\|_{\infty}\leq \text{cond}_{\infty}(A)\cdot \|x\|_{\infty}\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}=\left (1+|\gamma|\right )^2\cdot \max \{|1-\gamma|, 1\}\cdot \max \{|\delta_1|, |\delta_2|\}$ .

How could we continue?

How about splitting cases?
Case 1: $|1-\gamma| \le 1$.
Case 2: $|1-\gamma| > 1$.
(Thinking)

 

[mathmari]

Yes... although... shouldn't it be $\frac{\gamma^2+2+ \sqrt{\gamma^4+4\gamma^2}}{2}$?
I think that's what the biggest eigenvalue is. (Thinking)

Ah yes!
If we want to try the definition with the supremum, how can we find that? (Wondering)

How about splitting cases?
Case 1: $|1-\gamma| \le 1$.
Case 2: $|1-\gamma| > 1$.
(Thinking)

Is the relative error $\|\Delta x\|_{\infty}$ or $\frac{\|\Delta x\|_{\infty}}{\|x\|_{\infty}}$ ? (Wondering) Case 1: $\|\Delta x\|_{\infty}\leq \text{cond}_{\infty}(A)\cdot \|x\|_{\infty}\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}=\left (1+|\gamma|\right )^2\cdot \max \{|\delta_1|, |\delta_2|\} $

Case 2: $\|\Delta x\|_{\infty}\leq \text{cond}_{\infty}(A)\cdot \|x\|_{\infty}\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}=\left (1+|\gamma|\right )^2\cdot (|1-\gamma|)\cdot \max \{|\delta_1|, |\delta_2|\}$

What do we get from that? (Wondering)

 

[I like Serena]

If we want to try the definition with the supremum, how can we find that?

Let's see...

Method 1:
$$\|Ax\|_2 = \sup_{x\ne 0}\frac{\|Ax\|}{\|x\|} = \sup_{\|x\|= 1}\|Ax\| = \sqrt{\sup_{\|x\|= 1}\|Ax\|^2}
= \sqrt{\sup_{x^2+y^2= 1}((x+\gamma y)^2 + y^2)} \\
= \sqrt{\sup_{x^2+y^2= 1}(x^2+2\gamma xy + \gamma^2y^2 + y^2)}
= \sqrt{\sup_{x^2+y^2= 1}(\gamma^2y^2+2\gamma xy + 1)}
$$
We can find $\sup\limits_{x^2+y^2= 1}(\gamma^2y^2+2\gamma xy + 1)$ with Lagrange Multipliers can't we? (Thinking)

Method 2:
$$\|Ax\|_2 = \sup_{x\ne 0}\frac{\|Ax\|}{\|x\|} = \sup_{\|x\|= 1}\|Ax\| = \sqrt{\sup_{\|x\|= 1}\|Ax\|^2}
= \sqrt{\sup_{\|x\|= 1}(Ax)^TAx}
= \sqrt{\sup_{\|x\|= 1}x^T (A^T A) x} \\
= \sqrt{\sup_{\|x\|= 1}x^T V D V^T x}
= \sqrt{\sup_{\|x\|= 1}(V^T x)^T D (V^T x)}
= \sqrt{\sup_{\|y\|= 1}y^T D y}
= \sqrt{\sup_{\|y\|= 1}(\lambda_1 y_1^2 + \lambda_2 y_2^2)}
$$
where $D$ is a diagonal matrix with the eigenvalues $\lambda_1 \ge \lambda_2 \ge 0$ of $(A^TA)$ that you already found on its diagonal, and where $V$ is the corresponding matrix of normalized eigenvectors.

The expression reaches the supremum when $y_1=1$ and $y_2=0$ doesn't it? (Wondering)

Is the relative error $\|\Delta x\|_{\infty}$ or $\frac{\|\Delta x\|_{\infty}}{\|x\|_{\infty}}$ ?

$\|\Delta x\|$ is called the absolute error and $\frac{\|\Delta x\|}{\|x\|}$ is called the relative error.

Case 1: $\|\Delta x\|_{\infty}\leq \text{cond}_{\infty}(A)\cdot \|x\|_{\infty}\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}=\left (1+|\gamma|\right )^2\cdot \max \{|\delta_1|, |\delta_2|\} $

Case 2: $\|\Delta x\|_{\infty}\leq \text{cond}_{\infty}(A)\cdot \|x\|_{\infty}\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}=\left (1+|\gamma|\right )^2\cdot (|1-\gamma|)\cdot \max \{|\delta_1|, |\delta_2|\}$

What do we get from that?

I'd write it as:
\begin{cases}\|\Delta x\|_{\infty}\leq \left (1+|\gamma|\right )^3\cdot \|\Delta b\|_{\infty} & \text{if } \gamma < 0 \\
\|\Delta x\|_{\infty}\leq \left (1+|\gamma|\right )^2\cdot \|\Delta b\|_{\infty} & \text{if } 0\le \gamma\le 2 \\
\|\Delta x\|_{\infty}\leq \left (\gamma + 1\right )^2\left (\gamma - 1\right )\cdot \|\Delta b\|_{\infty} & \text{if } \gamma > 2 \\
\end{cases}
I didn't make a mistake did I? (Wondering)

It shows that the absolute error in the solution $x$ increases with $|\gamma|^3$ with respect to the absolute error in $b$ for sufficiently large positive and negative numbers.
It increases with $(1+|\gamma|)^3$ for negative numbers.
And with $(1+|\gamma|)^2$ for small positive numbers (smaller than $2$).

 

[mathmari]

$\|\Delta x\|$ is called the absolute error and $\frac{\|\Delta x\|}{\|x\|}$ is called the relative error.

I'd write it as:
\begin{cases}\|\Delta x\|_{\infty}\leq \left (1+|\gamma|\right )^3\cdot \|\Delta b\|_{\infty} & \text{if } \gamma < 0 \\
\|\Delta x\|_{\infty}\leq \left (1+|\gamma|\right )^2\cdot \|\Delta b\|_{\infty} & \text{if } 0\le \gamma\le 2 \\
\|\Delta x\|_{\infty}\leq \left (\gamma + 1\right )^2\left (\gamma - 1\right )\cdot \|\Delta b\|_{\infty} & \text{if } \gamma > 2 \\
\end{cases}
I didn't make a mistake did I? (Wondering)

It shows that the absolute error in the solution $x$ increases with $|\gamma|^3$ with respect to the absolute error in $b$ for sufficiently large positive and negative numbers.
It increases with $(1+|\gamma|)^3$ for negative numbers.
And with $(1+|\gamma|)^2$ for small positive numbers (smaller than $2$).

Ahh ok!

So from \begin{equation*}\frac{\|\Delta x\|_{\infty}}{\|x\|_{\infty}}\leq \left (1+|\gamma|\right )^2\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}\end{equation*} we get that the relative error in the solution $x$ increases with $\gamma^2$ with respect to the relatve error in $b$, right? (Wondering)

 

[I like Serena]

Ahh ok!

So from \begin{equation*}\frac{\|\Delta x\|_{\infty}}{\|x\|_{\infty}}\leq \left (1+|\gamma|\right )^2\cdot \frac{\|\Delta b\|_{\infty}}{\|b\|_{\infty}}\end{equation*} we get that the relative error in the solution $x$ increases with $\gamma^2$ with respect to the relatve error in $b$, right?

For sufficiently large $|\gamma|$ yes. (Nod)
For small $|\gamma|$ it increases linearly.