0

I was reading a book Lloyd N. Trefethen: Numerical Linear Algebra about GMRES, and on page 269 of book the authors say:

The GMRES solves an approximation problem, and space of polynomials is $P_n=\{ \text{polynomials $p$ of degree $\leq n$ with $p(0) = 1$} \}$

I have a problem with understanding why we need polynomial to be $p(0) = 1$. Can somebody help me please?

Carl Christian
  • 12,583
  • 1
  • 14
  • 37
nezudem
  • 101

1 Answers1

1

Let $K_j(A,b)$ denote the Krylov subspace $$K_j(A,b) = \text{span} \{b,Ab,\dotsc, A^{j-1} b\}. $$By definition, the GMRES (Generalized Minimal RESidual) algorithm computes $x_k \in K_k(A,b)$ such that $$\|b-Ax_k\|_2 = \min \{ \|b - Ax \|_2 \: : \: x \in K_k(A,b)\}.$$ We say, that GMRES minimizes the residual $b-Ax$ over all $x \in K_k(A,b)$. Now, if $x \in K_k(A,b)$ then $x = p(A)b$ for at least one polynomial $p$ of degree strictly less than $k$. The corresponding residual is $$r = b - Ax = b - Ap(A)b = q(A)b,$$ where $$q(t) = 1 - tp(t)$$ has $q(0) = 1$ and the degree of $q$ is at most $k$. Conversely, if $q$ is a polynomial of degree at most $k$ and $q(0) = 1$, then $x=0$ is a root of $q(x) - 1$ and we can therefore factor $q(x) - 1$ as $q(x) - 1 = x p(x)$ where $p$ is a polynomial of degree strictly less than $k$.

We conclude that finding the GMRES approximation $x_k$ is equivalent to minimizing $$\|q(A)b\|_2$$ where $q$ is a polynomial of degree at most $k$ and $q(0)=1$.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37
  • Looks like I got it, thanks – nezudem Jun 16 '23 at 15:01
  • So actually, q(0) = 1 by construction? I just got stucked because in Loyd this moment was strange a bit. – nezudem Jun 16 '23 at 15:05
  • 1
    @nezudem You can say that. I prefer to think about GMRES in terms of minimizing the residual over a sequence of Krylov subspaces because the residual is what we can compute without knowing the true solution, and because the residual is closely connected to the relative backward error. Minimizing $|q(A)b|_2$ with $q(0)=1$ (while equivalent) doesn't appeal to me in the same fashion. Both expression show that the residual norm will not increase as you increase $k$. Once the computed residuals deviate from this pattern, rounding errors have become significant and we should stop iterating. – Carl Christian Jun 16 '23 at 15:31