1

We seek to solve $Au= f$ via iteration, where

$$ A = \left ( \begin{array}{cc} I & S \\ -S^T & I \end{array} \right ) $$ Where $S$ is an arbitrary square matrix in $R^n$ and $I$ is the identity matrix for $R^n$.

Now consider the relaxation scheme $$ A = L+D+U = \left ( \begin{array}{cc} Z & Z \\ -S^T & Z \end{array} \right ) +\left ( \begin{array}{cc} I & Z \\ Z & I \end{array} \right ) +\left ( \begin{array}{cc} Z & S \\ Z & Z \end{array} \right ) $$ $$ (D+L)u^* = -U u_k +f $$ $$ u_{k+1} = u_k + \omega (u^*-u_k) $$ where $Z$ is the zero matrix.

For what values $\omega$ does this scheme converge?

So far I have that $$ u_{k+1} = ((1-\omega)D-\omega (D+L)^{-1} U)u_k +\omega (D+L)^{-1}f$$ So if $ \Phi = ((1-\omega)D-\omega (D+L)^{-1} U)$, we want to find $\omega$ such that $\rho (\Phi) <1$. Some work reveals $\lambda = 1-\omega$ is an eigenvalue , thus giving us the usual restriction $0<\omega<2$. However, I am left wondering how to solve $$ det( (1-\omega-\lambda)I-\omega S^TS )=0 $$

If $n = 1$ and if we let $S =s$, then

$$ \lambda = 1-\omega-\omega s^2$$

So then we require that $ 0< \omega < \frac{2}{1+s^2}$

InfiniteElementMethod
  • 921

1 Answers1

1

We want to solve the eigenvalue problem

$$ ((1-\omega)I-\omega S^TS) v = \lambda v $$ Let's multiply by $v^T$,

$$ (1-\omega)||v||^2-\omega v^TS^TSv = \lambda ||v||^2 $$

or $$ (1-\omega)||v||^2-\omega ||Sv||^2 = \lambda ||v||^2 $$

If we seek $ |\lambda| < 1$, then

$$ - ||v||^2 < (1-\omega)||v||^2-\omega ||Sv||^2 < ||v||^2 $$ or $$ 0 < \omega)||v||^2+\omega ||Sv||^2 < 2 ||v||^2 $$

Using $||Sv|| \leq ||S||||v||$,

$$ \omega||v||^2+\omega ||Sv||^2 \leq \omega||v||^2+\omega ||S||^2||v||^2 $$

So then this method will converge for $\omega $ such that

$$ 0 < \omega||v||^2+\omega ||S||^2||v||^2 < 2||v||^2 $$ That is,

$$ 0 < \omega < \frac{2}{1+||S||^2} $$

This is consistent with the known solution for $n=1,S=s$.

InfiniteElementMethod
  • 921