MHB Upper bound of the relative error

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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?
 
Mathematics news on Phys.org
evinda said:
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$.
 
I like Serena said:
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:
 
evinda said:
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:
 
I like Serena said:
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}$$
 
I like Serena said:
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:
 
evinda said:
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.
 
I like Serena said:
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 - - -

I like Serena said:
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:
 
evinda said:
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:
 
  • #10
I like Serena said:
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??
 
  • #11
evinda said:
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)
 
  • #12
I like Serena said:
Yes! (Nod)

Great!Thank you very much! :)
 
Back
Top