1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Cardinal Trigonometric interpolation</title> 5<link rel="stylesheet" href="../math.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../index.html" title="Math Toolkit 2.12.0"> 8<link rel="up" href="../interpolation.html" title="Chapter 12. Interpolation"> 9<link rel="prev" href="catmull_rom.html" title="Catmull-Rom Splines"> 10<link rel="next" href="cubic_hermite.html" title="Cubic Hermite interpolation"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="catmull_rom.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../interpolation.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="cubic_hermite.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 27<a name="math_toolkit.cardinal_trigonometric"></a><a class="link" href="cardinal_trigonometric.html" title="Cardinal Trigonometric interpolation">Cardinal Trigonometric 28 interpolation</a> 29</h2></div></div></div> 30<h4> 31<a name="math_toolkit.cardinal_trigonometric.h0"></a> 32 <span class="phrase"><a name="math_toolkit.cardinal_trigonometric.synopsis"></a></span><a class="link" href="cardinal_trigonometric.html#math_toolkit.cardinal_trigonometric.synopsis">Synopsis</a> 33 </h4> 34<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">interpolators</span><span class="special">/</span><span class="identifier">cardinal_trigonometric</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 35 36<span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">interpolators</span> <span class="special">{</span> 37 38<span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">RandomAccessContainer</span><span class="special">></span> 39<span class="keyword">class</span> <span class="identifier">cardinal_trigonometric</span> 40<span class="special">{</span> 41<span class="keyword">public</span><span class="special">:</span> 42 <span class="identifier">cardinal_trigonometric</span><span class="special">(</span><span class="identifier">RandomAccessContainer</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">y</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">t0</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">h</span><span class="special">);</span> 43 44 <span class="identifier">Real</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">Real</span> <span class="identifier">t</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 45 46 <span class="identifier">Real</span> <span class="identifier">prime</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">t</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 47 48 <span class="identifier">Real</span> <span class="identifier">double_prime</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">t</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 49 50 <span class="identifier">Real</span> <span class="identifier">period</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> 51 52 <span class="identifier">Real</span> <span class="identifier">integrate</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> 53 54 <span class="identifier">Real</span> <span class="identifier">squared_l2</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> 55<span class="special">};</span> 56<span class="special">}}}</span> 57</pre> 58<h4> 59<a name="math_toolkit.cardinal_trigonometric.h1"></a> 60 <span class="phrase"><a name="math_toolkit.cardinal_trigonometric.cardinal_trigonometric_interpola"></a></span><a class="link" href="cardinal_trigonometric.html#math_toolkit.cardinal_trigonometric.cardinal_trigonometric_interpola">Cardinal 61 Trigonometric Interpolation</a> 62 </h4> 63<p> 64 The cardinal trigonometric interpolation problem takes uniformly spaced samples 65 <span class="emphasis"><em>y</em></span><sub>j</sub> of a periodic function <span class="emphasis"><em>f</em></span> defined 66 via <span class="emphasis"><em>y</em></span><sub><span class="emphasis"><em>j</em></span></sub> = <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>t</em></span><sub>0</sub> + 67 <span class="emphasis"><em>j</em></span> <span class="emphasis"><em>h</em></span>) and represents them as a linear 68 combination of sines and cosines. If the period of <span class="emphasis"><em>f</em></span> is 69 <span class="emphasis"><em>T</em></span>, and the number of data points is <span class="emphasis"><em>n = 2m</em></span> 70 or <span class="emphasis"><em>n = 2m+1</em></span>, we hope to have 71 </p> 72<p> 73 <span class="emphasis"><em>f</em></span>(<span class="emphasis"><em>t</em></span>) ≈ <span class="emphasis"><em>a</em></span><sub>0</sub>/2 74 + ∑<sub><span class="emphasis"><em>k</em></span> = 1</sub><sup><span class="emphasis"><em>m</em></span></sup> <span class="emphasis"><em>a</em></span><sub><span class="emphasis"><em>k</em></span></sub> cos(2π 75 <span class="emphasis"><em>k</em></span> (<span class="emphasis"><em>t</em></span>-<span class="emphasis"><em>t</em></span><sub>0</sub>) /T) 76 + <span class="emphasis"><em>b</em></span><sub><span class="emphasis"><em>k</em></span></sub> sin(2π <span class="emphasis"><em>k</em></span> 77 (<span class="emphasis"><em>t</em></span>-<span class="emphasis"><em>t</em></span><sub>0</sub>)/T) 78 </p> 79<p> 80 Convergence rates depend on the number of continuous derivatives of <span class="emphasis"><em>f</em></span>; 81 see either Atkinson or Kress for details. 82 </p> 83<p> 84 A simple use of this interpolator is shown below: 85 </p> 86<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 87<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">interpolators</span><span class="special">/</span><span class="identifier">cardinal_trigonometric</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 88<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">interpolators</span><span class="special">::</span><span class="identifier">cardinal_trigonometric</span><span class="special">;</span> 89<span class="special">...</span> 90<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span> <span class="identifier">v</span><span class="special">(</span><span class="number">17</span><span class="special">,</span> <span class="number">3.2</span><span class="special">);</span> 91<span class="keyword">auto</span> <span class="identifier">ct</span> <span class="special">=</span> <span class="identifier">cardinal_trigonometric</span><span class="special">(</span><span class="identifier">v</span><span class="special">,</span> <span class="comment">/*t0 = */</span> <span class="number">0.0</span><span class="special">,</span> <span class="comment">/* h = */</span> <span class="number">0.125</span><span class="special">);</span> 92<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"ct(1.3) = "</span> <span class="special"><<</span> <span class="identifier">ct</span><span class="special">(</span><span class="number">1.3</span><span class="special">)</span> <span class="special"><<</span> <span class="string">"\n"</span><span class="special">;</span> 93 94<span class="comment">// Derivative:</span> 95<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">ct</span><span class="special">.</span><span class="identifier">prime</span><span class="special">(</span><span class="number">1.2</span><span class="special">)</span> <span class="special"><<</span> <span class="string">"\n"</span><span class="special">;</span> 96<span class="comment">// Second derivative:</span> 97<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">ct</span><span class="special">.</span><span class="identifier">double_prime</span><span class="special">(</span><span class="number">1.2</span><span class="special">)</span> <span class="special"><<</span> <span class="string">"\n"</span><span class="special">;</span> 98</pre> 99<p> 100 The period is always given by <code class="computeroutput"><span class="identifier">v</span><span class="special">.</span><span class="identifier">size</span><span class="special">()*</span><span class="identifier">h</span></code>. Off-by-one errors are common in programming, 101 and hence if you wonder what this interpolator believes the period to be, you 102 can query it with the <code class="computeroutput"><span class="special">.</span><span class="identifier">period</span><span class="special">()</span></code> member function. 103 </p> 104<p> 105 In addition, the transform into the trigonometric basis gives a trivial way 106 to compute the integral of the function over a period; this is done via the 107 <code class="computeroutput"><span class="special">.</span><span class="identifier">integrate</span><span class="special">()</span></code> member function. Evaluation of the square 108 of the L<sup>2</sup> norm is trivial in this basis; it is computed by the <code class="computeroutput"><span class="special">.</span><span class="identifier">squared_l2</span><span class="special">()</span></code> member function. 109 </p> 110<p> 111 Below is a graph of a <span class="emphasis"><em>C</em></span><sup>∞</sup> bump function approximated 112 by trigonometric series. The graphs are visually indistinguishable at 20 samples. 113 </p> 114<p> 115 <span class="inlinemediaobject"><object type="image/svg+xml" data="../../graphs/fourier_bump.svg"></object></span> 116 </p> 117<h4> 118<a name="math_toolkit.cardinal_trigonometric.h2"></a> 119 <span class="phrase"><a name="math_toolkit.cardinal_trigonometric.caveats"></a></span><a class="link" href="cardinal_trigonometric.html#math_toolkit.cardinal_trigonometric.caveats">Caveats</a> 120 </h4> 121<p> 122 This routine depends on FFTW3, and hence will only compile in float, double, 123 long double, and quad precision, unlike the large bulk of the library which 124 is compatible with arbitrary precision arithmetic. The FFTW linker flags must 125 be added to the compile step, i.e., <code class="computeroutput"><span class="special">-</span><span class="identifier">lm</span> <span class="special">-</span><span class="identifier">lfftw3</span></code> 126 for double precision, <code class="computeroutput"><span class="special">-</span><span class="identifier">lm</span> 127 <span class="special">-</span><span class="identifier">lfftw3f</span></code> 128 for float, so on. 129 </p> 130<p> 131 Evaluation of derivatives is done by differentiation of Horner's method. As 132 always, differentiation amplifies noise; and because some rounding error is 133 produced by computation of the Fourier coefficients, this error is amplified 134 by differentiation. 135 </p> 136<h4> 137<a name="math_toolkit.cardinal_trigonometric.h3"></a> 138 <span class="phrase"><a name="math_toolkit.cardinal_trigonometric.references"></a></span><a class="link" href="cardinal_trigonometric.html#math_toolkit.cardinal_trigonometric.references">References</a> 139 </h4> 140<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 141<li class="listitem"> 142 Atkinson, Kendall, and Weimin Han. <span class="emphasis"><em>Theoretical numerical analysis.</em></span> 143 Vol. 39. Berlin: Springer, 2005. 144 </li> 145<li class="listitem"> 146 Kress, Rainer. <span class="emphasis"><em>Numerical Analysis.</em></span> 1998. Academic 147 Edition 1. 148 </li> 149</ul></div> 150</div> 151<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 152<td align="left"></td> 153<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar 154 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 155 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 156 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 157 Daryle Walker and Xiaogang Zhang<p> 158 Distributed under the Boost Software License, Version 1.0. (See accompanying 159 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 160 </p> 161</div></td> 162</tr></table> 163<hr> 164<div class="spirit-nav"> 165<a accesskey="p" href="catmull_rom.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../interpolation.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="cubic_hermite.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 166</div> 167</body> 168</html> 169
