APPROXIMATION

#1. Weierstrass Approximation Theorem Step 2: Reproduction of constants and linear functions

Statement Bn (1 , x )=1Bn (t , x )=x

Let f be a continuous function on [ a , b ].
Then for every ε > 0there exists a polynomial Pn (x )such that
Step 3: Convergence
max ⁡ ∣ f (x)−P n (x) ∣< ε
x∈[ a ,b ]
Using properties of binomial distribution,
i.e. lim ⁡ B n (f , x)=f ( x)
n →∞
lim ⁡ Pn (x)=f (x)
n →∞ uniformly on [ 0 , 1 ].
uniformly on [ a , b ]. Hence

max ⁡ ∣ B n (f , x)−f (x )∣ →0
0 ≤ x ≤1
Proof (using Bernstein Polynomials)
Thus polynomials approximate any continuous function.
For f ∈ C [0 , 1]define
✔ Weierstrass theorem proved.

( kn )(nk) x ¿
n
Bn (f , x )=∑ f ⁣ k

k=0

#2. Fejér–Hermite Operator

These are called Bernstein polynomials.
Let Lnbe the Fejér-Hermite interpolation operator with nodes at
the zeros of
Step 1: Polynomial property
T n (x)
Bn (f , x )is a polynomial of degree n.
(Chebyshev polynomial).

1|Page
 Using Korovkin type argument

Goal If an operator sequence satisfies

Ln f → f for all f ∈C (−1 ,1) 2

Ln (1)→ 1 , Ln ( x )→ x , Ln ( x )→ x
2

then
Idea of Proof Ln f → f

The interpolation polynomial is uniformly for f ∈ C [−1 , 1].

n
Fejér-Hermite operator satisfies these conditions.
Ln ( f , x )=∑ f (¿ x k )l 2k (x)¿
k=1
Therefore
where
Ln f → f
x k = zeros of T n (x)

and l k (x )are Lagrange polynomials.

#3(a) Inequality for Polynomials

For polynomial Pwith degree ≤ n−1

Properties
max ⁡ ∣ P( x) ∣≤ max ⁡ ∣ n √ 1−x2 P(x )∣
−1 ≤ x ≤1 −1 ≤ x≤ 1
1. Operator is positive

2. Preserves constants
Idea
Ln (1)=1
Let
3. Kernel behaves like Fejér kernel
x=cos ⁡θ

Define

2|Page
 Q(θ)=P (cos ⁡θ) ∣T n (x)∣≤ 1

Then Q(θ)becomes a trigonometric polynomial of degree ≤ n−1. and

Using the inequality for trigonometric polynomials '

T n (1)=n
2

'
∣Q(θ)∣≤ max ⁡∣Q (θ)∣ Chebyshev polynomial gives the maximum derivative growth,
hence
and
' 2
' ' ∣ P (x )∣≤ n ∥ P∥ ∞
Q (θ)=−sin ⁡θ P (x )

After rearranging we obtain

#4(a) Error Bound for Lipschitz Functions
∣ P(x )∣ ≤ n √ 1−x 2 ∣ P' (x)∣
Given
which yields the required inequality.
∣ f (x )−f ( y)∣≤ λ ∣ x− y ∣

Then the best approximation error

#3(b) Markov Inequality
En (f )=min ⁡ max ⁡∣ f ( x )− pn ( x)∣
For polynomial Pof degree ≤ n pn

max
'
⁡ ∣ P (x)∣≤ n max
2
⁡ ∣ P(x )∣ satisfies
−1 ≤ x ≤1 −1≤ x ≤1
πλ
En (f )≤
2(n+1)
Proof Idea

Use Chebyshev polynomial

Proof Idea
T n (x)=cos ⁡(n arccos ⁡x)
Using Jackson theorem
which satisfies
3|Page
For Lipschitz functions Idea

ω (f , 1/n) Write
En (f )≤ C
n
S(θ)=sin ⁡θ T (θ)
where modulus of continuity
where T (θ)is trigonometric polynomial of degree ≤ n−1.
ω (f , δ)≤ λδ
Using Bernstein inequality for trigonometric polynomials
Substitute
∣T (θ)∣ ≤ n max ⁡∣ S(θ)∣
π
δ= which yields the result.
n+1

which gives
πλ #5(a) Fundamental Polynomials A k ( x)
En (f )≤
2(n+1)
Nodes are zeros of

¿
#4(b) Trigonometric Polynomial Inequality
where Pn−1= Legendre polynomial.
Let
For ( 0 , 2 )interpolation the fundamental polynomials satisfy
S(θ)
Conditions
be odd trigonometric polynomial of degree ≤ n.
1.
Then
A k ( x j)=δ kj
S(θ)
max ⁡ ∣ ∣≤ n max ⁡ ∣ S(θ)∣ 2.
−π ≤ θ ≤π sin θ −π ≤θ ≤ π
'
A k ( x j)=0

4|Page
 3. Thus each node is a double root.

Degree condition Number of roots ≥ 2 n.

deg ⁡A k (x )≤ 2 n−1 But

4. deg ⁡R (x)≤ 2n−1

Interpolation polynomial Hence only possibility

n
R(x )≡ 0
P(x )=∑ f (¿ x k ) Ak (x )¿
k=1
Therefore

P(x )=Q(x )
#5(b) Uniqueness of ( 0 , 2 )Interpolation
✔ Interpolation is unique.
Suppose two polynomials
#6(a) Zeros of the second derivative
P(x ), Q( x )
We need to show that the zeros of
satisfy same conditions. 2
d
2[
(1−x ) Pn−1 (x ) ]
2 '

Let dx

R(x )=P(x )−Q(x ) are the same as the zeros of

'
Then Pn (x )

R(x k )=0 where Pn (x )are Legendre polynomials.

and Legendre identity

'
R (x k )=0 Legendre polynomials satisfy

5|Page
 d 2 ' Bk (x )=¿ ¿
[(1−x ) Pn (x)]=−n(n+1) Pn (x )
dx
for
Replace nby n−1
k =2 ,3 , … , n−1
d 2 '
[(1−x ) Pn−1 (x)]=−(n−1)n Pn−1 (x )
dx Properties

Differentiate again: Bk (x j )=0 ( j ≠ k )Bk (x k )=1

2
d 2 ' '
2
[(1−x )Pn−1 ( x )]=−(n−1)n P n−1( x )
dx
#6(c) First fundamental polynomial A k ( x)
Using the Legendre recurrence relation
For the same interpolation problem,
' n
Pn (x )= 2
[ Pn−1 (x)−x Pn (x )] A k ( x)=¿
1−x

it follows that the roots coincide with those of P'n (x ). for

Hence proved. k =1 ,2 , … , n

#6(b) Fundamental polynomial Bk (x ) 8. Cubic spline with S' ' (x j)=M j

For interpolation of type ( 0 , 2 )on nodes Let

xk x 0 < x 1< ⋯< x nh j=x j −x j−1

which are zeros of The cubic spline on [ x j−1 , x j ]is

¿ S(x )=M j−1 ¿ ¿
the fundamental polynomial is
6|Page
Equations for M j #9(b) Equations for m j

Continuity of S' ( x) gives Using continuity of second derivative:

h j M j−1+2 (h j + h j +1) M j +h j+1 M j+1=6

[ y j+1− y j y j− y j−1
h j+1
−
hj ] h j m j−1+ 2(h j+ h j +1)m j +h j+1 m j+ 1=3
[ hj
h j +1
( y j+1− y j)+
h j+1
hj ]
( y j − y j−1 )

for

j=1 ,2 , … , n−1 #10(i)

b

∫¿¿
a
#9(a) Cubic spline with given slopes

Given
10(ii)
S(x j)= y j S' (x j )=m j
b n
M j−M j−1
The spline on [ x j−1 , x j ]becomes cubic Hermite form ∫f ''
(x )S (x )dx=M 0 f −M f + ∑ (¿ f j−f j −1 )
'' '
0
'
n n
hj
¿
a j=1

S(x )= y j−1 H 1 (t)+ y j H 2 (t )+ h j m j−1 H 3 (t)+h j m j H 4 (t)

where 10(iii)
x−x j−1 The stationary condition for
t=
hj
b

and E=∫ ¿ ¿
a

3 2 3 2 3 2 3 2
H 1=2 t −3 t +1H 2=−2 t + 3t H 3=t −2 t +t H 4 =t −t leads to the spline equations

7|Page
 [ ]
2
f j+1−f j f j−f j−1 f (x)=1, f (x)=x , f (x)=x
h j M j−1+2 (h j + h j +1) M j +h j+1 M j+1=6 −
h j+1 hj
Hence
which determine the M j . 2 2
Ln 1→ 1 , Ln x → x , Ln x → x
#1. Korovkin Theorem (for monotone operators)
Thus (ii) holds.
Let Lnbe a sequence of monotone (positive) linear operators on

Step 2: (ii) ⇒ (iii)

C [a , b].

Show the following are equivalent:

Take
1. Ln f → f uniformly for every f ∈ C [a ,b ].
ϕ (x )=¿
2. Ln f → f for the three functions 1 , x , x 2.
Expand:
3. Ln 1→ 1and
( t−x ¿2=t 2−2 tx+ x 2
Ln ϕ (t)→0
Apply Ln:
uniformly in t , where
2 2
Ln ϕ (t)=Ln ( t −2 tx+ x )
ϕ (x )=¿
Using linearity,

Step 1: (i) ⇒ (ii)

2 2
¿ t Ln 1−2 t Ln x + Ln x

If From (ii)
2 2
Ln f → f uniformly for all f ∈C [a , b] Ln 1→ 1 , Ln x → x , Ln x → x

then it must hold for the particular functions Thus

2 2 2
Ln ϕ (t)→t −2 t +t =0
8|Page
uniformly in t . Thus

Hence (iii) holds. Ln f → f

uniformly on [ a , b ].

Step 3: (iii) ⇒ (i) Hence (i) holds.

Let f ∈ C [a ,b ].

Because f is continuous on a closed interval, it is uniformly Conclusion

continuous.
¿
Hence for any ϵ >0 , there exists δ >0such that
Therefore all three conditions are equivalent.
∣ f (x )−f (t)∣<ϵ if ∣ x−t ∣<δ
#3(a) Solution
Using standard inequality,
Given the operator
∣ f (x )−f (t)∣ ≤ ϵ+ M ¿
¿
for some constant M .
where f is 2 π -periodic and f ' is continuous.
Apply operator Ln:
The Fourier coefficients are
∣ Ln f (t)−f (t)∣≤ Ln ∣ f (x )−f (t) ∣≤ ϵ Ln 1+ M Ln ¿ π π
1 1
From (iii)
a k= ∫
π −π
f (t)cos ⁡kt dtb k = ∫ f (t)sin ⁡kt dt
π −π

Ln 1→ 1 , Ln ¿

Therefore Step 1: Use Fourier series representation

∣ Ln f (t)−f (t)∣≤ ϵ + M ⋅ 0 For a 2 π -periodic function with continuous derivative,

9|Page
 a0 ∞
f (x)= + ∑ (¿ a k cos ⁡kx +b k sin ⁡kx)¿
2 k=1
#3(b) Solution
Hence
Show that
¿ π

∫ (sin ⁡kx )sgn(sin ⁡nx) dx =0 for k < n

0

Step 2: Use integration by parts for coefficients

Using Step 1: Express the sign function

{−11
π
1 sin ⁡nx> 0
a k cos ⁡kx +b k sin ⁡kx= ∫ f (t)cos ⁡k (x−t) dt
π −π
sgn (sin ⁡nx)=
sin ⁡nx< 0

Differentiate under the integral and integrate by parts: It alternates sign over intervals
t mπ (m+1)π
f (t)=f (x + π−t )−∫ f ( x + π−s)ds
' <x<
n n
x

Substituting into the representation and simplifying gives

Step 2: Split the integral
[
( −1 ¿
]
π n k
1 1
(Lf −f )( x)= ∫ + ∑
'
A k sin ⁡kt f (x+ π −t)dt π n−1
π −π 2 k=1 k
∫ (sin ⁡kx )sgn(sin ⁡nx)dx=¿ ∑ ¿ ¿ ¿
0 m =0

[
( −1 ¿
]
π n k
1 1
(Lf −f )( x)= ∫ + ∑
'
A k sin ⁡kt f (x+ π −t) dt Step 3: Evaluate the integral
π −π 2 k=1 k
−cos ⁡kx
which is the required result. ∫ sin ⁡kx dx=
k

10 | P a g e
Thus Define

1
n−1
Q(θ)=P (cos ⁡θ)
¿− ∑ ¿ ¿
k m=0
Since Phas degree ≤ n−1, Q(θ)is a trigonometric polynomial of
For k < n, the cosine terms cancel pairwise because of periodic order ≤ n−1.
symmetry.

Hence
Step 2: Apply Bernstein inequality
π

∫ (sin ⁡kx )sgn(sin ⁡nx) dx =0 For trigonometric polynomials

0
'
∣Q (θ)∣≤ n max ⁡∣Q( θ)∣

But
#4(a) Solution
' '
Q (θ)=−P (cos ⁡θ)sin ⁡θ
Prove that for any polynomial Pof degree ≤ n−1,
Hence
max ⁡ ∣ P( x) ∣≤ max ⁡ ∣ n √ 1−x2 P( x)∣
−1 ≤ x ≤1 −1 ≤ x≤ 1
∣ P(cos ⁡θ)∣ ≤ n∣ sin ⁡θP(cos ⁡θ)∣

Step 1: Substitute Step 3: Convert back to x

Let
sin ⁡θ=√ 1−x 2
x=cos ⁡θ
Thus
Then
∣ P(x )∣ ≤ n √ 1−x 2 ∣ P(x )∣
√ 1−x 2=sin ⁡θ Taking maximum over [ −1 ,1 ]:

11 | P a g e
 ∣ n √ 1−x2 P( x)∣
n
max ⁡ ∣ P( x) ∣≤ max ⁡
−1 ≤ x ≤1 −1 ≤ x≤ 1 E=∑ ¿ ¿
i=1

#We need to minimize

Only the last two terms depend on M i.
b
E=∫ ( f (x )−S Δ (x) ) dx
'' '' 2
Using
a

'' x i−x x−x i−1

where S Δ (x)is the cubic spline on the partition S Δ (x)= M i−1+ Mi
hi hi
Δ : a=x0 < x 1 <⋯< x n=b
we obtain
Let xi

hi =xi −xi−1 , M i =S Δ(x i )

'' ∫ ¿¿
xi−1

For a cubic spline, on [ x i−1 , x i ] Thus the discrete form

xi
x i−x x−x i−1 n
hi n
E=C+ ∑ ( M i−1+ M i−1 M i + M i ) −2 ∑ ∫ f ' ' (x )S 'Δ' (x )dx
'' 2 2
S Δ (x)= M i−1+ Mi
hi hi i=1 3 i =1 x i−1

where C is independent of M i.
1. Discrete form of E

Write the integral as a sum over subintervals: 2. Stationary condition

n xi
Stationary points occur when
E=∑ ∫ ¿ ¿ ¿
i=1 x i−1
∂E
=0
Expanding the square, ∂Mj

After differentiating and simplifying we obtain

12 | P a g e
 ( )
y j +1− y j y j− y j−1 ∣ P(x 0 )∣=M
h j M j−1+2 (h j + h j +1) M j +h j+1 M j+1=6 −
h j +1 hj
Define
for F (x)=P (x)−P (x 0)
j=1 ,2 , … , n−1
Then
where F (x 0)=0
y j=f (x j )
Since Phas degree ≤ n−1, F also has degree ≤ n−1.

Now consider
3. Final system of equations 2 '
G(x )=(1−x ) P (x )

h j M j−1+2 (h j + h j +1) M j +h j+1 M j+1=6

( y j +1− y j y j− y j−1
h j +1
−
hj ) By properties of extremal polynomials on [ −1 ,1 ], the maximum of
P(x )occurs where
with boundary conditions (natural spline) '
P (x 0)=0 or x 0 =±1
M 0=0 , M n=0 #Q5(a)
Using the standard inequality for polynomials on [ −1 ,1 ]:
Prove that for any polynomial Pof degree ≤ n−1,
∣ P(x )∣ ≤ n √ 1−x 2 ∣ P' (x)∣
max ⁡ ∣ P( x) ∣≤ max ⁡ ∣ n √ 1−x2 P' (x)∣ Taking maximum on both sides:
−1 ≤ x ≤1 −1 ≤ x≤ 1

Proof max ⁡ ∣ P( x) ∣≤ max ⁡ ∣ n √ 1−x2 P' (x)∣

−1 ≤ x ≤1 −1 ≤ x≤ 1

Let
Hence proved.
M =max ⁡ ∣ P(x )∣
−1≤ x ≤1

Then there exists x 0 ∈[−1 , 1]such that #Q5(b)

13 | P a g e
Prove that for any polynomial Pof degree ≤ n Multiplying by M :
' 2 ' 2
max ⁡ ∣ P (x)∣≤ n max ⁡ ∣ P(x )∣ ∣ P (x )∣≤ n M
−1 ≤ x ≤1 −1≤ x ≤1

Thus
Proof (Markov Inequality)
' 2
Let max ⁡ ∣ P ( x)∣≤ n max ⁡ ∣ P(x )∣
−1 ≤ x ≤1 −1≤ x ≤1

M =max ⁡ ∣ P(x )∣ Hence proved.

−1≤ x ≤1

Define

P (x) #Q6(a)
Q(x )=
M Show that the (0,2) interpolation on the zeros of
Then ¿
∣Q(x )∣ ≤1 exists.
Now the Markov inequality for polynomials states: Proof
If Q(x )is a polynomial of degree n satisfying Let
∣Q(x )∣ ≤1(−1≤ x ≤ 1) 2
ω (x)=(1−x ) Pn−1 (x )
'

then
The polynomial Pn−1 (x) is the Legendre polynomial of degree n−1.
' 2
∣Q (x )∣≤ n
Properties:
Therefore
1. Pn−1 (x) has n−1simple zeros in (−1 , 1 ).
'
P (x)
∣ ∣ ≤n 2 2. P'n−1 (x) therefore has n−2zeros in (−1 , 1 ).
M

14 | P a g e
Now If f (x)is a continuous function on [ a , b ], then for every ε > 0there
2 ' exists a polynomial Pn (x )such that
ω (x)=(1−x ) Pn−1 (x )
max ⁡ ∣ f (x)−P n (x) ∣< ε
Zeros occur at: x∈[ a ,b ]

x=−1 , x=1 i.e., every continuous function on a closed interval can be

uniformly approximated by polynomials.
and the zeros of P'n−1 (x) .

Hence total zeros:

Proof (using Bernstein Polynomials)
(n−2)+2=n
Consider f (x)∈C [0 ,1] .
Thus we obtain n interpolation nodes
Define the Bernstein polynomial
x 1 , x 2 ,… , x n

( kn )(nk) x ¿
n

For (0,2) interpolation, the conditions are: Bn (f ; x )=∑ f k

k=0
'
S(x k )=f (x k ), S (x k )=0 Properties:
for k =1 ,2 , … , n. 1. Bn (f ; x )is a polynomial of degree n .
Total conditions: 2. f continuous on [ 0 , 1 ]⇒ uniformly continuous.
2n Let ω (δ)be modulus of continuity.
A polynomial of degree ≤ 2 n−1has 2 ncoefficients. Then
Hence the system is solvable and (0,2) interpolation exists.

#Q2. Weierstrass Approximation Theorem

∣ Bn (f ; x)−f (x )∣≤ ω (√ x (1−x )
n )
Statement Since

15 | P a g e
 √ x (1−x) π π
1
n
→ 0(n→ ∞ ) I =∫ sin ⁡kx sin ⁡nx dx¿ ∫ [cos ⁡(k −n)x −cos ⁡(k +n) x ]dx
0 20
therefore
Integrate
lim ⁡ B n (f ; x )=f (x) π
sin ⁡(mπ )
n →∞
∫ cos ⁡(mx)dx =¿ m
¿
uniformly on [ 0 , 1 ]. 0

Since m integer,
Hence polynomial approximation exists.
sin ⁡(mπ)=0
Thus Weierstrass theorem proved.
Thus both integrals vanish.

I =0
#Q3(a)
Hence proved.
Show that if k < n
π

∫ (sin ⁡kx )(sin ⁡nx )dx=0 #Q4(a)

0

For f ∈ C2 π

Proof

Use trigonometric identity

3
En (f )≤ ω
2
π
n+1 ( )
where
1
sin ⁡kx sin ⁡nx = [cos ⁡(k −n)x−cos ⁡( k +n) x ]
2  En (f )= best approximation error
Thus  ω (δ)= modulus of continuity

16 | P a g e
Proof Sketch #Q4(b)

Define modulus of continuity Given

ω (δ) ∣ x−=y ∣ ≤δ ⁡ ∣ f (x )−f ( y )∣ −α

En (f )≤ A n , 0< α <1

Using Fejér kernel approximation Show f ∈ Lip(α )

π
1
σ n (f ; x)= ∫ f (x−t)F n (t )dt
π −π
Proof
where F nis Fejér kernel. Choose best approximating polynomial Pn
Properties ∣∣ f −P n ∣∣ ≤ A n
−α

1. σ n (f )is a trigonometric polynomial degree n

Then
2. ∣ f (x )−f ( y)∣≤ ∣ f (x)−P n (x)∣+∣ P n (x)−P n ( y)∣+ ∣ Pn ( y )−f ( y )∣
3
∣ f (x )−σ n ( f ; x)∣≤ ω
2
π
n+1 ( ) Thus
−α
∣ f (x )−f ( y)∣≤ 2 A n +∣ Pn (x )−Pn ( y )∣
Since En (f )is minimum approximation error
Using polynomial derivative estimate
En (f )≤ ∣∣ f −σ n (f )∣∣
∣ Pn (x )−Pn ( y)∣≤Cn ∣ x− y ∣
Therefore
Choose
3
En (f )≤ ω
2
π
n+1 ( ) n≈
1
∣ x− y ∣
Hence proved.
Then

17 | P a g e
 α
∣ f (x )−f ( y)∣≤ C ∣ x− y ∣

Hence Equations for m j

f ∈ Lip(α ) Using continuity of S' ' ( x)

#Q9. Cubic Spline S Δ (x)

m j+1 −m j m j −m j−1
h j+ 1
+
hj
=3
(
y j +1− y j y j− y j−1
2
h j +1
− 2
hj )
Conditions These form a tridiagonal linear system to compute m j .

S Δ (x j )= y j S'Δ (x j )=m j
#Q10
for j=0 , 1, … , n
Given cubic spline S Δ (x)

Spline on interval [ x j−1 , x j ]

(i)
Let
b
h j=x j −x j−1 ∫¿¿
a
Cubic Hermite form
Using integration by parts
S(x )=( 1−3t +2 t ) y j −1 + ( 3 t − 2t ) y j
2 3 2 3
b
2 3 2
+h j (t−2 t +t )m j−1 +h j (−t + t )m j
3
∫¿¿
a

where
Since spline minimizes energy functional,
x−x j−1 b
t=
hj ∫¿¿
a

18 | P a g e
is the minimum curvature energy among all interpolants.

(ii)
b

∫ f ' ' (x )S Δ (x )dx

a

Using integration by parts twice

b

∫ f ' ' Sdx=¿¿ ¿

a

Thus
b

∫ f ' ' (x )S Δ (x )dx =¿

a

19 | P a g e