Questions about iterative projection methods in Saad book

Question

I am reading Chapter 5 of Saad's iterative methods book, and I don't understand section 5.2.1 about the two propositions of optimality results. In the statements of the propositions, what does it mean that: $\tilde{x}$ is the result of a projection method onto $\mathcal K$ with the starting vector $x_0$? Because $\tilde{x}\in x_0 + \mathcal K$, does this mean $\tilde{x} = x_0 + Px_*$ or $\tilde{x} = Px_*$ for the true solution $x_* \in R^n$? I also can't see how section 1.12.4 can easily leads to the proof of the two conclusions,because they have a starting vector $x_0$. Also the A-norm in the first proposition is also different from the 2-norm in section 1.12.4. Could anyone give some explanations?

Answer 1

In order to understand these results, you need to know how minimization and projection problems are connected. Namely,

Let $\mathbb V$ be a subspace of $\mathbb C^n$ and take $y \in \mathbb C^n$; then $\hat y = \text{argmin}_{x \in \mathbb V} || y - x ||$ iff $(\hat y, x) = (y, x)$ for all $x \in \mathbb V$.

Here $(.,.)$ is a scalar product (not necessarily Euclidean) and $||.|| := (.,.)^{1/2}$.

Assume that $A\,x^* = b$ and consider a projection problem: find $x \in \mathbb L$ s.t. $(A\,x,k) = (b, k)$ for all $k \in \mathbb K$.

Idea #1: $\mathbb K := \mathbb L$

Take $\mathbb K := \mathbb L$ and assume $A = A^* > 0$ (so that $A$ induces a scalar product $(u, v)_A := (A\,u, v)$ and corresponding norm). Note that in the projection problem $(A\,x,k) =: (x, k)_A$ and $(b, k) = (A\,x^*, k) =: (x^*, k)_A$, so it may be rewritten as follows:

Find $x \in \mathbb L$ s.t. $(x, k)_A = (x^*, k)_A$ for all $k \in \mathbb K$.

From our theorem it follows that $$ x = \text{argmin}_{l \in \mathbb L} || x^* - l ||_A, $$ i.e. our $x$ is the best approximation of $x^*$ in $\mathbb L$ (in the sense of the energy norm).

Idea #2: $\mathbb K := A\,\mathbb L$

Now choose $\mathbb K := \{A\,l : l \in \mathbb L \} =: A\,\mathbb L$. Applying similar arguments, you will get that $$ x = \text{argmin}_{l \in \mathbb L} || b - A\,l ||. $$

Idea #1 gives rise to CG method and idea #2 gives rise to GMRES method when one chooses to use Krylov subspaces for $\mathbb L$ (but this is another story).

In the statements of the propositions, what does it mean that: $x$ is the result of a projection method onto $\mathbb K$ with the starting vector $x_0$?

Assume that you have some guess $x_0$ for $x^*$. Than you want to search for correction: find $c$ s.t. $A\,(x_0 + c) = b$, or $A\,c = r_0 := b - A\,x_0$. Then you can set $x = x_0 + c$.

Ideally you want $c = e_0 := x^* - x_0$, but you do not know the error since you do not know the exact solution $x^*$. So it is natural to apply projection method to search for an approximation of $e_0$:

Find $c \in \mathbb L$ s.t. $(A\,c, k) = (r_0, k)$ for all $k \in \mathbb K$.

Applying e.g. idea #1 we have that $$ c = \text{argmin}_{l \in \mathbb L} || e_0 - l ||_A = \\ \text{argmin}_{l \in \mathbb L} || (x^* - x_0) - l ||_A = \\ \text{argmin}_{l \in \mathbb L} || x^* - (x_0 + l) ||_A = \\ [ y := x_0 + l] = \\ \text{argmin}_{y \in x_0 + \mathbb L} || x^* - y ||_A - x_0, $$ or $$ x = \text{argmin}_{y \in x_0 + \mathbb L} || x^* - y ||_A. $$

Here $x_0 + \mathbb L := \{x_0 + l : l \in \mathbb L \}$ is an affine set (shifted subspace). That is, when you have some guess for your solution, you are minimizing some kind of functional (energy norm of the error in this case) over an affine set instead of a subspace.