Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-19T08:32:39.220Z Has data issue: false hasContentIssue false
  • English
  • Français

The condition of gram matrices and related problems

Published online by Cambridge University Press:  14 November 2011

J. M. Taylor
J. M. Taylor
Affiliation:
Mathematics Division, University of Sussex
Get access Rights & Permissions [Opens in a new window]

Synopsis

It has been known for some time that certain least-squares problems are “ill-conditioned”, and that it is therefore difficult to compute an accurate solution. The degree of ill-conditioning depends on the basis chosen for the subspace in which it is desired to find an approximation. This paper characterizes the degree of ill-conditioning, for a general inner-product space, in terms of the basis.

The results are applied to least-squares polynomial approximation. It is shown, for example, that the powers {1, z, z2,…} are a universally bad choice of basis. In this case, the condition numbers of the associated matrices of the normal equations grow at least as fast as 4n, where n is the degree of the approximating polynomial.

Analogous results are given for the problem of finite interpolation, which is closely related to the least-squares problem.

Applications of the results are given to two algorithms—the Method of Moments for solving linear equations and Krylov's Method for computing the characteristic polynomial of a matrix.

Type
Research Article
Information
Proceedings of the Royal Society of Edinburgh Section A: Mathematics , Volume 80 , Issue 1-2 , 1978 , pp. 45 - 56
Copyright
Copyright © Royal Society of Edinburgh 1978

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Todd, J. On condition numbers. Programmation en Mathématiques Numériques. Actes Colloq. Internat. C.N.R.S. 165, Besancon (1966), 141–159. Paris: Editions C.N.R.S., 1968.Google Scholar
2Bellman, R.Introduction to matrix analysis (New York: McGraw-Hill, 1960).Google Scholar
3Szegö, G.Orthogonal polynomials (Providence, R.I.: Amer. Math. Soc, 1939).Google Scholar
4Knopp, K.Theory and application of infinite series (Glasgow: Blackie, 1949).Google Scholar
5Todd, J.The condition of the finite segments of the Hilbert matrix. Nat. Bureau Standards Appl. Math. Ser. 39 (1954), 109–116.Google Scholar
6Hille, E.Analytic function theory II (Massachussets: Ginn, 1959).Google Scholar
7Vorobyev, U. V.Moments method in applied mathematics. (Delhi: Hindustani Publishing, 1962).Google Scholar
8Taylor, A. E.Introduction to functional analysis (New York: Wiley, 1958).Google Scholar
9Wilkinson, J. H.The algebraic eigenvalue problem (Oxford: Clarendon Press, 1965).Google Scholar