0

Let $A = \begin{bmatrix} 1 & -1 \\ 1 & -1.00001\end{bmatrix}$, give a posteriori extimate of the relative error in solving $Ax = b$, $||b||_2 = 1$.

To do this I was thinking of first finding the condition number of $A$ as follows. Letting $x = [\cos(\theta), \sin(\theta)]$ we are interested in the max to min ratio of the following quantity. \begin{align}\frac{||Ax||}{||x||}&=(\cos(\theta) - \sin(\theta))^2 + (\cos(\theta) -1.00001 \sin(\theta))^2\\ &= 2 - 4.00002\cos(\theta)\sin(\theta) + .0000200001\sin(\theta)^2\\ &\approx 2(1 - \sin(2\theta)) \end{align}

However, $\frac{\max 2(1 - \sin(2\theta))}{\min 2(1 - \sin(2\theta))}$ is $\infty$. Does this mean the desired estimate of the error is impossible?

Math_Day
  • 1,227

1 Answers1

1

It is large but not infinite.

Working with whole numbers $$f (\theta)=\frac{||Ax||}{||x||}=\frac{-40000200000 \sin (2 \theta )-200001 \cos (2 \theta )+40000200001}{20000000000}$$

The minimum is attained at $$\theta=\tan ^{-1}\left(\frac{\sqrt{40000000001}-1}{200000}\right)$$ and, at this point $$f (\theta)=\frac{40000200001-200001 \sqrt{40000000001}}{20000000000}$$

Similarly, the maximum is attained at $$\theta=\pi -\tan ^{-1}\left(\frac{1+\sqrt{40000000001}}{200000}\right)$$ and, at this point $$f (\theta)=\frac{40000200001+200001 \sqrt{40000000001}}{20000000000}$$

This makes $$\frac{\text{max}}{\text{min}}=\frac{1600016000100000400001+8000080000400001 \sqrt{40000000001}}{20000000000}\sim 1.6000\times 10^{11}$$

Edit

Making the problem more general

$$A = \begin{bmatrix} 1 & -1 \\ 1 & -1-\epsilon\end{bmatrix}$$ we have $$f(\theta)=\epsilon (\epsilon +2) \sin ^2(t)-(\epsilon +2) \sin (2 t)+2$$

Using series expansion $$\frac{\text{max}}{\text{min}} \sim \frac{\epsilon ^3+6 \epsilon ^2+16 \epsilon +32}{(2-\epsilon ) \epsilon ^2}\sim \frac {16} {\epsilon^2}$$

Claude Leibovici
  • 260,315