0

I am struggling to follow the derivation of the basis vectors of the Krylov subspace starting from 22:27 of this video.

If the next step of a search is given as

$$ x^k = x^{k - 1} + \alpha_{k - 1} r^{k - 1} $$

where $x^{k- 1}$ is the previous step, $r^{k- 1}$ is an orthogonal search direction and $\alpha_{k - 1}$ a constant. It follows that

$$ \begin{equation}\begin{aligned} b - A x^k & = b - A\left(x^{k - 1} + \alpha_{k - 1} r^{k - 1}\right) \\ & = b - A \, x^{k - 1} - \alpha_{k - 1} A \, r^{k - 1} \\ & = r^{k - 1} - \alpha_{k - 1} A \, r^{k - 1} \end{aligned}\end{equation} $$

The second to the last equation is where it to fall apart for me (see 24:42). The sign of the last term changes and the speaker writes

$$ \begin{equation}\begin{aligned} b - A x^k & = b - A x^{k - 1} + \alpha_{k - 1} A \, r^{k - 1} \\ & = r^{k - 1} + \alpha_{k - 1} A \, r^{k - 1} \end{aligned}\end{equation} $$

Subsequently the speaker uses the above equation as follows:

$$ \begin{equation}\begin{aligned} x^{k + 1} & = x^k + \alpha_k r^k \\ & = x^k + \alpha_k \left(b - A x^k\right) \\ & = x^k + \alpha_k \left(r^{k - 1} - \alpha_{k - 1} A \, r^{k - 1} \right) \\ & = x^k + \alpha_k r^{k - 1} - \alpha_k \alpha_{k - 1} A \, r^{k - 1} \end{aligned}\end{equation} $$

And from there makes the leap to write

$$ x^{k + 1} = x^0 + \alpha_1 r^0 + \alpha_2 A \, r^0 + \alpha_3 A^2 \, r^0 + \ldots + \alpha_{k - 1} A^k \, r^0 $$

Now I am lost completely.

Kroki
  • 13,135
Olumide
  • 1,241

1 Answers1

1

I think there is some small mistakes in the video, but the final result can be obtained easily. One thing to mentioned is the fact that $\alpha_k$ in the final result are not the same $\alpha_k$ at the beginning.

We know that:

\begin{align} x_{k+1} &= x_k + \alpha_{k} r_k\\ r_k &= b - Ax_k \end{align}

Let prove that $$x_{k} = x_0 + \sum_{l=0}^{k-1} \gamma^{k}_l A^l r_0$$

Using induction. For $k=0$ the result is trivial. Now since \begin{align} x_{k+1} &= x_k + \alpha_k r_k\\ &= x_k + \alpha_k \left(b - Ax_k\right)\\ &= x_k + \alpha_k \left(b - Ax_0 - A\sum_{l=0}^{k-1}\gamma^k_l A^lr_0\right)\\ &= x_0 + \sum_{l=0}^{k-1} \gamma^k_l A^lr_0 + \alpha_k \left(b - Ax_0\right) - \sum_{l=0}^{k-1} \alpha_k\gamma^k_l A^{l+1}r_0\\ &= x_0 + \sum_{l=0}^{k} \gamma^{k+1}_{l} A^{l}r_0 \end{align}

Where $\gamma^{k+1}_{0} = \alpha_k + \gamma^k_{0}$, $\gamma^{k+1}_{l} = \gamma^{k}_{l} - \alpha_k \gamma^{k}_l$ for $l=1,\ldots,k-1$ and $\gamma^{k}_{k+1} = -\alpha_k\gamma^{k-1}_{k}$

Kroki
  • 13,135