Next: A race: Jacobi verses
Up: A More Fundamental Analysis
Previous: Conditions for the the
We begin our discussion by considering a simpler iteration system,
Let C be the set of all sequences
created by this iteration such that
the sequence converges to
, i.e. we say
Define
![$\displaystyle \alpha=\lim_{k\rightarrow \infty}sup\vert x^k-x^*\vert^{1/k} \rightarrow 0 \leq \beta \leq 1$](img60.png) |
(3.11) |
We shall take liberties and call this
the asymptotic convergence factor of the
general iteration (see the references for a more sophisticated definition). For a given
iteration, the sequence will converge at least as rapidly as the sequence
goes
to zero.
From our previous definitions,
![$\displaystyle \vert x^k - x^*\vert \leq \vert H^k\vert\vert x^0-x^*\vert \leq \...
...-x^*\vert \ni \lim_{k\rightarrow \infty}sup\vert x^k-x^*\vert^{1/k}\leq \rho(H)$](img63.png) |
(3.12) |
Here we have used that
.
We have loosly demonstrated that
The spectral radius establishes the upper bound on the rate of convergence. We thus seek to maximize the spectral radius as a to minimize the convergence time.
To begin to do so, we wish to roughly demonstrate a rather elegant lemma that says
that eigenvalues of the Jacobi iteration matrix occur in pairs (except if
there is a zero eigenvalue), which we shall denote
Suppose we take some random value
and want to find
, where C has eigenvalues
. C can be diagonalized
with its eigenvalues via
, whereby
Thus, supposing the existance of p zero valued eigenvalues (p may be zero itself):
For a more thorough discussion of what is to follow, the reader is
referred to the references, especially on 2-Cyclic matrices (such as the one we are concerned with).
Now
may be written as
And we note that
We can thus write that
![$\displaystyle det(\lambda I - C)=det(\lambda I + C) = \lambda ^p \prod^{r}_{i=1}(\lambda + a_i) \Rightarrow \forall a_i > 0 \ \exists \ a_s < 0 \ \ni a_s = -a_i$](img80.png) |
(3.14) |
Thus (those with a strongly developed mathematical
sense will be unhappy with my use of thus here) we have Romanovsky's Lemma:
We can use this lemma to demonstrate another important detail about
form of matrices we are considering (formally called regular splittings).
We wish to show that the eigenvalues of
are equal to those of
. Let
We need to demonstrate that
That is to say, that the matrix
is consistently ordered.
Define
And
It is clear that
Whereby in the spirit of previous arguments we have thus shown Equation 3.15 to be true.
We are now ready to attack the problem head on. Recall that we defined
![$\displaystyle H = \left(D-wL\right)^{-1}\left((1-w)D+wU\right)$](img92.png) |
(3.16) |
from this discussion we can reformulate this as follows:
![$\displaystyle det(\lambda I - H)$](img93.png) |
![$\displaystyle =$](img22.png) |
![$\displaystyle det((D-wL)^{-1})det(D-wL)det(\lambda I - \left(D-wL\right)^{-1}\left((1-w)D+wU\right))$](img94.png) |
|
|
![$\displaystyle =$](img22.png) |
![$\displaystyle det((D-wL)^{-1})det((D-wL)\lambda I - (1-w)D+wU)$](img95.png) |
|
|
![$\displaystyle =$](img22.png) |
![$\displaystyle det(D^{-1})det((D-wL)\lambda I - (1-w)D+wU)$](img96.png) |
|
|
![$\displaystyle =$](img22.png) |
![$\displaystyle det((I-wD^{-1}L)\lambda I - (1-w)I - wD^{-1}U)$](img97.png) |
|
|
![$\displaystyle =$](img22.png) |
![$\displaystyle det((\lambda + w -1)I -\lambda w D^{-1}L - wD^{-1}U)$](img98.png) |
|
|
![$\displaystyle =$](img22.png) |
with from 3.15 |
|
|
![$\displaystyle =$](img22.png) |
Romanovsky's Lemma |
(3.17) |
The eigenvalues of H may be found from
From this we get
Since
comes in
pairs,
we can minimize our convergence time by choosing w such that
We are bound by the maximal
, the spectral radius, so that
Defining
and solving for w, we find
![$\displaystyle w=\frac{2-2\sqrt{1-\rho(J)^2}}{\rho(J)^2}=\frac{2(1-1+\rho(J)^2)}{\rho(J)^2(1+\sqrt{1-\rho(J)}}=\frac{2}{1+\sqrt{1+\rho(J)^2}}$](img109.png) |
(3.18) |
To find the spectral radius of J, we need find the eigenvectors/values of J.
The Jacobi equation is given, again, by
J is formed by stripping off the diagonal and multiplying by
Thus the eigenvalue equation gives
![$\displaystyle J\zeta = \nu \zeta \ \rightarrow \frac{1}{4}\left(\alpha_{i+1,j}+\alpha_{i-1,j}+\alpha_{i,j+1}+\alpha_{i,j-1}\right)=\nu \alpha_{i,j}$](img112.png) |
(3.19) |
Introduce the ansatz that
where N is the dimensions of the grid (matrix, i.e. the number of rows). Plugging this into the equation above yields the equation
Obviously the maximum possible value will be
, this thus defining the spectral radius of concern,
where by,
![$\displaystyle w=\frac{2}{1+\sqrt{1-\cos^2(\pi/N)}}=\frac{2}{1+\sin(\pi/N)}\approx\frac{2}{1+\frac{\pi}{N}}$](img116.png) |
(3.20) |
Next: A race: Jacobi verses
Up: A More Fundamental Analysis
Previous: Conditions for the the
Timothy Jones
2006-05-15