From c21f0db90e14920174026f446c338c0a88e35262 Mon Sep 17 00:00:00 2001
From: Christophe Guyeux <guyeux@gmail.com>
Date: Fri, 10 Oct 2014 15:20:12 +0200
Subject: [PATCH] =?utf8?q?Avanc=C3=A9es=20dans=20la=20preuve=20par=20induc?=
=?utf8?q?tion?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit
---
paper.tex | 13 ++++++++++---
1 file changed, 10 insertions(+), 3 deletions(-)
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
--
2.39.5