# Upper bound of the relative error

#### evinda

##### Well-known member
MHB Site Helper
Hello!!!
I am looking at the following exercise:
Let the linear system $Ax=b$ with $\begin{pmatrix} 2.001 & 2\\ 2& 2 \end{pmatrix}$
,$b=\begin{bmatrix} 2.001 &2 \end{bmatrix}^T$ and y an approximate solution,so that $Ay-b=\begin{bmatrix} 0.001 &0 \end{bmatrix}^T$ .Find an upper bound of the relative error $\frac{||x-y||_{1}}{||x||_{1}}$ .

I found that it is equal to 2,could you tell me if it is right?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hello!!!
I am looking at the following exercise:
Let the linear system $Ax=b$ with $\begin{pmatrix} 2.001 & 2\\ 2& 2 \end{pmatrix}$
,$b=\begin{bmatrix} 2.001 &2 \end{bmatrix}^T$ and y an approximate solution,so that $Ay-b=\begin{bmatrix} 0.001 &0 \end{bmatrix}^T$ .Find an upper bound of the relative error $\frac{||x-y||_{1}}{||x||_{1}}$ .

I found that it is equal to 2,could you tell me if it is right?
Hi!!

The actual result is $\frac{||x-y||_{1}}{||x||_{1}} = 2$.
But assuming we're not supposed to use the solution for $x$ and $y$, I get an upper bound of $2.001$.

#### evinda

##### Well-known member
MHB Site Helper
Hi!!

The actual result is $\frac{||x-y||_{1}}{||x||_{1}} = 2$.
But assuming we're not supposed to use the solution for $x$ and $y$, I get an upper bound of $2.001$.
How can we find the upper bound,without using the values of $x$ and $y$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
How can we find the upper bound,without using the values of $x$ and $y$ ?
By using the condition number of the matrix.
$$\text{cond}_1(A) = ||A||_1 \cdot ||A^{-1}||_1$$
Can it be that it is in your notes?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
By using the condition number of the matrix.
$$\text{cond}_1(A) = ||A||_1 \cdot ||A^{-1}||_1$$
Can it be that it is in your notes?
To elaborate:
$$\frac{||\Delta x||_1}{||x||_1} \le \text{cond}_1(A) \frac{||\Delta b||_1}{||b||_1}$$

#### evinda

##### Well-known member
MHB Site Helper
To elaborate:
$$\frac{||\Delta x||_1}{||x||_1} \le \text{cond}_1(A) \frac{||\Delta b||_1}{||b||_1}$$
We use $\frac{||\Delta x||_1}{||x||_1} \le \text{cond}_1(A) \frac{||\Delta b||_1}{||b||_1}$,if we have a derangment of $x$ and $b$.Right?But...is there a derangment of $b$ in this case??

#### Klaas van Aarsen

##### MHB Seeker
Staff member
We use $\frac{||\Delta x||_1}{||x||_1} \le \text{cond}_1(A) \frac{||\Delta b||_1}{||b||_1}$,if we have a derangment of $x$ and $b$.Right?But...is there a derangment of $b$ in this case??
Huh? How are derangements involved??
What do you think a derangement is?

When $Ax=b$, then $\frac{||\Delta x||_1}{||x||_1} \le \text{cond}_1(A) \frac{||\Delta b||_1}{||b||_1}$ applies.

#### evinda

##### Well-known member
MHB Site Helper
Huh? How are derangements involved??
What do you think a derangement is?

When $Ax=b$, then $\frac{||\Delta x||_1}{||x||_1} \le \text{cond}_1(A) \frac{||\Delta b||_1}{||b||_1}$ applies.
Could I also do this like that: $\frac{||x-y||}{||x||}=\frac{||A^{-1}Ay-A^{-1}b||}{||x||}=\frac{||A^{-1}r||}{||x||}$ or would this be wrong?

- - - Updated - - -

Huh? How are derangements involved??
What do you think a derangement is?

When $Ax=b$, then $\frac{||\Delta x||_1}{||x||_1} \le \text{cond}_1(A) \frac{||\Delta b||_1}{||b||_1}$ applies.
Don't we ue this formula if b and x change??

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Could I also do this like that: $\frac{||x-y||}{||x||}=\frac{||A^{-1}Ay-A^{-1}b||}{||x||}=\frac{||A^{-1}r||}{||x||}$ or would this be wrong?
That is correct... but it doesn't get us where we need to go...

Note that $||\Delta x|| = ||x - y||$, which is the error in $x$.
And that $||\Delta b|| = || Ay - b ||$, the error in $b$.

- - - Updated - - -
Don't we ue this formula if b and x change??
Huh??

#### evinda

##### Well-known member
MHB Site Helper
That is correct... but it doesn't get us where we need to go...

Note that $||\Delta x|| = ||x - y||$, which is the error in $x$.
And that $||\Delta b|| = || Ay - b ||$, the error in $b$.

I understand now!!!! I applied the formula you said me and I found that the relative error is $\leq 2.0005$.Have you found the same??

#### Klaas van Aarsen

##### MHB Seeker
Staff member
I understand now!!!! I applied the formula you said me and I found that the relative error is $\leq 2.0005$.Have you found the same??
Yes!

#### evinda

##### Well-known member
MHB Site Helper
Great!!!Thank you very much!!!!