Proof on why solution to a linear system Ax=b belong to the set of initial abitrary guess plus the Krylov subspace of the matrix & intitial residual?

170 Views Asked by At

The below is the digested summary of the Krylov properties section from this book. My question is about the conclusion presented at the end.

By applying the Cayley-Hamilton theorem, for $A \in \mathbb{R}^{n \times n}$ and $\forall y \in \mathbb{R}^n$, we can derive that

$$ A^{-1}y = -\frac{1}{|A|}\sum_{i=0}^{n-1}c_{i+1}A^iy $$

Now, assuming $|A| \ne 0$, let $x = A^{-1}b$ be the solution to the linear system $Ax = b$.

Let $x^{(0)}$ be any arbitrary vector. We define $e^{(0)} = x - x^{(0)}$, and $r^{(0)} = b - Ax^{(0)} = Ae^{(0)}$. Substituting $y = r^{(0)}$ in the above equation, we have

$$ e^{(0)} = A^{-1}r^{(0)} = -\frac{1}{|A|}\sum_{i=0}^{n-1}c_{i+1}A^ir^{(0)} $$

I understand everything thus far. However, the next part confuses me, wherein the authors state:

We conclude that: $$ A^{-1}b \in x^{(0)} + \mathcal{K}_n(A,r^{(0)}) $$ where $$ \mathcal{K}_n(A,r^{(0)}) = \text{span}(r^{(0)}, Ar^{(0)}, A^2r^{(0)}, \dots, A^{n-1}r^{(0)}) $$ is the $n^\text{th}$ Krylov subspace associated to $A$ and $r^{(0)}$. $$

I just do not understand the last part of the derivation i.e. how did they come to this conclusion? Shall appreciate a bit more details explaining this.

1

There are 1 best solutions below

2
On BEST ANSWER

From what you've said you understand, you've got \begin{align} A^{-1}b&=x\\ &=x^{(0)}+e^{(0)}\\ &=x^{(0)}-\frac{1}{|A|}\sum_{i=0}^{n-1}c_{i+1}A^ir^{(0)}\\ &\in x^{(0)}+\text{span}(r^{(0)}, Ar^{(0)}, A^2r^{(0)}, \dots, A^{n-1}r^{(0)})\ . \end{align}