Green''s Functions for Multiply Connected Domains via Conformal Mapping.
A method is described for the computation of the Green's function in the complex plane corresponding to a set of K symmetrically placed polygons along the real axis.  An important special case is a set of K real intervals.  The method is based on a Schwarz-Christoffel conformal map of the part of the upper half-plane exterior to the problem domain onto a semi-infinite strip whose end contains K-1 slits.  From the Green's function one can obtain a great deal of information about polynomial approximations, with applications in digital filters and matrix iterations.  By making the end of the strip jagged, the method can be generalized to weighted Green's functions and weighted approximations.
Introduction
. Green's functions in the complex plane are basic tools for the
analysis of real and complex polynomial approximations [10,21,24,30,32], which are
of central importance in the fields of digital signal processing [16,17,19] and matrix
iterations [5,6,11,20,28]. The aim of this article is to show that when the domain of
approximation is a collection of real intervals, or more generally symmetric polygons
along the real axis, the Green's function can be computed to high accuracy by Schwarz-
Christoffel conformal mapping. The computation of Schwarz-Christoffel maps has
become routine in recent years with the introduction of Driscoll's Matlab R
Christoffel Toolbox [4], a descendant of the second author's Fortran package SCPACK
[26].
The Green's function for a single interval can be obtained by a Joukowsky conformal
map, and related polynomial approximation problems were solved by Chebyshev
in the 1850s [3]. For two disjoint intervals, the Green's function can be expressed using
elliptic functions, and approximation problems were investigated by Akhiezer in the
1930s [2]. For K ? 2 intervals, the Green's function can be derived from a more general
Schwarz-Christoffel conformal map, and the formulas that result were stated in
a landmark article by Widom in 1969 [32]. Polynomial approximations can be readily
computed in this case by the Remes algorithm, which was adapted for digital filtering
by Parks and McClellan [3,18].
By a second conformal map, these ideas for intervals can be transplanted to the
more general problem of the Green's function for the region exterior to a string of
symmetric domains along the real axis ([32], p. 230). The conformal maps in question
can usually not be determined analytically, however, and even for the case of intervals
on the real axis, the formula for the Green's function requires numerical integration.
Here, for the case in which the domains are polygonal and thus can be reduced to
*Received by the editors XXX x, 19xx; accepted by the editors XXX x, 19xx. This work was
supported by NSF Grant DMS-9500975CS (US) and EPSRC Grant GR/M12414 (UK).
y Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, UK (embree
@comlab.ox.ac.uk).
z Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, UK (LNT@
comlab.ox.ac.uk).
intervals by a Schwarz-Christoffel map, we carry out the computations to put these
ideas into practice.
This article originated from discussions with Steve Mitchell of Cornell University,
who is writing a dissertation on applications of these ideas to the design of multirate
filters [15], and we are grateful to him for many suggestions. The contributions of
Jianhong Shen and Gilbert Strang at MIT were also a crucial help to us. Shen and
Strang have studied the accuracy of lowpass digital filters [22,23], and their asymptotic
formulas are directly connected to these Schwarz-Christoffel methods. In addition we
thank Toby Driscoll for his advice and assistance.
Our algorithm makes possible the computational realization of results in approximation
theory going back to Faber, Szeg-o, Walsh, Widom, and Fuchs, among others.
In particular, Walsh, Russell, and Fuchs obtained theorems concerning simultaneous
approximation of distinct entire functions on disjoint sets in the complex plane [8,9,30],
which we illustrate here in Section 6. Wolfgang Fuchs was for many years a leading
figure at Cornell University until his unfortunate death in 1997.
2. Description of the algorithm. Let E be a compact subset of the complex
plane consisting of K disjoint polygons P 1
numbered from left to right, with
each polygon symmetric with respect to the real axis. Degenerate cases are permitted
in which a portion of a polygon, or all of it, reduces to a line segment (but not to a
point). The Green's function problem for E is defined as follows:
Green's Function Problem. Find a real function g defined in the
region of the complex plane exterior to E satisfying
log jzj for z !1: (1c)
In (1a), \Delta denotes the Laplacian operator, and thus g is harmonic throughout the
complex plane exterior to the polygons P j . Standard results of potential theory ensure
that there exists a unique function g satisfying these conditions [12,13,29,32].
The solution to (1) can be constructed by conformal mapping. What makes this
possible is that the problem is symmetric with respect to the real axis, so it is enough
to find g(z) for the part of the upper half-plane Imz - 0 exterior to E; the solution in
the lower half-plane is then obtained by reflection (the Schwarz reflection principle).
This half-planar region is bounded by the upper halves of the polygons P j and by
the intervals along the real axis that separate the polygons, where the appropriate
boundary condition for g, by symmetry, is the Neumann condition
Restricting the map to the upper half-plane makes the domain simply-connected,
suggesting the following conformal mapping problem.
Conformal Mapping Problem. Find an analytic function f that
maps the portion of the upper half-plane exterior to E (Fig. 1a) conformally
onto a semi-infinite slit strip (Fig. 1c). Only the vertices f(S 1
-i, f(T K are prescribed. The remaining vertices,
and hence the lengths and heights of the slits, are not specified.
Once this mapping problem is solved, the function g defined by
GREEN'S FUNCTIONS FOR MULTIPLY CONNECTED DOMAINS 3
z-plane
(a)
(b)
a 1
a 2
(c)

Figure

1. Determination of the Green's function g(z) by a composition of two
conformal maps,
(z)). (a) The problem domain is restricted
to the part of the upper half-plane exterior to the polygons P j . (b) The first
Schwarz-Christoffel
takes this problem domain onto the upper half-plane itself.
(c) The second Schwarz-Christoffel map f 2
takes the upper half-plane to a slit semi-infinite
strip. The interval [s maps to a vertical boundary segment [oe
Re The gaps along the real axis between the intervals [s to horizontal
slits, and the semi-infinite intervals (\Gamma1; s 1
to semi-infinite
horizontal lines with imaginary parts - and 0, respectively. Only the real parts of the
left endpoints of the slits are prescribed; the imaginary parts and the right endpoints
as well as their pre-images a j , are determined as part of the calculation.
is the Green's function (1) for values of z in the upper half-plane. To see this we
note that g satisfies (1a) because the real part of an analytic function is harmonic,
it satisfies (1b) because of the form of the slit strip, and it satisfies (1c) because the
half-strip has height -. The existence and uniqueness of a solution to the Conformal
Mapping Problem can be derived from standard theory of conformal mapping [12] or
as a consequence of the corresponding facts for the Green's Function Problem.
w-plane

Figure

2. Composition of a third conformal map, the complex exponential, transplants
the slit strip to the exterior of a disk with radial spikes in the upper half-plane.
Reflection in the real axis completes the map of the problem domain of Fig. 1a, yielding
a function
The function f(z) is a conformal map from one polygon to another, and as such,
it can be represented by Schwarz-Christoffel formulas, an idea going back to Schwarz
and independently Christoffel around 1869. Figure 1 shows how f can be constructed
as the composition of two Schwarz-Christoffel maps. The first one maps the problem
domain in the upper half-plane to the upper half-plane, with the upper half of the
boundary of the polygon P j going to the interval [s This mapping problem is a
standard one, for which a parameter problem must be solved to determine accessory
parameters in the Schwarz-Christoffel formula; see [4,12,26]. By the second Schwarz-
Christoffel map, the upper half-plane is then mapped to the slit strip. This is a
Schwarz-Christoffel problem in the reverse, more trivial direction, with only a linear
parameter problem to be solved to impose the condition that the upper and lower
sides of each slit have equal length. Details can be found in [23] and [32]. A related
linear Schwarz-Christoffel problem involving slits in the complex plane is implicit in
[14].
By composing a third conformal map with the first two, we obtain a picture that
is even more revealing than Fig. 1. Figure 2 depicts the image of the slit strip under
the complex exponential:
(z))). The vertical segments now
map onto arcs of the upper half of the unit circle, the slits map onto radial spikes
protruding from that circle, and the infinite horizontal lines map to the portion of the
real axis exterior to the circle. The real axis is shown dashed, because we immediately
reflect across it to get a complete picture.
By the composition \Phi(z) of three conformal maps, we have transplanted the
K-connected exterior of the region E of Fig. 1a to the simply-connected exterior of
the spiked unit disk of Fig. 2. (These connectivities are defined with respect to the
Riemann sphere or the extended complex plane C [ f1g.) The Green's function for
E is given by the extraordinarily simple formula
Have we really mapped a K-connected region conformally onto a simply-connected
region? No, this is is not possible, and to resolve what looks like a contradiction
we must think more carefully about reflections. Suppose in Fig. 1a we think of
GREEN'S FUNCTIONS FOR MULTIPLY CONNECTED DOMAINS 5
the finite dashed intervals as branch cuts not to be crossed, and reflect only across
the semi-infinite dashed intervals at the ends. Then the complement of E becomes
simply-connected, and we have indeed constructed a conformal map onto the simply-connected
region of Fig. 2. However, the Schwarz reflection principle permits reflection
across arbitrary straight lines or circular arcs. There is no reason why one should exclude
the finite intervals in Fig. 1a as candidates, which would correspond in the
w-plane to reflection in the protruding spikes of Fig. 2. When such reflections are
allowed, \Phi(z) becomes a multi-valued function whose values depend on paths in the
complex plane-or equivalently, a single-valued conformal map of Riemann surfaces.
Even under arbitrary reflections with arbitrary multi-valuedness, fortunately, equation
(3) remains valid, since all reflections preserve the absolute value j\Phi(z)j and g(z)
depends only on this absolute value. Therefore, for the purpose of calculating Green's
functions, we escape the topological subtleties of the conformal mapping problem.
The phenomenon of multivaluedness is a familiar one in complex analysis. An
analysis of the multivalued function \Phi(z) is the basis of Widom's approximation theoretic
results in [32], and earlier discussions of the same function can be found, for
example, in [30] and [31].
3. Computed example; electrostatic interpretation. Our first computed
example is presented in detail to illustrate our methods. The region E of Fig. 3(a)
has polygons, a red hexagon and a green square. (The hexagon is defined by
coordinates \Gamma6:5, \Gamma5 \Sigma 1:5i, \Gamma5:75 \Sigma 2:25i, \Gamma8 and the square by coordinates 9:5,
8:75 \Sigma 0:75i, 8.) In Fig. 3(b), three subsets of the real axis have been introduced, blue
and turquoise and magenta, to complete the boundary of the half-planar region. Plots
(c) and (d) show the conformal images of this region as a slit strip and the exterior
of the disk with a spike. The color coding is maintained to indicate which boundary
segments map to which.
All of these computations, like those in our later examples, have been carried out
with the high accuracy that comes cheaply in Schwarz-Christoffel mapping [26]. Thus
our figures can be regarded as exact for plotting purposes. For the sake of those who
may wish to duplicate some of these computations, in the sections below we report
occasional numbers, which are believed in each case to be correct to all digits listed.
Green's functions have a physical interpretation in terms of two-dimensional electric
charge distributions, that is, cross-sections of infinite parallel line charge distributions
in three dimensions. In Fig. 3(d), the equilibrium distribution of one (negative)
unit of charge along the unit circle is the uniform distribution, which generates the
associated potential log jwj. By conformal transplantation under the map
maps to a non-uniform distribution along the boundaries of the
polygons P j in the z-plane. This nonuniform charge distribution on the polygons P j
is precisely the minimal-energy, equilibrium charge distribution for these sets. It is
the charge distribution that would be achieved if each polygon were an electrical conductor
connected to the other polygons by wires in another dimension so as to put
them all at the same voltage. Mathematically, the charge distribution is distinguished
by the special property that it generates the potential g(z) with constant value on the
boundaries of the polygons.
4. Asymptotic convergence factor, harmonic measure, and capacity.
Every geometrical detail of Fig. 3 has a mathematical interpretation for the Green's
function problem, which becomes a physical interpretation if we think in terms of
equilibrium charge distributions. We now describe several items that are particularly
important.
6 MARK EMBREE AND LLOYD N. TREFETHEN
(a) Problem domain, showing the computed
critical level curve c as well as one
lower and one higher level curve.
z-plane
(b) To obtain these results, first the real axis
is drawn in as an artificial boundary. Heavy
lines mark the boundary of the new simply-connected
problem domain.
(c) The half-planar region is then transplanted
by a composition of two Schwarz-Christoffel
maps to a slit semi-infinite strip. The real interval
between the polygons (turquoise) maps
to a horizontal slit whose coordinates are determined
as part of the solution. Vertical lines
in the strip correspond to level curves of the
Green's function of the original problem.
(d) Finally, the exponential function maps the
strip to the upper half of the exterior of the
unit disk. The slit becomes a protruding turquoise
spike. Here the Green's function is
log jwj, with concentric circles as level curves.
Reflection extends the circles to the lower half-
plane, and following the maps in reverse produces
the curves of (a).
w-plane

Figure

3. Color-coded computed illustration of our algorithm for an example with
polygons. The blue, red, turquoise, green, and magenta boundary segments
in the various domains correspond under conformal maps. Fainter lines distinguish
function values obtained by reflection.
GREEN'S FUNCTIONS FOR MULTIPLY CONNECTED DOMAINS 7
Critical point, potential, and level curve. For sufficiently small ffl ? 0, the region
of CnE where g(z) ! ffl consists of K disjoint open sets surrounding the polygons P j .
At some value g c , two of these sets first coalesce at a point z c 2 R, which will be
a saddle point of g(z), i.e., a point where the gradient of g(z) and also the complex
derivative \Phi 0 (z) are zero [30]. We call z c the critical point, g c the critical potential,
and c g the critical level curve. (We speak as if z c is a single point
and just two sets coalesce there, which is the generic situation, but in special cases
there may be more than one critical point and more than two coalescing regions, as
in Fig. 7 below.)
These critical quantities can be immediately obtained from the geometry of our
conformal mapping problem. Let w c denote the endpoint of the shortest protruding
spike as in Figs. 2 or 3(d). Then z is the index of
the critical point a j as in Figure 1), g c = log(jw c j), and the critical level curve is the
pre-image under \Phi of the circle j. For the example of Fig. 3, z
0:634942, and the critical level curve is plotted in Fig. 3(a).
Asymptotic convergence factor. In applications to polynomial approximation, as
described in Section 6, the absolute value of the end of the shortest spike is of particular
interest. With the same notation as above, we define the asymptotic convergence factor
associated with g(z) by
For the example of Fig. 3, ae = 0:529966.
Note that g c and ae depend on the shape of the domain E, but not on its scale.
Doubling the sizes of the polygons and the distances between them, for example, does
not change these quantities. They are also invariant with respect to translation of the
set E in the complex plane.
Harmonic measure. Another scale-independent quantity is the proportion - j of
the total charge on each polygon P j , which is known as the harmonic measure of P j
(with respect to the point This quantity is equal to - \Gamma1 times the
distance between the appropriate two slits in the strip domain (or a slit and one of
the semi-infinite boundary lines), or equivalently to - \Gamma1 times the angle between two
spikes (or a spike and the real axis) in the w-plane. In the notation of Fig. 1,
For the example of Fig. 3, the slit is at height Im oe 2
1:290334, and dividing by -
shows that the proportion of charge on the green square is 0:410726. The density
of charge at particular points along the boundary is equal to -
a number that is easy to evaluate since the Schwarz-Christoffel formula expresses \Phi(z)
in terms of integrals. (This density can be used to define the harmonic measure of
arbitrary measurable subsets of the boundary of E, not just of the boundary of P j .)
Capacity. The capacity C (= logarithmic capacity, also called the transfinite
diameter) of a compact set E ae C is a standard notion in complex analysis and approximation
theory [1,13]. This scale-dependent number can be defined informally as
the average distance between charges, in the geometric-mean sense, for an equilibrium
charge density distribution on the boundary of E. Familiar special cases are
for a disk of radius R and for an interval of length L. For a general domain
E, C is equal to the derivative dz=dw evaluated at
(Normally one would have absolute values, but for our problem \Phi 0 (1) is real and
positive.)
One way to compute C is to note that \Phi(z) is the composition of f 1 (z) and
exp(f 2 (z)), in the notation of Figs. 1 and 2, and f 0(1) is just the multiplicative
constant of the first of our two Schwarz-Christoffel maps. Thus the crucial quantity
to determine is the limit of z= exp(f 2 (z)) as z !1, whose logarithm is given by
lim
Z z
f 0(i) di
dz
since f 2 (t K This is a convergent integral of Schwarz-Christoffel type that can
be evaluated accurately by numerical methods related to those of SCPACK and the
Toolbox.
Alternatively, we have found that sufficient accuracy can be achieved without the
explicit manipulation of integrals. Using the Schwarz-Christoffel maps, we calculate
the quantities
for a collection of values of z such as 15. The function C(z) is
analytic at z = 1, and the capacity can be obtained in a standard manner
by Richardson extrapolation. For the example of Fig. 3,
The ideas of this section can be spelled out more fully in formulas, generally
integrals or double integrals involving the charge density distribution; see [13,21,29].
We omit these details here.
5. Further examples. Figures 4-7 present computed examples with
and 5 polygons. In each case, the critical level curve of g(z) has been plotted together
with three level curves outside the critical one. In the case of Fig. 6, a fifth level curve
has also been plotted that corresponds to the highest of the three saddle points of
g(z) for that problem. If the small square on the right in that figure were not present,
then by symmetry, there would be two saddle points between the long quadrilaterals
at the same value of g(z). The square, however, breaks the symmetry, moving those
saddle points to the slightly distinct levels
shown).

Figure

7 may puzzle the reader. Why does the critical level curve self-intersect at
four points, indicating four saddles at exactly the same level, even though there is no
left-right symmetry in the figure? The answer is that the coordinates of the squares in
this example have been adjusted to make this happen. The widths of the squares are
1, 2, 3, 4, and 5, with the left-hand edges of the first two located at
This gave us a system of three nonlinear equations in three unknowns to solve for the
locations of the remaining three left-hand edges that would achieve the uniform critical
value. (This is an example of a generalized Schwarz-Christoffel parameter problem, in
which geometric constraints from various domains are mixed [27].) The locations that
satisfy the conditions are 10:948290, 20:326250, and 31:191359, the critical potential
value is 0:0698122, and the capacity is
6. Applications to polynomial approximation. Many uses of Green's functions
pertain to problems of polynomial approximation. The basis of this connection
is an elementary fact: if
log and thus the
size of a polynomial p(z) is essentially the same as the value of the potential generated
GREEN'S FUNCTIONS FOR MULTIPLY CONNECTED DOMAINS 9

Figure

4. Green's function for a region defined by two polygons. This computation
is identical in structure to that of Fig. 3.

Figure

5. Green's function for a region defined by three degenerate polygons with
empty interior. As it is exteriors that are conformally mapped, the degeneracy has no
effect on the mathematical problem or the method of solution.
by "point charges" with potentials log located at its roots fz j g. In the limit
as the number of roots and charges goes to 1, one obtains a continuous problem such
as (1). Generally speaking, the properties of optimal degree-n polynomials for various
approximation problems can typically be determined to leading order as n !1 from
the Green's function in the sense that we get the exponential factors right but not the
algebraic ones. Numerous results in this vein are set forth in the treatise of Walsh

Figure

6. Green's function for a region defined by four polygons. The square on the
side breaks the symmetry.

Figure

7. Green's function for a region defined by five polygons. The spacing of the
squares has been adjusted to make all the critical points lie at the same value g c .
[30].
Perhaps the simplest approximation topic one might consider is the Chebyshev
polynomials fTng associated with a compact set E ' C. For each n, defined
as the monic polynomial of degree n that minimizes (z)j. The
following result indicates one of the connections between Tn and the Green's function
for E.
Theorem 1. Let E ' C be a compact set with capacity C. Then a unique
Chebyshev polynomial exists for each n - 0, and
lim
It follows from this theorem that the numerical methods of this paper enable us to
determine the leading order behavior of Chebyshev polynomials for polygons symmetrically
located on the real axis. For example, the nth Chebyshev polynomial of
the five-square region of Fig. 7 has size approximately (10:292969) n . Other related
matters, such as generalized Faber polynomials [32], can also be pursued.
GREEN'S FUNCTIONS FOR MULTIPLY CONNECTED DOMAINS 11
Theorem 1 is due to Szeg-o [25], who extended earlier work of Fekete; a proof can
be found for example in [29]. For the case in which E is a smooth Jordan domain,
Faber showed that in fact consists of two intervals,
Akhiezer showed that kTnk=C n oscillates between two constants, and the starting
point of the paper of Widom [32] is the generalization of this result to a broad class
of sets E with multiple components.
Instead of discussing Chebyshev polynomials further, we shall consider a different,
related approximation problem investigated by Walsh, Russell, and Fuchs, among
others [8,9,30,31]. Let h 1
K be entire functions, i.e., each h j is analytic
throughout the complex plane, and to keep the formulations simple, assume that
these functions are distinct. The following is a special case of the general complex
Chebyshev approximation problem:
Polynomial Approximation Problem. Given n, find a polynomial
pn of degree n that minimizes the quantity
Note that we are concerned here with simultaneous approximation of distinct functions
on disjoint sets by a single polynomial. The approximations are measured only
on the polygons nothing is required in the "don't care'' space in-between. For
digital filtering, the polygons would typically be intervals corresponding to pass and
stop bands, and for matrix iterations, they would be regions approximately enclosing
various components of the spectrum or pseudospectra of the matrix.
According to results of approximation theory going back to Chebyshev, there
exists a polynomial pn that minimizes (7), and it is unique [2,3,30]. What is interesting
is how much about pn can be inferred from the Green's function. We summarize two
of the known facts about this problem as follows:
Theorem 2. Let fpng and fEng be the optimal polynomials and corresponding
errors for the Polynomial Approximation Problem, let g be the Green's function, and
let the critical level curve and the asymptotic convergence factor ae be defined as in
Section 4. Then
(a) lim sup n!1 E 1=n
(b) ("Overconvergence") pn (z) ! h j (z) as n !1, not only for z 2 P j , but for
all z in the region enclosed by the component of the critical level curve enclosing P j ,
with uniform convergence on compact subsets. Conversely, pn (z) does not converge
uniformly to h j (z) in any neighborhood of any point on the critical level curve.
These results are due in important measure to Walsh, and are proved in his
treatise [30]; see Theorems 4.5-4.7 and 4.11 and the discussions surrounding them.
Some of this material was presented earlier in a 1934 paper by Walsh and Helen G.
Russell [31], which attributes previous related work to Faber, Bernstein, M. Riesz,
Fej'er, and Szeg-o. The formulations as we have stated them are not very sharp. The
original results of Walsh are more quantitative, and they were sharpened further by
Fuchs, especially for the case in which E is a collection of intervals [8,9].
Theorem 2 concerns the exact optimal polynomials for the Polynomial Approximation
Problem, which are usually unknown and difficult to compute. Walsh showed
that the same conclusions apply more generally, however, to any sequence of polynomials
that is maximally convergent, which means, any sequence fpng whose errors
fEng as defined by (7) satisfy condition (a) of Theorem 2. Now then, how can we
construct maximally convergent sequences? Further results of Walsh establish that
this can be done via interpolation in suitably distributed points:
Theorem 3. Consider a sequence of sets of
either
lying in E or converging uniformly to E as n !1, and suppose that the potential they
generate in the sense of Section 4 converges uniformly to the Green's function g(z) on
all compact subsets disjoint from E. Let fpng be the sequence of polynomials of degrees
generated by interpolation in these points of a function h(z) defined in
C with in a neighborhood of each P j . This sequence of polynomials is
maximally convergent for the Polynomial Approximation Problem.
Theorem 4. The overconvergence result of Theorem 2(b) applies to any sequence
fpng of maximally convergent polynomials for the Polynomial Approximation Problem.
For proofs see Theorems 4.11 and 7.2 of [30] and the discussions nearby.
Theorem 3 implies that once the Green's function g(z) is known, it can be used to
construct maximally convergent polynomials by a variety of methods. The simplest
approach is to take pn to be the polynomial defined by interpolation of h j in the
pre-images along the boundary of P j of roots of unity in the w-plane:
Alternatively, and perhaps slightly more effective in practice, we may adjust the points
along the boundary of each polygon P j . Given n, we determine by (8) and (9) the
number n j of interpolation points that will lie on the boundary of P j . If ' and ' are
the lower and upper edge angles along the unit circle in the w-plane corresponding
to P j (in the notation of Fig. 1, then we define the actual
interpolation points along the boundary of P j by (8) and
Both of the choices (9) and (10) lead to maximal convergence as in Theorem 3.

Figure

8 illustrates the ideas of Theorems 2 and 3, especially the phenomenon of
overconvergence. Here we continue with the same geometry as in Fig. 3 and construct
near-best approximations pn (z) by interpolation of the constants \Gamma1 on the hexagon
and +1 on the square in the points described by (8) and (9). These two constants
represent distinct entire functions, so the polynomials fpn (z)g cannot converge glob-
ally. They converge on regions much larger than the polygons themselves, however, as
the figure vividly demonstrates: all the way out to the critical "figure-8" level curve,
in keeping with Theorem 2. The colors correspond to just the real part of pn (z), but
the imaginary part (not shown) looks similar, taking values close to zero inside the
figure-8 and growing approximately exponentially outside.
Our final example, motivated by the work of Mitchell, Shen and Strang on digital
filters, takes a special case in which E consists of two real intervals. Consider the
approximation problem defined by a "stop band" P 1
and a "pass band" P 2
That is, the problem is to find
polynomials pn of degree n that minimize
ae
oe
GREEN'S FUNCTIONS FOR MULTIPLY CONNECTED DOMAINS 13
[ The original image
is of higher quality,
and is attached at
the end of the paper. ]

Figure

8. Illustration of the overconvergence phenomenon of Theorem 2(b) and
Theorem 4. On the same two-polygon region as in Fig. 3, a polynomial p(z) is sought
that approximates the values \Gamma1 on the hexagon and +1 on the square. For this
figure, p is taken as the degree-29 near-best approximation defined by interpolation in
pre-images of roots of unity in the unit circle under the conformal map
(eqs. (8) and (9)); a similar plot for the exactly optimal polynomial would not look
much different. The figure shows Rep(z) by a blue-red color scale together with the
polygons, the interpolation points, and the figure-8 shaped critical level curve of the
Green's function. Not just on the polygons themselves, but throughout the two lobes
of the figure-8, Rep(z) comes close to the constant values \Gamma1 and +1. Outside, it
grows very fast.
Our Schwarz-Christoffel computations (elementary, since the more difficult first map
f 1 of Fig. 1 is the identity in this case) show that the asymptotic convergence factor
0:947963, the capacity is 0:499287, the critical point and level are z
\Gamma0:350500 and g c = 0:053440, and the harmonic measures are -
For Fig. 9 plots the near-best polynomial pn defined by interpolation
in the points defined by (8) and (10). The polynomial has approximately equiripple
form, suggesting that it is close to optimal. The horizontal dashed lines suggest the
error in this approximation, but it is clear they do not exactly touch the maximal-
error points of the curve. In fact, these dashed lines are drawn at distances \Sigmaae
from the line to be approximated, where ae is the asymptotic convergence factor; the
adjustment by p
n is suggested by the theorems of Fuchs [8]. In other words, these
lines mark a predicted error based on the Green's function, not the actual error of the
polynomial approximation obtained from it.

Figure

shows the actual optimal polynomial for this approximation problem,
with equiripple behavior. Something looks wrong here-the errors seem bigger than
14 MARK EMBREE AND LLOYD N. TREFETHEN
Figure

9. The near-best polynomial p 19
(x) obtained from the Green's function by
interpolation in the 20 points (8), (10) of 0 in the stop band [\Gamma1; \Gamma0:4] and 1 in the
pass band [\Gamma0:3; 1]. The polynomial is not optimal, but it is close.
Figure

10. Same as Fig. 9, but for the optimal polynomial p 19
computed by the
Remes algorithm. At first glance, the approximation looks worse. In fact, it is better,
since there are large errors in Fig. 9 at the inner edges of the stop and pass bands.
GREEN'S FUNCTIONS FOR MULTIPLY CONNECTED DOMAINS 15
-0.3506
proportion of interpolation
points in the stop band
position of critical point

Figure

11. Comparison of Green's function predictions (solid curves) with exact
equiripple approximations (dots) for the example (11). Details in the text.
in Fig. 9, not smaller! In fact, Fig. 9 is not as good as it looks. At the right edge of
the stop band and at the left edge of the pass band, for x - \Gamma0:4 and x - \Gamma0:3, there
are large errors. The numerical results line up as follows:
Optimal error En : 0:1176
n estimated from Green's function: 0:0831
in polynomial obtained from Green's function: 0:2030
In some engineering applications, of course, Fig. 9 might represent a better filter than
Fig. 10 after all.

Figure

presents three comparisons between properties of the exactly optimal
polynomials pn (x) for this problem (solid dots) and predictions based on the Green's
function (curves). Plot (a) compares the error En with the prediction ae
(the
distances between the horizontal dashed lines in Figs. 9 and 10). Evidently these
quantities differ by a factor of less than 2. Plot (b) compares the proportion of the
interpolation points that lie in the stop band with the harmonic measure - 1 . The
agreement is as good as one could hope for. Finally, plot (c) compares the point x in
[\Gamma1; 1] at which the optimal polynomial satisfies vertical dashed line
of Fig. 10) with the critical point z c (the vertical dashed line of Fig. 9). Evidently
the Green's function makes a good prediction of this transition point for finite n and
exactly the right prediction as n !1, as it must by Theorem 2(b).
7. Weighted Green's functions for weighted approximation. In signal
processing applications, rather than a uniform approximation, one commonly wants
an approximation corresponding to errors weighted by different constants W j in different
In closing we note that the techniques we have described can be
generalized to this case by considering a weighted Green's function in which (1b) is
replaced by the condition
which depends on n. The function g can now be determined by a conformal map
onto a semi-infinite strip whose end is jagged, with the K segments lying at real parts
\Gamman \Gamma1 log W j . Numerical experiments show that this method is effective, and very
general theoretical developments along these lines are described in the treatise of Saff
and Totik [21].



--R

Topics in Geometric Function Theory
Theory of Approximation
Introduction to Approximation Theory
Algorithm 756: A MATLAB toolbox for Schwarz-Christoffel mapping
From potential theory to matrix iterations in six steps
Polynomial Based Iteration Methods for Symmetric Linear Systems
Topics in the Theory of Functions of One Complex Variable
On the degree of Chebyshev approximation on sets with several components
On Chebyshev approximation on several disjoint intervals
Lectures on Complex Approximation
Iterative Methods for Solving Linear Systems
Applied and Computational Complex Analysis
Analytic Function Theory
The small dispersion limit of the Korteweg-de Vries equation
of Elect.

Digital Filter Design
Chebyshev approximation for nonrecursive digital filters with linear phase
Theory and Applications of Digital Signal Processing
Iterative Methods for Sparse Linear Systems
Logarithmic Potentials with External Fields
The asymptotics of optimal (equiripple) filters
The potential theory of several intervals and its applications
Cambridge U.
Bermerkungen zu einer Arbeit von Herrn M.
Numerical computation of the Schwarz-Christoffel transformation
Analysis and design of polygonal resistors by conformal mapping

Potential Theory in Modern Function Theory
Interpolation and Approximation by Rational Functions in the Complex Domain
On the convergence and overconvergence of sequences of polynomials of best simultaneous approximation to several functions analytic in distinct regions
Extremal polynomials associated with a system of curves in the complex plane
--TR

--CTR
Tobin A. Driscoll, Algorithm 843: Improvements to the Schwarz--Christoffel toolbox for MATLAB, ACM Transactions on Mathematical Software (TOMS), v.31 n.2, p.239-251, June 2005
krylov subspace iteration;chebyshev polynomial;potential theory;conformal mapping;polynomial approximation;schwarz-christoffel formula;digital filter;green's function