Upper bound of the relative error

[evinda]

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?

 

[I like Serena]

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]

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$ ?

 

[I like Serena]

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?

 

[I like Serena]

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]

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??

 

[I like Serena]

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]

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??

 

[I like Serena]

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]

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??

 

[I like Serena]

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]

Yes! (Nod)

Great!Thank you very much! :)