Full download test bank at ebook textbookfull.

com

Numerical Fourier Analysis 1st

CLICK LINK TO DOWLOAD

https://textbookfull.com/product/numerical-
fourier-analysis-1st-edition-gerlind-plonka/

textbookfull
More products digital (pdf, epub, mobi) instant
download maybe you interests ...

Numerical Exploration of Fourier Transform and Fourier

Series: The Power Spectrum of Driven Damped Oscillators
(Synthesis Lectures on Mathematics & Statistics) 1st
Edition Chowdhury
https://textbookfull.com/product/numerical-exploration-of-
fourier-transform-and-fourier-series-the-power-spectrum-of-
driven-damped-oscillators-synthesis-lectures-on-mathematics-
statistics-1st-edition-chowdhury/

Fourier Integrals in Classical Analysis Christopher D.

Sogge

https://textbookfull.com/product/fourier-integrals-in-classical-
analysis-christopher-d-sogge/

Fourier Integrals in Classical Analysis 2nd Edition

Christopher D. Sogge

https://textbookfull.com/product/fourier-integrals-in-classical-
analysis-2nd-edition-christopher-d-sogge/

Music Through Fourier Space Discrete Fourier Transform

in Music Theory 1st Edition Emmanuel Amiot (Auth.)

https://textbookfull.com/product/music-through-fourier-space-
discrete-fourier-transform-in-music-theory-1st-edition-emmanuel-
amiot-auth/
Hermitian Analysis: From Fourier Series to Cauchy-
Riemann Geometry 2nd Edition John P. D’Angelo

https://textbookfull.com/product/hermitian-analysis-from-fourier-
series-to-cauchy-riemann-geometry-2nd-edition-john-p-dangelo/

Computational methods for numerical analysis with R 1st

Edition James Patrick Howard Ii

https://textbookfull.com/product/computational-methods-for-
numerical-analysis-with-r-1st-edition-james-patrick-howard-ii/

Numerical Analysis for Applied Science 2nd Edition

Myron B. Allen Iii

https://textbookfull.com/product/numerical-analysis-for-applied-
science-2nd-edition-myron-b-allen-iii/

Using R for Numerical Analysis in Science and

Engineering 1st Edition Victor A. Bloomfield

https://textbookfull.com/product/using-r-for-numerical-analysis-
in-science-and-engineering-1st-edition-victor-a-bloomfield/

Numerical Methods for Conservation Laws From Analysis

to Algorithm First Edition Jan S. Hesthaven

https://textbookfull.com/product/numerical-methods-for-
conservation-laws-from-analysis-to-algorithm-first-edition-jan-s-
hesthaven/
 Applied and Numerical Harmonic Analysis

Gerlind Plonka
Daniel Potts
Gabriele Steidl
Manfred Tasche

Numerical
Fourier
Analysis
Applied and Numerical Harmonic Analysis
Series Editor
John J. Benedetto
University of Maryland
College Park, MD, USA

Editorial Advisory Board

Akram Aldroubi Gitta Kutyniok

Vanderbilt University Technische Universität Berlin
Nashville, TN, USA Berlin, Germany

Douglas Cochran Mauro Maggioni

Arizona State University Duke University
Phoenix, AZ, USA Durham, NC, USA

Hans G. Feichtinger Zuowei Shen

University of Vienna National University of Singapore
Vienna, Austria Singapore, Singapore

Christopher Heil Thomas Strohmer

Georgia Institute of Technology University of California
Atlanta, GA, USA Davis, CA, USA

Stéphane Jaffard Yang Wang

University of Paris XII Michigan State University
Paris, France East Lansing, MI, USA

Jelena Kovačević
Carnegie Mellon University
Pittsburgh, PA, USA

More information about this series at http://www.springer.com/series/4968

Gerlind Plonka • Daniel Potts • Gabriele Steidl •
Manfred Tasche

Numerical Fourier Analysis

Gerlind Plonka Daniel Potts
University of Göttingen Chemnitz University of Technology
Göttingen, Germany Chemnitz, Germany

Gabriele Steidl Manfred Tasche

TU Kaiserslautern University of Rostock
Kaiserslautern, Germany Rostock, Germany

ISSN 2296-5009 ISSN 2296-5017 (electronic)

Applied and Numerical Harmonic Analysis
ISBN 978-3-030-04305-6 ISBN 978-3-030-04306-3 (eBook)
https://doi.org/10.1007/978-3-030-04306-3

Library of Congress Control Number: 2018963834

Mathematics Subject Classification (2010): 42-01, 65-02, 42A10, 42A16, 42A20, 42A38, 42A85, 42B05,
42B10, 42C15, 65B05, 65D15, 65D32, 65F35, 65G50, 65T40, 65T50, 65Y20, 94A11, 94A12, 94A20,
15A12, 15A22

© Springer Nature Switzerland AG 2018

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of
the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,
broadcasting, reproduction on microfilms or in any other physical way, and transmission or information
storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology
now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this book
are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or
the editors give a warranty, express or implied, with respect to the material contained herein or for any
errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional
claims in published maps and institutional affiliations.

This book is published under the imprint Birkhäuser, www.birkhauser-science.com by the registered
company Springer Nature Switzerland AG
The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
ANHA Series Preface

The Applied and Numerical Harmonic Analysis (ANHA) book series aims to
provide the engineering, mathematical, and scientific communities with significant
developments in harmonic analysis, ranging from abstract harmonic analysis to
basic applications. The title of the series reflects the importance of applications
and numerical implementation, but richness and relevance of applications and
implementation depend fundamentally on the structure and depth of theoretical
underpinnings. Thus, from our point of view, the interleaving of theory and
applications and their creative symbiotic evolution is axiomatic.
Harmonic analysis is a wellspring of ideas and applicability that has flourished,
developed, and deepened over time within many disciplines and by means of
creative cross-fertilization with diverse areas. The intricate and fundamental rela-
tionship between harmonic analysis and fields such as signal processing, partial
differential equations (PDEs), and image processing is reflected in our state-of-the-
art ANHA series.
Our vision of modern harmonic analysis includes mathematical areas such as
wavelet theory, Banach algebras, classical Fourier analysis, time-frequency analysis,
and fractal geometry, as well as the diverse topics that impinge on them.
For example, wavelet theory can be considered an appropriate tool to deal with
some basic problems in digital signal processing, speech and image processing,
geophysics, pattern recognition, biomedical engineering, and turbulence. These
areas implement the latest technology from sampling methods on surfaces to fast
algorithms and computer vision methods. The underlying mathematics of wavelet
theory depends not only on classical Fourier analysis, but also on ideas from abstract
harmonic analysis, including von Neumann algebras and the affine group. This leads
to a study of the Heisenberg group and its relationship to Gabor systems, and of the
metaplectic group for a meaningful interaction of signal decomposition methods.
The unifying influence of wavelet theory in the aforementioned topics illustrates the
justification for providing a means for centralizing and disseminating information
from the broader, but still focused, area of harmonic analysis. This will be a key role
of ANHA. We intend to publish with the scope and interaction that such a host of
issues demands.

v
vi ANHA Series Preface

Along with our commitment to publish mathematically significant works at the

frontiers of harmonic analysis, we have a comparably strong commitment to publish
major advances in the following applicable topics in which harmonic analysis plays
a substantial role:
Antenna theory Prediction theory
Biomedical signal processing Radar applications
Digital signal processing Sampling theory
Fast algorithms Spectral estimation
Gabor theory and applications Speech processing
Image processing Time-frequency and
Numerical partial differential equations time-scaleanalysis
Wavelet theory
The above point of view for the ANHA book series is inspired by the history of
Fourier analysis itself, whose tentacles reach into so many fields.
In the last two centuries Fourier analysis has had a major impact on the
development of mathematics, on the understanding of many engineering and
scientific phenomena, and on the solution of some of the most important problems
in mathematics and the sciences. Historically, Fourier series were developed in
the analysis of some of the classical PDEs of mathematical physics; these series
were used to solve such equations. In order to understand Fourier series and the
kinds of solutions they could represent, some of the most basic notions of analysis
were defined, e.g., the concept of “function.” Since the coefficients of Fourier
series are integrals, it is no surprise that Riemann integrals were conceived to deal
with uniqueness properties of trigonometric series. Cantor’s set theory was also
developed because of such uniqueness questions.
A basic problem in Fourier analysis is to show how complicated phenomena,
such as sound waves, can be described in terms of elementary harmonics. There are
two aspects of this problem: first, to find, or even define properly, the harmonics or
spectrum of a given phenomenon, e.g., the spectroscopy problem in optics; second,
to determine which phenomena can be constructed from given classes of harmonics,
as done, for example, by the mechanical synthesizers in tidal analysis.
Fourier analysis is also the natural setting for many other problems in engineer-
ing, mathematics, and the sciences. For example, Wiener’s Tauberian theorem in
Fourier analysis not only characterizes the behavior of the prime numbers, but also
provides the proper notion of spectrum for phenomena such as white light; this
latter process leads to the Fourier analysis associated with correlation functions in
filtering and prediction problems, and these problems, in turn, deal naturally with
Hardy spaces in the theory of complex variables.
Nowadays, some of the theory of PDEs has given way to the study of Fourier
integral operators. Problems in antenna theory are studied in terms of unimodular
trigonometric polynomials. Applications of Fourier analysis abound in signal
processing, whether with the fast Fourier transform (FFT), or filter design, or the
ANHA Series Preface vii

adaptive modeling inherent in time-frequency-scale methods such as wavelet theory.

The coherent states of mathematical physics are translated and modulated Fourier
transforms, and these are used, in conjunction with the uncertainty principle, for
dealing with signal reconstruction in communications theory. We are back to the
raison d’être of the ANHA series!

University of Maryland John J. Benedetto

College Park, MD, USA Series Editor
Preface

Fourier analysis has grown to become an essential mathematical tool with numerous
applications in applied mathematics, engineering, physics, and other sciences. Many
recent technological innovations from spectroscopy and computer tomography to
speech and music signal processing are based on Fourier analysis. Fast Fourier
algorithms are the heart of data processing methods, and their societal impact can
hardly be overestimated.
The field of Fourier analysis is continuously developing toward the needs in
applications, and many topics are part of ongoing intensive research. Due to the
importance of Fourier techniques, there are several books on the market focusing on
different aspects of Fourier theory, as e.g. [28, 58, 72, 113, 119, 125, 146, 205, 219,
221, 260, 268, 303, 341, 388, 392], or on corresponding algorithms of the discrete
Fourier transform, see e.g. [36, 46, 47, 63, 162, 257, 307, 362], not counting further
monographs on special applications and generalizations as wavelets [69, 77, 234].
So, why do we write another book? Examining the existing textbooks in Fourier
analysis, it appears as a shortcoming that the focus is either set only on the
mathematical theory or vice versa only on the corresponding discrete Fourier and
convolution algorithms, while the reader needs to consult additional references on
the numerical techniques in the one case or on the analytical background in the
other.
The urgent need for a unified presentation of Fourier theory and corresponding
algorithms particularly emerges from new developments in function approximation
using Fourier methods. It is important to understand how well a continuous signal
can be approximated by employing the discrete Fourier transform to sampled
spectral data. A deep understanding of function approximation by Fourier rep-
resentations is even more crucial for deriving more advanced transforms as the
nonequispaced fast Fourier transform, which is an approximative algorithm by
nature, or sparse fast Fourier transforms on special lattices in higher dimensions.
This book encompasses the required classical Fourier theory in the first part
in order to give deep insights into the construction and analysis of corresponding
fast Fourier algorithms in the second part, including recent developments on

ix
x Preface

nonequispaced and sparse fast Fourier transforms in higher dimensions. In the third
part of the book, we present a selection of mathematical applications including
recent research results on nonlinear function approximation by exponential sums.

Our book starts with two chapters on classical Fourier analysis and Chap. 3 on the
discrete Fourier transform in one dimension, followed by Chap. 4 on the multivariate
case. This theoretical part provides the background for all further chapters and
makes the book self-contained.
Chapters 5–8 are concerned with the construction and analysis of corresponding
fast algorithms in the one- and multidimensional case. While Chap. 5 covers the
well-known fast Fourier transforms, Chaps. 7 and 8 are concerned with the con-
struction of the nonequispaced fast Fourier transforms and the high-dimensional fast
Fourier transforms on special lattices. Chapter 6 is devoted to discrete trigonometric
transforms and Chebyshev expansions which are closely related to Fourier series.
The last part of the book contains two chapters on applications of numerical
Fourier methods for improved function approximation.
Starting with Sects. 5.4 and 5.5, the book covers many recent well-recognized
developments in numerical Fourier analysis which cannot be found in other books
in this form, including research results of the authors obtained within the last 20
years.
This includes topics such as:
• The analysis of the numerical stability of the radix-2 FFT in Sect. 5.5
• Fast trigonometric transforms based on orthogonal matrix factorizations and fast
discrete polynomial transforms in Chap. 6
• Fast Fourier transforms and fast trigonometric transforms for nonequispaced data
in space and/or frequency in Sects. 7.1–7.4
• Fast summation at nonequispaced knots in Sect. 7.5
More recent research results can be found on:
• Sparse FFT for vectors with presumed sparsity in Sect. 5.4
• High-dimensional sparse fast FFT on rank-1 lattices in Chap. 8
• Applications of multi-exponential analysis and Prony method for recovery of
structured functions in Chap. 10

An introductory course on Fourier analysis at the advanced undergraduate level

can for example be built using Sects. 1.2–1.4, 2.1–2.2, 3.2–3.3, 4.1–4.3, and 5.1–
5.2. We assume that the reader is familiar with basic knowledge on calculus of
univariate and multivariate functions (including basic facts on Lebesgue integration
and functional analysis) and on numerical linear algebra. Focusing a lecture on
discrete fast algorithms and applications, one may consult Chaps. 3, 5, 6, and 9.
Chapters 7, 8, and 10 are at an advanced level and require pre-knowledge from
Chaps. 1, 2, and 4.
Preface xi

Parts of the book are based on a series of lectures and seminars given by
the authors to students of mathematics, physics, computer science, and electrical
engineering. Chapters 1, 2, 3, 5, and 9 are partially based on teaching material
written by G. Steidl and M. Tasche that was published in 1996 by the University
of Hagen under the title “Fast Fourier Transforms—Theory and Applications” (in
German). The authors wish to express their gratitude to the University of Hagen for
the friendly permission to use this material for this book.
Last but not least, the authors would like to thank Springer/Birkhäuser for
publishing this book.

Göttingen, Germany Gerlind Plonka

Chemnitz, Germany Daniel Potts
Kaiserslautern, Germany Gabriele Steidl
Rostock, Germany Manfred Tasche
October 2018
Contents

1 Fourier Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1
1.1 Fourier’s Solution of Laplace Equation . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1
1.2 Fourier Coefficients and Fourier Series . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 6
1.3 Convolution of Periodic Functions . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 16
1.4 Pointwise and Uniform Convergence of Fourier Series . . . . . . . . . . . . 27
1.4.1 Pointwise Convergence .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 30
1.4.2 Uniform Convergence . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 40
1.4.3 Gibbs Phenomenon .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 45
1.5 Discrete Signals and Linear Filters . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 51
2 Fourier Transforms.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 61
2.1 Fourier Transforms on L1 (R). . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 61
2.2 Fourier Transforms on L2 (R). . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 78
2.3 Poisson Summation Formula and Shannon’s Sampling
Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 83
2.4 Heisenberg’s Uncertainty Principle . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 88
2.5 Fourier-Related Transforms in Time–Frequency Analysis . . . . . . . . . 95
2.5.1 Windowed Fourier Transform.. . . . . . . . .. . . . . . . . . . . . . . . . . . . . 95
2.5.2 Fractional Fourier Transforms . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 101
3 Discrete Fourier Transforms . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 107
3.1 Motivations for Discrete Fourier Transforms . . .. . . . . . . . . . . . . . . . . . . . 107
3.1.1 Approximation of Fourier Coefficients and
Aliasing Formula . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 108
3.1.2 Computation of Fourier Series and Fourier
Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 112
3.1.3 Trigonometric Polynomial Interpolation . . . . . . . . . . . . . . . . . . 114
3.2 Fourier Matrices and Discrete Fourier Transforms . . . . . . . . . . . . . . . . . 118
3.2.1 Fourier Matrices . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 118
3.2.2 Properties of Fourier Matrices . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 124
3.2.3 DFT and Cyclic Convolutions . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 130

xiii
xiv Contents

3.3 Circulant Matrices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 137

3.4 Kronecker Products and Stride Permutations . . .. . . . . . . . . . . . . . . . . . . . 142
3.5 Discrete Trigonometric Transforms . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 151
4 Multidimensional Fourier Methods . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 159
4.1 Multidimensional Fourier Series . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 159
4.2 Multidimensional Fourier Transforms . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 166
4.2.1 Fourier Transforms on S (Rd ) . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 167
4.2.2 Fourier Transforms on L1 (Rd ) and L2 (Rd ). . . . . . . . . . . . . . . 176
4.2.3 Poisson Summation Formula.. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 178
4.2.4 Fourier Transforms of Radial Functions .. . . . . . . . . . . . . . . . . . 180
4.3 Fourier Transform of Tempered Distributions . .. . . . . . . . . . . . . . . . . . . . 183
4.3.1 Tempered Distributions.. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 183
4.3.2 Fourier Transforms on S  (Rd ) . . . . . . . .. . . . . . . . . . . . . . . . . . . . 193
4.3.3 Periodic Tempered Distributions.. . . . . .. . . . . . . . . . . . . . . . . . . . 199
4.3.4 Hilbert Transform and Riesz Transform .. . . . . . . . . . . . . . . . . . 205
4.4 Multidimensional Discrete Fourier Transforms.. . . . . . . . . . . . . . . . . . . . 213
4.4.1 Computation of Multivariate Fourier Coefficients . . . . . . . . 213
4.4.2 Two-Dimensional Discrete Fourier Transforms .. . . . . . . . . . 217
4.4.3 Higher-Dimensional Discrete Fourier Transforms .. . . . . . . 226
5 Fast Fourier Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 231
5.1 Construction Principles of Fast Algorithms .. . . .. . . . . . . . . . . . . . . . . . . . 231
5.2 Radix-2 FFTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 235
5.2.1 Sande–Tukey FFT in Summation Form . . . . . . . . . . . . . . . . . . . 236
5.2.2 Cooley–Tukey FFT in Polynomial Form . . . . . . . . . . . . . . . . . . 239
5.2.3 Radix-2 FFT’s in Matrix Form .. . . . . . . .. . . . . . . . . . . . . . . . . . . . 242
5.2.4 Radix-2 FFT for Parallel Programming . . . . . . . . . . . . . . . . . . . 247
5.2.5 Computational Costs of Radix-2 FFT’s . . . . . . . . . . . . . . . . . . . 250
5.3 Other Fast Fourier Transforms.. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 253
5.3.1 Chinese Remainder Theorem . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 254
5.3.2 Fast Algorithms for DFT of Composite Length .. . . . . . . . . . 256
5.3.3 Radix-4 FFT and Split–Radix FFT . . . .. . . . . . . . . . . . . . . . . . . . 263
5.3.4 Rader FFT and Bluestein FFT . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 269
5.3.5 Multidimensional FFTs . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 276
5.4 Sparse FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 281
5.4.1 Single Frequency Recovery . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 282
5.4.2 Recovery of Vectors with One Frequency Band . . . . . . . . . . 285
5.4.3 Recovery of Sparse Fourier Vectors . . .. . . . . . . . . . . . . . . . . . . . 288
5.5 Numerical Stability of FFT . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 295
6 Chebyshev Methods and Fast DCT Algorithms. . . . .. . . . . . . . . . . . . . . . . . . . 305
6.1 Chebyshev Polynomials and Chebyshev Series . . . . . . . . . . . . . . . . . . . . 305
6.1.1 Chebyshev Polynomials .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 306
6.1.2 Chebyshev Series . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 312
Contents xv

6.2 Fast Evaluation of Polynomials.. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 320

6.2.1 Horner Scheme and Clenshaw Algorithm .. . . . . . . . . . . . . . . . 320
6.2.2 Polynomial Evaluation and Interpolation at
Chebyshev Points . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 323
6.2.3 Fast Evaluation of Polynomial Products.. . . . . . . . . . . . . . . . . . 330
6.3 Fast DCT Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 333
6.3.1 Fast DCT Algorithms via FFT . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 334
6.3.2 Fast DCT Algorithms via Orthogonal Matrix
Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 338
6.4 Interpolation and Quadrature Using Chebyshev Expansions.. . . . . . 348
6.4.1 Interpolation at Chebyshev Extreme Points . . . . . . . . . . . . . . . 348
6.4.2 Clenshaw–Curtis Quadrature . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 357
6.5 Discrete Polynomial Transforms . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 365
6.5.1 Orthogonal Polynomials . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 365
6.5.2 Fast Evaluation of Orthogonal Expansions .. . . . . . . . . . . . . . . 367
7 Fast Fourier Transforms for Nonequispaced Data ... . . . . . . . . . . . . . . . . . . . 377
7.1 Nonequispaced Data Either in Space or Frequency Domain .. . . . . . 377
7.2 Approximation Errors for Special Window Functions . . . . . . . . . . . . . 385
7.3 Nonequispaced Data in Space and Frequency Domain.. . . . . . . . . . . . 394
7.4 Nonequispaced Fast Trigonometric Transforms . . . . . . . . . . . . . . . . . . . . 397
7.5 Fast Summation at Nonequispaced Knots. . . . . . .. . . . . . . . . . . . . . . . . . . . 403
7.6 Inverse Nonequispaced Discrete Transforms . . .. . . . . . . . . . . . . . . . . . . . 410
7.6.1 Direct Methods for Inverse NDCT and Inverse NDFT . . . 411
7.6.2 Iterative Methods for Inverse NDFT . . .. . . . . . . . . . . . . . . . . . . . 417
8 High-Dimensional FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 421
8.1 Fourier Partial Sums of Smooth Multivariate Functions . . . . . . . . . . . 422
8.2 Fast Evaluation of Multivariate Trigonometric Polynomials .. . . . . . 427
8.2.1 Rank-1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 428
8.2.2 Evaluation of Trigonometric Polynomials on
Rank-1 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 430
8.2.3 Evaluation of the Fourier Coefficients .. . . . . . . . . . . . . . . . . . . . 432
8.3 Efficient Function Approximation on Rank-1 Lattices .. . . . . . . . . . . . 434
8.4 Reconstructing Rank-1 Lattices . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 437
8.5 Multiple Rank-1 Lattices. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 442
9 Numerical Applications of DFT . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 449
9.1 Cardinal Interpolation by Translates . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 449
9.1.1 Cardinal Lagrange Function . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 454
9.1.2 Computation of Fourier Transforms . . .. . . . . . . . . . . . . . . . . . . . 464
9.2 Periodic Interpolation by Translates . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 468
9.2.1 Periodic Lagrange Function .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 469
9.2.2 Computation of Fourier Coefficients . .. . . . . . . . . . . . . . . . . . . . 475
9.3 Quadrature of Periodic Functions . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 478
xvi Contents

9.4 Accelerating Convergence of Fourier Series . . . .. . . . . . . . . . . . . . . . . . . . 485

9.4.1 Krylov–Lanczos Method .. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 486
9.4.2 Fourier Extension .. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 490
9.5 Fast Poisson Solvers.. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 495
9.6 Spherical Fourier Transforms .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 507
9.6.1 Discrete Spherical Fourier Transforms . . . . . . . . . . . . . . . . . . . . 510
9.6.2 Fast Spherical Fourier Transforms .. . . .. . . . . . . . . . . . . . . . . . . . 511
9.6.3 Fast Spherical Fourier Transforms for
Nonequispaced Data . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 513
9.6.4 Fast Quadrature and Approximation on S2 . . . . . . . . . . . . . . . . 518
10 Prony Method for Reconstruction of Structured Functions . . . . . . . . . . . 523
10.1 Prony Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 523
10.2 Recovery of Exponential Sums . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 529
10.2.1 MUSIC and Approximate Prony Method . . . . . . . . . . . . . . . . . 531
10.2.2 ESPRIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 536
10.3 Stability of Exponentials .. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 542
10.4 Recovery of Structured Functions . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 556
10.4.1 Recovery from Fourier Data . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 556
10.4.2 Recovery from Function Samples . . . . .. . . . . . . . . . . . . . . . . . . . 561
10.5 Phase Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 567

A List of Symbols and Abbreviations . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 575

A.1 Table of Some Fourier Series . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 575
A.2 Table of Some Chebyshev Series . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 576
A.3 Table of Some Fourier Transforms . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 577
A.4 Table of Some Discrete Fourier Transforms . . . .. . . . . . . . . . . . . . . . . . . . 578
A.5 Table of Some Fourier Transforms of Tempered Distributions . . . . 579

References .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 589

Index . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 607

Applied and Numerical Harmonic Analysis (90 Volumes) . . . . . . . . . . . . . . . . . . 615

Chapter 1
Fourier Series

Chapter 1 covers the classical theory of Fourier series of 2π-periodic functions. In

the introductory section, we sketch Fourier’s theory on heat propagation. Section 1.2
introduces some basic notions such as Fourier coefficients and Fourier series of
a 2π-periodic function. The convolution of 2π-periodic functions is handled in
Sect. 1.3. Section 1.4 presents main results on the pointwise and uniform conver-
gence of Fourier series. For a 2π-periodic, piecewise continuously differentiable
function f , a complete proof of the important convergence theorem of Dirichlet–
Jordan is given. Further we describe the Gibbs phenomenon for partial sums of the
Fourier series of f near a jump discontinuity. Finally, in Sect. 1.5, we apply Fourier
series in digital signal processing and describe the linear filtering of discrete signals.

1.1 Fourier’s Solution of Laplace Equation

In 1804, the French mathematician and egyptologist Jean Baptiste Joseph Fourier
(1768–1830) began his studies on the heat propagation in solid bodies. In 1807, he
finished a first paper about heat propagation. He discovered the fundamental partial
differential equation of heat propagation and developed a new method to solve this
equation. The mathematical core of Fourier’s idea was that each periodic function
can be well approximated by a linear combination of sine and cosine terms. This
theory contradicted the previous views on functions and was met with resistance
by some members of the French Academy of Sciences, so that a publication was

© Springer Nature Switzerland AG 2018 1

G. Plonka et al., Numerical Fourier Analysis, Applied and Numerical
Harmonic Analysis, https://doi.org/10.1007/978-3-030-04306-3_1
2 1 Fourier Series

Fig. 1.1 The mathematician

and egyptologist Jean
Baptiste Joseph
Fourier (1768–1830)

initially prevented. Later, Fourier presented these results in the famous book “The
Analytical Theory of Heat” published firstly 1822 in French, cf. [119]. For an image
of Fourier, see Fig. 1.1 (Image source: https://commons.wikimedia.org/wiki/File:
Joseph_Fourier.jpg).
In the following, we describe Fourier’s idea by a simple example. We consider
the open unit disk Ω = {(x, y) ∈ R2 : x 2 + y 2 < 1} with the boundary Γ =
{(x, y) ∈ R2 : x 2 + y 2 = 1}. Let v(x, y, t) denote the temperature at the point
(x, y) ∈ Ω and the time t ≥ 0. For physical reasons, the temperature fulfills the
heat equation

∂ 2v ∂ 2v ∂v
2
+ 2
=c , (x, y) ∈ Ω, t > 0
∂x ∂y ∂t

with some constant c > 0. At steady state, the temperature is independent of the
time such that v(x, y, t) = v(x, y) satisfies the Laplace equation

∂ 2v ∂ 2v
+ = 0, (x, y) ∈ Ω.
∂x 2 ∂y 2

What is the temperature v(x, y) at any point (x, y) ∈ Ω, if the temperature at each
point of the boundary Γ is known?
Using polar coordinates

x = r cos ϕ , y = r sin ϕ, 0 < r < 1, 0 ≤ ϕ < 2π,

1.1 Fourier’s Solution of Laplace Equation 3

we obtain for the temperature u(r, ϕ) := v(r cos ϕ, r sin ϕ) by chain rule

∂ 2v ∂ 2v ∂ 2 u 1 ∂u 1 ∂ 2u
+ = + + = 0.
∂x 2 ∂y 2 ∂r 2 r ∂r r 2 ∂ϕ 2

If we extend the variable ϕ periodically to the real line R, then u(r, ϕ) is 2π-periodic
with respect to ϕ and fulfills

∂ 2u ∂u ∂ 2u
r2 + r = − , 0 < r < 1, ϕ ∈ R. (1.1)
∂r 2 ∂r ∂ϕ 2

Since the temperature at the boundary Γ is given, we know the boundary condition

u(1, ϕ) = f (ϕ), ϕ ∈ R, (1.2)

where f is a given continuously differentiable, 2π-periodic function. Applying

separation of variables, we seek nontrivial solutions of (1.1) of the form u(r, ϕ) =
p(r) q(ϕ), where p is bounded on (0, 1) and q is 2π-periodic. From (1.1) it follows
 2  
r p (r) + r p (r) q(ϕ) = −p(r) q  (ϕ)

and hence
r 2 p (r) + r p (r) q  (ϕ)
=− . (1.3)
p(r) q(ϕ)
The variables r and ϕ can be independently chosen. If ϕ is fixed and r varies, then
the left-hand side of (1.3) is a constant. Analogously, if r is fixed and ϕ varies, then
the right-hand side of (1.3) is a constant. Let λ be the common value of both sides.
Then we obtain two linear differential equations

r 2 p (r) + r p (r) − λ p(r) = 0 , (1.4)

q  (ϕ) + λ q(ϕ) = 0 . (1.5)

Since nontrivial solutions of (1.5) must have the period 2π, we obtain the solutions
a0
2 for λ = 0 and an cos(nϕ) + bn sin(nϕ) for λ = n , n ∈ N, where a0 , an , and
2

bn with n ∈ N are real constants. For λ = 0, the linear differential equation (1.4)
has the linearly independent solutions 1 and ln r, where only 1 is bounded on (0, 1).
For λ = n2 , Eq. (1.4) has the linearly independent solutions r n and r −n , where only
r n is bounded on (0, 1). Thus we see that a20 and r n (an cos(nϕ) + bn sin(nϕ)),
n ∈ N, are the special solutions of the Laplace equation (1.1). If u1 and u2 are
4 1 Fourier Series

solutions of the linear equation (1.1), then u1 + u2 is a solution of (1.1) too. Using
the superposition principle, we obtain a formal solution of (1.1) of the form
∞
a0  n  
u(r, ϕ) = + r an cos(nϕ) + bn sin(nϕ) . (1.6)
2
n=1

By the boundary condition (1.2), the coefficients a0 , an , and bn with n ∈ N must be

chosen so that
∞
a0   
u(1, ϕ) = + an cos(nϕ) + bn sin(nϕ) = f (ϕ), ϕ ∈ R. (1.7)
2
n=1

Fourier conjectured that this could be done for an arbitrary 2π-periodic function f .
We will see that this is only the case, if f fulfills some additional conditions. As
shown in the next section, from (1.7) it follows that
 2π
1
an = f (ψ) cos(nψ) dψ, n ∈ N0 , (1.8)
π 0
 2π
1
bn = f (ψ) sin(nψ) dψ, n ∈ N. (1.9)
π 0

By assumption, f is bounded on R, i.e., |f (ψ)| ≤ M. Thus we obtain that

 2π
1
|an | ≤ |f (ψ)| dψ ≤ 2M, n ∈ N0 .
π 0

Analogously, it holds |bn | ≤ 2M for all n ∈ N.

Now we have to show that the constructed function (1.6) with the coeffi-
cients (1.8) and (1.9) is really a solution of (1.1) which fulfills the boundary
condition (1.2). Since the 2π-periodic function f is continuously differentiable, we
will see by Theorem 1.37 that
∞

(|an | + |bn |) < ∞ .
n=1
 
Introducing un (r, ϕ) := r n an cos(nϕ) + bn sin(nϕ) , we can estimate

|un (r, ϕ)| ≤ |an | + |bn |, (r, ϕ) ∈ [0, 1] × R.

a0
∞ Weierstrass criterion for uniform convergence it follows that the series 2 +
From
n=1 un converges uniformly on [0, 1] × R. Since each term un is continuous on
[0, 1]×R, the sum u of this uniformly convergent series is continuous on [0, 1]×R,
too. Note that the temperature in the origin of the closed unit disk is equal to the
 2π
mean value a20 = 2π1
0 f (ψ) dψ of the temperature f at the boundary.
1.1 Fourier’s Solution of Laplace Equation 5

Now we show that u fulfills the Laplace equation in [0, 1) × R. Let 0 < r0 < 1
be arbitrarily fixed. By

∂k  kπ kπ 
un (r, ϕ) = r n nk an cos(nϕ + ) + bn sin(nϕ + )
∂ϕ k 2 2

for arbitrary k ∈ N, we obtain

∂k
| un (r, ϕ)| ≤ 4 r n nk M ≤ 4 r0n nk M
∂ϕ k

for 0 ≤ r ≤ r0 . The series 4 M ∞ n k
n=1 r0 n is convergent. By the Weierstrass
∞ ∂ k ∂k
criterion, n=1 ∂ϕ k un is uniformly convergent on [0, r0 ] × R. Consequently, ∂ϕ k u
exists and

 ∂k ∞
∂k
u = un .
∂ϕ k ∂ϕ k
n=1

∂k
Analogously, one can show that ∂r k
u exists and

 ∂k ∞
∂k
u = un .
∂r k ∂r k
n=1

Since all un are solutions of the Laplace equation (1.1) in [0, 1) × R, it follows by
term by term differentiation that u is also a solution of (1.1) in [0, 1) × R.
Finally, we simplify the representation of the solution (1.6) with the coeffi-
cients (1.8) and (1.9). Since the series in (1.6) converges uniformly on [0, 1] × R,
we can change the order of summation and integration such that
 1 ∞

1 2π  
u(r, ϕ) = f (ψ) + r n cos n(ϕ − ψ) dψ.
π 0 2
n=1

Taking the real part of the geometric series

∞
 1
1+ r n einθ = .
1 − reiθ
n=1

it follows
∞
 1 − r cos θ
1+ r n cos(nθ ) =
1 + r 2 − 2r cos θ
n=1
6 1 Fourier Series

and hence
∞
1  n 1 1 − r2
+ r cos(nθ ) = .
2 2 1 + r 2 − 2r cos θ
n=1

Thus for 0 ≤ r < 1 and ϕ ∈ R, the solution of (1.6) can be represented as Poisson
integral
 2π
1 1 − r2
u(r, ϕ) = f (ψ) dψ .
2π 0 1 + r − 2r cos(ϕ − ψ)
2

1.2 Fourier Coefficients and Fourier Series

A complex-valued function f : R → C is 2π-periodic or periodic with period 2π,

if f (x + 2π) = f (x) for all x ∈ R. In the following, we identify any 2π-periodic
function f : R → C with the corresponding function f : T → C defined on the
torus T of length 2π. The torus T can be considered as quotient space R/(2πZ)
or its representatives, e.g. the interval [0, 2π] with identified endpoints 0 and 2π.
For short, one can also geometrically think of the unit circle with circumference 2π.
Typical examples of 2π-periodic functions are 1, cos(n·), sin(n·) for each angular
frequency n ∈ N and the complex exponentials ei k· for each k ∈ Z.
By C(T) we denote the Banach space of all continuous functions f : T → C
with the norm

f C(T) := max |f (x)|

x∈T

and by C r (T), r ∈ N the Banach space of r-times continuously differentiable

functions f : T → C with the norm

f C r (T) := f C(T) + f (r) C(T) .

Clearly, we have C r (T) ⊂ C s (T) for r > s.

Let Lp (T), 1 ≤ p ≤ ∞ be the Banach space of measurable functions f : T →
C with finite norm
 1  π 1/p
f Lp (T) := |f (x)|p dx , 1 ≤ p < ∞,
2π −π
f L∞ (T) := ess sup {|f (x)| : x ∈ T} ,

where we identify almost equal functions. If a 2π-periodic function f is integrable

on [−π, π], then we have
 π  π+a
f (x) dx = f (x) dx
−π −π+a
1.2 Fourier Coefficients and Fourier Series 7

for all a ∈ R so that we can integrate over any interval of length 2π.
Using Hölder’s inequality it can be shown that the spaces Lp (T) for 1 ≤ p ≤ ∞
are continuously embedded as

L1 (T) ⊃ L2 (T) ⊃ . . . ⊃ L∞ (T).

In the following we are mainly interested in the Hilbert space L2 (T) consisting of
all absolutely square-integrable functions f : T → C with inner product and norm
 π  1  π
1 1/2
f, g L2 (T) := f (x) g(x) dx , f L2 (T) := |f (x)|2 dx .
2π −π 2π −π

If it is clear from the context which inner product or norm is addressed, we

abbreviate f, g := f, g L2 (T) and f  := f L2 (T) . For all f, g ∈ L2 (T) it
holds the Cauchy–Schwarz inequality

| f, g L2 (T) | ≤ f L2 (T) gL2 (T) .

Theorem 1.1 The set of complex exponentials

eik· = cos(k·) + i sin(k·) : k ∈ Z (1.10)

forms an orthonormal basis of L2 (T).

Proof
1. By definition, an orthonormal basis is a complete orthonormal system. First we
show the orthonormality of the complex exponentials in (1.10). We have
 π
ij · 1
ik·
e ,e = ei(k−j )x dx ,
2π −π

which implies for integers k = j

 π
1
eik· , eik· = 1 dx = 1.
2π −π

On the other hand, we obtain for distinct integers j , k

1  πi(k−j ) 
eik· , eij · = e − e−πi(k−j )
2πi(k − j )
2i sin π(k − j )
= = 0.
2πi(k − j )

2. Now we prove the completeness of the set (1.10). We have to show that f, eik· =
0 for all k ∈ Z implies f = 0.
8 1 Fourier Series

First we consider a continuous function f ∈ C(T) having f, eik· = 0 for

all k ∈ Z. Let us denote by


n 
Tn := ck eik· : ck ∈ C (1.11)
k=−n

the space of all trigonometric polynomials up to degree n. By the approximation

theorem of Weierstrass, see Theorem 1.21, there exists for any function f ∈
C(T) a sequence (pn )n∈N0 of trigonometric polynomials pn ∈ Tn , which
converges uniformly to f , i.e.,
 
f − pn C(T) = max f (x) − pn (x) → 0 for n → ∞ .
x∈T

By assumption we have


n 
n
f, pn = f, ck ei k· = ck f, ei k· = 0 .
k=−n k=−n

Hence we conclude

f 2 = f, f − f, pn = f, f − pn → 0 (1.12)

as n → ∞, so that f = 0.
3. Now let f ∈ L2 (T) with f, eik· = 0 for all k ∈ Z be given. Then
 x
h(x) := f (t) dt, x ∈ [0, 2π),
0

is an absolutely continuous function satisfying h (x) = f (x) almost everywhere.

We have further h(0) = h(2π) = 0. For k ∈ Z\{0} we obtain
 2π
1
h, eik· = h(x) e−ikx dx
2π 0
2π  2π
1  1 1
=− h(x) e−ikx  + h (x) e−ikx dx = f, eik· = 0 .
2πik 0 2πik 0    2πik
=f (x)

Hence the 2π-periodically continued continuous function h − h, 1 fulfills h −

h, 1 , eik· = 0 for all k ∈ Z. Using the first part of this proof, we obtain
h = h, 1 = const. Since f (x) = h (x) = 0 almost everywhere, this yields
the assertion.
1.2 Fourier Coefficients and Fourier Series 9

Once we have an orthonormal basis of a Hilbert space, we can represent its elements
with respect to this basis. Let us consider the finite sum


n  π
1
Sn f := ck (f ) e ik·
∈ Tn , ck (f ) := f, e ik·
= f (x) e−ikx dx ,
2π −π
k=−n

called nth Fourier partial sum of f with the Fourier coefficients ck (f ). By definition
Sn : L2 (T) → L2 (T) is a linear operator which possesses the following important
approximation property.
Lemma 1.2 The Fourier partial sum operator Sn : L2 (T) → L2 (T) is an
orthogonal projector onto Tn , i.e.

f − Sn f  = min {f − p : p ∈ Tn }

for arbitrary f ∈ L2 (T). In particular, it holds


n
f − Sn f 2 = f 2 − |ck (f )|2 . (1.13)
k=−n

Proof
1. For each trigonometric polynomial


n
p= ck eik· (1.14)
k=−n

with arbitrary ck ∈ C and all f ∈ L2 (T) we have

f − p2 = f 2 − p, f − f, p + p2

n
 
= f 2 + − ck ck (f ) − ck ck (f ) + |ck |2
k=−n


n 
n
= f 2 − |ck (f )|2 + |ck − ck (f )|2 .
k=−n k=−n

Thus,


n
f − p ≥ f  −
2 2
|ck (f )|2 ,
k=−n

where equality holds only in the case ck = ck (f ), k = −n, . . . , n, i.e., if and

only if p = Sn f .
10 1 Fourier Series

2. For p ∈ Tn of the form (1.14), the corresponding Fourier coefficients are

ck (p) = ck for k = −n, . . . , n and ck (p) = 0 for all |k| > n. Thus
we have Sn p = p and Sn (Sn f ) = Sn f for arbitrary f ∈ L2 (T). Hence
Sn : L2 (T) → L2 (T) is a projection onto Tn . By


n
Sn f, g = ck (f ) ck (g) = f, Sn g
k=−n

for all f, g ∈ L2 (T), the Fourier partial sum operator Sn is self-adjoint,

i.e., Sn is an orthogonal projection. Moreover, Sn has the operator norm
Sn L2 (T)→L2 (T) = 1.
As an immediate consequence of Lemma 1.2 we obtain the following:
Theorem 1.3 Every function f ∈ L2 (T) has a unique representation of the form
  π
1
f = ik·
ck (f ) e , ck (f ) := f, e ik·
= f (x) e−ikx dx , (1.15)
2π −π
k∈Z

where the series (Sn f )∞

n=0 converges in L2 (T) to f , i.e.

lim Sn f − f  = 0 .
n→∞

Further the Parseval equality is fulfilled

  
f 2 =  f, eik· 2 = |ck (f )|2 < ∞ . (1.16)
k∈Z k∈Z

Proof By Lemma 1.2, we know that for each n ∈ N0


n
2
Sn f  = |ck (f )|2 ≤ f 2 < ∞ .
k=−n

For n → ∞, we obtain Bessel’s inequality

∞

|ck (f )|2 ≤ f 2 .
k=−∞

Consequently, for arbitrary ε > 0, there exists an index N(ε) ∈ N such that

|ck (f )|2 < ε .
|k|>N(ε)
1.2 Fourier Coefficients and Fourier Series 11

For m > n ≥ N(ε) we obtain

 −n−1 
 
m 
Sm f − Sn f  = 2
+ |ck (f )|2 ≤ |ck (f )|2 < ε .
k=−m k=n+1 |k|>N(ε)

Hence (Sn f )∞
n=0 is a Cauchy sequence. In the Hilbert space L2 (T), each Cauchy
sequence is convergent. Assume that limn→∞ Sn f = g with g ∈ L2 (T). Since

g, eik· = lim Sn f, eik· = lim f, Sn eik· = f, eik·

n→∞ n→∞

for all k ∈ Z, we conclude by Theorem 1.1 that f = g. Letting n → ∞ in (1.13)

we obtain the Parseval equality (1.16).
The representation (1.15) is the so-called Fourier series of f . Figure 1.2 shows
2π-periodic functions as superposition of two 2π-periodic functions.
Clearly, the partial sums of the Fourier series are the Fourier partial sums. The
π
constant term c0 (f ) = 2π1
−π f (x) dx in the Fourier series of f is the mean value
of f .
Remark 1.4 For fixed L > 0, a function f : R → C is called L-periodic, if
f (x + L) = f (x) for all x ∈ R. By substitution we see that the Fourier series of an
L-periodic function f reads as follows:

  L/2
1
f = ck(L) (f ) e2πik·/L , ck(L)(f ) := f (x) e−2πikx/L dx . 
L −L/2
k∈Z
(1.17)
In polar coordinates we can represent the Fourier coefficients in the form
 
ck (f ) = |ck (f )| ei ϕk , ϕk := atan2 Im ck (f ), Re ck (f ) , (1.18)

1 y 1 y

0.5
0.5
x
−π − π2 π π x
2
−π − π2 π π
−0.5 2

−0.5
−1

−1.5 −1

Fig. 1.2 Two 2π-periodic functions sin x + 1

2 cos(2x) (left) and sin x − 1
10 sin(4x) as superposi-
tions of sine and cosine functions
12 1 Fourier Series

where
⎧
⎪
⎪ arctan yx x > 0,
⎪
⎪
⎪
⎪ arctan yx + π x < 0, y ≥ 0 ,
⎪
⎪
⎪
⎨ arctan y − π x < 0, y < 0 ,
atan2(y, x) := π x
⎪
⎪ x = 0, y > 0 ,
⎪
⎪ 2
⎪−π
⎪ x = 0, y < 0 ,
⎪
⎪
⎪
⎩
2
0 x = y = 0.

Note that atan2 is a modified inverse tangent. Thus for (x, y) ∈ R2 \ {(0, 0)},
atan2(y, x) ∈ (−π, π] is defined as the angle between the vectors (1, 0) and
(x, y) . The sequence |ck (f )| k∈Z is called the spectrum or modulus of f and
 
ϕk k∈Z the phase of f .
For fixed a ∈ R, the 2π-periodic extension of a function f : [−π + a, π + a) →
C to the whole line R is given by f (x + 2πn) := f (x) for all x ∈ [−π + a, π + a)
and all n ∈ Z. Often we have a = 0 or a = π.
Example 1.5 Consider the 2π-periodic extension of the real-valued function
f (x) = e−x , x ∈ (−π, π) with f (±π) = cosh π = 12 (e−π + eπ ). Then the
Fourier coefficients ck (f ) are given by
 π
1
ck (f ) = e−(1+ik)x dx
2π −π

1  (−1)k sinh π
=− e−(1+ik)π − e(1+ik)π = .
2π (1 + ik) (1 + i k) π

Figure 1.3 shows both the 8th and 16th Fourier partial sums S8 f and S16 f .

y y
20 20

15 15

10 10

5 5

x x
π − π2 π π π − π2 π π
2 2

Fig. 1.3 The 2π-periodic function f given by f (x) := e−x , x ∈ (−π, π), with f (±π) =
cosh(π) and its Fourier partial sums S8 f (left) and S16 f (right)
1.2 Fourier Coefficients and Fourier Series 13

For f ∈ L2 (T) it holds the Parseval equality (1.16). Thus the Fourier coefficients
ck (f ) converge to zero as |k| → ∞. Since
 π
1
|ck (f )| ≤ |f (x)| dx = f L1 (T) ,
2π −π

the integrals
 π
1
ck (f ) = f (x) e−ikx dx , k∈Z
2π −π

also exist for all functions f ∈ L1 (T), i.e., the Fourier coefficients are well-defined
for any function of L1 (T). The next lemma contains simple properties of Fourier
coefficients.
Lemma 1.6 The Fourier coefficients of f, g ∈ L1 (T) have the following properties
for all k ∈ Z:
1. Linearity: For all α, β ∈ C,

ck (αf + βg) = α ck (f ) + β ck (g) .

2. Translation–Modulation: For all x0 ∈ [0, 2π) and k0 ∈ Z,

 
ck f (· − x0 ) = e−ikx0 ck (f ) ,
ck (e−ik0 · f ) = ck+k0 (f ) .

In particular |ck (f (· − x0 ))| = |ck (f )|, i.e., translation does not change the
spectrum of f .
3. Differentiation–Multiplication: For absolute continuous functions f ∈ L1 (T)
with f  ∈ L1 (T) we have

ck (f  ) = i k ck (f ) .

Proof The first property follows directly from the linearity of the integral. The
translation–modulation property can be seen as

  1 π
ck f (· − x0 ) = f (x − x0 ) e−ikx dx
2π −π
 π
1
= f (y) e−ik(y+x0) dy = e−ikx0 ck (f ),
2π −π

and similarly for the modulation–translation property.

14 1 Fourier Series

For the differentiation property recall that an absolute continuous function has a
derivative almost everywhere. Then we obtain by integration by parts
 π  π
1 1
ik f (x) e−ikx dx = f  (x) e−ikx dx = ck (f  ).
2π −π 2π −π

The complex Fourier series


f = ck (f ) eik·
k∈Z

can be rewritten using Euler’s formula eik· = cos(k·) + i sin(k·) as

 ∞
1 
f = a0 (f ) + ak (f ) cos(k·) + bk (f ) sin(k·) , (1.19)
2
k=1

where

ak (f ) = ck (f ) + c−k (f ) = 2 f, cos(k·) , k ∈ N0 ,
 
bk (f ) = i ck (f ) − c−k (f ) = 2 f, sin(k·) , k ∈ N .
 √  √ 
Consequently 1, 2 cos(k·) : k ∈ N ∪ 2 sin(k·) : k ∈ N form also an ortho-
normal basis of L2 (T). If f : T → R is a real-valued function, then ck (f ) = c−k (f )
and (1.19) is the real Fourier series of f . Using polar coordinates (1.18), the Fourier
series of a real-valued function f ∈ L2 (T) can be written in the form

 ∞
1 π
f = a0 (f ) + rk sin(k · + + ϕk ).
2 2
k=1

with sine oscillations of amplitudes rk = 2 |ck (f )|, angular frequencies k, and phase
shifts π2 + ϕk . For even/odd functions the Fourier series simplify to pure cosine/sine
series.
Lemma 1.7 If f ∈ L2 (T) is even, i.e., f (x) = f (−x) for all x ∈ T, then ck (f ) =
c−k (f ) for all k ∈ Z and f can be represented as a Fourier cosine series
∞
  ∞
1
f = c0 (f ) + 2 ck (f ) cos(k·) = a0 (f ) + ak (f ) cos(k·) .
2
k=1 k=1

If f ∈ L2 (T) is odd, i.e., f (x) = −f (−x) for all x ∈ T, then ck (f ) = −c−k (f )

for all k ∈ Z and f can be represented as a Fourier sine series
∞
 ∞

f = 2i ck (f ) sin(k·) = bk (f ) sin(k·).
k=1 k=1
Another random document with
no related content on Scribd:
excitement among the few who might learn of it. Perhaps they might
bury it; maybe they would leave that duty to the wolves. Who
knows?"
Endicott's face darkened, for the tone of the woman's voice had a
disdainful ring that cut into his pride like the needle points of a
tattooer. There was sharp pain and an ugly picture left behind. He
tried to smile at her earnestness, but it was a very dismal smile, and
his courage dropped away down toward zero. Not that he feared
death—he only found that he feared the woman!
"Death's-heads and thigh-bones! Run out the black flag if you
choose, yet there will many a day pass before I walk the plank. I see
no vision of sudden death, feel no premonition of approaching
dissolution. Say your say, for you are honest at heart, and when I
have listened to you, you will listen to me, I know. And for my corpse
—I entreat you to give it a Christian burial, should it be found with a
ball in the base of my skull or an underhanded knife-thrust in the
small of my back. Danger of that kind though, is I trust far off."
"Laugh if you will at my warning; yet, as you stand there in the full
moonlight, you make a fair target; and on my honor you stand this
minute covered by more than one weapon of death. You doubt me?
Well, I see a rifle-barrel aimed at your head by the hand of a man
who never yet missed his mark. I see it gleaming, and a wave of my
hand brings the leaden messenger. So go your way; if you remain
here five minutes longer, so help me Heaven, I will see you shot
down with as little mercy as I would a prowling coyote."
How or exactly where she disappeared, Endicott scarcely knew. A
mist appeared to sweep across his eyes, and when the mist rolled
away she was gone. He stared a moment blankly before him, with
the words of her warning ringing in his ears, and a doubt as to what
to do in his heart.
"'Shot as a prowling coyote!' Faith, she is in one of her tragic moods
to-night, and I verily believe she would do as she says. She may
speak truly too about some one lying in wait; this is a queer region
here, and if all accounts be true, a bullet from behind a bush would
be no unprecedented thing. I will find my way back to camp as best I
can. But how came she here?"
While muttering these things to himself he remounted his horse,
turned its head in the direction from which he had come and slowly
and thoughtfully began to retrace his steps.
Charles Endicott was a young man. He was well built, strong limbed,
easy in his motions, with a clear, strong voice. His brown hair, long
and well kept, was pushed back from a square forehead; his gray
eyes looked out keenly from under long eyelashes; his nose was
shapely, mouth not ungainly, his beard and mustache full and silken.
He settled firmly in his saddle as though he belonged there, and his
horse bore him as though knowing its master. The manner of his
hand upon the bridle-rein seemed to tell that, though his thoughts
might be elsewhere, still there was will left behind—will and a soul
prepared for any emergency. A face seen by moonlight, it is said, is
a heart unmasked. It may not be so in all cases; but it was in this.
There was a heart then unmasked, a heart untrammeled by the
fetters of conscience or the gyves of moral law. The man was a
plotter, the man was a schemer. Perhaps his plots and schemes
might come in contravention with right? Then right must of needs go
to the wall, for the measure of expediency was the measure of equity
with Endicott.
As he passed from the clear space into the wood the animal he
bestrode gave a start, which, while it caused no particular emotion in
the heart of the rider, was still sufficient to make him look warily
around. He thought he saw a gleaming and a glancing some little
distance off; he imagined he could hear the tread of some one
approaching. He was right in his thought, and in his imagination. The
gleaming and glancing were the moonbeams shivering off of the long
rifle, and the noise of footsteps announced the approach of Dick
Martin.
Endicott at first sight of the man had thrown his hand warily in search
of a weapon. But, almost instantly recognizing the man, he suffered
it to drop by his side, and, reining in his horse, awaited the issue of
the interview which he foresaw was about to ensue.
When Martin was within a few feet he paused, and the two gave a
look at each other as though they would read the man confronting to
the very soul.
It was Endicott who first broke the silence. He urged his steed
onward a few paces, bent down in his saddle and extended his
hand, at the same time exclaiming:
"Then it is you, Martin. I had half-suspected as much when I first
caught sight of you, and it gave me a shock. We meet as friends, I
hope?"
Martin remained standing unmoved, and as though he did not see
the proffered hand, and answered, in a cool, careless tone:
"Yes, Endicott, it is I—no more, and no less. I know you've got
nerves that are tolerably steady, so I won't show any wonder at your
taking this meeting so coolly; but it's kind of unexpected. You've
drifted a long way out of your latitude to be floating along Back Load
Trail. What's wrong in the East? Are the fools all dead, are the geese
not worth the plucking, have the sheep come short in the wool crop,
that you come here? Or are you in the stream that sets to the gold-
diggings?"
"Bah, don't talk to me about the fools, geese and sheep that I've left
behind me! Tell me how it is here. You and I used to understand
each other pretty well, ay, and each other's secrets; so, come now;
what's the best news in this heaven-forsaken region. Dick Martin
doesn't locate here for nothing."
"No, he ain't located here for nothing; you're right. That something
happens to be necessity. My luck in my little speculations ran out
first, and I had to leave. As to what I'm doing here—that's not to be
talked about. Maybe prospecting for gold; maybe Injun trading;
maybe putting daylight through stray travelers and vamoosing with
their traps; maybe any or all of these things—but not likely. I ain't
here for nothing. That's all I can say."
"Martin, we have done business together many a time; we were
allies, if not friends, and I want to know how the case stands now. I
don't want to pry and peer into your private affairs. Maybe I'd be
bringing something to the light that wouldn't stand it so well; but, I've
heard somewhat of you as I came in this direction. Of course I didn't
know it was you I heard the talk about, and of course there is a
chance of what I heard being either true or false, with a little extra
weight on the truth. You remember how we separated, and I don't
think you have any thing to complain of, or any charges of ill faith on
my part to bring against me. Now, the question I want to ask is: Can
we rely on each other as we could of old? A plain yes or no will make
the best answer to the question."
"Well, Endicott, I haven't heard of you particularly, either good or
bad, though I had an intimation that you were in the neighborhood. It
makes no difference what reports have gone trailing toward the East,
and I don't claim to know them; they're bad enough, no doubt. You
ask me a question, and if you must have an answer, why all I can
say, is: In some things, yes, in other things, no! Will that suit you, or
shall I go ahead and explain?"
"What do you mean by yes?"
"I mean that, in the first place, I would rely on you just as much as I
ever did, and not a particle more. In the second, whatever you get
my word to, that you can depend on my carrying through; but if you
think to find me ready to promise to any and every mad scheme, you
are very much mistaken."
"Any thing that is honest, eh?"
A grim smile flitted over Martin's face at the mention of the word
honest. It was gone in a moment though, and he proceeded:
"Yes, any thing that's honest. Now what is it that you have to
propose? I don't suppose you would have made so much of an
introductory if you had not had something behind it."
"You are partly right. My motto is business first and pleasure
afterward, else I would have had a thousand things to say with
regard to our mutual lives in the past few years. Yet I hardly know
what I would say. I did not seek you; yet, since I have met you, I
want to know if I can count upon your assistance in a little matter
which, springing up suddenly, has found me unprepared to meet it."
"Then you didn't hunt up Back Load Trail for any special reason?"
"No, indeed! It is just my lucky chance. The party I am with are
camped half a mile over yonder. I left them for no very definable
reason, and thereby met with an adventure that may have a great
influence on my actions, perhaps on my whole future life. When we
camped over there by the side of the stream, I thought it was but for
the night, now I may linger in this neighborhood for a day or so. The
question is, if I need a friend will you stand behind me?"
"What's this adventure, and how do you want me to stand behind
you? If what I think is true, you may have more need of it than you
think for."
"Well, Martin, I scarce know in what manner I would have you aid
me; perhaps after all only by a neutrality. As to the adventure—I met
with a woman."
There seemed to be nothing either astonishing or disconcerting in
this revelation. After waiting in unbroken silence for any remarks that
Martin might feel inclined to make, Endicott proceeded:
"It was rather strange for a man to ride out of camp with no aim or
object and to stumble upon a woman; stranger, too, when that
woman chanced to be one whom you had known long before, and
for whom you had been long searching and in vain. I do not know
what may come of it; but I know what I want to. How is it? There is
no one of our little party that I care to trust—if I need assistance
within the next twenty-four hours will you give it, and where can I find
you?"
Martin looked up slowly and deliberately.
"It seems to me you're putting things on their old basis, what one of
us plans the other is to help carry through."
"Why not? Neither you nor I have grown what the world calls better
since then, and of course the understanding would be now as it
always was—nothing for nothing, all for whatever pays."
"No, I don't suppose we have grown much better; but there may
have been a few changes. As to the woman you speak of, here is all
I have to say. If you have any plans and can carry them out openly
and above board, no force, no underhanded means, no fraud, I'll not
lay a straw in your way; maybe I can help you."
"If not?"
"This. Just you attempt the slightest bit of compulsion, or the first
grain of trickery—try any thing that's not honest, make a move
toward abduction, or take a step toward foul play, and I'll lay you
dead in your tracks."
"What do you mean?"
"I mean what I say. I give you fair leave and fair warning, too. I don't
intend to interfere in any thing she wishes to do, but I mean she shall
not do what she doesn't want to do."
"Do you mean to say that you will exert any control over her
actions?"
"Yes, just so far as to let her have her own will. She's one of the few
persons that I have cared for, and when time stops and the sea gives
up its dead, you may, perhaps, see me go back on my dead sister's
daughter."

CHAPTER IV.
BILL BLAZE, THE "SNOLLIGOSTER."
At the very edge of the camp-fire lay two men, mutually clutching
each other, although hostile operations seemed, for the nonce, to
have been suspended. So near to the fire were they that one of
them, without relaxing his hold, had been able to give a log thereon a
rousing kick which had caused the light to flare up, thus enabling him
to obtain a fair view of the other. As Harry Winkle staggered into the
circle of light the two men loosened their grips, and with deliberation
rose to their feet, one of them returning to its sheath a knife, the
other dropping to the ground a hatchet.
"A'mitey Moses, but yer kim neah gittin' a crack across yer skull.
What yer want to steal dat hoss fur—eh?"
"Pompey, there war a nigger nigh onto goin' under about two minnits
ago, an' so yer had better not be axing fool's questions. How d'yer
s'pose I knowed whose hoss that war? The durned red niggers
cleaned me out, root an' branch, 'bout a week ago, an' cum clost to
rizin' my ha'r. I've bin trampin' on the back trace, an' when I cum
acrost a animile handy I wouldn't 'a' bin Bill Blaze ef I hadn't gone fur
him—'special arter what I met to-night. What yer doin' here? Last
time I see'd yer yer war on the Big Red with Cap. Le Compte."
"Hi! You t'ink so! Somebody mite 'a' bin hurt ef I hadn't'a' knowed it
was you when you talk; but dunno 'bout it's bein' dis chile. I's not bin
with dem Hudson Bay fellers sence dat winter when you got so bad
bit up wid dat grizzly. I's on my own hook now, an' takin' care o'
Mass'r Winkle. An' bress my soul, dar he am now!"
The speaker, who was an African of the unmitigated breed, caught
sight of Winkle standing upon the opposite side of the fire.
"Mass'r, dis yere am Mister Bill Blaze. I knows 'um well, an' he's a
fust-rate feller, ef he war a-goin' fur yer hoss. Nussed him up when
he war tore all into leetle bits."
Winkle appeared to be somewhat recalled to life by this address of
his sable attendant; and turning, looked the man thus recommended
full in the face.
Blaze, once introduced, did not stand upon ceremony; but advanced
across the intervening space, extending his hand as he walked.
"Yes siree, I'm that identikle individool, Bill Blaze, jist frum the
mountings! I kin trap more beaver, eat more buffler, steal more hoss-
flesh an' raise more top-knots than any man frum here to the
Columby River. I'm a blarsted bulldorg an' a high-heeled snolligoster.
I kin lick my weight in b'ar's meat, an' my name's Bill Blaze. Waugh!"
"I've heard that name before," said Winkle, taking the offered hand,
"and you're welcome. I'm a little abroad just now, and don't feel like
my own self—for I've seen a ghost."
"Thunder! You look kinder skeery; but ghosts ain't nothin'. I've seen
more ghosts than any man a-trampin'. Had 'em for pards onc't. Fact.
Three on 'em an' myself camped in a shanty down on Black-horn
Lick fur nigh onto a month. There war a woman with her throat cut,
an' a half-breed with his brains stove in, an' his skulp a-danglin'
ahind, an' a black b'ar with his back bruk. The way they tore around
that 'ere shanty war nasty. Why, down thar on that thar Lick, ghosts
war as plenty as ha'rs in yer head. An' yell? The catamounts got so
'shamed of their own mule music they packed their trapsacks an' got.
Yer couldn't find a painter nigher ner fifty mile. No, stranger; don't talk
to Bill Blaze about ghosts, fur he's bin thar!"
Winkle appeared to be little moved by this address. His face still bore
marks of evident perturbation, and there was an absence of mind
depicted in his manner and actions that seemed to strike Blaze as
rather unwarranted. To some remark made he answered rather
shortly; but he accepted of the hospitalities offered him, so far at
least as to seat himself by the fire, and, in default of other
entertainment, entertained himself by the sound of his own voice.
"No, ghosts don't bother this hyar hoss. Nor red-skins nor grizzlies
neither. I kin trap more beaver, kill more b'ar, shoot straighter, run
quicker, jump further, lie faster, stampede more animiles, an' carry
more pelts than any bloody bulldorg ever invented. But, I'm the man
without luck. I've wrastled with the old boy fur thirty years; he's got
an under holt on me; but, I'm dead game, I am! Luck or no luck, I'll
hang like seventeen pair o' tongs and a last inch gamecock. Waugh!"
The negro listened to these announcements, if Winkle did not. He
was accustomed to this style of thing and had heard Blaze before.
"Mass'r Blaze, 'pears to me de bad luck ain't so mitey bad; I's t'inkin
it's toder way cl'ar. Any odder man 'ud bin gone under—dun gone
suah—ef he'd had de half what you's had to go tru. You's allers a-
sayin' you's nary luck, an' allers a-gittin inter de w'ustest kind o'
skrimdigers—an' still you am heah. What's de trouble now?"
"Wal, Pomp, I allow it's no luck as pulls me through, but just pure grit
and muskle in this huyer hoss. I war camped out in a bully old spot
last week; meat plenty, beaver to be had for the taken of 'em, and
every thing going along on a string. Didn't think thar was Injin within
twenty mile, an', blast me, ef they didn't cum down an' clear us out
quicker than the jerk of a dead deer's tail. Bob Short an' I war thar
together, you see, an' Bob struck all right, but they got my old sorrel
mare, an' all our provender, an' I just cum down from them are
mountings after a chase o' four days, poorer ner Job's turkey, an'
nothen left me but Slicer an' this huyer old shootin'-iron. An' this
huyer very blessed night, as I were movin' along promisc'us, thar war
a rifle-ball went sizz a-past my head-piece, ad' I squatted an' see'd
two men a talkin', an' found that thar bit o' lead warn't meant fur me
an' while I war a-listenin', sock cum somethin' right acrost me, an'
hove a yell wuss ner forty catamounts fitin' in a small box. I know'd it
war a copper-belly an' clinched. We hed it, pull an' hug a bit, an' then
I got Slicer out. That thar red-skin won't cum a-pryin' an' a-peerin'
down along Back Load Trace soon ag'in. Nary; not much; waugh!"
The story of the trapper began to interest Winkle; he thought less
and less of the ghost; he descended from the clouds and listened
with earnestness to what the man was saying. He thought of the
corpse that Martin and he had seen drifting down the stream, and
believed that the Indian would not come prying and peering in that
neighborhood soon again. Perhaps, too, this man might be of service
to him? At any rate it would do no harm to meet him cordially.
"Then you are the man who had the tussle over there with an
Indian? I heard the yell, saw him shoot into the stream, and went
across to see what it was about. I was following your trail, when I
came across a sight, or rather a sight came across me, that
unhinged my nerves. But, how came the difficulty with the Indian?
What was he doing there? Is there danger from others that should be
specially guarded against?"
"Yes, siree, I'm the man! The diffikilty perobably arove from his not
keepin' both eyes peeled. He was so bent on hearin' that he couldn't
take time to see, an' tumbled onto a hornet's nest. He clinched right
in then by instink, an' as it war die dorg er eat the hatchet, I hed to let
it inte him, though I'd as ruther not. What he was a-doin' I dunno.
Injin deviltry are various. Thar oughtn't to be a red-skin within fifty
miles o' huyer. Thar may be a couple more on 'em or thar mayn't.
What they'd be arter I can't say. Martin ought to know'd ef thar war
any, an' I guess he's got his men out by this time a-lookin'."
"It will be best then to keep a bright look-out?"
"'Twouldn't be onsensible. Leastwise, though I don't think thar's
much danger, it won't hurt to keep one eye open, for I've found it
don't altogether gee right to be too confiding in this section with
anybody—white er red. I'd advise it. I'd advise it, partickler, arter the
talk I heard between you an' Martin. You see, I hain't any doubt but
what yer a good man an' a game man; but, supposin' he was to tell it
to some o' his cronies around here, an' one on 'em should be the
man yer after—I wouldn't put it a-past 'em to slip in here an' slide a
few inch o' steel in somewhar nigh yer jug'lar."
Winkle meditated some little time before he responded; then his
words dropped out slowly and distinctly.
"I am safe from any thing in that shape. It is no mere bravado on my
part when I say so, but a belief so settled that it must be true. I bear
a charmed life while that one other man lives. I have passed through
all straits during the past three years, and from desperate
encounters have come forth unharmed; from beds of deadly
sickness have come up sound and well. I have changed in that time
wonderfully, and the change was not for naught. I do most firmly
believe that destiny has something in store for me; till to-night I
thought I knew what it was. Now I am uncertain; but that it is
something more than a stab in the back or a chance shot in the
melée of a night attack I have no doubt."
"That's all right. I only give my 'pinion on the matter, seein' as may be
I've tramped around here ruther more nor you hev. Jest keep yer
weather eye open—you an' Pomp here is all I mean. And ef any
thing should turn up while I'm in shooting distance, yer kin kalkerlate
that Bill Blaze'll give yer a hint on it."
"Well, well," responded Winkle, "I am not likely to have much
dealings with any one hereabouts; but I begin to think my intentions
have deceived me. I have been lingering in this neighborhood for
several days; but I will do so no longer. To-morrow I will move on
westward—and perhaps, if you have nothing better, you could find it
to your interest to go along."
"That's my identikle name—Moovin'-west Blaze. But I'm steerin' in
toward the settlements to see if thar's anybody sich a blarsted fool
as to trust me fur an outfit. The season's jist commencing, an' ef I
hev any thing like nateral luck I kin pay 'em back when I cum in ag'in
and hev a few pelts in my sack."
"I can arrange that matter, I think," responded Winkle. "I have an
extra horse, and, in fact, nearly every thing you need. I was going on
to the trapping-grounds. Suppose you remain with me a couple days,
and if nothing turns up I will leave this region. If I should, however,
accomplish any of my aims, you shall have what you need anyhow."
"Durn my Trojan! I'm your man. I kin put in a week here, easy. Hev
yer seen Martin's head-quarters yit? If yer hevn't yer ought to call in
on him."
"No; I didn't know that I was so near to it. I have been near here for
some days—within ten or twelve miles perhaps—but I only came into
camp here to-night."
"Yer must go in then. Some on en 'em nosed ye out long ago, an' if
yer don't they may come playin' tricks on yer without sayin' any thing
to Dick. Maybe ye kin git some hints of what yer arter down thar."
"You are right. It may be as well to look a little in that direction. I've
hardly been systematic in my plan of procedure. That comes,
though, of trusting to chance and drifting in the direction Fate seems
to call me. And, by the way, are there any females with the party?"
"Wal, to-morrer morning early will be time enuff to talk it over. I'm
goin' to turn in now and git a snooze. I've had a blarsted long tramp
to-day, and them legs o' mine ain't exackly a steam injine—though,"
by way of a saving clause, and to prevent the idea of any derogatory
admission, "I'm a bloody, blarsted bull-dog and a high-heeled
snolligoster on wheels."
To make arrangements for the night occupied but a short time; and
soon, wrapped in a blanket of Winkle's, Blaze was wooing
 "Sleep that knits up the raveled sleeve of care,
The death of each day's life, sore labor's bath,
Chief nourisher in life's feast,"

while silence and darkness reigned around.

CHAPTER V.
THE SCREAM AT NIGHT.
How long Blaze had been slumbering he could scarcely have even
guessed; but suddenly, and without any assignable cause, he found
himself wide awake. He looked around; he listened. He saw nothing
but dim shadows, heard nothing but the regular breathing of the two
sleepers by his side. Yet his first thought was of danger. He was
accustomed to premonitions. Men who live in an atmosphere of peril
meet with them, understand them, act on them.
He leisurely and thoughtfully unrolled himself from his blanket and
arose to his feet. "Most durn queer," he soliloquized, turning his eyes
in every direction. "This old hoss's narves must be gittin' weak, er
thar's sumthin' wrong a-brewin'. Don't often feel this here way; last
time I did was t'other night, when the copper-bellies was a-cumin' in
onto us without words er warnin'. I'll jist scout around a bit, an' see if
enny thing's broke loose."
Taking his rifle with him, the trapper noiselessly stole away from the
vicinity. He moved around the camp in a gradually increasing circle,
pausing but once in his pace, and that was when he was opposite to
the point where he believed Martin's cabin lay. Full ten minutes
passed, when he heard footsteps and the voices of men engaged in
conversation. Sinking upon the ground at the foot of the tree by
which he was standing, Blaze watched and waited.
Both men were strangers to him; but one of them already has been
introduced to the reader, under the name of Endicott. He had had
time to leave Martin and meet with another man, who seemed a
friend; and to him was imparting information, both as to what had
already occurred that night in the vicinity of Back Load Trace, and as
to what might occur. His words, that spoke of violence and treachery,
appeared to fall upon sympathizing ears. As they drew nearer, all the
time becoming more deeply interested in their conversation, Blaze
gave a start of surprise and recognition; he crouched closely in the
shadow and listened with redoubled interest.
Charles Endicott has been already described, and his companion
merits notice. He, too, differed in something from the class of men
one naturally expects to find on the very outer verge of semi-
civilization. He was a man of perhaps thirty-five years of age, of
medium hight. He walked with a steady, stealthy, cat-like pace, his
head, for the most part, bent down; but now and then it was lifted,
and he cast a sharp, steady gaze around him. The features were
firmly cut, the eyes were steady; yet an undescribable something
seemed to be shifting across his face, which would say to a stranger:
Beware of Eben Rothven!
"Yes, Eben, it does make a change in the programme, I'll admit, but,
it's a change to the advantage of both. Don't you see that?"
"I see that we waste here a couple of weeks, and no one knows
what the end of it all will be. You can't count on a woman, and
especially such a woman as you say this is. Break them down
physically and mentally, trample the life out of them, and then they'll
rise again. Out of a wreck that, were it of manhood, would founder
with the first breath of wind, will rise again a good stout ship. You
think you can waken the old dream in her, do you? Why, man, I'm
surprised at you! The deadest thing on the earth is a dead love, and
there is no mending a broken idol. Take my advice and let her go.
She will be a burden that will sink us both. We are on the trail to
fortune now; don't let us lose it, or fly wild at the first scent that
crosses it."
"You're welcome to your philosophy about dead idols and the like;
welcome to shake your head and prophesy; but, what I want is your
help. Of course I will get it in some shape or other; but, I prefer it to
be freely and enthusiastically given."
"How much does my help enter into your calculations? I tell you
frankly that I am none of your dashing adventurers, ready to ride into
Martin's camp of Free Trappers. So far as a word of advice and a
sacrifice of time goes, you may count on me; but, don't expect me to
stand behind you, to assist in any mad experiment you see proper to
try."
"My 'count' is upon your services as a Reverend—a title and
authority that, as far as you and I know, is still legitimately borne. I
want to use you; a piece of joinery of your handiwork will last for all
time. I can not believe that the cause by fair means is hopeless, and
shall try them first; after that, why, there are a few stout hands and
bold heads at our back, and we must e'en make the most of our
stock in trade. To be sure, we are on the road toward fortune in other
directions; but this is a certainty. The woman is worth her weight in
gold, almost; and, besides, it's no new dream with me. It's not so
many years since she was an idol of mine."
"Yes, I've heard of it—and I think, too, that you handled it—or would
have handled it—not over tenderly. Do you think she would forgive
that?"
"That was no fault of mine. I would have done better if the fates had
let me; but they were against me. What could I do, hedged in as I
was? If I could have sunk my past record, and stood out a new man,
I'd not have let 'e'en the winds of heaven visit her face too roughly.'
Perhaps I've got colder and harder since then; but, if so, I think my
tongue can move as glibly and smoothly as ever, and there are fair
excuses to be made for all that was seemingly wrong in the past."
"There is a limit, you may find, to human credulity. You can not wash
out the recollections of the past. Do you think it was any light cause
that drove her out of the world, out of society, refinement, and all that
women of her stamp hold dear? Every day she has spent here,
every rude face and lonely hour that she has seen or felt has cried
out against you. Why, man, you murdered her name, and that is a
crime no woman could ever forgive."
Endicott was silent a moment before the impressiveness of his
companion. Then, by an effort, he broke into a short laugh: "'Is Saul
also among the prophets?' Since when has Eben Rothven set
himself up as a judge of the workings of the human soul? Of course,
what you say may be true as holy writ. But what of it? Fair means or
foul—I don't mince matters. This is no new plan of mine, and so,
when opportunity comes, I can decide on my course quickly. Delay
never makes a man. She knows nothing of the financial aspect of the
affair, even now; while I did, years before it was revealed to the
world, or to those who chose to notice. The time for action has come.
Are you with me?"
The man called Rothven hesitated a moment, as if weighing the
matter in his mind; then answered simply: "I am."
"Come on, then," and the two left the spot.
Much of this conversation was Greek to Blaze, but, somehow, he got
it in his head that it related to his new-made friend, Harry Winkle. He
seated himself leisurely against the tree to think it all over. Both
these conspirators were strangers to him, they did not belong to
Martin's men; who were they? He might perhaps have learned more
as to that by following them, but he neglected to do so. And,
pondering over the thing, he must have fallen asleep, for
consciousness faded away. For how long, he could not at once,
perhaps, have told, but he came back to life with a sudden shock,
that brought him upon his feet like the thrill of a strong galvanic
battery. He was wakened by a woman's scream, long, shrill, cutting
into and through his ears like an Indian's death-wail.
He listened to catch it again, but it was not repeated. For a moment
all was silence; then he heard the steady beat of horses' hoofs
stretching away at fullest gallop, and then, the sharp, quick report of
a rifle. He heard the footsteps coming nearer and nearer, and he
crouched in the shadow of the tree, with his hand upon the lock of
his weapon, almost nervously waiting for whatever might follow.
Suddenly he felt a hand laid upon his shoulder. He started, and
turned with a quick motion of offense. It was Winkle, rifle in hand.
The moonlight fell past the tree full upon his face, on which was an
excited if not a wild look.
"Am I crazy to-night? or did you hear it, too? I've seen a ghost this
night, and now, again, I heard it scream for help. What was it,
Blaze?"
This he hurriedly asked.
"If yer a lunatic there's a pair on 'em, fur I heard it too. Lay low here a
minnit, an you'll see some more on it."
The hoof-beats sounded nearer; they swept on and on toward them.
Then three horses emerged from the trees out into the light, and
neared the spot where the two men were concealed.
"Is it he?" whispered Winkle, hissing the words out between his
clenched teeth, and with a sharp click the hammer of his rifle went
back.
But Blaze, quickly reaching back, seized his arm.
"Hold hard, there's more ner he thar."
The horsemen raced by like a tornado. It was a party of Blackfeet!
And across the saddle-bow of the savage nearest to Blaze, was
flung, or held, the form of a woman! In a moment Winkle's eye had
caught sight of that which Blaze had perceived—the woman. For a
moment he seemed to lose all control of himself, all power for action.
Just one glimpse of a white, wild face, and a hand clutching fiercely.
"Did you see it—did you see it?" he asked.
"Yes! I seen it! They've just went an' gone an' done it. Thar's grit in
the red-skins, thar are. But you'll be able to see another corpse
along Back Load Trail afore many hours. Dick Martin will be behind
'em in the shake of a buck's tail—Hello! What's bu'sted?"
The man by his side had sunk, stiff and motionless, upon the grass.
"Blast my tail-feather, ef the young cuss hain't fainted. Thar must be
somethin' wrong in the upper story, sure!"
 CHAPTER VI.
A DOUBLE TRAIL.
On the prairie, alone by moonlight, there is a lonesome solemnity
that startles, appalls. Look in one direction. For miles and miles there
stretches away a tract of rolling land where the grass grows, the
buffaloes graze, the coyotes howl, but no human form can be seen,
no tree waving—a loneliness of nature that you think must somehow
of necessity be interminable. Turn and look in another. Down from
the tableland there stretches a long, grassy slope, where the foliage
is more than ordinarily luxuriant, and at the foot of the declivity is the
long line of timber which marks the course of some stream. There
the broad elm flourishes, the lofty cottonwood shoots upward, and
the white sycamore trees stand gleaming ghostlike under the mellow
moonlight. Perhaps, further away to the left, where the rich bottom is
broken by rising ridges of rocky bluffs, you see the gloomy spread of
the cedar tree reaching upward its dismal-looking arms. Wherever
the rolling prairie-fires have been unable to sweep, there you see the
shade of timber and bush; everywhere else is the blue and red stem,
the blue and bunch-grass or the short, crisp buffalo-grass; and far off
in the distance, with a quiet grandeur of its own, you see the trace-
line of the mountain range.
Some such grand and lonely scene would the reader have noted had
he been standing in some favorable position on the high prairie near
Back Load Trace, a few moments before the occurrence of the
incidents just detailed.
It can well be imagined that Blaze was not the only one startled into
action by the occurrences of the night. The shot, by one of Dick
Martin's men on guard, aroused the Free Trappers, and also caused
Charles Endicott and his companions the keenest alarm. Had their
destined prey been seized by other human wolves? If so—who were
those wolves?
As for Blaze he lost but little time. Almost Herculean in strength, he
gathered on one arm the two rifles, while with the other he bore
Harry toward the camp. On the way he met the negro, who relieved
him of the rifles, and, upon reaching the side of the now smoldering
camp-fire, produced a bottle of spirits and a canteen of water.
It was but a short time until consciousness returned to the fainting
man. He opened his eyes, raised himself, sat upright, looked Blaze
full in the face.
"You saw it all, did you? Now tell me, who was that woman?"
"That bit o' caliker, mister, tho' I dunno as I ever seen it afore, war
most likely a woman that Dick Martin claims a sort o' relationship to,
an' she's bin livin' round hyar fur some considerable time. Frum yer
ackshuns I'd think yer must hev hed a priur morgidge on it, an', ef so,
ye'd better be up an' stirrin', fur by the mitey the durned Blackfoot is
goin' to foreclose."
"Ready, quick, quick," was Winkle's terse answer, looking from one
man to the other. Then he turned, and burying his face in his hands
lay stretched for a moment prone. When he sprung to his feet there
was a new light in his eye, and redoubled strength in his arm. He
vaulted into his saddle, gathered up his reins, and turning to Blaze,
in a firm-set whisper, muttered:
"Lead on—to life or death—but I must see her again."
So, fully armed and fairly equipped, the three men rode out from
under the shadows and cast themselves, with clenched teeth and
iron will, upon the trail. All this took but a few moments to
accomplish, since the three men had within them, each separately,
the highest development of trained sagacity.
As they came out upon the prairie, Blaze took a sweeping glance
around him, as though he would fain impress upon his mind every
minutiæ of the lay of the country.
"Dog-gone the'r hides, thar's just two routes for 'em, an' on'y two, to
take, an' ef I know'd which one it war it's cussed leetle trailin' I'd do
to-night. In this yere leetle game it takes too much eye-pullin' to run
nose-down. It ain't accordin' to reason to s'pose we won't hev to look
out fur all the cussed red-skin tricks ever invented. They've got one
on me a'ready due, so ef I don't squar' with 'em afore beaver-pelts is
prime, I hope I may never tote a trapsack, er p'izen a buffler-wolf
ag'in."
This was said more in the manner of a soliloquy than of a direct
address; in fact, it is doubtful if either of the others could have heard
his low-toned words. Winkle meant work; and so, for the present,
thought little of speaking or of listening. Blaze meant work, too; but,
talk to him was second nature, and when there were no ears open to
hear he would rather press his own into service than, no pressing
emergency demanding it, keep silent. Having a full twenty minutes
start, they reached the spot where Martin and men had first been at
fault long in advance of those worthies, and, as they had not a third
trail to confuse them, and perhaps being more trail-wise, Bill did not
have to spend many minutes in finding the tracks left by the two
parties of Indians.
"One on each route, by mitey! Now, which to foller?"
He gave both the benefit of a close scouting. On the one leading to
the right he found the imprint of a horse's hoof which he recognized
as having been with the abductors. He noticed, too, that one was
double laden. After a bit he came upon some shreds of a woman's
dress. He showed these marks to Winkle, being careful, for the
benefit of Martin, whom he shrewdly suspected would follow hard
after, to leave them untouched. Harry's heart bounded more
buoyantly at sight of these indications, and Blaze took one more look
around him before all three dashed on with redoubled energy. But,
as the trail at length lay before them plain and undisguised, Blaze's
enthusiasm suddenly fell away down below zero. From time to time
he glanced at it and at length reined in his horse.
"Dog-gone my knock-kneed tail-feather!" he exclaimed, "I ain't fit to
lead blind rabbits to water!"
Winkle looked at him in astonishment.
"What is the matter now? Why do you halt?"
But Blaze paid but little attention to his query.
"What a gaul-blasted fool this hyar old hoss are. Tuk right in the fust
pop by a bit o' baby-play. Can't yer see? That gal couldn't a-tore
them bits off o' her dress. It stan's to reason not, sure. Why, cuss
'em, thar's two Injuns ridin' double here, dead shot. I thort it was too
soft a thing. That led hoss in t'other party is the one ez has the gal
on. Jist seen it in time. I'd gamble high thar's ez purty a leetle
hornets' nest a-hangin' under the fust bit o' timber we'd come to, ez
you'll find frum hyar to the Big Red."
How this suggestion was received may well be imagined.
"What are we to do then?" queried Harry. "Must we go all the way
back and start fresh on the other trail?"
"Wal, not quite that bad; but, somewheres blamed nigh. Change my
hind-sights, ef they ain't a-strikin' fur Crooked Cañon, full drive—
we're goin', from the taste I've had of the hosses, to be jist a leetle
too late to see 'em git under kiver."
"You think we can find them yet, though?"
"Think! I know it. Thar ain't no trouble about that; thar's only two
trails, an' like a blarsted green purp I've bin a-barkin' up the wrong
one."
"Then the sooner we look for the right one, the better."
"That's so, only it's provokin' to hev bin losin' all this time. Come on
now, an ef ever an arrer went straight—an' the copper-skins kin sling
'em nasty, I kin take yer to the spot whar they're headin' fur to-night.
I've bin ham-strung an' sot down on, which ain't very lively fur the
boys!"
Without more hesitation or further parley, Blaze turned to the left and
led off at a rate which he judged best suited to continued effort. Not
for a long time did he utter a word. But when the silence had begun
to be monotonous, he broke it by bringing his hand down with
violence upon his thigh, exclaiming:
"Cussed ef sand-paper ain't slick as grease along side o' this streak
o' roughness. Won't some one draw a bead on me afore I get my
ha'r cut fur nuthin'?"
"Why, what is the trouble now? I hope we are not at fault again?"
anxiously remarked Winkle.