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


$$x_{N-i} = 2^{i-1}\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\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)$


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?


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.