Böttcher, Albrecht ; Potts, Daniel : Probability against condition number and sampling of multivariate trigonometric

Author(s):

Böttcher, Albrecht
Potts, Daniel

Title:

Probability against condition number and sampling of multivariate trigonometric

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 2, 2006

Mathematics Subject Classification:

65F35			[ Matrix norms, conditioning, scaling ]
15A12			[ Conditioning of matrices ]
47B35			[ Toeplitz operators, Hankel operators, Wiener-Hopf operators ]
60H25			[ Random operators and equations ]
94A20			[ Sampling theory ]

Abstract:

The difficult term in the condition number $\| A\n \, \| A^{-1}\|$ of a large linear system $Ap=y$ is the spectral norm of $A^{-1}$. To eliminate this term, we here replace worst case analysis by a probabilistic argument. To be more precise, we randomly take $p$ from a ball with the uniform distribution and show that then, with a certain probability close to one, the relative errors $\| \de p\|$ and $\| \de y\|$ satisfy $\| \delta p\| \le C \| \delta y\|$ with a constant $C$ that involves only the Frobenius and spectral norms of $A$. The success of this argument is demonstrated for Toeplitz systems and for the problem of sampling multivariate trigonometric polynomials on nonuniform knots. The limitations of the argument are also shown.

Keywords:

condition number, probability argument, linear system, Toeplitz matrix, nonuniform sampling, multivariate trigonometric polynomial

Language:

English

Publication time:

3 / 2006