Number of points needed for linear interpolation of sine in $[0,\frac{\pi}{2}]$ with given error bound

526 Views Asked by At

I want to get a set of equispaced points in $[0,\pi/2]$ and use piecewise linear interpolation generated by those points to fit the sine function. And I want to determine how many points do I need to put in to generate the linear interpolation fit such that maximum error in that interval can be guaranteed not exceeding $10^{-4}$.

Theoritically, we have $|f(t)-l(t)|\leq\frac{h^2}{8}\max\limits_{0\leq c_t\leq\frac{\pi}{2}}|f''(c_t)|$. Using this, roughly estimating this by letting the max second derivative be 1, I would get the result that nearly 57 points are needed to divide the interval. But are there any better ways of estimating this?

1

There are 1 best solutions below

0
On

You can get a better result by using non-uniform partitions. The goal is to partition $[0,\pi/2]$ by points $0=x_0<x_1<\dots<x_n=\pi/2$ such that $$ \frac18 (x_j-x_{j-1})^2 \sin x_j \le 10^{-4} $$ for all $j$. Here I'm using the fact that the maximum of $|\sin x|$ on a subinterval is attained at the right endpoint.

These points can be computed from right to left, starting with $x_n=\pi/2$ and using $$ x_{j-1}=x_j - \sqrt{8\cdot 10^{-4}/\sin x_j} $$ After $44$ steps the value turns out to be negative. Replacing that value by $0$, we get a partition with $44$ subintervals. The points $x_j$ are listed below.

I'm not saying this is a practical way to interpolate (uniform partition is much simpler and works just fine), but if you really want to reduce the number of points, this achieves something.

1.570796327
1.542512056
1.514222126
1.485915202
1.457579878
1.429204629
1.400777761
1.372287352
1.343721194
1.315066738
1.28631102
1.257440593
1.228441446
1.199298919
1.169997599
1.140521215
1.110852507
1.080973083
1.050863253
1.020501835
0.9898659257
0.9589306338
0.9276687595
0.8960504105
0.8640425372
0.8316083629
0.7987066799
0.7652909687
0.7313082823
0.6966978128
0.661389021
0.6252991535
0.5883298773
0.550362616
0.5112519086
0.4708156524
0.4288202176
0.3849566726
0.3388005789
0.2897388135
0.2368226436
0.1784288121
0.1112911923
0.02641946608
0