×

Probability against condition number and sampling of multivariate trigonometric random polynomials. (English) Zbl 1171.65389

Summary: The difficult factor in the condition number \(\|A\|\,\|A^{-1}\|\) of a large linear system \(Ap=y\) is the spectral norm of \(A^{-1}\). To eliminate this factor, 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 \(\|\Delta p\|\) and \(\|\Delta y\|\) satisfy \(\|\Delta p\|\leq 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.

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
15A12 Conditioning of matrices
47B35 Toeplitz operators, Hankel operators, Wiener-Hopf operators
60H25 Random operators and equations (aspects of stochastic analysis)
94A20 Sampling theory in information and communication theory
PDFBibTeX XMLCite
Full Text: EuDML EMIS