Database Reference
In-Depth Information
and refer to error vectors that are dominated by contributions in directions of
eigenvectors of the iteration matrix that correspond to small-magnitude eigenvalues
as (algebraically)
smooth.
Similarly to the PDE setting, we would like to eliminate
these smooth error components by means of a correction step on an algebraic coarse
grid, the notion of which shall be specified subsequently.
In compliance with the notation introduced in foregoing chapters, we shall
denote the set of the first
n
natural numbers by
n
. Each element of this set is an
index corresponding to an entry in of a vector of length
n
. With the graph-theoretic
framework introduced in Sect.
3.9.2
in mind, we also refer to such an index as a
node. So, a reasonable approach to mimicking the multi-scale framework in the
continuous setting consists in considering a set of nodes, that is, a subset of
n
,asan
(algebraic) grid. The
fine grid
, then, is simply the set
n
itself, and a
coarse grid
is a
suitably chosen subset
m
of
n
such that the number
m
of nodes therein is consid-
erably smaller than
n
. Given a
coarse grid m
, we construct, by means of a method
yet to be specified, a restriction operator enabling to restrict a given residual
r
:¼ b Ax
to the coarse grid and an interpolation operator allowing us to prolong the coarse
grid correction to the fine grid. If we denote these operators by
R
and
L
, respec-
tively, the algebraic version of the coarse grid correction step in the V-cycle
(Algorithm 6.1) becomes
x
:¼ x þ L
e
x
,
where
e
x
is the solution of the
coarse grid equation
RAL
e
x ¼ Rr
:
ð
6
:
6
Þ
Combining the above equations, summarize the coarse grid correction step in a
single assignment:
Þ
1
Rb Ax
x
:¼ x þ L RAL
ð
ð
Þ:
ð
6
:
7
Þ
To provide some evidence for the soundness of the approach, we shall, for now,
assume that
A
be symmetric and positive definite and
R ¼ L
T
. As it turns out, this
case is easy to handle mathematically. The crucial fact is that a symmetric positive
definite matrix induces the so-called energetic inner product
h
,
i
A
given by
h
A
:¼ x
T
Ay
x
;
:
The catch consists in carrying out the error analysis in terms of the thereby
induced norm
q
x
kk
A
:¼
h
A
;
:
