1 Weirstrass Theorem ¶ Weirstrass Theorem says that we can approximate continuous functions by polynomials. Take f : [ 0 , 1 ] → R f : [0,1] \to \re f : [ 0 , 1 ] → R
p n ( x ) = ∑ k = 0 n ( n k ) f ( k / n ) x k ( 1 − x ) n − k , x ∈ [ 0 , 1 ] p_n(x) = \sum_{k=0}^n \binom{n}{k} f(k/n) x^k (1-x)^{n-k}, \qquad x \in [0,1] p n ( x ) = k = 0 ∑ n ( k n ) f ( k / n ) x k ( 1 − x ) n − k , x ∈ [ 0 , 1 ] If f f f x x x
lim n → ∞ p n ( x ) = f ( x ) \lim_{n \to \infty} p_n(x) = f(x) n → ∞ lim p n ( x ) = f ( x ) If f f f x ∈ [ 0 , 1 ] x \in [0,1] x ∈ [ 0 , 1 ] p n → f p_n \to f p n → f [ 0 , 1 ] [0,1] [ 0 , 1 ]
lim n → ∞ max 0 ≤ x ≤ 1 ∣ f ( x ) − p n ( x ) ∣ = 0 \lim_{n \to \infty} \max_{0 \le x \le 1}|f(x) - p_n(x)| = 0 n → ∞ lim 0 ≤ x ≤ 1 max ∣ f ( x ) − p n ( x ) ∣ = 0 We have written p n p_n p n
B r n ( x ) = ( n r ) x r ( 1 − x ) n − r and ( n k ) = n ! k ! ( n − k ) ! B_r^n(x) = \binom{n}{r} x^r (1-x)^{n-r} \qquad \textrm{and} \qquad \binom{n}{k} = \frac{n!}{k! (n-k)!} B r n ( x ) = ( r n ) x r ( 1 − x ) n − r and ( k n ) = k ! ( n − k )! n ! Let f : [ a , b ] → R f:[a,b] \to \re f : [ a , b ] → R ϵ > 0 \epsilon > 0 ϵ > 0 p p p
∣ f ( x ) − p ( x ) ∣ ≤ ϵ , x ∈ [ a , b ] |f(x) - p(x)| \le \epsilon, \qquad x \in [a,b] ∣ f ( x ) − p ( x ) ∣ ≤ ϵ , x ∈ [ a , b ] This theorem states that given any error tolerance ϵ > 0 \epsilon > 0 ϵ > 0 p p p
max x ∈ [ a , b ] ∣ f ( x ) − p ( x ) ∣ ≤ ϵ \max_{x\in[a,b]}|f(x) - p(x)| \le \epsilon x ∈ [ a , b ] max ∣ f ( x ) − p ( x ) ∣ ≤ ϵ i.e., polynomials can provide uniform approximation. This is only an existence result and does not give us a solution with a desired error bound. It also does not tell us the degree of the polynomial.
Consider
f ( x ) = x 2 , x ∈ [ 0 , 1 ] f(x) = x^2, \qquad x \in [0,1] f ( x ) = x 2 , x ∈ [ 0 , 1 ] Then the Bernstein polynomial satisfies
lim n → ∞ n [ p n ( x ) − x 2 ] = x ( 1 − x ) ⟹ p n ( x ) − x 2 ≈ 1 n x ( 1 − x ) , n ≫ 1 \lim_{n \to \infty} n [p_n(x) - x^2] = x (1-x) \limplies p_n(x) - x^2 \approx \frac{1}{n} x (1-x), \quad n \gg 1 n → ∞ lim n [ p n ( x ) − x 2 ] = x ( 1 − x ) ⟹ p n ( x ) − x 2 ≈ n 1 x ( 1 − x ) , n ≫ 1 The error decreases at linear rate, which is very slow convergence. A quadratic interpolation will recovery the function exactly using just three function values.
1 = 1 n = ( 1 − x + x ) n = ∑ k = 0 n ( n k ) x k ( 1 − x ) n − k 1 = 1^n = (1-x + x)^n = \sum_{k=0}^n \binom{n}{k} x^k (1-x)^{n-k} 1 = 1 n = ( 1 − x + x ) n = k = 0 ∑ n ( k n ) x k ( 1 − x ) n − k p n ( x ) − x 2 = ∑ k = 0 n ( n k ) ( ( k / n ) 2 − x 2 ) x k ( 1 − x ) n − k p_n(x) - x^2 = \sum_{k=0}^n \binom{n}{k} ( (k/n)^2 - x^2) x^k (1-x)^{n-k} p n ( x ) − x 2 = k = 0 ∑ n ( k n ) (( k / n ) 2 − x 2 ) x k ( 1 − x ) n − k 2 Taylor expansion ¶ The Taylor expansion provides another way to approximate a function in a neighbourhood of some point at which the expansion is written. A Taylor expansion will exactly recover a polynomial function so we consider somewhat more non-trivial but still simple function. E.g.
f ( x ) = exp ( x ) , x ∈ [ − 1 , 1 ] f(x) = \exp(x), \qquad x \in [-1,1] f ( x ) = exp ( x ) , x ∈ [ − 1 , 1 ] The third degree Taylor expansion around x = 0 x=0 x = 0
p 3 ( x ) = 1 + x + 1 2 x 2 + 1 6 x 3 p_3(x) = 1 + x + \half x^2 + \frac{1}{6} x^3 p 3 ( x ) = 1 + x + 2 1 x 2 + 6 1 x 3 We can estimate the error also from the remainder term
exp ( x ) − p 3 ( x ) = 1 24 x 4 exp ( ξ ) , ξ between 0 and x \exp(x) - p_3(x) = \frac{1}{24} x^4 \exp(\xi), \qquad \textrm{$\xi$ between $0$ and $x$} exp ( x ) − p 3 ( x ) = 24 1 x 4 exp ( ξ ) , ξ between 0 and x and we get the following estimate
1 24 x 4 ≤ exp ( x ) − p 3 ( x ) ≤ e 24 x 4 , 0 ≤ x ≤ 1 \frac{1}{24} x^4 \le \exp(x) - p_3(x) \le \frac{\ee}{24} x^4, \qquad 0 \le x \le 1 24 1 x 4 ≤ exp ( x ) − p 3 ( x ) ≤ 24 e x 4 , 0 ≤ x ≤ 1 1 24 e x 4 ≤ exp ( x ) − p 3 ( x ) ≤ 1 24 x 4 , − 1 ≤ x ≤ 0 \frac{1}{24\ee} x^4 \le \exp(x) - p_3(x) \le \frac{1}{24} x^4, \qquad -1 \le x \le 0 24 e 1 x 4 ≤ exp ( x ) − p 3 ( x ) ≤ 24 1 x 4 , − 1 ≤ x ≤ 0 By a direct calculation, the error is
max − 1 ≤ x ≤ 1 ∣ exp ( x ) − p 3 ( x ) ∣ ≈ 0.0516 \max_{-1 \le x \le 1}|\exp(x) - p_3(x)| \approx 0.0516 − 1 ≤ x ≤ 1 max ∣ exp ( x ) − p 3 ( x ) ∣ ≈ 0.0516 Plotting the error, we see that it is not uniformly distributed in the interval [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] x = 0 x=0 x = 0
FIGURE
3 Cubic interpolation ¶ We can get much better cubic polynomial approximation than the Taylor polynomial. Let us interpolate a cubic polynomial at { − 1 , − 1 3 , + 1 3 , + 1 } \{-1, -\frac{1}{3}, +\frac{1}{3}, +1\} { − 1 , − 3 1 , + 3 1 , + 1 }
p 3 ( x ) = 0.99519577 + 0.99904923 x + 0.54788486 x 2 + 0.17615196 x 3 p_3(x) = 0.99519577 + 0.99904923 x + 0.54788486 x^2 + 0.17615196 x^3 p 3 ( x ) = 0.99519577 + 0.99904923 x + 0.54788486 x 2 + 0.17615196 x 3 The maximum error is approximately 0.00998 which is almost five times smaller than the Taylor polynomial. The error is also more uniformly distributed and oscillates in sign.
FIGURE