from pylab import *
from scipy.interpolate import barycentric_interpolate
6.4.1 Analytic functions ¶ We first recall some results about analytic functions. For more details and some proofs, see Davis, 1963
A function f : [ a , b ] → R f : [a,b] \to \re f : [ a , b ] → R [ a , b ] [a,b] [ a , b ] x 0 ∈ [ a , b ] x_0 \in [a,b] x 0 ∈ [ a , b ]
f ( x ) = a 0 + a 1 ( x − x 0 ) + a 2 ( x − x 0 ) 2 + … , ∣ x − x 0 ∣ < ρ ( x 0 ) f(x) = a_0 + a_1(x-x_0) + a_2 (x-x_0)^2 + \ldots, \qquad |x-x_0| < \rho(x_0) f ( x ) = a 0 + a 1 ( x − x 0 ) + a 2 ( x − x 0 ) 2 + … , ∣ x − x 0 ∣ < ρ ( x 0 ) We write f ∈ A [ a , b ] f \in A[a,b] f ∈ A [ a , b ]
A [ a , b ] A[a,b] A [ a , b ] f ∈ A [ a , b ] f \in A[a,b] f ∈ A [ a , b ] f ∈ C ∞ [ a , b ] f \in \cts^\infty[a,b] f ∈ C ∞ [ a , b ]
a n = 1 n ! f ( n ) ( x 0 ) , n = 0 , 1 , … a_n = \frac{1}{n!} f^{(n)}(x_0), \qquad n=0,1,\ldots a n = n ! 1 f ( n ) ( x 0 ) , n = 0 , 1 , … The converse is not true; not all C ∞ C^\infty C ∞
A single valued function f : R → C f : R \to \complex f : R → C R ⊂ C R \subset \complex R ⊂ C z 0 ∈ R z_0 \in R z 0 ∈ R
f ( z ) = ∑ n = 0 ∞ a n ( z − z 0 ) n , ∣ z − z 0 ∣ < ρ ( z 0 ) f(z) = \sum_{n=0}^\infty a_n (z - z_0)^n, \qquad |z - z_0| < \rho(z_0) f ( z ) = n = 0 ∑ ∞ a n ( z − z 0 ) n , ∣ z − z 0 ∣ < ρ ( z 0 ) If this holds for all z 0 ∈ R z_0 \in R z 0 ∈ R R R R f ∈ A ( R ) f \in A(R) f ∈ A ( R )
Theorem 3 (Cauchy integral formula)
Let R ⊂ C R \subset \complex R ⊂ C f ∈ A ( R ) f \in A(R) f ∈ A ( R ) z 0 ∈ R z_0 \in R z 0 ∈ R C C C R R R z 0 z_0 z 0
f ( n ) ( z 0 ) = n ! 2 π i ∮ C f ( z ) ( z − z 0 ) n + 1 d z f^{(n)}(z_0) = \frac{n!}{2 \pi \ii} \oint_C \frac{f(z)}{(z-z_0)^{n+1}} \ud z f ( n ) ( z 0 ) = 2 π i n ! ∮ C ( z − z 0 ) n + 1 f ( z ) d z In particular, for n = 0 n=0 n = 0
f ( z 0 ) = 1 2 π i ∮ C f ( z ) z − z 0 d z f(z_0) = \frac{1}{2 \pi \ii} \oint_C \frac{f(z)}{z-z_0} \ud z f ( z 0 ) = 2 π i 1 ∮ C z − z 0 f ( z ) d z Real analytic functions can be completely characterized by the growth of their derivatives.
Let f ∈ C ∞ [ a , b ] f \in \cts^\infty[a,b] f ∈ C ∞ [ a , b ] f ∈ A [ a , b ] f \in A[a,b] f ∈ A [ a , b ] r > 0 r > 0 r > 0
∣ f ( n ) ( x ) ∣ ≤ r n n ! , x ∈ [ a , b ] , n = 0 , 1 , 2 , … |f^{(n)}(x)| \le r^n n!, \qquad x \in [a,b], \qquad n=0,1,2,\ldots ∣ f ( n ) ( x ) ∣ ≤ r n n ! , x ∈ [ a , b ] , n = 0 , 1 , 2 , … Analyticity can be related to differentiability.
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 ) z = x + i y z=x+\ii y z = x + i y
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
Theorem 5 (Cauchy-Riemann equations)
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 ) z = x + i y z = x + \ii y z = x + i y u x , u y , v x , v y u_x, u_y, v_x, v_y u x , u y , v x , v y
∂ 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 6.4.2 Lagrange interpolation ¶ Let x 0 , x 1 , … , x n x_0,x_1,\ldots,x_n x 0 , x 1 , … , x n n + 1 n+1 n + 1
ℓ ( x ) = ( x − x 0 ) ( x − x 1 ) … ( x − x n ) \ell(x) = (x-x_0) (x-x_1) \ldots (x-x_n) ℓ ( x ) = ( x − x 0 ) ( x − x 1 ) … ( 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
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
Γ j \Gamma_j Γ j x j x_j x j 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}
& \quad \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' Γ ′ { x j } \{x_j\} { x j } x x x f f f Γ ′ \Gamma' Γ ′ Γ ′ = ∪ j Γ j \Gamma' = \cup_j \Gamma_j Γ ′ = ∪ j Γ j Γ j \Gamma_j Γ j x j x_j x j
Then we can combine the Γ j \Gamma_j Γ j
p ( x ) = ∑ j f ( x j ) ℓ j ( x ) = 1 2 π i ∑ j ∮ Γ j f ( x j ) ℓ ( x ) d t ℓ ( t ) ( x − t ) using same type of argument used above, we get = 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)
&= \sum_j f(x_j) \ell_j(x) \\
&= \frac{1}{2\pi\ii} \sum_j \oint_{\Gamma_j} f(x_j) \frac{\ell(x) \ud t}{\ell(t) (x- t)} \\
& \qquad \textrm{using same type of argument used above, we get} \\
&= \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 ) = j ∑ f ( x j ) ℓ j ( x ) = 2 π i 1 j ∑ ∮ Γ j f ( x j ) ℓ ( t ) ( x − t ) ℓ ( x ) d t using same type of argument used above, we get = 2 π i 1 j ∑ ∮ Γ j f ( t ) ℓ ( t ) ( x − t ) ℓ ( x ) d t = 2 π i 1 ∮ Γ ′ ℓ ( t ) ( x − t ) ℓ ( x ) f ( t ) d t Now suppose we enlarge the contour of integration Γ ′ \Gamma' Γ ′
Γ that encloses x x x { x j } \{x_j\} { x j } f f f Γ = Γ ′ ∪ Γ ′ ′ \Gamma = \Gamma' \cup \Gamma'' Γ = Γ ′ ∪ Γ ′′ Γ ′ ′ \Gamma'' Γ ′′ x x x
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 ) − ℓ ( x ) f ( x ) ℓ ( x ) = 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) - \ell(x) \frac{f(x)}{\ell(x)} \\
&= 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 ) − ℓ ( x ) ℓ ( x ) f ( x ) = p ( x ) − f ( x ) where we used the Cauchy integral formula to get the second term: − f ( x ) -f(x) − f ( x )
Let f f f x 0 , x 1 , … , x n x_0,x_1,\ldots,x_n x 0 , x 1 , … , x n p ∈ P n p \in \poly_n p ∈ P n f f f
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
(1) If Γ encloses x x x f ( x ) f(x) f ( x )
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 x x x
(2) The formula for f ( x ) − p ( x ) f(x)-p(x) f ( x ) − p ( x )
6.4.3 Effect of point distribution { x j } \{x_j\} { x j } ¶ On a fixed contour Γ inside which f f f f ( t ) f(t) f ( t ) t − x t-x t − x (17) { x j } \{x_j\} { x j }
ℓ ( 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 Γ can be taken far away from { x j } \{x_j\} { x j } 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 → ∞ p ( x ) p(x) p ( x ) f ( x ) f(x) f ( x ) n → ∞ n \to \infty n → ∞ it must be possible to continue f f f .
Let S S S stadium in the complex plane consisting of all points lying at a distance ≤ 2 \le 2 ≤ 2 [ − 1 , + 1 ] [-1,+1] [ − 1 , + 1 ] f f f S S S
theta = linspace(-pi/2,pi/2,100)
plot( 1.0+2*cos(theta),2*sin(theta),'b-')
plot(-1.0-2*cos(theta),2*sin(theta),'b-')
plot([-1,1],[2,2],'b-')
plot([-1,1],[-2,-2],'b-')
plot([-1,1],[0,0],'r-')
text(0,1,'S',ha='center',va='center')
xlabel('Real'), ylabel('Imag')
axis('equal'), grid(True);∣ x − x j ∣ ≤ 2 , ∣ t − x j ∣ > 2 ⟹ ∣ t − x j ∣ ∣ x − x j ∣ > 1 , t ∈ Γ |x-x_j| \le 2, \qquad |t-x_j| > 2 \limplies \frac{|t-x_j|}{|x-x_j|} > 1, \qquad t \in \Gamma ∣ x − x j ∣ ≤ 2 , ∣ t − x j ∣ > 2 ⟹ ∣ x − x j ∣ ∣ t − x j ∣ > 1 , t ∈ Γ there exists a γ such that
∣ t − x j ∣ ∣ x − x j ∣ ≥ γ > 1 , t ∈ Γ \frac{|t-x_j|}{|x-x_j|} \ge \gamma > 1, \qquad t \in \Gamma ∣ x − x j ∣ ∣ t − x j ∣ ≥ γ > 1 , t ∈ Γ This implies
∣ ℓ ( x ) ℓ ( t ) ∣ = ∏ j = 0 n ∣ x − x j t − x j ∣ ≤ γ − ( n + 1 ) , ∀ x ∈ [ − 1 , + 1 ] , t ∈ Γ \left| \frac{\ell(x)}{\ell(t)} \right| = \prod_{j=0}^n \left| \frac{x - x_j}{t - x_j} \right| \le \gamma^{-(n+1)}, \qquad \forall x \in [-1,+1],
\quad t \in \Gamma ∣ ∣ ℓ ( t ) ℓ ( x ) ∣ ∣ = j = 0 ∏ n ∣ ∣ t − x j x − x j ∣ ∣ ≤ γ − ( n + 1 ) , ∀ x ∈ [ − 1 , + 1 ] , t ∈ Γ and thus the error formula (17)
∥ f − p ∥ ∞ = O ( γ − n ) \norm{f-p}_\infty = 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 ]