Condition number - Relative error

In summary, the conversation discusses calculating condition numbers for a given matrix and how it affects the relative error of the result. The condition number is found to be dependent on the norm, with different norms resulting in different condition numbers. The conversation also touches on finding the norm of a matrix and solving for x in the equation Ax=b.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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
  • #2
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)
 
  • #3
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:
  • #4
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)
 
  • #5
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:
  • #6
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)
 
  • #7
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)
 
  • #8
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$).
 
  • #9
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.
 

Related to Condition number - Relative error

1. What is the condition number of a matrix?

The condition number of a matrix is a measure of the sensitivity of the solution to small changes in the input. It is calculated as the ratio of the largest singular value to the smallest singular value of the matrix.

2. How does the condition number relate to the accuracy of a solution?

The condition number is inversely proportional to the accuracy of a solution. A higher condition number indicates a more ill-conditioned problem, meaning small changes in the input can result in large changes in the output.

3. What is the relative error in a solution?

The relative error in a solution is a measure of the difference between the true solution and the approximate solution. It is usually calculated as the ratio of the norm of the error to the norm of the true solution.

4. How does the relative error change with the condition number?

The relative error tends to increase with the condition number. As the condition number increases, the accuracy of the solution decreases, resulting in a larger relative error.

5. How can the condition number and relative error be used to evaluate the stability of a problem?

The condition number and relative error can be used as indicators of the stability of a problem. A smaller condition number and lower relative error indicate a more well-conditioned and stable problem, while a larger condition number and higher relative error suggest an ill-conditioned and potentially unstable problem.

Similar threads

  • General Math
Replies
4
Views
899
  • General Math
2
Replies
42
Views
3K
  • General Math
Replies
16
Views
3K
Replies
1
Views
771
  • General Math
Replies
21
Views
4K
Replies
3
Views
999
Replies
9
Views
4K
  • General Math
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
453
  • General Math
Replies
10
Views
2K
Back
Top