Function approximation: Fourier, Chebyshev, Lagrange Orthogonal functions Fourier

Function approximation: Fourier, Chebyshev, Lagrange Orthogonal functions Fourier

Function approximation: Fourier, Chebyshev, Lagrange Orthogonal functions Fourier Series Discrete Fourier Series Fourier Transform: properties Chebyshev polynomials Convolution DFT and FFT Scope: Understanding where the Fourier Transform comes from. Moving from the continuous to the discrete world. The concepts are the basis for pseudospectral methods and the spectral element approach. Orthogonal functions 1 Fourier Series: one way to derive them The Problem we are trying to approximate a function f(x) by another function g n(x) which consists of a sum over N orthogonal functions (x) weighted by some coefficients an. N f ( x) g N ( x) ai i ( x) i 0 Orthogonal functions 2 The Problem ... and we are looking for optimal functions in a least squares (l 2) sense ... b

2 f ( x) g N ( x) f ( x) g N ( x) dx 2 a 1/ 2 Min ! ... a good choice for the basis functions (x) are orthogonal functions. What are orthogonal functions? Two functions f and g are said to be orthogonal in the interval [a,b] if b f ( x) g ( x)dx 0 a How is this related to the more conceivable concept of orthogonal vectors? Let us look at the original definition of integrals: Orthogonal functions 3 Orthogonal Functions b N f i ( x) g i ( x)x a f ( x) g ( x)dx Nlim i 1 ... where x0=a and xN=b, and xi-xi-1=x ... If we interpret f(xi) and g(xi) as the ith components of an N component vector, then this sum corresponds directly to a scalar product of vectors.

The vanishing of the scalar product is the condition for orthogonality of vectors (or functions). fi Orthogonal functions gi f i g i f i g i 0 i 4 Periodic functions Let us assume we have a piecewise continuous function of the form f ( x 2 ) f ( x) 40 f ( x 2 ) f ( x) x 2 30 20 10 0 -15 -10 -5 0 5 10 15 20 ... we want to approximate this function with a linear combination of 2 periodic functions:

1, cos( x), sin( x ), cos( 2 x ), sin( 2 x),..., cos( nx ), sin( nx ) N 1 f ( x) g N ( x) a0 ak cos(kx) bk sin(kx) 2 k 1 Orthogonal functions 5 Orthogonality ... are these functions orthogonal ? j k 0 cos( jx ) cos( kx ) dx 2 j k 0 j k 0 0 j k , j , k 0 sin( jx ) sin( kx ) dx

j k 0 cos( jx ) sin(kx )dx 0 j 0, k 0 ... YES, and these relations are valid for any interval of length 2. Now we know that this is an orthogonal basis, but how can we obtain the coefficients for the basis functions? from minimising f(x)-g(x) Orthogonal functions 6 Fourier coefficients optimal functions g(x) are given if g n ( x) f ( x) 2 Min! or ak g n ( x) f ( x) 2

0 ... with the definition of g(x) we get ... g n ( x) f ( x) ak 2 2 2 N 1 a0 ak cos(kx) bk sin( kx) f ( x ) dx ak 2 k 1 leading to N 1 g N ( x) a0 ak cos(kx) bk sin(kx) 2 k 1 1 ak 1 bk Orthogonal functions with

f ( x) cos(kx) dx, k 0,1,..., N f ( x) sin( kx) dx, k 1,2,..., N 7 Fourier approximation of |x| ... Example ... f ( x) x , x leads to the Fourier Serie 1 4 cos( x ) cos(3 x ) cos(5 x ) g ( x) ... 2 12 32 52

.. and for n<4 g(x) looks like 4 3 2 1 0 -20 Orthogonal functions -15 -10 -5 0 5 10 15 20 8 Fourier approximation of x2 ... another Example ... f ( x) x 2 , 0 x 2 leads to the Fourier Serie N 4 2 4 4 g N ( x) 2 cos(kx) sin(kx) 3 k

k 1 k .. and for N<11, g(x) looks like 40 30 20 10 0 -10 -10 Orthogonal functions -5 0 5 10 15 9 Fourier - discrete functions ... what happens if we know our function f(x) only at the points 2 xi i N it turns out that in this particular case the coefficients are given by 2 ak N * 2 bk N *

N f (x j ) cos(kx j ), k 0,1,2,... j ) sin(kx j ), k 1,2,3,... j 1 N f (x j 1 .. the so-defined Fourier polynomial is the unique interpolating function to the function f(xj) with N=2m 1 * m 1 * 1 g ( x) a 0 a k cos(kx) b*k sin(kx) am* cos(kx) 2 2 k 1 * m Orthogonal functions 10 Fourier - collocation points ... with the important property that ...

g m* ( xi ) f ( xi ) ... in our previous examples ... 3.5 3 2.5 2 1.5 1 0.5 0 -10 -5 0 5 10 f(x)=|x| => f(x) - blue ; g(x) - red; xi - + Orthogonal functions 11 Fourier series - convergence f(x)=x2 => f(x) - blue ; g(x) - red; xi - + Orthogonal functions 12 Fourier series - convergence f(x)=x2 => f(x) - blue ; g(x) - red; xi - + Orthogonal functions 13 Gibbs phenomenon f(x)=x2 => f(x) - blue ; g(x) - red; xi - + N = 16 N = 64

N = 32 6 6 6 4 4 4 2 2 2 0 0 0 -2 -2 -2 -4 -4 -4 -6 0 0.5

1 N = 128 1.5 -6 0 6 6 4 4 2 2 0 0 -2 -2 -4 -4 -6 0 0.5 Orthogonal functions 1 1.5

-6 0.5 1 N = 256 1.5 -6 0 0.5 1 1.5 The overshoot for equispaced Fourier interpolations is 14% of the step height. 0 0.5 1 1.5 14 Chebyshev polynomials We have seen that Fourier series are excellent for interpolating (and differentiating) periodic functions defined on a regularly spaced grid. In many circumstances physical phenomena which are not periodic (in space) and occur in a limited area. This quest leads to the use of Chebyshev polynomials. We depart by observing that cos(n) can be expressed by a polynomial in cos(): cos( 2 ) 2 cos 2 1 cos(3 ) 4 cos 3 3 cos cos( 4 ) 8 cos 4 8 cos 2 1

... which leads us to the definition: Orthogonal functions 15 Chebyshev polynomials - definition cos(n ) Tn (cos( )) Tn ( x), x cos( ), x [ 1,1], n N ... for the Chebyshev polynomials Tn(x). Note that because of x=cos() they are defined in the interval [-1,1] (which - however can be extended to ). The first polynomials are T0 ( x) 1 T1 ( x) x T2 ( x) 2 x 2 1 T3 ( x) 4 x 3 3 x T4 ( x) 8 x 4 8 x 2 1 Tn ( x) 1 Orthogonal functions for where x [ 1,1] and n N 0 16 Chebyshev polynomials - Graphical The first ten polynomials look like [0, -1] 1 T_n(x) 0.5 0

-0.5 -1 0 0.2 0.4 0.6 0.8 1 x The n-th polynomial has extrema with values 1 or -1 at x Orthogonal functions ( ext ) k k cos( ), n k 0,1,2,3,..., n 17 Chebyshev collocation points These extrema are not equidistant (like the Fourier extrema) k x(k) x Orthogonal functions

( ext ) k k cos( ), n k 0,1,2,3,..., n 18 Chebyshev polynomials - orthogonality ... are the Chebyshev polynomials orthogonal? Chebyshev polynomials are an orthogonal set of functions in the interval [-1,1] with respect to the weight function 1 / 1 x 2 such that 0 dx T ( x ) T ( x ) / 2 k j 2 1 x 1 1 for

k j for k j 0, for k j 0 k, j N0 ... this can be easily verified noting that x cos , dx sin d Tk ( x) cos(k ), T j ( x) cos( j ) Orthogonal functions 19 Chebyshev polynomials - interpolation ... we are now faced with the same problem as with the Fourier series. We want to approximate a function f(x), this time not a periodical function but a function which is defined between [-1,1]. We are looking for gn(x) n 1 f ( x ) g n ( x) c0T0 ( x) ck Tk ( x ) 2 k 1 ... and we are faced with the problem, how we can determine the coefficients ck. Again we obtain this by finding the extremum (minimum) 1 dx 2 g n ( x) f ( x) 0 2 ck 1 1 x Orthogonal functions

20 Chebyshev polynomials - interpolation ... to obtain ... 2 ck 1 f ( x)Tk ( x) 1 dx 1 x 2 , k 0,1,2,..., n ... surprisingly these coefficients can be calculated with FFT techniques, noting that 2 ck f (cos ) cos kd , 0 k 0,1,2,..., n ... and the fact that f(cos) is a 2-periodic function ... 1 ck f (cos ) cos kd , k 0,1,2,..., n

... which means that the coefficients ck are the Fourier coefficients ak of the periodic function F()=f(cos )! Orthogonal functions 21 Chebyshev - discrete functions ... what happens if we know our function f(x) only at the points xi cos i N in this particular case the coefficients are given by 2 ck N * N f (cos j ) cos(k j ), k 0,1,2,... N / 2 j 1 ... leading to the polynomial ... m 1 * g ( x ) c0T 0 ck*Tk ( x ) 2 k 1 * m ... with the property g m* ( x) f ( x) Orthogonal functions

at x j cos(j/N) j 0,1,2,..., N 22 Chebyshev - collocation points - |x| f(x)=|x| => f(x) - blue ; gn(x) - red; xi - + N=8 1 0.8 8 points 0.6 0.4 0.2 0 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 N = 16

1 0.8 0.6 16 points 0.4 0.2 0 -1 Orthogonal functions -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 23 Chebyshev - collocation points - |x| f(x)=|x| => f(x) - blue ; gn(x) - red; xi - + N = 32 1 0.8 32 points

0.6 0.4 0.2 0 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.2 0.4 0.6 0.8 1 N = 128 1 0.8 128 points 0.6 0.4 0.2

0 -1 Orthogonal functions -0.8 -0.6 -0.4 -0.2 0 0.6 0.8 1 24 Chebyshev - collocation points - x2 f(x)=x2 => f(x) - blue ; gn(x) - red; xi - + N=8 1.2 1 0.8 8 points 0.6 0.4 0.2 0 -1 -0.8 -0.6 -0.4

-0.2 0 N = 64 0.2 0.4 0.6 0.8 1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 1 The interpolating function gn(x) was shifted by a small amount to be visible at all!

0.8 0.6 64 points 0.4 0.2 0 -1 Orthogonal functions 25 Chebyshev vs. Fourier - numerical Chebyshev Fourier N = 16 N = 16 1 35 0.8 30 25 0.6 20 15 0.4 10 5 0.2 0 0

0 0.2 0.4 0.6 0.8 1 -5 0 2 4 6 f(x)=x2 => f(x) - blue ; gN(x) - red; xi - + This graph speaks for itself ! Gibbs phenomenon with Chebyshev? Orthogonal functions 26 Chebyshev vs. Fourier - Gibbs Chebyshev Fourier N = 16 N = 16 1.5 1.5 1

1 0.5 0.5 0 0 -0.5 -0.5 -1 -1 -1.5 -1 -0.5 0 0.5 1 -1.5 0 2 4 6 f(x)=sign(x-) => f(x) - blue ; gN(x) - red; xi - + Gibbs phenomenon with Chebyshev? YES! Orthogonal functions 27

Chebyshev vs. Fourier - Gibbs Chebyshev Fourier N = 64 N = 64 1.5 1.5 1 1 0.5 0.5 0 0 -0.5 -0.5 -1 -1 -1.5 -1 -0.5 0 0.5 1

-1.5 0 2 4 6 8 f(x)=sign(x-) => f(x) - blue ; gN(x) - red; xi - + Orthogonal functions 28 Fourier vs. Chebyshev Chebyshev Fourier 2 xi i N collocation points periodic functions domain cos(nx ), sin( nx ) basis functions 1 g m* ( x) a *0 2 m 1

xi cos a *k cos(kx) b*k sin( kx) interpolating function i N limited area [-1,1] Tn ( x ) cos(n ), x cos m 1 * g ( x ) c0T 0 ck*Tk ( x ) 2 k 1 * m k 1 1 * am cos(kx) 2 Orthogonal functions 29 Fourier vs. Chebyshev (contd) Chebyshev Fourier 2 ak

N * 2 bk N * N f (x j ) cos(kx j ) j 1 coefficients N f (x j 2 ck N * N f (cos j ) cos(k j ) j 1 ) sin(kx j ) j 1

Gibbs phenomenon for discontinuous functions Efficient calculation via FFT infinite domain through periodicity limited area calculations some properties grid densification at boundaries coefficients via FFT excellent convergence at boundaries Gibbs phenomenon Orthogonal functions 30 The Fourier Transform Pair 1 F ( ) 2 f (t )e i t dt Forward transform f (t ) F ( )e it d Inverse transform

Note the conventions concerning the sign of the exponents and the factor. Orthogonal functions 31 Some properties of the Fourier Transform Defining as the FT: Linearity Symmetry Time shifting Time differentiation Orthogonal functions f (t ) F ( ) af1 (t ) bf 2 (t ) aF1 ( ) bF2 ( ) f ( t ) 2F ( ) f (t t ) eit F ( ) n f (t ) n ( i ) F ( ) n t 32 Differentiation theorem Time differentiation Orthogonal functions n f (t )

n ( i ) F ( ) n t 33 Convolution The convolution operation is at the heart of linear systems. Definition: f (t ) g (t ) f (t ' ) g (t t ' )dt ' f (t t ' ) g (t ' )dt ' Properties: f (t ) g (t ) g (t ) f (t ) f (t ) (t ) f (t ) f (t ) H (t ) f (t )dt H(t) is the Heaviside function: Orthogonal functions 34 The convolution theorem A convolution in the time domain corresponds to a multiplication in the frequency domain. and vice versa a convolution in the frequency domain corresponds to a multiplication in the time domain f (t ) g (t ) F ( )G ( )

f (t ) g (t ) F ( ) G ( ) The first relation is of tremendous practical implication! Orthogonal functions 35 Summary The Fourier Transform can be derived from the problem of approximating an arbitrary function. A regular set of points allows exact interpolation (or derivation) of arbitrary functions There are other basis functions (e.g., Chebyshev polynomials, Legendre polynomials) with similar properties These properties are the basis for the success of the spectral element method Orthogonal functions 36

Recently Viewed Presentations

  • Creating an evidence-based framework to support biodiversity ...

    Creating an evidence-based framework to support biodiversity ...

    Unique feature is that it incorporates resampling statistics (percentile bootstrap confidence limits and bias-corrected bootstrap confidence limits), and you can test for differences among classes of studies using a randomization test to evaluate between-group homogeneity. Eddy, D.M. & Hasselblad, V....
  • The Life Cycle of Stars

    The Life Cycle of Stars

    The Life Cycle of Stars * * Cycle for all stars Stage One- Born in vast, dense clouds of gas, mostly hydrogen along with small amounts of helium, and dust called Nebulae. Stage Two - As a nebula collapses, gravity...
  • Jodie Misiak Federation Square March 7, 2003 Project

    Jodie Misiak Federation Square March 7, 2003 Project

    Federation Square Overview Federation Square Overview Jodie Misiak March 7, 2003 Project Evaluation (1.011) 1997 International Design Competition for redevelopment of Melbourne Waterfront London-based Lab architecture studio Melbourne-based Bates Smart Finance for project from State of Victoria ...
  • circabc.europa.eu

    circabc.europa.eu

    Expert Group on Reporting (Brussels, 17 October 2017)Update on the development of Emerald Network &Resolution No. 8(2012) ReportingMarc Roekaerts, Expert to the Bern ConventionOtars Opermanis, Expert to the Bern Convention A fewwords on the Council of Europe and why the...
  • Eft Základní Manuál

    Eft Základní Manuál

    Bod na temeni hlavy 2. vnitřní strana obočí 3. vedle oka na spánku 4. pod středem oka 5. pod nosem 6. brada - důlek mezi dolním rtem a bradou 7. pod vnitřním okrajem klíční kosti 8. pod paží Body na...
  • 1. Introduction - USTC

    1. Introduction - USTC

    In this data set, each movie has >=1 genres, thus the prediction of genres is a multi-label classification, and the calculation of average precision and recall and F1-value is as follows. For example, if there are 2 test samples, and...
  • Multiply Binomials with Patterns

    Multiply Binomials with Patterns

    use patterns to multiply special binomials. SOL: A.2b Designed by Skip Tyler, Varina High School There are formulas (shortcuts) that work for certain polynomial multiplication problems. (a + b)2 = a2 + 2ab + b2 (a - b)2 = a2...
  • Cryptography (the art of scrambling) ECMM 6000, Fall

    Cryptography (the art of scrambling) ECMM 6000, Fall

    Cryptography (the art of scrambling) Beside programming e-commerce applications, what other cs issues are there? Application (web) design: HCI Data mining Server and client security (how can we protect our systems and data hackers malicious code denial-of-service (DOS) attacks privacy...