Newsgroups: sci.math.num-analysis
From: lpa@netcom.com (Pierre Asselin)
Subject: Re: Proof of bad condition of Hilbert matrix
Date: Sat, 31 Aug 1996 04:56:05 GMT

tmoon@artemis.ece.usu.edu (Todd K. Moon) writes:

>It is well known that the condition number of large Hilbert matrices
>grows very large, and is easy to verify experimentally.  However, I
>have been unable to find a proof of this fact.  I would appreciate a
>pointer to a reference, if such exists.

Well, let's see...  You need estimates of the max and min values
that the Rayleigh quotient R(u) can take, where

    R(u) = (u^t H u)/(u^t u)  ,  u= any nonzero vector.

Now, H is the Gram matrix of the polynomials over the interval [0,1].
If p(x) = u_0 + u_1*x + u_2*x^2 + ...  then

  u^t H u  =  integral[from 0 to 1](p(x)^2 dx).

Take p(x) = Tchebychev polynomial (shifted from the inverval [-1,1]
to [0,1]).  The coefficients grow exponentially with n, so (u^t u)
grows exponentially with n;  yet p(x) oscillates between -1 and +1,
so the integral is less than 1.  So Rmin decreases exponentially
with n.

For Rmax, use u= [1,0,0,0...];  Rmax is >= 1.
So Rmax/Rmin grows exponentially.  If you want a tight bound you'll
need to find a good estimates of the coefficients of Tchebychev
polynomials.  Legendre polynomials should give an even tighter bound.

-- 
--Pierre Asselin, Westminster, Colorado
  lpa@netcom.com
  pa@verano.sba.ca.us
==============================================================================

From: jacquesg@clic1.qbc.clic.net (Jacques Gelinas)
Newsgroups: sci.math.num-analysis
Subject: Re: Proof of bad condition of Hilbert matrix
Date: 31 Aug 1996 13:08:35 GMT

Todd K. Moon (tmoon@artemis.ece.usu.edu) wrote:
: It is well known that the condition number of large Hilbert matrices
: grows very large, and is easy to verify experimentally.  However, I
: have been unable to find a proof of this fact.  I would appreciate a
: pointer to a reference, if such exists.

Well, I once knew a CS prof who tested each new system by inverting 9x9,
10x10 ... Hilbert natrices until it crashed. Not as severe as the BLAS
test, but efficient.

In the well known article "Pitfalls in Computation, or Why a Math Book
ins'nt enough, Amer.Math.Month. 77(9), Nov 1970, 931-955", G.E. Forsythe
starts from a 1894 article of David Hilbert and shows that least squares
approximation on [0,1] of a function f(x) by a polynomial of degree n-1
leads to a linear system based on the Hilbert matrix of order n.

He then shows that the growth of the elements of the inverse matrix
leads to numerical instability because any small variation in the RHS
could be greatly magnified in multiplying by the inverse matrix:

"It cannot be demonstrated here, but if the maximal element of the
 inverse matris is much bigger than b^s, you cannot solve the
 system with s-digit arithmetic in base b."

Forsythe gives a reference to his 1967 book on linear algebra (with Moler).


Here is how I would suggest you attack the problem of estimating the

0) Adopt  ||A|| ||A^-1|| as a measure of ill-conditioning with, say,
   the maximal matrix norm.

1) Use a theorem of Cauchy on determinants to estimate the elements
   of the inverse matrix.

     A. Ralston, A First Course on Numerical Analysis, p. 263

     "A theorem of Cauchy states that if a1...an,b1...bn are 2n numbers,
      the determinant with elements (ai+bk)^-1, i=1..n, k=1..n, has the
      value

  \prod^n_{i>k=1} (a_i-a_k)(b_i-b_k) / \prod^n_{i=1}\prod^n_{k=1}(a_i+b_k)"