System of equations - Relative error

[mathmari]

We have the linear system of equations $Ax=b$ with \begin{equation*}A=\begin{pmatrix}0 & 1 & 1 \\ 0.5 & 1.0001 & 3 \\ 1 & 2 & 4\end{pmatrix} \ \ \ \text{ und } \ \ \ b=\begin{pmatrix}2 \\ 3 \\ 4\end{pmatrix}\end{equation*}

First, I want to calculate the solution using the Gauss algorithm with complete pivoting, with accuracy $\text{eps}=5\cdot 10^{-5}$ and floating-point arithmetic with $4$ decimal places.

I have done the following:

The maximal element of the matrix is $a_{3,3}$. We exchange the first and the last column and the first and last row (we make also the respective changes at the vector x and b)

So, we have the following:
\begin{align*}\begin{bmatrix}
\left.\begin{matrix}
4 & 2 & 1 \\
3 & 1.0001 & 0.5 \\
1 & 1 & 0
\end{matrix}\right| \begin{matrix}
4 \\ 3 \\ 2
\end{matrix}
\end{bmatrix} \ \overset{ 2.\text{Row } : \ 2.\text{Row } - \frac{3}{4}\cdot 1.\text{Row}}{ \longrightarrow } &\begin{bmatrix}
\left.\begin{matrix}
4 & 2 & 1 \\
0 & -0.4999 & -0.25 \\
1 & 1 & 0
\end{matrix}\right| \begin{matrix}
4 \\ 0 \\ 2
\end{matrix}
\end{bmatrix}\ \\ \overset{ 3.\text{Row } : \ 3.\text{Row } -\frac{1}{4}\cdot 1.\text{Row}}{ \longrightarrow } &\begin{bmatrix}
\left.\begin{matrix}
4 & 2 & 1 \\
0 & -0.4999 & -0.25 \\
0 & \frac{1}{2} & -\frac{1}{4}
\end{matrix}\right| \begin{matrix}
4 \\ 0 \\ 1
\end{matrix}
\end{bmatrix} \ \\ \overset{ 3.\text{Row } : \ 4\cdot 3.\text{Row } }{ \longrightarrow } &\begin{bmatrix}
\left.\begin{matrix}
4 & 2 & 1 \\
0 & -0.4999 & -0.25 \\
0 & 2 & -1
\end{matrix}\right| \begin{matrix}
4 \\ 0 \\ 4
\end{matrix}
\end{bmatrix} \ \\ \overset{ 3.\text{Row } : \ 3.\text{Zeile }+\frac{2}{0.4999}\cdot 2.\text{Row }}{ \longrightarrow } &\begin{bmatrix}
\left.\begin{matrix}
4 & 2 & 1 \\
0 & -0.4999 & -0.25 \\
0 & 0 & -2.0002
\end{matrix}\right| \begin{matrix}
4 \\ 0 \\ 4
\end{matrix}
\end{bmatrix} \end{align*}

So, we get the equations:
\begin{align*}4x_3+2x_2+x_1 & = 4 \\ -0.4999x_2 -0.25 x_1 &=0 \\ -2.0002x_1 &= 4\end{align*}

From the last equation we get $x_1=-\frac{4}{2.0002}\approx -1.9998$.

From the second equationwe get $-0.4999x_2 =0.25 x_1 \Rightarrow -0.4999x_2 =0.25 \cdot \left (-1.9998\right )\Rightarrow -0.4999x_2 =-0.5000 \Rightarrow x_2=\frac{0.5000}{0.4999}\Rightarrow x_2\approx 1.0002$.

From the first equation we get $4x_3 = 4-2x_2-x_1 \Rightarrow 4x_3 = 4-2\cdot 1.0002-\left (-1.9998\right )\Rightarrow 4x_3 = 4-2.0004+1.9998\Rightarrow 4x_3 = 3.9994\Rightarrow x_3\approx 0.9999$.

So we get the solution \begin{equation*}x=\begin{pmatrix}-1.9998 \\ 1.0002 \\ 0.9999\end{pmatrix}\end{equation*}

The exact solution is (according to Wolfram) \begin{equation*}x=\begin{pmatrix}-1.9998\ldots \\ 1.0001\ldots \\ 0.9999\ldots\end{pmatrix}\end{equation*} To check the accuracy of $\text{eps}=5\cdot 10^{-5}$ do we have to calculate the difference between the exact solution and the solution that we found? (Wondering)
I also have to calculate an estimate of the relative error using the condition number in respect of $\|\cdot \|_{\infty}$.

Do we have to use forthat the following inequality?
\begin{equation*}\frac{\|\delta x\|}{\|x\|}\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\left (\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right )\end{equation*}

(Wondering)

 

[I like Serena]

To check the accuracy of $\text{eps}=5\cdot 10^{-5}$ do we have to calculate the difference between the exact solution and the solution that we found?

Hey mathmari! (Smile)

I think that is indeed what we'd supposed to be doing.

I also have to calculate an estimate of the relative error using the condition number in respect of $\|\cdot \|_{\infty}$.

Do we have to use forthat the following inequality?
\begin{equation*}\frac{\|\delta x\|}{\|x\|}\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\left (\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right )\end{equation*}

Yep. I think so.
And afterwards, we can compare the result with the $\delta x$ we found in the previous question. (Thinking)

 

[mathmari]

I think that is indeed what we'd supposed to be doing.

We have that $x-\tilde{x}=\begin{pmatrix}-1.9998\ldots \\ 1.0001\ldots \\ 0.9999\ldots\end{pmatrix}-\begin{pmatrix}-1.9998 \\ 1.0002 \\ 0.9999\end{pmatrix}$

To find the difference should we have more digits at the exact solution, or not? So, do we have to calculate it with Matlab for example? (Wondering)

Or do we have to calculate $A\tilde{x}-b$ ? (Wondering)

Yep. I think so.
And afterwards, we can compare the result with the $\delta x$ we found in the previous question. (Thinking)

How can we calculate $\frac{\|\delta b\|}{\|b\|}$ and $\frac{\|\delta A\|}{\|A\|}$ ? (Wondering)

 

[I like Serena]

We have that $x-\tilde{x}=\begin{pmatrix}-1.9998\ldots \\ 1.0001\ldots \\ 0.9999\ldots\end{pmatrix}-\begin{pmatrix}-1.9998 \\ 1.0002 \\ 0.9999\end{pmatrix}$

To find the difference should we have more digits at the exact solution, or not? So, do we have to calculate it with Matlab for example? (Wondering)

Or do we have to calculate $A\tilde{x}-b$ ?

That wouldn't give us the error in $x$ would it?
I think the most straight forward way is to indeed use e.g. Matlab.

How can we calculate $\frac{\|\delta b\|}{\|b\|}$ and $\frac{\|\delta A\|}{\|A\|}$ ? (Wondering)

$\|\delta b\|_\infty$ is the maximum absolute value of the elements in $\delta b$ isn't it?
Can we give an upper bound for it? (Wondering)

 

[mathmari]

That wouldn't give us the error in $x$ would it?
I think the most straight forward way is to indeed use e.g. Matlab.

Ah ok!

$\|\delta b\|_\infty$ is the maximum absolute value of the elements in $\delta b$ isn't it?
Can we give an upper bound for it? (Wondering)

But do we have the vector $\delta b$ ? (Wondering)

 

[I like Serena]

But do we have the vector $\delta b$ ? (Wondering)

Nope. But we don't need it to find an upper bound of $\|\delta b\|_\infty$ do we? (Wondering)
That is assuming that $b$ is as accurate as possible within the given precision.

 

[mathmari]

Nope. But we don't need it to find an upper bound of $\|\delta b\|_\infty$ do we? (Wondering)
That is assuming that $b$ is as accurate as possible within the given precision.

Does it hold that $\|\delta b\|_{\infty}<\text{eps}$ ? (Wondering)

 

[I like Serena]

Does it hold that $\|\delta b\|_{\infty}<\text{eps}$ ? (Wondering)

Nitpick: I'd make it $\|\delta b\|_{\infty}\le\text{eps}$.
That's because if the first element was for instance really $2-\text{eps}=1.99995$, it would still be rounded to $2$, wouldn't it? (Nerd)

 

[mathmari]

Nitpick: I'd make it $\|\delta b\|_{\infty}\le\text{eps}$.
That's because if the first element was for instance really $2-\text{eps}=1.99995$, it would still be rounded to $2$, wouldn't it? (Nerd)

Ah ok!

The same holds also for $A$, i.e. $\frac{\|\delta A\|}{\|A\|}\le\text{eps}$, or not? Then we have that \begin{align*}\frac{\|\delta x\|}{\|x\|}&\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\left (\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right ) \\ & \leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\left (\text{eps}+\text{eps}\right ) \\ & \leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\cdot 2\text{eps} \end{align*}
What about $\frac{\|\delta A\|}{\|A\|}$ in the denominator? (Wondering)

 

[I like Serena]

Ah ok!

The same holds also for $A$, i.e. $\frac{\|\delta A\|}{\|A\|}\le\text{eps}$, or not?

Isn't $\|\delta A\|_\infty$ slightly different since it's about a matrix?
What was the definition again?

Separately from that, don't we still need to calculate both $\|b\|_\infty$ and $\|A\|_\infty$? (Thinking)

 

[mathmari]

Isn't $\|\delta A\|_\infty$ slightly different since it's about a matrix?
What was the definition again?

It is $\|\delta A\|_{\infty}=\max_{i=1}^n\sum_{j=1}^n|\tilde{a}_{i,j}|$, where $\delta A=(\tilde{A}_{i,j})$.

Why is this different, I haven't really understood that. Could you explain it further to me? (Wondering)

Separately from that, don't we still need to calculate both $\|b\|_\infty$ and $\|A\|_\infty$? (Thinking)

We have that $\|b\|_\infty=\max_{i=1}^n|b_i|=4$ and $\|A\|_\infty=\max_{i=1}^n\sum_{j=1}^n|a_{i,j}|=\max \{2, 4.5001, 7\}=7$, right? (Wondering)

 

[I like Serena]

It is $\|\delta A\|_{\infty}=\max_{i=1}^n\sum_{j=1}^n|\tilde{a}_{i,j}|$, where $\delta A=(\tilde{A}_{i,j})$.

Why is this different, I haven't really understood that. Could you explain it further to me?

Each $a_{ij}$ has a $|\delta a_{ij}|\le\text{eps}$ doesn't it?
And we add $n$ of them togerther.
So shouldn't we have $\|\delta A\|_{\infty}\le n\operatorname{eps}$? (Wondering)

We have that $\|b\|_\infty=\max_{i=1}^n|b_i|=4$ and $\|A\|_\infty=\max_{i=1}^n\sum_{j=1}^n|a_{i,j}|=\max \{2, 4.5001, 7\}=7$, right? (Wondering)

Yep. (Nod)

 

[mathmari]

Ah ok!

So, we have
\begin{align*}\frac{\|\delta x\|}{\|x\|}&\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\left (\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right ) \\ &\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{7}}\left (\frac{\text{eps}}{4}+\frac{n\cdot \text{eps}}{7}\right ) \end{align*}

But what about with $\|\delta A\|$ at the denominator? (Wondering)

 

[I like Serena]

So, we have
\begin{align*}\frac{\|\delta x\|}{\|x\|}&\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\left (\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right ) \\ &\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{7}}\left (\frac{\text{eps}}{4}+\frac{n\cdot \text{eps}}{7}\right ) \end{align*}

But what about with $\|\delta A\|$ at the denominator?

Isn't that $n\cdot\text{eps}=3\cdot\text{eps}$ as well? (Wondering)

 

[mathmari]

Ah yes!

We also have that $\text{eps}=5\cdot 10^{-5}$.

We have that $\|A\|_{\infty}=7$.

The inverse matrix is (with for decimal places)
\begin{equation*}A^{-1}=\begin{pmatrix}-1.9998 & -2.0002 & 2.0001 \\ 1.0001 & -1.0001 & 0.5001 \\ -0.0001 & 1.0001 & -0.5001\end{pmatrix}\end{equation*}

So, \begin{equation*}\|A^{-1}\|=\max \{|-1.9998 |+| -2.0002 |+| 2.0001|, |1.0001 |+| -1.0001 |+| 0.5001|, |-0.0001 |+| 1.0001 |+|-0.5001|\}=\max \{6.0001, 2.5003, 1.5003\}=6.0001\end{equation*}

The condition number is defined as $ \operatorname{cond}_{\infty}(A)=\|A\|_{\infty}\, \|A^{-1}\|_{\infty}=7\cdot 6.0001=42.0007$.

So, we get:
\begin{align*}\frac{\|\delta x\|}{\|x\|}&\leq \frac{\operatorname{cond}(A)}{1-\operatorname{cond}(A)\frac{\|\delta A\|}{\|A\|}}\left (\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right ) \\ &\leq \frac{42.0007}{1-42.0007\frac{\|\delta A\|}{7}}\left (\frac{5\cdot 10^{-5}}{4}+\frac{15\cdot 10^{-5}}{7}\right ) \\ & = \frac{42.0007}{1-42.0007\frac{\|\delta A\|}{7}}\cdot \frac{95\cdot 10^{-5}}{28} \\ & = \frac{0.00142502375}{1-6.0001 \|\delta A\|}\end{align*}

Since $\|\delta A\|_{\infty}\le 3\operatorname{eps}=3\cdot 5\cdot 10^{-5}=15\cdot 10^{-5}$ then \begin{align*}6.0001 \|\delta A\|\leq 6.0001\cdot 15\cdot 10^{-5}&\Rightarrow 6.0001 \|\delta A\|\leq 9.00015 \cdot 10^{-4}\\ & \Rightarrow -6.0001 \|\delta A\|\geq -9.00015 \cdot 10^{-4}\\ & \Rightarrow 1-6.0001 \|\delta A\|\geq 1-9.00015 \cdot 10^{-4}\\ & \Rightarrow 1-6.0001 \|\delta A\|\geq 0.999099985 \\ & \Rightarrow \frac{1}{1-6.0001 \|\delta A\|}\leq \frac{1}{0.999099985}\\ & \Rightarrow \frac{0.00142502375}{1-6.0001 \|\delta A\|}\leq \frac{0.00142502375}{0.999099985}\approx 0.00142631\end{align*}
That means that the relative is $\frac{\|\delta x\|}{\|x\|}\leq 0.00142631$, right? (Wondering)

 

[I like Serena]

That means that the relative is $\frac{\|\delta x\|}{\|x\|}\leq 0.00142631$, right? (Wondering)

Yep. That looks correct to me. (Nod)

Do note that we're measuring 2 different things here.
Calculating $\frac{\|\delta x\|}{\|x\|}$ using Matlab yields the relative error due to rounding errors when using full pivot Gaussian elimination, and it assumes that $\delta A = 0$ and $\delta b = 0$.
Calculating $\frac{\|\delta x\|}{\|x\|}$ using the condition number of the matrix as we did, calculates how rounding errors in $A$ and $b$ propagate while assuming that there are no rounding errors during the algorithm to solve the system.
So we would need to add them together to estimate the full relative error. (Thinking)

 

[mathmari]

Ah ok! Thank you! (flower)