1 Complex Analysis ¶ We first recall some results from complex variables.
A function f ( z ) = u ( x , y ) + i v ( x , y ) f(z) = u(x,y) + \ii v(x,y) f ( z ) = u ( x , y ) + i v ( x , y ) is differentiable at a point z = x + i y z=x+\ii y z = x + i y if
lim Δ z → 0 f ( z + Δ z ) − f ( z ) Δ z \lim_{\Delta z \to 0} \frac{f(z + \Delta z) - f(z)}{\Delta z} Δ z → 0 lim Δ z f ( z + Δ z ) − f ( z ) exists and is unique.
The necessary and sufficient condition is given by
A function f ( z ) = u ( x , y ) + i v ( x , y ) f(z) = u(x,y) + \ii v(x,y) f ( z ) = u ( x , y ) + i v ( x , y ) is differentiable at a point z = x + i y z = x + \ii y z = x + i y of a region in the complex plane if and only if the partial derivatives u x , u y , v x , v y u_x, u_y, v_x, v_y u x , u y , v x , v y are continuous and satisfy the
Cauchy-Riemann equations
∂ u ∂ y = − ∂ v ∂ x , ∂ u ∂ x = ∂ v ∂ y \df{u}{y} = -\df{v}{x}, \qquad \df{u}{x} = \df{v}{y} ∂ y ∂ u = − ∂ x ∂ v , ∂ x ∂ u = ∂ y ∂ v A function f ( z ) f(z) f ( z ) is analytic at z = z 0 z=z_0 z = z 0 if it is differentiable in a neighbourhood of z 0 z_0 z 0 .
A function f ( z ) f(z) f ( z ) is analytic in a region of the complex plane if it is analytic at every point of this
region.
A function f ( z ) f(z) f ( z ) is an entire function if it is analytic in the finite part of the complex plane.
2 Laurent expansion and residue ¶ If f ( z ) f(z) f ( z ) is not analytic at a single point z 0 z_0 z 0 , then we can use a Laurent series. Let f ( z ) f(z) f ( z ) be analytic in the region
D = { z : 0 < ∣ z − z 0 ∣ < ρ } D = \{ z : 0 < |z-z_0| < \rho \} D = { z : 0 < ∣ z − z 0 ∣ < ρ } and let z 0 z_0 z 0 be an isolated singular point of f ( z ) f(z) f ( z ) . The Laurent expansion of f ( z ) f(z) f ( z ) in D D D is given by
f ( z ) = ∑ n = − ∞ ∞ C n ( z − z 0 ) n f(z) = \sum_{n=-\infty}^\infty C_n (z-z_0)^n f ( z ) = n = − ∞ ∑ ∞ C n ( z − z 0 ) n with
C n = 1 2 π i ∮ C f ( z ) d z ( z − z 0 ) n + 1 C_n = \frac{1}{2\pi \ii} \oint_C \frac{f(z) \ud z}{(z-z_0)^{n+1}} C n = 2 π i 1 ∮ C ( z − z 0 ) n + 1 f ( z ) d z where C C C is a simple closed contour lying in D D D . The coefficient C − 1 C_{-1} C − 1 is called the residue of f ( z ) f(z) f ( z ) at z 0 z_0 z 0 . When n = − 1 n=-1 n = − 1 , we have
∮ C f ( z ) d z = 2 π i C − 1 \oint_C f(z) \ud z = 2\pi \ii C_{-1} ∮ C f ( z ) d z = 2 π i C − 1 3 Lagrange interpolation ¶ Let x 0 , x 1 , … , x n x_0,x_1,\ldots,x_n x 0 , x 1 , … , x n be a set of n + 1 n+1 n + 1 distinct interpolation points. Define
ℓ ( x ) = ( x − x 0 ) … ( x − x n ) \ell(x) = (x-x_0)\ldots(x-x_n) ℓ ( x ) = ( x − x 0 ) … ( x − x n ) The Lagrange polynomials are given by
ℓ j ( x ) = ℓ ( x ) ℓ ′ ( x j ) ( x − x j ) \ell_j(x) = \frac{\ell(x)}{\ell'(x_j)(x-x_j)} ℓ j ( x ) = ℓ ′ ( x j ) ( x − x j ) ℓ ( x ) and the interpolant of degree n n n is
p ( x ) = ∑ j = 0 n f ( x j ) ℓ j ( x ) p(x) = \sum_{j=0}^n f(x_j) \ell_j(x) p ( x ) = j = 0 ∑ n f ( x j ) ℓ j ( x ) Let x x x be any point which is distinct from the interpolation points. Let Γ j \Gamma_j Γ j be a contour in the complex plane that encloses x j x_j x j but none of the other points, nor the point x x x . Using the Cauchy integral formula, we see that
1 2 π i ∮ Γ j d t ℓ ( t ) ( x − t ) = 1 2 π i ∮ Γ j ϕ ( t ) t − x j d t where ϕ ( t ) = 1 ( t − x 0 ) … ( t − x j − 1 ) ( t − x j + 1 ) … ( t − x n ) ( x − t ) = ϕ ( x j ) = 1 ( x j − x 0 ) … ( x j − x j − 1 ) ( x j − x j + 1 ) … ( x j − x n ) ( x − x j ) = 1 ℓ ′ ( x j ) ( x − x j ) \begin{aligned}
& \frac{1}{2\pi\ii} \oint_{\Gamma_j} \frac{\ud t}{\ell(t) (x-t)} \\
=& \frac{1}{2\pi\ii} \oint_{\Gamma_j} \frac{\phi(t)}{t-x_j} \ud t \\
& \textrm{where} \qquad \phi(t) =
\frac{1}{(t-x_0)\ldots(t-x_{j-1})(t-x_{j+1})\ldots(t-x_n)(x-t)} \\
=& \phi(x_j) \\
=& \frac{1}{(x_j-x_0)\ldots(x_j-x_{j-1})(x_j-x_{j+1})\ldots(x_j-x_n)(x-x_j)} \\
=& \frac{1}{\ell'(x_j)(x-x_j)}
\end{aligned} = = = = 2 π i 1 ∮ Γ j ℓ ( t ) ( x − t ) d t 2 π i 1 ∮ Γ j t − x j ϕ ( t ) d t where ϕ ( t ) = ( t − x 0 ) … ( t − x j − 1 ) ( t − x j + 1 ) … ( t − x n ) ( x − t ) 1 ϕ ( x j ) ( x j − x 0 ) … ( x j − x j − 1 ) ( x j − x j + 1 ) … ( x j − x n ) ( x − x j ) 1 ℓ ′ ( x j ) ( x − x j ) 1 Hence
ℓ j ( x ) = ℓ ( x ) ℓ ′ ( x j ) ( x − x j ) = 1 2 π i ∮ Γ j ℓ ( x ) d t ℓ ( t ) ( x − t ) \ell_j(x) = \frac{\ell(x)}{\ell'(x_j)(x-x_j)} = \frac{1}{2\pi\ii} \oint_{\Gamma_j}
\frac{\ell(x) \ud t}{\ell(t) (x-t)} ℓ j ( x ) = ℓ ′ ( x j ) ( x − x j ) ℓ ( x ) = 2 π i 1 ∮ Γ j ℓ ( t ) ( x − t ) ℓ ( x ) d t Now let Γ ′ \Gamma' Γ ′ be a curve which encloses all of the points { x j } \{x_j\} { x j } but not the point x x x and let f f f be analytic on and interior to Γ ′ \Gamma' Γ ′ . Then we can combine the Γ j \Gamma_j Γ j integrals to get an expression for the interpolant
p ( x ) = 1 2 π i ∑ j ∮ Γ j f ( x j ) ℓ ( x ) d t ℓ ( t ) ( x − t ) = 1 2 π i ∑ j ∮ Γ j f ( t ) ℓ ( x ) d t ℓ ( t ) ( x − t ) = 1 2 π i ∮ Γ ′ ℓ ( x ) f ( t ) d t ℓ ( t ) ( x − t ) \begin{aligned}
p(x) =& \frac{1}{2\pi\ii} \sum_j \oint_{\Gamma_j} f(x_j) \frac{\ell(x) \ud t}{\ell(t) (x-
t)} \\
=& \frac{1}{2\pi\ii} \sum_j \oint_{\Gamma_j} f(t) \frac{\ell(x) \ud t}{\ell(t) (x-t)} \\
=& \frac{1}{2\pi\ii} \oint_{\Gamma'} \frac{\ell(x) f(t) \ud t}{\ell(t) (x-t)}
\end{aligned} p ( x ) = = = 2 π i 1 j ∑ ∮ Γ j f ( x j ) ℓ ( t ) ( x − t ) ℓ ( x ) d t 2 π i 1 j ∑ ∮ Γ j f ( t ) ℓ ( t ) ( x − t ) ℓ ( x ) d t 2 π i 1 ∮ Γ ′ ℓ ( t ) ( x − t ) ℓ ( x ) f ( t ) d t by using the same type of argument we used above.
Now suppose we enlarge the contour of integration to a new contour Γ that encloses x x x as well as { x j } \{x_j\} { x j } , and we assume f f f is analytic on and inside Γ. Then
1 2 π i ∮ Γ ℓ ( x ) f ( t ) d t ℓ ( t ) ( x − t ) = 1 2 π i ∮ Γ ′ ℓ ( x ) f ( t ) d t ℓ ( t ) ( x − t ) + 1 2 π i ∮ Γ ′ ′ ℓ ( x ) f ( t ) d t ℓ ( t ) ( x − t ) = p ( x ) − f ( x ) \begin{aligned}
\frac{1}{2\pi\ii} \oint_{\Gamma} \frac{\ell(x) f(t) \ud t}{\ell(t) (x-t)} =&
\frac{1}{2\pi\ii} \oint_{\Gamma'} \frac{\ell(x) f(t) \ud t}{\ell(t) (x-t)} + \frac{1}
{2\pi\ii} \oint_{\Gamma''} \frac{\ell(x) f(t) \ud t}{\ell(t) (x-t)} \\
=& p(x) - f(x)
\end{aligned} 2 π i 1 ∮ Γ ℓ ( t ) ( x − t ) ℓ ( x ) f ( t ) d t = = 2 π i 1 ∮ Γ ′ ℓ ( t ) ( x − t ) ℓ ( x ) f ( t ) d t + 2 π i 1 ∮ Γ ′′ ℓ ( t ) ( x − t ) ℓ ( x ) f ( t ) d t p ( x ) − f ( x ) where we used the Cauchy integral formula to get − f ( x ) -f(x) − f ( x ) .
Let f f f be analytic in a region Ω containing distinct points x 0 , x 1 , … , x n x_0,x_1,\ldots,x_n x 0 , x 1 , … , x n , and let Γ be a contour in Ω enclosing these points in the positive direction. The polynomial interpolant p ∈ P n p \in \poly_n p ∈ P n to f f f at these nodes is
p ( x ) = 1 2 π i ∮ Γ f ( t ) [ ℓ ( t ) − ℓ ( x ) ] ℓ ( t ) ( t − x ) d t p(x) = \frac{1}{2\pi\ii} \oint_{\Gamma} \frac{f(t)[\ell(t) - \ell(x)]}{\ell(t) (t-x)} \ud t p ( x ) = 2 π i 1 ∮ Γ ℓ ( t ) ( t − x ) f ( t ) [ ℓ ( t ) − ℓ ( x )] d t and if x x x is enclosed by Γ, the error in the interpolant is
f ( x ) − p ( x ) = 1 2 π i ∮ Γ ℓ ( x ) ℓ ( t ) f ( t ) ( t − x ) d t f(x) - p(x) = \frac{1}{2\pi\ii} \oint_{\Gamma} \frac{\ell(x)}{\ell(t)} \frac{f(t)}{(t-x)}
\ud t f ( x ) − p ( x ) = 2 π i 1 ∮ Γ ℓ ( t ) ℓ ( x ) ( t − x ) f ( t ) d t (1) If Γ encloses x x x , then by Cauchy integral formula, f ( x ) f(x) f ( x ) can be written as
f ( x ) = 1 2 π i ∮ Γ f ( t ) ( t − x ) d t = 1 2 π i ∮ Γ ℓ ( t ) f ( t ) ℓ ( t ) ( t − x ) d t f(x) = \frac{1}{2\pi\ii} \oint_{\Gamma} \frac{f(t)}{(t-x)} \ud t = \frac{1}{2\pi\ii}
\oint_{\Gamma} \frac{\ell(t) f(t)}{\ell(t) (t-x)} \ud t f ( x ) = 2 π i 1 ∮ Γ ( t − x ) f ( t ) d t = 2 π i 1 ∮ Γ ℓ ( t ) ( t − x ) ℓ ( t ) f ( t ) d t From previously derived formula for p ( x ) − f ( x ) p(x)-f(x) p ( x ) − f ( x ) ,
p ( x ) = f ( x ) + 1 2 π i ∮ Γ ℓ ( x ) f ( t ) ℓ ( t ) ( x − t ) d t = 1 2 π i ∮ Γ ℓ ( t ) f ( t ) ℓ ( t ) ( t − x ) d t − 1 2 π i ∮ Γ ℓ ( x ) f ( t ) ℓ ( t ) ( t − x ) d t = 1 2 π i ∮ Γ f ( t ) [ ℓ ( t ) − ℓ ( x ) ] ℓ ( t ) ( t − x ) d t \begin{aligned}
p(x) =& f(x) + \frac{1}{2\pi\ii} \oint_{\Gamma} \frac{\ell(x) f(t)}{\ell(t) (x-t)} \ud t\\
=& \frac{1}{2\pi\ii} \oint_{\Gamma} \frac{\ell(t) f(t)}{\ell(t) (t-x)} \ud t - \frac{1}
{2\pi\ii} \oint_{\Gamma} \frac{\ell(x) f(t)}{\ell(t) (t-x)} \ud t\\
=& \frac{1}{2\pi\ii} \oint_{\Gamma} \frac{f(t)[\ell(t) - \ell(x)]}{\ell(t) (t-x)} \ud t
\end{aligned} p ( x ) = = = f ( x ) + 2 π i 1 ∮ Γ ℓ ( t ) ( x − t ) ℓ ( x ) f ( t ) d t 2 π i 1 ∮ Γ ℓ ( t ) ( t − x ) ℓ ( t ) f ( t ) d t − 2 π i 1 ∮ Γ ℓ ( t ) ( t − x ) ℓ ( x ) f ( t ) d t 2 π i 1 ∮ Γ ℓ ( t ) ( t − x ) f ( t ) [ ℓ ( t ) − ℓ ( x )] d t In this formula, the integrand does not have a pole at t = x t=x t = x and hence it is valid even if Γ does not enclose x x x .
(2) The formula for f ( x ) − p ( x ) f(x)-p(x) f ( x ) − p ( x ) has already been derived.
4 Effect of point distribution { x j } \{x_j\} { x j } ¶ On a fixed contour Γ, the quantities f ( t ) f(t) f ( t ) and t − x t-x t − x in the error formula are independent of { x j } \{x_j\} { x j } . The error depends on the ratio
ℓ ( x ) ℓ ( t ) = ∏ j = 0 n ( x − x j ) ∏ j = 0 n ( t − x j ) \frac{\ell(x)}{\ell(t)} = \frac{ \prod\limits_{j=0}^n (x-x_j)}{\prod\limits_{j=0}^n(t-
x_j)} ℓ ( t ) ℓ ( x ) = j = 0 ∏ n ( t − x j ) j = 0 ∏ n ( x − x j ) If Γ is far away from { x j } \{x_j\} { x j } , then for each t ∈ Γ t \in \Gamma t ∈ Γ ,
∣ ℓ ( x ) ℓ ( t ) ∣ ≈ ∣ ℓ ( x ) ∣ ∣ t ∣ n + 1 , ∣ t ∣ → ∞ \left| \frac{\ell(x)}{\ell(t)} \right| \approx \frac{|\ell(x)|}{|t|^{n+1}}, \qquad |t| \to
\infty ∣ ∣ ℓ ( t ) ℓ ( x ) ∣ ∣ ≈ ∣ t ∣ n + 1 ∣ ℓ ( x ) ∣ , ∣ t ∣ → ∞ this ratio will shrink exponentially as n → ∞ n \to \infty n → ∞ , and if this happens, we may conclude that p ( x ) p(x) p ( x ) converges exponentially to f ( x ) f(x) f ( x ) as n → ∞ n \to \infty n → ∞ . The crucial condition is that it must be possible to continue f f f analytically far out to Γ .
Let S S S be the stadium in the complex plane consisting of all points lying at a distance ≤ 2 \le 2 ≤ 2 from [ − 1 , + 1 ] [-1,+1] [ − 1 , + 1 ] . Suppose f f f is analytic in a larger region Ω that includes a curve Γ enclosing S S S . Since
∣ x − x j ∣ ≤ 2 , ∣ t − x j ∣ > 2 , ∣ t − x j ∣ ∣ x − x j ∣ > 1 |x-x_j| \le 2, \qquad |t-x_j| > 2, \qquad \frac{|t-x_j|}{|x-x_j|} > 1 ∣ x − x j ∣ ≤ 2 , ∣ t − x j ∣ > 2 , ∣ x − x j ∣ ∣ t − x j ∣ > 1 there exists a γ such that
∣ t − x j ∣ ∣ x − x j ∣ ≥ γ > 1 \frac{|t-x_j|}{|x-x_j|} \ge \gamma > 1 ∣ x − x j ∣ ∣ t − x j ∣ ≥ γ > 1 This implies
∣ ℓ ( x ) ℓ ( t ) ∣ ≤ γ − ( n + 1 ) , ∀ x ∈ [ − 1 , + 1 ] , t ∈ Γ \left| \frac{\ell(x)}{\ell(t)} \right| \le \gamma^{-(n+1)}, \qquad \forall x \in [-1,+1],
\quad t \in \Gamma ∣ ∣ ℓ ( t ) ℓ ( x ) ∣ ∣ ≤ γ − ( n + 1 ) , ∀ x ∈ [ − 1 , + 1 ] , t ∈ Γ and thus by the error formula
∥ f − p ∥ = O ( γ − n ) \norm{f-p} = O(\gamma^{-n}) ∥ f − p ∥ = O ( γ − n ) Note that this conclusion applies regardless of the distribution of interpolation points in [ − 1 , + 1 ] [-1,+1] [ − 1 , + 1 ] . They could be equally spaced or random[1] .
So convergence of polynomial interpolants to analytic functions on [ − 1 , + 1 ] [-1,+1] [ − 1 , + 1 ] is all about how small ℓ ( x ) \ell(x) ℓ ( x ) is on [ − 1 , + 1 ] [-1,+1] [ − 1 , + 1 ] compared to how large it is on a contour Γ inside which f f f is analytic.