A Fast Algorithm for the Evaluation of Legendre Expansions
A Fast Algorithm for the Evaluation of Legendre Expansions
复制标题
DOI：
10.1137/0912009
复制
发表时间：
1991-01
期刊：
影响因子：
--
通讯作者：
B. Alpert;V. Rokhlin
中科院分区：
文献类型：
--
作者：
B. Alpert;V. Rokhlin
给出了一种快速计算有限勒让德级数的值和系数的算法。给定一个n项勒让德展开，该算法在区间$[-1，1]$上的n个切比雪夫节点处产生其值，成本与$n\log n$成比例。类似地，给定函数f在n个切比雪夫节点处的值，该算法产生在这些节点处等于f的n - 1次多项式的n项勒让德展开。该算法的成本大约是长度为n的快速傅立叶变换的三倍，前提是计算执行到单精度精度。在双精度中，比率约为5.5。所采用的方法承认深远的推广，目前正在应用于其他几个问题。
An algorithm is presented for the rapid calculation of the values and coefficients of finite Legendre series. Given an n-term Legendre expansion, the algorithm produces its values at n Chebyshev nodes on the interval $[-1,1]$ for a cost proportional to $n\log n$. Similarly, given the valuesof a function f at n Chebyshev nodes, the algorithm produces the n-term Legendre expansion of the polynomial of degree $n - 1$ that is equal to f at these nodes. The cost of the algorithm is roughly three times that of the Fast Fourier Transform of length n, provided that calculations are performed to single precision accuracy. In double precision, the ratio is approximately 5.5.The method employed admits far-reaching generalizations and is currently being applied to several other problems.