MHB Condition number - Relative error

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Mathematics news on Phys.org
mathmari said:
  • \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)

mathmari said:
  • 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)

mathmari said:
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)
 
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
 
Last edited by a moderator:
mathmari said:
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)
mathmari said:
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)
 
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)

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

Oh yes, you're right!
Klaas van Aarsen said:
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)
 
Last edited by a moderator:
mathmari said:
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)

mathmari said:
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)
 
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
 
mathmari said:
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)
mathmari said:
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.
mathmari said:
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$).
 
Klaas van Aarsen said:
$\|\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)
 
  • #10
mathmari said:
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.
 

Similar threads

Replies
4
Views
1K
Replies
42
Views
4K
Replies
16
Views
4K
Replies
21
Views
4K
Replies
9
Views
5K
Replies
5
Views
2K
Replies
1
Views
1K
Replies
10
Views
2K
Back
Top