Hueper - Calculus Approach To Matrix Eigenvalue Algorithms.pdf

(360 KB) Pobierz
133731036 UNPDF
A Calculus Approach to
Matrix Eigenvalue Algorithms
Habilitationsschrift
der Fakultat fur Mathematik und Informatik
der Bayerischen Julius-Maximilians-Universitat Wurzburg
fur das Fach Mathematik vorgelegt von
Knut Huper
Wurzburg im Juli 2002
2
Meiner Frau Barbara
und unseren Kindern Lea, Juval und Noa gewidmet
Contents
1 Introduction
5
2 Jacobi-type Algorithms and Cyclic Coordinate Descent 8
2.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Jacobi and Cyclic Coordinate Descent . . . . . . . . . 9
2.1.2 Block Jacobi and Grouped Variable Cyclic Coordinate
Descent . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Applications and Examples for 1-dimensional Optimiza-
tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.4 Applications and Examples for Block Jacobi . . . . . . 22
2.2 Local Convergence Analysis . . . . . . . . . . . . . . . . . . . 23
2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Re¯ning Estimates of Invariant Subspaces 32
3.1 Lower Unipotent Block Triangular Transformations . . . . . . 33
3.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Main Ideas . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2 Formulation of the Algorithm . . . . . . . . . . . . . . 40
3.2.3 Local Convergence Analysis . . . . . . . . . . . . . . . 44
3.2.4 Further Insight to Orderings . . . . . . . . . . . . . . . 48
3.3 Orthogonal Transformations . . . . . . . . . . . . . . . . . . . 52
3.3.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . 57
3.3.2 Local Convergence Analysis . . . . . . . . . . . . . . . 59
3.3.3 Discussion and Outlook . . . . . . . . . . . . . . . . . 62
4 Rayleigh Quotient Iteration, QR-Algorithm, and Some Gen-
eralizations 63
4.1 Local Cubic Convergence of RQI . . . . . . . . . . . . . . . . 64
CONTENTS
4
4.2 Parallel Rayleigh Quotient Iteration or Matrix-valued Shifted
QR-Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3 Local Convergence Properties of the Shifted QR-Algorithm . . 73
Chapter 1
Introduction
The interaction between numerical linear algebra and control theory has cru-
cially in°uenced the development of numerical algorithms for linear systems
in the past. Since the performance of a control system can often be mea-
sured in terms of eigenvalues or singular values, matrix eigenvalue methods
have become an important tool for the implementation of control algorithms.
Standard numerical methods for eigenvalue or singular value computations
are based on the QR-algorithm. However, there are a number of compu-
tational problems in control and signal processing that are not amenable to
standard numerical theory or cannot be easily solved using current numerical
software packages. Various examples can be found in the digital ¯lter design
area. For instance, the task of ¯nding sensitivity optimal realizations for
¯nite word length implementations requires the solution of highly nonlinear
optimization problems for which no standard numerical solution algorithms
exist.
There is thus the need for a new approach to the design of numerical
algorithms that is °exible enough to be applicable to a wide range of com-
putational problems as well as has the potential of leading to e±cient and
reliable solution methods. In fact, various tasks in linear algebra and system
theory can be treated in a uni¯ed way as optimization problems of smooth
functions on Lie groups and homogeneous spaces. In this way the powerful
tools of di®erential geometry and Lie group theory become available to study
such problems.
Higher order local convergence properties of iterative matrix algorithms
are in many instances proven by means of tricky estimates. E.g., the Jacobi
method, essentially, is an optimization procedure. The idea behind the proof

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin