This chapter contains topics related to matrices with special structures that arise in many applications. It discusses companion matrices that are a classic linear algebra topic. It constructs circulant matrices from a particular companion matrix and describes their signal processing applications. It discusses the closely related family of Toeplitz matrices. It describes the power iteration that is used later in the chapter for Markov chains. It discusses nonnegative matrices and their relationships to graphs, leading to the analysis of Markov chains. The chapter ends with two applications: Google’s PageRank method and spectral clustering using graph Laplacians.

Chapter 6 starts out with a physics motivation, as well as a mathematical statement of the problems that will be tackled in later sections. First, polynomial interpolation is carried out using both the monomial basis and the Lagrange-interpolation formalism, sped up via the barycentric formula. This includes a derivation of the error and an emphasis on using unequally spaced points (Chebyshev nodes). Second, cubic-spline interpolation is introduced. Third, a section is dedicated to trigonometric interpolation, carefully working through the conventions and formalism needed to implement one of the most successful algorithms ever, the fast Fourier transform (FFT). Fourth, the topic of linear least-squares fitting is tackled, including the general formalism of the normal equations. The second edition includes a substantive new section on statistical inference, covering both frequentist and Bayesian approaches to linear regression. Nonlinear least-squares fitting is covered next, including the Gauss-Newton method and artificial neural networks. The chapter is rounded out by a physics project, on the experimental verification of the Stefan-Boltzmann law, and a problem set. In addition to providing a historical background on black-body radiation, the physics project shows an example of nonlinear least-squares fitting.

Periodic differential equations and their approximation are the topic of this chapter. We discuss the application of classical finite difference schemes and their analysis in this setting. The spectral Galerkin method, that is, using trigonometric polynomials as basis is then discussed and we show its spectral accuracy. Finally the pseudo-spectral method is presented, its implementation via the DFT is discussed.

In this chapter we study finite difference schemes for parabolic partial differential equations. The notions of conditional and unconditional stability, and CFL condition are introduced to analyze the classical schemes for the heat equation. Different techniques, like maximum principles and energy arguments are presented to obtain stability in different norms. Then, we turn to the study of the pure initial value problem, the grand goal being to discuss the von Neumann stability analysis. To accomplish this we introduce the notions of Fourier-Z transform of grid functions and the symbol of a finite difference scheme. This allows us to state the von Neumann stability condition and prove that it is necessary and sufficient for stability. These notions are also used to present a covergence analysis that is somewhat different than the one presented in previous sections.

This chapter introduces the fast Fourier Transform (FFT) for discrete Fourier Transform, beginning with the discretization of the Fourier Transform to its digital expression with constant time intervals. When the integral in Fourier Transform is replaced by a summation, the continuous Fourier Transform is changed to discrete. The discrete Fourier Transform and its inverse are exact relations. An example of the discrete Fourier Transform is discussed for a simple rectangular window function which results in the sinc function, useful for the interpretation of finite sampling effect. A technique of zero-padding is introduced with the discrete Fourier Transform for better visualization of the spectrum. But the computation of discrete Fourier Transform of a long time series can be quite “labor intensive” or costly in computer time with a direct computation. However, since the base functions are periodic, a direct computation can have many duplications in multiplications of terms. Algorithms can be designed to reduce the duplications so that the speed of computation is increased. The reduction of duplicated computations can be repeatedly done through an FFT algorithm. In MATLAB, this is done by a simple command fft. The efficiency of FFT is discussed.

This chapter discusses the transition between Fourier series and Fourier Transform, which is the tool for spectrum analysis. Generally, the use of linearly independent base functions allows a wide range of linear regression models that work in a least square sense such that the total error squared is minimized in finding the coefficients of the base functions. A special case is sinusoidal functions based on a fundamental frequency and all its harmonics up to infinity. This leads to the Fourier series for periodic functions. In this chapter, we start from the original Fourier series expression and convert the sinusoidal base functions to exponential functions. We can then consider the limit when the length of the function and the period of the original function approach infinity (so that the fundamental frequency approaches 0, including aperiodic functions), leading to the Fourier integral and Fourier Transform. We can then define the inverse Fourier Transform and establish the relationship between the coefficients of Fourier series and the discrete form Fourier Transform. All these are preparations for the fast Fourier Transform (FFT), an efficient algorithm of computation of the discrete Fourier Transform that is widely used in data analysis for oceanography and other applications.

This chapter introduces the power spectrum. The power spectrum is the Fourier Transform of the autocovariance function, and the autocovariance function is the (inverse) Fourier Transform of the power spectrum. As such, the power spectrum and autocovariance function offer two complementary but mathematically equivalent descriptions of a stochastic process. The power spectrum quantifies how variance is distributed over frequencies and is useful for identifying periodic behavior in time series. The discrete Fourier transform of a time series can be summarized in a periodogram, which provides a starting point for estimating power spectra. Estimation of the power spectrum can be counterintuitive because the uncertainty in periodogram elements does not decrease with increasing sample size. To reduce uncertainty, periodogram estimates are averaged over a frequency interval called the bandwidth. Trends and discontinuities in time series can lead to similar low-frequency structure despite very different temporal characteristics. Spectral analysis provides a particularly insightful way to understand the behavior of linear filters.

This chapter can be used as a six week “lab" component to a mathematical methods course, one section each week.The chapter is relatively self-contained, and consists of numerical methods that complement the analytic solutions found in the rest of the book.There are methods for solving ODE problems (both in initial and boundary value form) approximating integrals, and finding roots.There is also a discussion of the eigenvalue problem in the context of approximate solutions in quantum mechanics and a section on the discrete Fourier transform.