Heath - Scientific Computing (523150), страница 101

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 101)

.. ... ..  =  .. . .......   . ,z u···u1u0 un−1  vn−2 n−2n−2zn−1vn−1un−1···u2u1u0then the corresponding transformed sequences ẑ, û, and v̂ are related byû0 0 · · · · · ·0v̂0ẑ0 0 û1 0 ẑ1 ···0   v̂1  .  . .. .. .  ..  = n  ... . . . . . ...

 . . 0 · · · 0 û ẑ0   v̂n−2 n−2n−2ẑn−10 ··· ···0ûn−1v̂n−1For this reason, when computing the convolution of two sequences it is often advantageousto use the FFT algorithm to compute the DFT of each sequence, compute their pointwiseproduct in the frequency domain, then compute the inverse DFT to get back into the timedomain, again via the FFT algorithm.The FFT algorithm forms the basis for some exceptionally efficient methods for solvingcertain elliptic boundary value problems, such as Poisson’s equation on a regular domainwith periodic boundary conditions (see Section 11.4.2). It also provides a similarly efficientapproach for implementing spectral or pseudospectral methods for time-dependent partialdifferential equations with periodic boundary conditions.12.3.1Fast Polynomial MultiplicationThe FFT algorithm also provides a fast method for some computations that might notat first glance seem related to it. Consider, for example, the problem of multiplying twopolynomials p(t) and q(t), whose complexity by straightforward multiplication, using thecoefficients of the polynomials, is proportional to the product of their degrees.

Supposethat the product polynomial whose coefficients we wish to determine is of degree n − 1.A polynomial of degree n − 1 is uniquely determined by its values at n distinct points.Moreover, the value of the product polynomial at a particular point t is equal to the productof the factor polynomials at that point, i.e., (p · q)(t) = p(t)q(t). The product polynomialis therefore uniquely determined by the values of the pointwise product of p and q at ndistinct points.Thus, one way to compute the product polynomial is to evaluate p and q at n distinct points, compute their pointwise product, and then obtain the product polynomialby interpolation from these values.

Since the pointwise product requires<b>Текст обрезан, так как является слишком большим</b>.

Характеристики

Список файлов книги