Welcome to our community

Be a part of something great, join today!

Upper bound of the relative error

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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
Mar 5, 2012
8,780
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
Apr 13, 2013
3,720
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$ ? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
How can we find the upper bound,without using the values of $x$ and $y$ ? :confused:
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? :rolleyes:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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? :rolleyes:
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
Apr 13, 2013
3,720
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?? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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?? :confused:
Huh? How are derangements involved?? :confused:
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
Apr 13, 2013
3,720
Huh? How are derangements involved?? :confused:
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?? :confused:
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?? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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?? :confused:
Huh?? :confused:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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
Mar 5, 2012
8,780
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! (Nod)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720