DISCRETE FEKETE POINTS AND SUPERLINEAR CONVERGENCE DISCRETE FEKETE POINTS AND SUPERLINEAR CONVERGENCE OF CONJUGATE GRADIENTS

Bernhard Beckermann

Laboratoire d'Analyse Num'erique et d'Optimisation
UFR IEEA - M3, UST Lille, F-59655 Villeneuve d'Ascq CEDEX, France
e-mail: bbecker@ano.univ-lille1.fr

Given a sequence of uniformly bounded discrete sets EN (N = 0,1,...) in the complex plane, # EN = N, we will study the functions

fn(z,EN) : =
max
P ð Pn 
 |P(z)|

max
z ð EN 
 |P(z)|
 ,       0 ú n < N ,
Pn denoting the set of polynomials of degree at most n, and their nth root asymptotics for n,N « Ñ, with n/N « t ð (0,1). We assume that the sequence of normalized zero counting measures corresponding to the sets EN converges to some probability measure s.

Our work is partially motivated by the investigation of the rate of convergence of the conjugate gradient method (CG) applied to large symmetric positive systems AN x = bN: it is well-known that the relative error in the energy norm at the nth iteration is bounded above by 1/Fn(0,EN), where EN is the spectrum of AN. As a typical model problem, for the 2D discretized Poisson equation on a uniform grid one obtains after rescaling as asymptotic eigenvalue distribution the complete elliptic integral

ds
dx
 (x) = 1
4p2
 K †
‡
‡
‡
‡
ˆ
  _____
Ùx(8-x)
 
4
 ÷
•
•
•
•
° 		,    x ð [0,8] ,    K(k) = 
 		1

0 
 dy
  ____________
Ù(1-y2)(1-k2y2)
 
.
For this model problem, the classical (linear) error bound in terms of the condition number of AN is far too pessimistic, which can be explained by the fact that the asymptotic eigenvalue distribution is quite different from the equilibrium distribution of [0,8].

In the present talk we will give lower and upper bounds for the nth root limit of fn(z,EN) in terms of the unique measure mt which under all probability measures m satisfying the constraint tm ú s has minimal logarithmic energy I(m). This constrained energy problem has been investigated by Rakhmanov (1996), Dragnev-Saff (1997), and several others in connection with the asymptotic behavior of discrete orthogonal polynomials. Our lower bound is valid for all complex z which do not attract ``too many'' of the elements of the sets EN. For establishing upper bounds, we need to impose some separation condition for the elements of EN. Here we show that it is sufficient to require that the discrete logarithmic energy of the sets EN tends to I(s) for N « Ñ, as conjectured by Rakhmanov (1998). An important tool in our investigation are discrete Fekete points, i.e., subsets of EN which have minimal discrete logarithmic energy. We finally show that the new resulting CG error bounds fit quite well the corresponding CG error curves for a number of examples.

References:

[1] B. Beckermann, On a conjecture of E.A. Rakhmanov. To appear in Constructive Approximation (1999).

[2] B. Beckermann & A.B.J. Kuijlaars, Superlinear Convergence of Conjugate Gradients. Manuscript (1999).

File translated from TEX by TTH, version 2.00.
On 14 Sep 1999, 18:17.