With $A=A^T$, $Ax=b$ is solved backward stably for $x$ yielding computed $y$. Show that $y / | y |$ is close to $x / | x |$.

36 Views Asked by At

Suppose $A \in \mathbb{R}^{m \times m}$ is a real symmetric matrix with orthonormal eigenvector basis $\{ \vec{q}_1, \ldots, \vec{q}_m \}$. Let $b \in \mathbb{R}^m$ be expressed in this basis as:

\begin{gather*} b = \sum\limits_{j=1}^m a_j \vec{q}_j \\ \end{gather*}

Suppose we solve $Ax = b$ for $x$ with a backward stable algorithm yielding $y$. $A$ may be ill-conditioned and possibly singular. Show that although $y$ may be far from $x$, $y / {\lVert y \rVert}$ will not be far from $x / {\lVert x \rVert}$.

Because $A x = b$ is solved backward stably, there is some small $\Delta A$ such that:

\begin{gather*} \frac{ {\lVert \Delta A \rVert} }{ {\lVert A \rVert} } = O(\epsilon_M) \\ b = A x = (A + \Delta A) y \\ {\lVert b \rVert} \le {\lVert A \rVert} {\lVert x \rVert} \\ {\lVert b \rVert} \le {\lVert A + \Delta A \rVert} {\lVert y \rVert} \\ \end{gather*}

I'm a little stuck on where to go from here.