1
$\begingroup$

Problem statement

The linear system $A\vec{x}=\vec{b}$, where $$A_{(n\times n)}=\begin{bmatrix} 1 &-1 &\dots &\dots &-1 \\ 0& 1 &-1 &... &-1 \\ \vdots & \ddots &\ddots &\vdots &\vdots \\ \vdots & \dots & \ddots & 1&-1 \\ 0&0 &0 &0 & 1 \end{bmatrix}$$

$$\vec{x}= \begin{bmatrix} x_1\\ x_1\\ \vdots\\ x_{n-1}\\ x_{n}\\ \end{bmatrix}$$

$$\vec{b}=\begin{bmatrix} 1\\ 0\\ \vdots\\ 0\\ 0\\ \end{bmatrix}$$

where $A$ is upper triangular, has all $+1$ in the diagonal, and $-1$ above the diagonal, is perturbed by $0<\epsilon<1$ such that $A$ remains the same but $\vec{b}$ is now

$$\vec{b}_\epsilon=\begin{bmatrix} 1\\ 0\\ \vdots\\ 0\\ \epsilon\\ \end{bmatrix}$$

so that $\vec{x}_\epsilon$ is the solution to the perturbed linear system.

Question: What is the relative error $\frac{\Vert \vec{x}-\vec{x_\epsilon} \Vert_\infty}{\Vert \vec{x}_\infty\Vert}$?

My solution:

$$x_N = \epsilon$$

$$x_{N-1} = \epsilon$$

$$x_{N-2} = 2\epsilon$$

$$x_{N-2} = 4\epsilon$$

$$x_{N-4} = 8\epsilon$$

$$x_{N-5} = 16\epsilon$$

$$\vdots$$

$$x_{N-i} = 2^{i-1}\epsilon$$

$$\vdots$$

$$x_3=2^{N-3}\epsilon$$

$$x_4=2^{N-4}\epsilon$$

Thus $x_1-x_2-x_3-...-x_N=1$ implies that $x_1 = 1+ (2^{N-2}+2^{N-3}+...2^{N-3}+2+1+1)\epsilon$, which in turn implies that $x_1=1+4(2^{N-4}+2^{N-5}+...+1)\epsilon$.

Now, [calculation (*)]:

$(2^{N-4}+2^{N-5}+...+1)=2^N(2^{-4}+2{-5}+...+2^{-N})$

$=2^N\left(\sum\limits_{k=0}^N (\frac{1}{2})^k-2^{-3}-2^{-2}-2^{-1} -1\right)$

$=2^N\left(2-2^{-N}-2^{-3}-2^{-2}-2^{-1} -1\right)$

$=2^N\left( \frac{1}{8}-2^{-N}\right)$

$=2^{N-3}-1$.

Thus $x_1 = 1 + (2^{N-1} -4)\epsilon$, which implies that $\Vert \vec{x^\epsilon} \Vert_\infty = 1 + (2^{N-1} -4)\epsilon$.

The above implies that $\Vert \vec{x} - \vec{x^\epsilon} \Vert_\infty = (2^{N-1} -4)\epsilon$, and thus $\frac{\Vert \vec{x} - \vec{x^\epsilon} \Vert_\infty}{\Vert \vec{x} \Vert_\infty} = (2^{N-1} -4)\epsilon$.

However, instructor insists that calculation (*) must lead to a different answer. I have re-verified my answer several times, and didn't find an error. Could you please let me know what is the error in my calculation?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.