From: Christophe Guyeux <guyeux@gmail.com>
Date: Fri, 10 Oct 2014 13:20:12 +0000 (+0200)
Subject: Avancées dans la preuve par induction
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/GMRES2stage.git/commitdiff_plain/c21f0db90e14920174026f446c338c0a88e35262

Avancées dans la preuve par induction
---

diff --git a/paper.tex b/paper.tex
index 436909a..d9880d1 100644
--- a/paper.tex
+++ b/paper.tex
@@ -759,11 +759,17 @@ where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}.
 \begin{proof}
 Let $r_k = b-Ax_k$, where $x_k$ is the approximation of the solution after the
 $k$-th iterate of TSIRM.
-We will prove that $r_k \rightarrow 0$ when $k \rightarrow +\infty$.
+We will prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, 
+$||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0||.$
 
-Each step of the TSIRM algorithm \\
+The base case is obvious, as for $k=1$, the TSIRM algorithm simply consists in applying GMRES($m$) once, leading to a new residual $r_1$ which follows the inductive hypothesis due to Proposition~\ref{prop:saad}.
 
-Let $\operatorname{span}(S) = \left \{ {\sum_{i=1}^k \lambda_i v_i \Big| k \in \mathbb{N}, v_i \in S, \lambda _i \in \mathbb{R}} \right \}$ be the linear span of a set of vectors $S$. So,\\
+Suppose now that the claim holds for all $m=1, 2, \hdots, k-1$, that is, $\forall m \in \{1,2,\hdots, k-1\}$, $||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0||$.
+We will show that the statement holds too for $r_k$. Two situations can occur:
+\begin{itemize}
+\item If $k \mod m \neq 0$, then
+
+\item Else, let $\operatorname{span}(S) = \left \{ {\sum_{i=1}^k \lambda_i v_i \Big| k \in \mathbb{N}, v_i \in S, \lambda _i \in \mathbb{R}} \right \}$ be the linear span of a set of real vectors $S$. So,\\
 $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$
 
 $\begin{array}{ll}
@@ -773,6 +779,7 @@ $\begin{array}{ll}
 & \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k-1} ||_2\\
 & \leqslant ||b-Ax_{k-1}||_2 .
 \end{array}$
+\end{itemize}
 \end{proof}
 
 We can remark that, at each iterate, the residue of the TSIRM algorithm is lower