The second-order pseudo-spectral derivative can be computed as the

product of the matrix D and the vector f , that is, f = Df , or by di-

rectly applying matrix D2 to the vector f .

450 10. Orthogonal Polynomials in Approximation Theory

10.11 Transforms and Their Applications

In this section we provide a short introduction to the most relevant integral

transforms and discuss their basic analytical and numerical properties.

10.11.1 The Fourier Transform

De¬nition 10.1 Let L1 (R) denote the space of real or complex functions

de¬ned on the real line such that

∞

|f (t)| dt < +∞.

’∞

For any f ∈ L1 (R) its Fourier transform is a complex-valued function

F = F[f ] de¬ned as

∞

f (t)e’i2πνt dt.

F (ν) =

’∞

Should the independent variable t denote time, then ν would have the

meaning of frequency. Thus, the Fourier transform is a mapping that to a

function of time (typically, real-valued) associates a complex-valued func-

tion of frequency.

The following result provides the conditions under which an inversion for-

mula exists that allows us to recover the function f from its Fourier trans-

form F (for the proof see [Rud83], p. 199).

Property 10.3 (inversion theorem) Let f be a given function in L1 (R),

F ∈ L1 (R) be its Fourier transform and g be the function de¬ned by

∞

t ∈ R.

F (ν)ei2πνt dν,

g(t) = (10.74)

’∞

Then g ∈ C 0 (R), with lim|x|’∞ g(x) = 0, and f (t) = g(t) almost every-

where in R (i.e., for any t unless possibly a set of zero measure).

The integral at right hand side of (10.74) is to be meant in the Cauchy

principal value sense, i.e., we let

∞ a

i2πνt

F (ν)ei2πνt dν

F (ν)e dν = lim

a’∞

’∞ ’a

10.11 Transforms and Their Applications 451

and we call it the inverse Fourier transform or inversion formula of the

Fourier transform. This mapping that associates to the complex function

F the generating function f will be denoted by F ’1 [F ], i.e., F = F[f ] i¬

f = F ’1 [F ].

Let us brie¬‚y summarize the main properties of the Fourier transform and

its inverse.

1. F and F ’1 are linear operators, i.e.

F[±f + βg] = ±F[f ] + βF[g], ∀±, β ∈ C,

(10.75)

F ’1 [±F + βG] = ±F ’1 [F ] + βF ’1 [G], ∀±, β ∈ C;

2. scaling: if ± is any nonzero real number and f± is the function f± (t) =

f (±t), then

1

F[f± ] = F1

|±| ±

where F ± (ν) = F (ν/±);

1

3. duality: let f (t) be a given function and F (ν) be its Fourier trans-

form. Then the function g(t) = F (’t) has a Fourier transform given

by f (ν). Thus, once an associated function-transform pair is found,

another dual pair is automatically generated. An application of this

property is provided by the pair r(t)-F[r] in Example 10.5;

4. parity: if f (t) is a real even function then F (ν) is real and even, while

if f (t) is a real and odd function then F (ν) is imaginary and odd.

This property allows one to work only with nonnegative frequencies;

5. convolution and product: for any given functions f, g ∈ L1 (R), we

have

F[f — g] = F[f ]F[g], F[f g] = F — G, (10.76)

where the convolution integral of two functions φ and ψ is given by

∞

(φ — ψ)(t) = φ(„ )ψ(t ’ „ ) d„. (10.77)

’∞

Example 10.5 We provide two examples of the computation of the Fourier

transforms of functions that are typically encountered in signal processing.

Let us ¬rst consider the square wave (or rectangular) function r(t) de¬ned as

if ’ ¤t¤

T T

A ,

2 2

r(t) =

0 otherwise,

452 10. Orthogonal Polynomials in Approximation Theory

where T and A are two given positive numbers. Its Fourier transform F[r] is the

function

T /2

sin(πνT )

Ae’i2πνt dt = AT ν∈R

F (ν) = ,

πνT

’T /2

where AT is the area of the rectangular function.

Let us consider the sawtooth function

±

2At if ’ T ¤ t ¤ T

,

2 2

T

s(t) =

0 otherwise,

whose DFT is shown in Figure 10.3 and whose Fourier transform F[s] is the

function

AT sin(πνT )

cos(πνT ) ’ ν∈R

F (ν) = i ,

πνT πνT

and is purely imaginary since s is an odd real function. Notice also that the

functions r and s have a ¬nite support whereas their transforms have an in¬nite

support (see Figure 10.7). In signal theory this corresponds to saying that the

•

transform has an in¬nite bandwidth.

1 0.5

0.4

0.8

0.3

0.6 0.2

0.1

0.4

0

0.2

’0.1

’0.2

0

’0.3

’0.2

’0.4

’0.4 ’0.5

,

’10 ’8 ’6 ’4 ’2 0 2 4 6 8 10 ’10 ’8 ’6 ’4 ’2 0 2 4 6 8 10

FIGURE 10.7. Fourier transforms of the rectangular (left) and the sawtooth

(right) functions

Example 10.6 The Fourier transform of a sinusoidal function is of paramount

interest in signal and communication systems. To start with, consider the constant

function f (t) = A for a given A ∈ R. Since it has an in¬nite time duration its

Fourier transform F[A] is the function

a

sin(2πνa)

Ae’i2πνt dt = A lim

F (ν) = lim ,

πν

a’∞ a’∞

’a

where the integral above is again the Cauchy principal value of the corresponding

integral over (’∞, ∞). It can be proved that the limit exists and is unique in the

sense of distributions (see Section 12.4) yielding

F (ν) = Aδ(ν), (10.78)

10.11 Transforms and Their Applications 453

where δ is the so-called Dirac mass, i.e., a distribution that satis¬es

∞

δ(ξ)φ(ξ) dξ = φ(0) (10.79)

’∞

for any function φ continuous at the origin. From (10.78) we see that the trans-

form of a function with in¬nite time duration has a ¬nite bandwidth.

Let us now consider the computation of the Fourier transform of the function

f (t) = A cos(2πν0 t) where ν0 is a ¬xed frequency. Recalling Euler™s formula

eiθ + e’iθ

θ ∈ R,

cos(θ) = ,

2

and applying (10.78) twice we get

A A

F[A cos(2πν0 t)] = δ(ν ’ ν0 ) + δ(ν + ν0 ),

2 2

which shows that the spectrum of a sinusoidal function with frequency ν0 is

centred around ±ν0 (notice that the transform is even and real since the same

•

holds for the function f (t)).

It is worth noting that in real-life there do not exist functions (i.e. signals)

with in¬nite duration or bandwidth. Actually, if f (t) is a function whose

value may be considered as “negligible” outside of some interval (ta , tb ),

then we can assume that the e¬ective duration of f is the length ∆t =

tb ’ ta . In a similar manner, if F (ν) is the Fourier transform of f and

it happens that F (ν) may be considered as “negligible” outside of some

interval (νa , νb ), then the e¬ective bandwidth of f is ∆ν = νb ’νa . Referring

to Figure 10.7, we clearly see that the e¬ective bandwidth of the rectangular

function can be taken as (’10, 10).

10.11.2 (Physical) Linear Systems and Fourier Transform

Mathematically speaking, a physical linear system (LS) can be regarded

as a linear operator S that enjoys the linearity property (10.75). Denoting

by i(t) and u(t) an admissible input function for S and its corresponding

output function respectively, the LS can be represented as u(t) = S(i(t))

or S : i ’ u. A special category of LS are the so-called shift invariant (or

time-invariant) linear systems (ILS) which satisfy the property

S(i(t ’ t0 )) = u(t ’ t0 ), ∀t0 ∈ R

and for any admissible input function i.

Let S be an ILS system and let f and g be two admissible input functions

for S with w = S(g). An immediate consequence of the linearity and shift-

invariance is that

S((f — g)(t)) = (f — S(g))(t) = (f — w)(t) (10.80)

454 10. Orthogonal Polynomials in Approximation Theory

where — is the convolution operator de¬ned in (10.77).

Assume we take as input function the impulse function δ(t) introduced in

the previous section and denote by h(t) = S(δ(t)) the corresponding output

through S (usually referred to as the system impulse response function).

Property (10.79) implies that for any function φ, (φ — δ)(t) = φ(t), so that,

recalling (10.80) and taking φ(t) = i(t) we have

u(t) = S(i(t)) = S(i — δ)(t) = (i — S(δ))(t) = (i — h)(t).

Thus, S can be completely described through its impulse response function.

Equivalently, we can pass to the frequency domain by means of the ¬rst

relation in (10.76) obtaining

U (ν) = I(ν)H(ν), (10.81)

where I, U and H are the Fourier transforms of i(t), u(t) and h(t), respec-

tively; H is the so-called system transfer function.

Relation (10.81) plays a central role in the analysis of linear time-invariant

systems as it is simpler to deal with the system transfer function than with

the corresponding impulse response function, as demonstrated in the fol-

lowing example.

Example 10.7 (ideal low-pass ¬lter) An ideal low-pass ¬lter is an ILS char-

acterized by the transfer function

if |ν| ¤ ν0 /2,

1,

H(ν) =

0, otherwise.

Using the duality property, the impulse response function F ’1 [H] is

sin(πν0 t)

h(t) = ν0 .

πν0 t

Given an input signal i(t) with Fourier transform I(ν), the corresponding output

u(t) has a spectrum given by (10.81)

if |ν| ¤ ν0 /2,

I(ν),

I(ν)H(ν) =

0 otherwise.

The e¬ect of the ¬lter is to cut o¬ the input frequencies that lie outside the

window |ν| ¤ ν0 /2. •

The input/output functions i(t) and u(t) usually denote signals and

the linear system described by H(ν) is typically a communication system.

Therefore, as pointed out at the end of Section 10.11.1, we are legitimated

in assuming that both i(t) and u(t) have a ¬nite e¬ective duration. In

10.11 Transforms and Their Applications 455

particular, referring to i(t) we suppose i(t) = 0 if t ∈ [0, T0 ). Then, the

computation of the Fourier transform of i(t) yields

T0

i(t)e’i2πνt dt.

I(ν) =

0

Letting ∆t = T0 /n for n ≥ 1 and approximating the integral above by the

composite trapezoidal formula (9.14), we get

n’1

i(k∆t)e’i2πνk∆t .

˜

I(ν) = ∆t

k=0

˜

It can be proved (see, e.g., [Pap62]) that I(ν)/∆t is the Fourier transform

of the so-called sampled signal

∞

i(k∆t)δ(t ’ k∆t),

is (t) =

k=’∞

where δ(t ’ k∆t) is the Dirac mass at k∆t. Then, using the convolution

and the duality properties of the Fourier transform, we get

∞

j

˜ I ν’

I(ν) = , (10.82)

∆t

j=’∞

which amounts to replacing I(ν) by its periodic repetition with period

1/∆t. Let J∆t = [’ 2∆t , 2∆t ]; then, it su¬ces to compute (10.82) for ν ∈

1 1

J∆t . This can be done numerically by introducing a uniform discretization

of J∆t with frequency step ν0 = 1/(m∆t) for m ≥ 1. By doing so, the

˜

computation of I(ν) requires evaluating the following m+1 discrete Fourier

transforms (DFT)

n’1

i(k∆t)e’i2πjν0 k∆t , j = ’ m , . . . , m .

˜

I(jν0 ) = ∆t 2 2

k=0

For an e¬cient computation of each DFT in the formula above it is crucial

to use the FFT algorithm described in Section 10.9.2.

10.11.3 The Laplace Transform

The Laplace transform can be employed to solve ordinary di¬erential equa-

tions with constant coe¬cients as well as partial di¬erential equations.

De¬nition 10.2 Let f ∈ L1 ([0, ∞)) i.e., f ∈ L1 ([0, T ]) for any T > 0.

loc

Let s = σ + iω be a complex variable. The Laplace integral of f is de¬ned

456 10. Orthogonal Polynomials in Approximation Theory

as

∞ T

f (t)e’st dt = lim f (t)e’st dt.

T ’∞

0 0

If this integral exists for some s, it turns out to be a function of s; then,

the Laplace transform L[f ] of f is the function

∞

f (t)e’st dt.

L(s) =

0

The following relation between Laplace and Fourier transforms holds

L(s) = F (e’σt f (t)),

˜

˜ ˜

where f (t) = f (t) if t ≥ 0 while f (t) = 0 if t < 0.

Example 10.8 The Laplace transform of the unit step function f (t) = 1 if t > 0,

f (t) = 0 otherwise, is given by

∞

1

e’st dt =

L(s) = .

s

0

•

We notice that the Laplace integral exists if σ > 0.

In Example 10.8 the convergence region of the Laplace integral is the half-

plane {Re(s) > 0} of the complex ¬eld. This property is quite general, as

stated by the following result.

Property 10.4 If the Laplace transform exists for s = s then it exists