2
$\begingroup$

We have a matrix A that is diagonally dominant by rows $|a_{ii}|>\sum_{j\neq i} |a_{ij}|$ and I want to show that it will converge by showing that this statement is true $\lVert e^{(k)}\rVert_\infty \leq \lVert T\rVert^k_\infty \lVert e^{(0)}\rVert_\infty$, where $e^{(k)} = x^{(k)} - x^\ast$ and $x^\ast$ is the exact solution to $Ax=b$. I have already proved $\lVert T^k x\rVert \leq \lVert T\rVert^k \lVert x\rVert$ that statement but I have not sure how to apply it to help prove the convergence.

$\endgroup$
2
$\begingroup$

We know that $e^{(k+1)} = x^{(k+1)} - x^*$, so now consider the norms and use the relation $Tx^k = x^{(k+1)}$ so that we have: $$ \begin{equation}\label{star} \|x^{(k+1)} - x^*\| = \|Tx^k - Tx^*\| = \|T(x^(k) - x^*)\| \leq \|T\| \|e^k\| \end{equation} $$

Then by submultiplicativity of operator norms, we have using $\|T^k\| \leq \|T\|^k$, and inductively (by applying the above equation $k$ times) we have $\|e^{(k+1)}\| \leq \|T\|^k \|e^{(0)}$.

Now for convergence, you need to show something about $\|T\|$...

$\endgroup$
  • 1
    $\begingroup$ For the convergence would it be proving that $\|T\|$ is always $<1$? $\endgroup$ – user1775500 Oct 29 '17 at 19:03
  • $\begingroup$ Also why do you start with $e^{(k+1)}$ instead of $e^k$? $\endgroup$ – user1775500 Oct 29 '17 at 20:04
  • 1
    $\begingroup$ @user1775500: started with $e^{(k+1)}$ out of habit and could have equally started with $e^{(k)}$ and used $x^{(k)} = Tx^{(k-1)}$ $\endgroup$ – jjjjjj Oct 29 '17 at 21:48
  • 1
    $\begingroup$ and yes for $\|T\| < 1$. Consider: $\|T\|_{\infty} = \max_i \sum_{i\neq j} \frac{a_{ij}}{a_{ii}} < 1$ $\endgroup$ – jjjjjj Oct 29 '17 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.