**UFRJ**

# A First Course in Fourier Analysis - David W. Kammler (Cambridge University Press,...

(Parte **1** de 4)

This page intentionally left blank This page intentionally left blank

A First Course in Fourier Analysis

This unique book provides a meaningful resource for applied mathematics through Fourier analysis. It develops a uniﬁed theory of discrete and continuous (univariate) Fourier analysis, the fast Fourier transform, and a powerful elementary theory of generalized functions, including the use of weak limits. It then shows how these mathematical ideas can be used to expedite the study of sampling theory, PDEs, wavelets, probability, diffraction, etc. Unique features include a uniﬁed development of Fourier synthesis/analysis for functions on R, Tp, Z, and PN; an unusually complete development of the Fourier transform calculus (for ﬁnding Fourier transforms, Fourier series, and DFTs); memorable derivations of the FFT; a balanced treatment of generalized functions that fosters mathematical understanding as well as practical working skills; a careful introduction to Shannon’s sampling theorem and modern variations; a study of the wave equation, diffusion equation, and diffraction equation by using the Fourier transform calculus, generalized functions, and weak limits; an exceptionally efﬁcient development of Daubechies’ compactly supported orthogonalwavelets; generalizedprobabilitydensityfunctionswithcorrespondingversions of Bochner’s theorem and the central limit theorem; and a real-world application of Fourier analysis to the study of musical tones. A valuable reference on Fourier analysis for a variety of scientiﬁc professionals, including Mathematicians, Physicists, Chemists, Geologists, Electrical Engineers, Mechanical Engineers, and others.

David Kammler is a Professor and Distinguished Teacher in the Mathematics Department at Southern Illinois University.

A First Course in Fourier Analysis

DavidW. Kammler

Department of Mathematics Southern Illinois University at Carbondale

CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo

Cambridge University Press The Edinburgh Building, Cambridge CB28RU, UK

ISBN-13 | 978-0-521-88340-5 |

ISBN-13 | 978-0-521-70979-8 |

First published in print format ISBN-13 978-0-511-37689-4

© D. W. Kammler 2007 2008

Information on this title: w.cambridge.org/9780521883405

This publication is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

Published in the United States of America by Cambridge University Press, New York w.cambridge.org paperback eBook (EBL) hardback

Mathematics: Source and Substance

Profound study of nature is the most fertile source of mathematical discoveries.

Joseph Fourier, The Analytical Study of Heat,p .7

Mathematics is the science of patterns. The mathematician seeks patterns in number, in space, in science, in computers, and in imagination. Mathematical theories explain the relations among patterns; functions and maps, operators and morphisms bind one type of pattern to another to yield lasting mathematical structures. Applications of mathematics use these patterns to explain and predict natural phenomena that ﬁt the patterns. Patterns suggest other patterns, often yielding patterns of patterns. In this way mathematics follows its own logic, beginning with patterns from science and completing the portrait by adding all patterns that derive from initial ones.

Lynn A. Steen, The science of patterns, Science 240(1988), 616.

Contents

Preface xi The Mathematical Core

Chapter 1 Fourier’s representation for functions on R, Tp, Z, and PN 1

1.1 Synthesis and analysis equations 1 1.2 Examples of Fourier’s representation 12 1.3 The Parseval identities and related results 23 1.4 The Fourier–Poisson cube 31 1.5 The validity of Fourier’s representation 37

Further reading 59 Exercises 61

Chapter 2 Convolution of functions on R, Tp, Z, and PN 89

2.1 Formal deﬁnitions of f ∗ g, f g 89 2.2 Computation of f ∗ g 91 2.3 Mathematical properties of the convolution product 102 2.4 Examples of convolution and correlation 107

Further reading 115 Exercises 116

Chapter 3 The calculus for ﬁnding Fourier transforms of functions on R 129

3.1 Using the deﬁnition to ﬁnd Fourier transforms 129 3.2 Rules for ﬁnding Fourier transforms 134 3.3 Selected applications of the Fourier transform calculus 147

Further reading 155 Exercises 156 vii viii Contents

Chapter 4 The calculus for ﬁnding Fourier transforms of functions on Tp, Z, and PN 173

4.1 Fourier series 173 4.2 Selected applications of Fourier series 190 4.3 Discrete Fourier transforms 196 4.4 Selected applications of the DFT calculus 212

Further reading 216 Exercises 217

Chapter 5 Operator identities associated with Fourier analysis 239

5.1 The concept of an operator identity 239 5.2 Operators generated by powers of F 243 5.3 Operators related to complex conjugation 251 5.4 Fourier transforms of operators 255 5.5 Rules for Hartley transforms 263 5.6 Hilbert transforms 266

Further reading 271 Exercises 272

Chapter 6 The fast Fourier transform 291

6.1 Pre-FFT computation of the DFT 291 6.2 Derivation of the FFT via DFT rules 296 6.3 The bit reversal permutation 303 6.4 Sparse matrix factorization of F when N =2 m 310 6.5 Sparse matrix factorization of H when N =2 m 323

6.6 Sparse matrix factorization of F when N = P1P2 · Pm 327 6.7 Kronecker product factorization of F 338

Further reading 345 Exercises 345

Chapter 7 Generalized functions on R 367

7.1 The concept of a generalized function 367 7.2 Common generalized functions 379 7.3 Manipulation of generalized functions 389 7.4 Derivatives and simple diﬀerential equations 405 7.5 The Fourier transform calculus for generalized functions 413 7.6 Limits of generalized functions 427 7.7 Periodic generalized functions 440 7.8 Alternative deﬁnitions for generalized functions 450

Further reading 452 Exercises 453

Contents ix

Selected Applications

Chapter 8 Sampling 483

8.1 Sampling and interpolation 483 8.2 Reconstruction of f from its samples 487

8.3 Reconstruction of f from samples of a1 ∗ f, a2 ∗ f, | 497 |

8.4 Approximation of almost bandlimited functions 505

Further reading 508 Exercises 509

Chapter 9 Partial diﬀerential equations 523

9.1 Introduction 523 9.2 The wave equation 526 9.3 The diﬀusion equation 540 9.4 The diﬀraction equation 553 9.5 Fast computation of frames for movies 571

Further reading 573 Exercises 574

Chapter 10 Wavelets 593

10.1 The Haar wavelets 593 10.2 Support-limited wavelets 609 10.3 Analysis and synthesis with Daubechies wavelets 640 10.4 Filter banks 655

Further reading 673 Exercises 674

Chapter 1 Musical tones 693

1.1 Basic concepts 693 1.2 Spectrograms 702 1.3 Additive synthesis of tones 707 1.4 FM synthesis of tones 71 1.5 Synthesis of tones from noise 718 1.6 Music with mathematical structure 723

Further reading 727 Exercises 728 x Contents

12.1 Probability density functions on R 737 12.2 Some mathematical tools 741 12.3 The characteristic function 746 12.4 Random variables 753 12.5 The central limit theorem 764

Further reading 780 Exercises 780

Appendices A-1

Appendix 1 The impact of Fourier analysis A-1 Appendix 2 Functions and their Fourier transforms A-4 Appendix 3 The Fourier transform calculus A-14 Appendix 4 Operators and their Fourier transforms A-19 Appendix 5 The Whittaker–Robinson ﬂow chart for harmonic analysis A-23

Appendix 6 FORTRAN code for a radix 2 FFT A-27 Appendix 7 The standard normal probability distribution A-3 Appendix 8 Frequencies of the piano keyboard A-37

Index I-1

Preface

To the Student

This book is about one big idea: You can synthesize a variety of complicated functions from pure sinusoids in much the same way that you produce a major chord by striking nearby C, E, G keys on a piano. A geometric version of this idea forms the basis for the ancient Hipparchus-Ptolemy model of planetary motion (Almagest, 2nd century see Fig. 1.2). It was Joseph Fourier (Analytical Theory of Heat, 1815), however, who developed modern methods for using trigonometric series and integrals as he studied the ﬂow of heat in solids. Today, Fourier analysis is a highly evolved branch of mathematics with an incomparable range of applications and with an impact that is second to none (see Appendix 1). If you are a student in one of the mathematical, physical, or engineering sciences, you will almost certainly ﬁnd it necessary to learn the elements of this subject. My goal in writing this book is to help you acquire a working knowledge of Fourier analysis early in your career.

convergence, | ) from an analysis or advanced calculus course. You may choose to |

[solve y′(x)+ αy(x)=0 , y′(x)= xy(x), y′′(x)+ α2y(x)=0 , | ], complex analysis |

(Euler’s formula: eiθ = cosθ+isinθ, arithmetic for complex numbers, | ), number |

theory (integer addition and multiplication modulo N, Euclid’s gcd algorithm, | ), |

probability (random variable, mean, variance, | ), physics (F = ma, conservation |

of energy, Huygens’ principle, | ), signals and systems (LTI systems, low-pass |

ﬁlters, the Nyquist rate, | ), etc. You will have no trouble picking up these concepts |

If you have mastered the usual core courses in calculus and linear algebra, you have the maturity to follow the presentation without undue diﬃculty. A few of the proofs and more theoretical exercises require concepts (uniform continuity, uniform skip over the diﬃcult steps in such arguments and simply accept the stated results. The text has been designed so that you can do this without severely impacting your ability to learn the important ideas in the subsequent chapters. In addition, I will use a potpourri of notions from undergraduate courses in diﬀerential equations as they are introduced in the text and exercises.

If you wish, you can ﬁnd additional information about almost any topic in this book by consulting the annotated references at the end of the corresponding chapter. You will often discover that I have abandoned a traditional presentation xii Preface

X, | in Chapter 7 uses only notions from elementary calculus. Once you master |

probability, diﬀraction, |

in favor of one that is in keeping with my goal of making these ideas accessible to undergraduates. For example, the usual presentation of the Schwartz theory of distributions assumes some familiarity with the Lebesgue integral and with a graduate-level functional analysis course. In contrast, my development of δ, this theory, you can use generalized functions to study sampling, PDEs, wavelets,

mathematical details: Give a suﬃcient condition for | , given an example of ... , |

show that, | Some involve your personal harmonic analyzers: Experimentally |

The exercises (541 of them) are my greatest gift to you! Read each chapter carefully to acquire the basic concepts, and then solve as many problems as you can. You may ﬁnd it beneﬁcial to organize an interdisciplinary study group, e.g., mathematician + physicist + electrical engineer. Some of the exercises provide routine drill: You must learn to ﬁnd convolution products, to use the FT calculus, to do routine computations with generalized functions, etc. Some supply historical perspective: You can play Gauss and discover the FFT, analyze Michelson and Stratton’s analog supercomputer for summing Fourier series, etc. Some ask for determine the bandwidth of your eye, describe what would you hear if you replace

notes with frequencies f1,f2, | by notes with frequencies C/f1, C/f2, ... . Some |

prepare you for computer projects: Compute π to 1000 digits, prepare a movie for

broken into simple steps so you can do (a), then (b), then (c), | until you reach |

a vibrating string, generate the sound ﬁle for Risset’s endless glissando, etc. Some will set you up to discover a pattern, formulate a conjecture, and prove a theorem. (It’s quite a thrill when you get the hang of it!) I expect you to spend a lot of time working exercises, but I want to help you work eﬃciently. Complicated results are the goal. I frequently supply hints that will lead you to a productive line of inquiry. You will sharpen your problem-solving skills as you take this course.

Synopsis xiii

Synopsis The chapters of the book are arranged as follows:

Fourier’s Representation

2 Convolution

FT Calculus R

FT Calculus Tp,Z,PN

Generalized Functions

FT Operators6 The FFT

8Sampling10 Wavelets

Musical Tones

9 PDEs

The mathematical core is given in Chapters 1–7 and selected applications are developed in Chapters 8–12.

We present the basic themes of Fourier analysis in the ﬁrst two chapters. Chapter 1 opens with Fourier’s synthesis and analysis equations for functions on the real line R, on the circle Tp, on the integers Z, and on the polygon PN. We discretize xiv Preface by sampling (obtaining functions on Z,PN from functions on R,Tp), we periodize by summing translates (obtaining functions on Tp,PN from functions on R,Z), and we informally derive the corresponding Poisson identities. We combine these mappings to form the Fourier–Poisson cube, a structure that links the Fourier transforms, Fourier series, and discrete Fourier transforms students encounter in their undergraduate classes. We prove that these equations are valid when certain elementary suﬃcient conditions are satisﬁed. We complete the presentation of basic themes by describing the convolution product of functions on R,Tp,Z, and PN in Chapter 2.

Chapters 3 and 4 are devoted to the development of computational skills. We introduce the Fourier transform calculus for functions on R by ﬁnding transforms of the box, Π(x), the truncated exponential, e−x h(x), and the unit gaussian e−πx2 .

We present the rules (linearity, translation, dilation, convolution, inversion, | ) |

and use them to obtain transforms for a large class of functions on R. Various methods are used to ﬁnd Fourier series. In addition to direct integration (with Kronecker’s rule), we present (and emphasize) Poisson’s formula, Eagle’s method, and the use of elementary Laurent series (from calculus). Corresponding rules facilitate the manipulation of the Fourier representations for functions on Tp and Z.

An understanding of the Fourier transform calculus for functions on PN is essential for anyone who wishes to use the FFT. We establish a few well-known DFT pairs and develop the corresponding rules. We illustrate the power of this calculus by deriving the Euler–Maclaurin sum formula from elementary numerical analysis and evaluating the Gauss sums from elementary number theory.

In Chapter 5 we use operators, i.e., function-to-function mappings, to organize the multiplicity of specialized Fourier transform rules. We characterize the basic symmetries of Fourier analysis and develop a deeper understanding of the Fourier transform calculus. We also use the operator notation to facilitate a study of Sine, Cosine, Hartley, and Hilbert transforms.

The subject of Chapter 6 is the FFT (which Gilbert Strang calls the most important algorithm of the 20th century!). After describing the O(N2) scheme of Horner, we use the DFT calculus to produce an N-point DFT with only O(N log2 N) operations. We use an elementary zipper identity to obtain a sparse factorization of the DFT matrix and develop a corresponding algorithm (including the clever enhancements of Bracewell and Buneman) for fast machine computation. We brieﬂy introduce some of the more specialized DFT factorizations that can be obtained by using Kronecker products.

An elementary exposition of generalized functions (the tempered distributions of

Schwartz) is given in Chapter 7, the heart of the book. We introduce the Dirac δ [as the second derivative of the ramp r(x) := max(x,0)], the comb X; the reciprocal

, | and carefully extend the FT calculus rules to |

inﬁnite series, inﬁnite products, ordinary derivatives, partial derivatives, |

“1/x”, the Fresnel function eiπx2 this new setting. We introduce generalized (weak) limits so that we can work with

Selected applications of Fourier analysis are given in the remaining chapters. (You can ﬁnd whole textbooks devoted to each of these topics.) Mathematical

To the Instructor xv models based on Fourier synthesis, analysis done with generalized functions, and FFT computations are used to foster insight and understanding. You will experience the enormous “leverage” Fourier analysis can give as you study this material!

(Parte **1** de 4)