Information Technology Reference
In-Depth Information
1.13.1 Direct Versus Iterative Computation Methods
The direct computation methods are the classical TLS and the PTLS; their effi-
ciency is determined essentially by the dimensions of the data matrix, the desired
accuracy, the dimension
p
of the desired singular subspace, and the motor gap.
The iterative methods are efficient in solving TLS problems if:
1. The start matrix is good and the problem is generic.
2. The desired accuracy is low.
3. The dimension
p
of the desired singular subspace is known.
4. The dimension
d
of the problem is low.
5. The data matrix dimensions are moderate.
6. The gap is sufficiently large.
In contrast to the iterative methods, the direct methods
always
converge to
the desired solution.
In the sequel a list of the principal
nonneural
iterative methods is presented,
together with their own field of application (see [98]).
1.13.2 Inverse Iteration
Many authors have studied the inverse iteration (II) method in (non)symmetric
eigenvalue problems (see [75,150]). According to Wilkinson [193], it is the most
powerful and accurate method for computing eigenvectors.
Being
S
=
C
T
C
,where
C
=
[
A
;
B
],the
iteration matrix Q
k
is given by
=
(
S
−
λ
0
I
)
−
k
Q
0
Q
k
(1.57)
with
Q
0
a start matrix and
λ
0
a chosen shift. Given the dimension
p
of the TLS
eigensubspace of
S
,taking
λ
0
zero or such that the ratio
|
σ
n
2
n
−
p
+
1
−
λ
0
|
is high enough, matrix
Q
k
converges to the desired minor eigensubspace. The
iteration destroys the structure of the matrix
S
(for details, see [98]).
−
λ
0
|
/
|
σ
−
p
2
n
Remark 39 (Convergence Property)
If the motor gap
(
the gap between
σ
−
p
2
n
−
p
+
and
σ
)
is large,
fast convergence
occurs
(
this requirement is satisfied for
many TLS problems
)
.
1
1.13.3 Chebyshev Iteration
When the motor gap is small, the convergence can be accelerated by apply-
ing the Chebyshev polynomials (see [136,150,164,193]), instead of the inverse
power functions as before, to the matrix
C
T
C
for the
ordinary Chebyshev itera-
tion
(OCI) and to the matrix
C
T
C
−
1
for the
inverse Chebyshev iteration
(ICI).
Search WWH ::
Custom Search