#%config InlineBackend.figure_format = 'svg'
from pylab import *
from scipy.interpolate import barycentric_interpolate
Let X = ( X , ∥ ⋅ ∥ ) X = (X, \norm{\cdot}) X = ( X , ∥ ⋅ ∥ ) x ∈ X x \in X x ∈ X y ∈ Y y \in Y y ∈ Y Y Y Y X X X x x x Y Y Y
δ = δ ( x , Y ) = inf y ∈ Y ∥ x − y ∥ \delta = \delta(x,Y) = \inf_{y \in Y} \norm{x - y} δ = δ ( x , Y ) = y ∈ Y inf ∥ x − y ∥ If there is y 0 ∈ Y y_0 \in Y y 0 ∈ Y
∥ x − y 0 ∥ = δ \norm{x -y_0} = \delta ∥ x − y 0 ∥ = δ then y 0 y_0 y 0 best approximation to x x x Y Y Y
∥ x − y 0 ∥ ≤ ∥ x − y ∥ , ∀ y ∈ Y \norm{x - y_0} \le \norm{x - y}, \qquad \forall y \in Y ∥ x − y 0 ∥ ≤ ∥ x − y ∥ , ∀ y ∈ Y 7.5.1 Existence ¶ If Y Y Y X = ( X , ∥ ⋅ ∥ ) X=(X, \norm{\cdot}) X = ( X , ∥ ⋅ ∥ ) x ∈ X x \in X x ∈ X x x x Y Y Y
Let us apply this result to some examples.
Example 2 (Approximation in
L p [ a , b ] L^p[a,b] L p [ a , b ] )
X = C [ a , b ] , ∥ x ∥ = ( ∫ a b ∣ x ( t ) ∣ p d x ) 1 / p , p ≥ 1 Y = P n \begin{gather}
X = \cts[a,b], \qquad \norm{x} = \left( \int_a^b |x(t)|^p \ud x \right)^{1/p}, \qquad p \ge 1 \\
Y = \poly_n
\end{gather} X = C [ a , b ] , ∥ x ∥ = ( ∫ a b ∣ x ( t ) ∣ p d x ) 1/ p , p ≥ 1 Y = P n Then by Theorem 1 Y Y Y x ∈ L p [ a , b ] x \in L^p[a,b] x ∈ L p [ a , b ]
The finite dimensionality of Y Y Y
Let
Y = { p : [ 0 , 1 2 ] → R , p is a polynomial } Y = \{ p :[0,\shalf] \to \re , p \textrm{ is a polynomial} \} Y = { p : [ 0 , 2 1 ] → R , p is a polynomial } and dim( Y ) = ∞ (Y) = \infty ( Y ) = ∞ C [ 0 , 1 2 ] \cts[0,\shalf] C [ 0 , 2 1 ]
x ( t ) = 1 1 − t x(t) = \frac{1}{1 - t} x ( t ) = 1 − t 1 Then for every ϵ > 0 \epsilon > 0 ϵ > 0 N N N
y n ( t ) = 1 + t + … + t n satisfies ∥ x − y n ∥ ∞ < ϵ , n > N y_n(t) = 1 + t + \ldots + t^n \qquad\textrm{satisfies}\qquad \norm{x - y_n}_\infty < \epsilon, \quad n > N y n ( t ) = 1 + t + … + t n satisfies ∥ x − y n ∥ ∞ < ϵ , n > N and hence δ ( x , Y ) = 0 \delta(x,Y) = 0 δ ( x , Y ) = 0 x x x y 0 ∈ Y y_0\in Y y 0 ∈ Y δ ( x , Y ) = ∥ x − y 0 ∥ ∞ = 0 \delta(x,Y) = \norm{x - y_0}_\infty = 0 δ ( x , Y ) = ∥ x − y 0 ∥ ∞ = 0
We can state the existence result in another way.
Let X X X x ∈ X x \in X x ∈ X { x 1 , x 2 , … , x n } ⊂ X \{ x_1, x_2, \ldots, x_n \} \subset X { x 1 , x 2 , … , x n } ⊂ X
min { a i } ∥ x − ( a 1 x 1 + … + a n x n ) ∥ \min_{\{a_i\}} \norm{x - (a_1 x_1 + \ldots + a_n x_n)} { a i } min ∥ x − ( a 1 x 1 + … + a n x n ) ∥ has a solution. We only need ∥ ⋅ ∥ \norm{\cdot} ∥ ⋅ ∥ X X X Y = span { x 1 , x 2 , … , x n } Y = \textrm{span}\{ x_1, x_2, \ldots, x_n \} Y = span { x 1 , x 2 , … , x n }
Let us apply this result to some examples.
Example 4 (Discrete minimax)
Let X = C [ a , b ] X = \cts[a,b] X = C [ a , b ] t 0 , t 1 , … , t m t_0, t_1, \ldots, t_m t 0 , t 1 , … , t m m + 1 m+1 m + 1 [ a , b ] [a,b] [ a , b ] m ≥ n m \ge n m ≥ n Theorem 2 x ∈ X x \in X x ∈ X
min a 0 , a 1 , … , a n max 0 ≤ i ≤ m ∣ x ( t i ) − ( a 0 + a 1 t i + … + a n t i n ) ∣ \min_{a_0,a_1,\ldots,a_n} \max_{0 \le i \le m}| x(t_i) - (a_0 + a_1 t_i + \ldots + a_n t_i^n)| a 0 , a 1 , … , a n min 0 ≤ i ≤ m max ∣ x ( t i ) − ( a 0 + a 1 t i + … + a n t i n ) ∣ has a solution. Here Y = P n Y = \poly_n Y = P n
∥ p ∥ = max 0 ≤ i ≤ m ∣ p ( t i ) ∣ \norm{p} = \max_{0 \le i \le m} |p(t_i)| ∥ p ∥ = 0 ≤ i ≤ m max ∣ p ( t i ) ∣ is a norm on Y Y Y
Example 5 (Discrete least squares)
Let X = C [ a , b ] X = \cts[a,b] X = C [ a , b ] t 0 , t 1 , … , t m t_0, t_1, \ldots, t_m t 0 , t 1 , … , t m m + 1 m+1 m + 1 [ a , b ] [a,b] [ a , b ] m ≥ n m \ge n m ≥ n Theorem 2 x ∈ X x \in X x ∈ X
min a 0 , a 1 , … , a n ∑ i = 0 m [ x ( t i ) − ( a 0 + a 1 t i + … + a n t i n ) ] 2 \min_{a_0,a_1,\ldots,a_n} \sum_{i=0}^m [ x(t_i) - (a_0 + a_1 t_i + \ldots + a_n t_i^n)]^2 a 0 , a 1 , … , a n min i = 0 ∑ m [ x ( t i ) − ( a 0 + a 1 t i + … + a n t i n ) ] 2 has a solution. Here Y = P n Y = \poly_n Y = P n
∥ p ∥ = ∑ i = 0 m [ p ( t i ) ] 2 \norm{p} = \sum_{i=0}^m [p(t_i)]^2 ∥ p ∥ = i = 0 ∑ m [ p ( t i ) ] 2 is a norm on Y Y Y
7.5.2 Convexity ¶ To show uniqueness of the best approximation, we need some convexity property. Let M M M
M = { y ∈ Y : ∥ x − y ∥ ≤ ∥ x − z ∥ , ∀ z ∈ Y } M = \{ y \in Y : \norm{x-y} \le \norm{x - z}, \ \forall z \in Y \} M = { y ∈ Y : ∥ x − y ∥ ≤ ∥ x − z ∥ , ∀ z ∈ Y } In a normed space ( X , ∥ ⋅ ∥ ) (X, \norm{\cdot}) ( X , ∥ ⋅ ∥ ) M M M x x x Y Y Y X X X
The set M M M
Definition 1 (Strict convexity)
A strictly convex norm ∥ ⋅ ∥ \norm{\cdot} ∥ ⋅ ∥ x ≠ y x \ne y x = y ∥ x ∥ = ∥ y ∥ = 1 \norm{x} = \norm{y} = 1 ∥ x ∥ = ∥ y ∥ = 1
∥ x + y ∥ < 2 \norm{x + y} < 2 ∥ x + y ∥ < 2 A normed space with such a norm is called a strictly convex normed space.
Show that ( C n , ∥ ⋅ ∥ ) (\complex^n, \norm{\cdot}) ( C n , ∥ ⋅ ∥ )
∥ x ∥ = ( ∑ i = 1 n ∣ x i ∣ p ) 1 / p , p > 1 \norm{x} = \left( \sum_{i=1}^n |x_i|^p \right)^{1/p}, \qquad p > 1 ∥ x ∥ = ( i = 1 ∑ n ∣ x i ∣ p ) 1/ p , p > 1 is a strictly convex normed space.
Every Hilbert space is strictly convex. The space C [ a , b ] \cts[a,b] C [ a , b ] x ( t ) = 1 x(t)=1 x ( t ) = 1 y ( t ) = ( t − a ) / ( b − a ) y(t) = (t-a)/(b-a) y ( t ) = ( t − a ) / ( b − a ) The space L p [ a , b ] L^p[a,b] L p [ a , b ] 1 < p < ∞ 1 < p < \infty 1 < p < ∞ 7.5.3 Uniqueness ¶ We cannot use the results of this chapter to show uniqueness of minimax problem since maximum norm is not strictly convex. We have shown the uniqueness of minimax by different techniques in previous chapter, using equioscillation property.
7.5.4 Hilbert spaces ¶ We have quite general results in inner product spaces.
(1) Let X X X Y Y Y x ∈ X x \in X x ∈ X y ∈ Y y \in Y y ∈ Y
(2) If Y Y Y X X X y ∈ Y y \in Y y ∈ Y x − y x - y x − y Y Y Y
In the above result, Y Y Y
From these two results, we can again conclude Corollary 1
7.5.4.1 Solution in finite dimensional case ¶ If X X X Y Y Y Y Y Y
Y = span { x 1 , x 2 , … , x n } , ( x i , x j ) = δ i j Y = \textrm{span}\{x_1, x_2, \ldots, x_n\}, \qquad \ip{x_i, x_j} = \delta_{ij} Y = span { x 1 , x 2 , … , x n } , ( x i , x j ) = δ ij The best approximation
y = a 1 x 1 + a 2 x 2 + … + a n x n y = a_1 x_1 + a_2 x_2 + \ldots + a_n x_n y = a 1 x 1 + a 2 x 2 + … + a n x n to x ∈ X x \in X x ∈ X x − y ⊥ Y x - y \perp Y x − y ⊥ Y
( x − y , x j ) = 0 , 1 ≤ j ≤ n \ip{x - y, x_j} = 0, \qquad 1 \le j \le n ( x − y , x j ) = 0 , 1 ≤ j ≤ n which yields the solution
a j = ( x , x j ) , 1 ≤ j ≤ n a_j = \ip{x, x_j}, \qquad 1 \le j \le n a j = ( x , x j ) , 1 ≤ j ≤ n and
y = ∑ j = 1 n ( x , x j ) x j y = \sum_{j=1}^n \ip{x, x_j} x_j y = j = 1 ∑ n ( x , x j ) x j We now consider the best approximation problem in maximum norm. Since we dont have convexity, we need different techniques to prove uniqueness.
Definition 2 (Haar condition)
A subspace Y Y Y C [ a , b ] \cts[a,b] C [ a , b ] ( y ) = n (y)=n ( y ) = n y ∈ Y y \in Y y ∈ Y y ≠ 0 y \ne 0 y = 0 n − 1 n-1 n − 1 [ a , b ] [a,b] [ a , b ]
Let Y = P m Y = \poly_m Y = P m
n = dim ( Y ) = m + 1 n = \textrm{dim}(Y) = m+1 n = dim ( Y ) = m + 1 Every nonzero polynomial y ∈ Y y \in Y y ∈ Y m = n − 1 m = n-1 m = n − 1 P m \poly_m P m
The Haar condition is equivalent to the condition that for every basis { y 1 , y 2 , … , y n } \{ y_1, y_2, \ldots, y_n\} { y 1 , y 2 , … , y n } Y Y Y n n n t 1 , … , t n t_1, \ldots, t_n t 1 , … , t n [ a , b ] [a,b] [ a , b ]
det V ≠ 0 , V i j = y i ( t j ) \det V \ne 0, \qquad V_{ij} = y_i(t_j) det V = 0 , V ij = y i ( t j ) Recall that V V V Y Y Y n n n
An extremal point of an x ∈ C [ a , b ] x \in \cts[a,b] x ∈ C [ a , b ] t 0 ∈ [ a , b ] t_0 \in [a,b] t 0 ∈ [ a , b ] ∣ x ( t 0 ) ∣ = ∥ x ∥ |x(t_0)| = \norm{x} ∣ x ( t 0 ) ∣ = ∥ x ∥
Lemma 4 (Extremal points)
Suppose a subspace Y Y Y C [ a , b ] \cts[a,b] C [ a , b ] ( Y ) = n (Y)=n ( Y ) = n x ∈ C [ a , b ] x \in \cts[a,b] x ∈ C [ a , b ] y ∈ Y y \in Y y ∈ Y x − y x-y x − y n + 1 n+1 n + 1 y y y x x x Y Y Y
Notice the similarity with the equioscillation property. If Y = P m Y = \poly_m Y = P m y ∈ P m y \in \poly_m y ∈ P m x − y x - y x − y m + 2 m+2 m + 2 y y y
Theorem 6 (Haar uniqueness theorem)
Let Y Y Y C [ a , b ] \cts[a,b] C [ a , b ] Y Y Y x ∈ C [ a , b ] x \in \cts[a,b] x ∈ C [ a , b ] Y Y Y
Corollary 2 (Polynomials)
Given any x ∈ C [ a , b ] x \in \cts[a,b] x ∈ C [ a , b ] y ∈ P m y \in \poly_m y ∈ P m x x x