Transcript universal functions - Muskingum University

UNIVERSAL FUNCTIONS
A Construction Using Fourier
Approximations
Presentation Overview
1. An intuitive concept of Universal Functions
2. Function Approximation and  - Bans about Functions
3. Fourier Interpolation on the Interval [0, 2]
4. Fourier Approximation on an interval [a,b]
5. The Construction of a Universal Function
6. Other Universal Functions
7. The Category of Universal Functions
Universal Functions
(An Intuitive Concept)
A universal function is a function whose behavior on an interval (or part of
its graph) is "like any" continuous function you might select. Think of it as a
single function that can be used to describe all other functions.
The Universal Function we will construct in this presentation will be a function
whose translations (shift in their graph) will approximate any continuous function we
can think of on a given closed bounded interval (i.e. U(x+t)f(x)).
Think of the graph of such a function call it U(x) has the property that if you look
along the x-axis the graph of U(x) will be "close" to being the graph of any
continuous function f(x) (such as x2, 4+sin(2x) or arctan(x) etc.) you might select.
Graph of U x
6
4
...
2
-2
2
4
6
...
12
16
20
48
64
80
-4
-6
U x  4  x 2
U x  4  x 2  0
For x in 2,6
U x  16  4  sin 2 x 
U x  16  4  sin( 2 x)   0
For x in 12,20
U x  64  arctan x 
U x  64  arctan x   0
For x in 48,80
 - Bans of Functions on an Interval
The concept of a translation of U(x) coming "close" to being a function f(x) on a
closed bounded interval [a,b] has a more formal mathematical characterization.
We say a function p(x) approximates
a function f(x) within  (think of  as a
small positive number) on an interval
[a,b] if the following condition is
satisfied for all x in [a,b].
Intuitively we can think of this as the
graph of p(x) must lie below the graph
of f(x)+ and above the graph of f(x)-.
In other words, the graph of p(x) must
remain in the shaded area between the
two graphs for all of the points x in the
interval [a,b].
px   f x   
or
f x     px   f x   
f(x)+
f(x)
f(x)-
a
b
Fourier Interpolation
The Fourier Method of Interpolation is a way constructing a function to exactly
agree with a set of data points that uses combinations of sin(qx) and cos(qx) where
q is an integer.
Trigonometric Polynomials
A trigonometric polynomial of degree m (am0 or bm0) is a polynomial of the form:
p (t ) 
a0
2
 a1 cos(t )  a2 cos( 2t )  a3 cos(3t )    am cos( mt )
 b1 sin( t )  b2 sin( 2t )  b3 sin( 3t )    bm sin( mt )

a0
2
m
m
k 1
k 1
  ak cos( k t )   bk sin( k t )
Degree of a Trigonometric Interpolating Polynomial
For a data set with n data points the degree of the polynomial depends on if n is
even or odd. If m is the degree of the trigonometric polynomial the relation between n
and m is that:
n 1
m
(if n is odd )
2
m
n
(if n is even)
2
Interpolating Polynomials
Because of the distinction between even and odd the interpolating polynomials
take on two different forms. One if the data set has an even number of data items
another if it is odd.
This is the form if n (the number of data points) is odd:
p(t ) 
a0
2
 a1 cos(t )  a2 cos( 2t )  a3 cos(3t )    am cos( mt)
 b1 sin( t )  b2 sin( 2t )  b3 sin( 3t )    bm sin( mt)
This is the form if n (the number of data points) is even (notice the am term):
p(t ) 
a0
2
 a1 cos(t )  a2 cos( 2t )  a3 cos(3t )    a2m cos( mt)
 b1 sin( t )  b2 sin( 2t )  b3 sin( 3t )    bm sin( mt)
In either case the aj and bj terms are given by:
2 n 1
a j   xk cos j  2 kn  and
n k 0
2 n 1
b j   xk sin  j  2 kn 
n k 0
Example: Let’s use a Fourier Interpolation of the data {1,3,-5,2}
The number of data points is n=4 so m=4/2=2 as before. We begin by computing a0,
a1, a2, b1, b2. (Notice from the formula we can assume b0 is always 0.)
2
1 sin 0  204   3  sin 0  214   5 sin 0  224   2 sin 0  234 
4
1
1
b0  1  sin 0   3  sin 0   5 sin 0  2 sin 0   0  0  0  0   0
2
2
2
1 cos0  204   3  cos0  214   5 cos0  224   2 cos0  234 
4
1
1
1
a0  1  cos0   3  cos0   5 cos0   2 cos0   1  3  5  2  
2
2
2
b0 
2
1 cos1 204   3  cos1 214   5 cos1 224   2 cos1 234 
4
1
1
a1  1  cos0   3  cos2   5 cos   2 cos 32   1  0  5  0   3
2
2
b1 
a0 
a1 
2
1 cos2  204   3  cos2  214   5 cos2  224   2 cos2  234 
4
1
1
9
a2  1  cos0   3  cos   5 cos2   2 cos3   1  3  5  2  
2
2
2
a2 
2
1 sin 1 204   3  sin 1 214   5 sin 1 224   2 sin 1 234 
4
1
1
1
b1  1  sin 0   3  sin 2   5 sin    2 sin  32   0  3  0  2  
2
2
2
2
1 sin 2  204   3  sin 2  214   5 sin 2  224   2 sin 2  234 
4
1
1
b2  1  sin 0  3  sin    5 sin 2   2 sin 3   0  0  0  0   0
2
2
b2 
The interpolating polynomial is:
3
p (t ) 

a0
2
 a1 cos(t )  a22 cos( 2t )  b1 sin( t )  b2 sin( 2t )
1
9
1
 3 cos(t )  cos( 2t )  sin( t )
4
4
2
2
1
-1
-2
-3
-4
-5
2
3
2
2
Approximation on a Closed Interval [a,b]
We can interpolate any data set on an interval [a,b] by translating the interval [a,b] to
the interval [0,2] then translating back. The trade off we make is that the function
p(x) that is used to do this takes a slightly different form.
m
a0 m
p x     ak cosck x    bk sin d k x 
2 k 0
k 0
ck and d k real numbers
Below we show how (x-4)2 can be interpolated on the interval [2,6].
Interpolation on
2,6
with 20 data points
Interpolation on
2,6
with 40 data points
4
4
3
3
2
2
1
1
2
4
6
2
4
6
An interpolating function for a set of data will exactly match that set of data. We
can find and approximating function that will remain in an -Ban around the
function p(x) no matter how small of a number  we take. This function p(x) can be
found so that all of the numbers ak, bk, ck, dk, ek and fk are rational numbers:
m
a0 m
p x     ak cosck x  ek    bk sin d k x  f k 
2 k 0
k 0
An epsilon ban around the function
5
4
3
2
1
2
-1
4
6
In the construction of a universal function we will need to be able to find a
trigonometric polynomial with rational parameters that can behave like two
different functions on two different intervals. Below is an example of how we can
have a function that behaves like (x-4)2 on the interval [2,6] and the function
4+sin(2(x-16)) on the interval [12,20].
The Construction of a Universal Function
Seidel and Walsh (W. Seidel and J.L. Walsh, "On Approximation by Euclidean and
Non-Euclidean Translations of Analytic Functions", Bulletin of the American
Mathematical Society, Vol. 47, 1941, pp. 916-920) were the first to use a similar
method of construction using ordinary polynomials instead of trigonometric
polynomials.
The set of finite linear combinations of trigonometric functions with rational
parameters ak, bk, ck, dk, ek, fk of the form given below is countable.
m
a0 m
p x     ak cosck x  ek    bk sin d k x  f k 
2 k 0
k 0
This implies that this set of functions can be enumerated call them {pm(x)}.
pm x  p1 x, p2 x, p3 x,
Any rational translation of one of these functions is another function of this form.
p j x  r   pm x  for any rational number r
We define two sequences of closed bounded intervals Cn that are intervals centered
at powers of 4 and In intervals centered at the origin as given below.

Cn  x  4 n  2 n  4 n  2 n , 4 n  2 n




I n  x  4 n  2 n  1   4 n  2 n  1 ,4 n  2 n  1
The particular lengths of the intervals have been chosen so that the intervals
have the following properties.
1. The Cn are disjoint:
C j  Ck  
2. The In are nested:
I1  I 2  I 3  
3. In and Cn+1 are disjoint:
I n  Cn 1  
4. In contains C1, C2,…, Cn:
C j  In
C1
[ ]
0
4
…
C2
[
]
16
In
[
Cn
4n
for j  n
Cn+1
]]
[
4n+1
]
A sequence of trigonometric polynomials {m(x)} can be chosen from the set {pm(x)}
using a recursive definition. This can be done using the previous result.
1
Choose  1  x  so that : p1  x  4   1  x  
x  C1
2
1

for x  I1
  1 x    2 x   4
Choose  2 x  so that : 
 p x  4 2   x   1 for x  C
2
2
 2
4


In general if n-1(x) has been defined the function n(x) can be chosen as follows.
1

  n 1 x    n x   2 n
Choose  n x  so that : 
 p x  42   x   1
n
 n
2n


for x  I n 1
for x  Cn
For any x in the interval In the sequence {n(x)} will be a Cauchy Sequence.
 m k x    m x    m  k x    m  k 1 x    m  k 1 x    m k  2 x      m 1 x    m x 

1
2mk
1
 m 1
2

1
2 m  k 1

1
2 m1
This implies the sequence {n(x)} will converge on
the interval In. This means that the limit will exist
for all x in this interval. The intervals In can be as
large as you wish so for any x in (-,) We can
define the function U(x) as a limit of n(x).
U x   lim  n x 
n 
Because the sequence {n(x)} is Cauchy, the function U(x) will can be written as a
convergent telescopic series.
U x    n x    n1 x    n x    n 2 x    n1 x    n3 x    n 2 x   
Consider a point x in the set Cn. Look at how U(x) and pn(x-4n) will differ.




U x   pn x  4 n  pn x  4 n   n x    n 1 x    n x    n  2 x    n 1 x   
1
1
1



n
n 1
n2
2
2
2
1
 n 1
2

If we replace x by x+4n in the inequality
above we get the following relation for any
x in the closed bounded interval [-2n,2n].


1
U x  4  pn  x   n 1
2
n
If we begin with an arbitrary function f(x) on an interval [a,b] and a value for >0.
First find a a large enough n so that [a,b] is in [-2n,2n], then find a lager value for n
so that |f(x)-pn(x)|</2 and an even larger value for n so that the inequality above
is less than /2.




U x  4 n  f  x   U x  4 n  pn  x   pn  x   f  x  

2


2

Other Universal Functions
You can add or subtract certain types of function to a universal function and get
another universal function. For instance adding or subtracting one of the
combinations of finite trigonometric polynomials with rational parameters. If we start
with a Universal Function U(x) each of the following will also be universal.
U  x   3x 4  2 x 2  7
Add a polynomial to it.
U x  3 cos4 x  5 sin x
Add a trig functions to it.
3U 7 x     9e7 x
U x   4e x  9 x 7  sin x
Examples of other
Universal functions
Translations and dialations.
Combinations of them.
Once you have found one there seem to be an infinite number of possibilities. A
strange fact is that if you add two universal functions together you might not get a
universal function.
It turns out that this method can also be used to construct Universal Functions on
different domains (even sets in the complex plane) that will have a different operation
in which the function will be universal.
For the domain that is the real line with 0 deleted (i.e. (-,)U(0,)) a universal
function U(x) can be constructed so that a dilation or contraction of U(x)
approximates a function f(x).
U cx  f x
c0
For the domain that is the open interval |x|<1 (i.e. (-1,1)) a universal function U(x)
can be constructed so that a rational transformation of U(x) approximates a
function f(x).
 xc 
U
  f x 
 1  cx 
c 1
The Category of Universal Functions
By knowing one Universal Function it is easy to create an infinite number of other
Universal Functions a typical question mathematicians like to ask is:
How "common" are Universal Functions among continuous functions?
The word common to a mathematician needs to be more precise. It is too vague to be
able to get any type of results from.
One way to think of meaning of the word common would be in what mathematicians
call the measure of the functions. We could rephrase this question as:
If I picked a function at random what is the chance it is Universal?
Another way to think of the meaning of the word common would be in what
mathematicians call the topology of functions. This question can be rephrased as:
Can the complement of the set of Universal Functions be broken into a
countable union of sets of functions so that each set of functions is "closed"
and each set contains no "open" set of functions?
Once the concept of the meaning of and "open" and "closed" set of functions is
known, this is what topologists call a Residual Set. A set being residual means its
elements are "commonly" found.
The concept of a set of functions being "closed" is a complicated concept when you
are first introduce to it. If S is a set of continuous functions we say that S is closed if
we take a sequence of functions fn(x) in S that has the following property:
If lim max f n x   f x   0 for any closed bounded set K then f x  S
n xK
A set of functions is "open" if its complement is closed. This is called the topology of
almost uniform convergence. Using the trigonometric functions {pi(x)} we used in the
construction of U(x), define the following sets of functions indexed by three positive
integer parameters i, j and k.

1
S i, j , k    g  x  inf max g x  t   pi  x   k 
t   ,  x  j


It can be proven each S(i,j,k) is closed and contains no open subsets. We can also
show the following:
hx  hx  is not a universal
function    S i, j , k 
i , j , kN
This means that Universal Functions are common in the topological sense.