pi approximation with Newton's method to an arbitrary rate of convergence

Question

If $a_1$ to $a_3$ is the solution of this linear system of equations $$\left(\begin{array}{rrr|r} -1&2&-3& -1\\ 1&-8&27&0 \\ -1 & 32 & -243 & 0 \end{array}\right)$$

then $f_3(x) = a_1\sin(x)+ a_2 \sin(2x) + a_3 \sin(3x)$ defines a function with $f_3(\pi) = 0$ and the convergence rate of Newton's methods should locally be of 6th order since $f_3'(\pi) = -1$ and the 2nd to 6th derivatives vanish at $\pi$ (That's how the system of equations is constructed). As far as I know from my class on numerical methods, this is sufficient for the rate of convergence.

Similarly, one can extend the defining system of equations above to construct functions which imply an arbitrary rate of convergence for Newton's method by computing coefficients $a_1$ to $a_k$ with $f_k(\pi) = 0$, $f_k'(\pi) = -1$ and $f_k^{(i)}(\pi) = 0$ for $2 \leq i \leq 2k$. The convergence rate of Newton's method is therfore of the order $2k$.

Numerical calculations in Matlab confirm these results.

By plotting the functions $f_k$ one can observe that the function seems to converge pointwise to $g(x) = \pi -x $ for $x \in (0, 2\pi)$.

If this is true, how can one prove this?

I'm not familiar with functions definied by solutions of linear systems of equations and have never seen something like this before.

I tried to use the Taylor expansion of $|f_k(x)| = |\frac{1}{(2k+1)!} \cdot f^{(2k+1)}(\xi)| \gtrapprox a_k\frac{k^{2k+1}}{(2k+1)!} (x-\pi)^{2k+1}$.

But $\frac{k^{2k+1}}{(2k+1)!}$ diverges when $k$ approches $\infty$, so I either need an estimation of $a_k$ or another approach to show pointwise convergence.

Is there any material about functions defined by linear system of equations or closely related topics (preferably undergraduate level)? Did anyone, by chance, have a smiliar idea to this and/or is there any further material available on this topic?

Is it connected to the Fourier series?

Another question I asked myself when I discovered these functions was if it is connected to the Fourier series of $\pi-x$ (extended periodically beyond $[0, 2\pi]$) because it is a linear combination of sine functions with integer factors in the argument. I remember that if there exits a uniformly convergent series of the form $\sum_{k= -\infty}^\infty c_k e^{ikx}$ it must be the Fourier series. We can write $f_k = \sum_{i= 0}^k a_{ki}\sin(ix)$, so there can't be any coefficients $a_{\infty i}$ such that the sum defined by $f_\infty$ converges uniformly to $\pi-x$ because that would imply the uniform convergence of the Fourier Series of $\pi-x$, which it does not, if I remember correctly.

Can one define something like $a_{\infty i}$ in a reasonable way? And if so, are they the Fourier coefficients?I have no idea how to start here. I have found some results about infinite systems of linear equations but nothing directly applicable to my problem.

Thanks in advance for any answers.

Answer 1

Interesting question! Here are some general comments.

1. On the one hand, your result is not really unexpected (e.g., cf. uniqueness of Fourier series). Say you want the best trigonometric approximation of $\pi-x$: $$ \pi-x=\sum_{i=0}^ka_i\sin(ix)+R_N(x) $$ A possible approximation can be obtained by insisting that both sides have the same value, and derivatives, at (say) $x=\pi$. This leads to your conditions on the coefficients. To make this precise, one must prove that $R_k(x)\to0$. But, intuitively speaking, this is indeed what you expect. Furthermore, in this limit, the coefficients should become the Fourier coefficients of $\pi-x$, to wit, $$ \lim_{k\to\infty}a_i=\frac{1}{\pi}\int_0^{2\pi}(x-\pi)\sin(ix)\mathrm dx=\frac{2}{i} $$

2. With a little bit of work, you can prove that the coefficients are actually given by $$ a_i=\frac{2 (k!)^2}{i (i+k)! (k-i)!}=\frac{2}{i}-\frac{2i}{k}+\mathcal O(k^{-2}) $$ as expected.

3. More generally, say you are interested in a series of the form $$ \sum_{i=0}^ka_i f_i(x) $$ where $\{f_i\}$ are a basis (of some reasonable function space), and the $\{a_i\}$ are fixed by some differential conditions. In the limit $k\to \infty$, if this converges to a function $f(x)$, then this function should satisfy the same differential conditions than its truncation (under some typical regularity assumptions). Here you want $f(\pi)=0$, $f'(\pi)=-1$, and all the rest of derivatives to vanish. The only (analytic) function that satisfies these conditions is indeed $f(x)=\pi-x$, as follows from uniqueness of Taylor expansions.

Answer 2

So, what you are doing is a Hermite interpolation, with trigonometric polynomials, of the (inverted) sawtooth wave $$ g(x) = \pi - x\quad \left| {\;x \in \left( {0,2\pi } \right)} \right. $$ $$ g(x) = 2\pi \left( {\left\lfloor {{1 \over 2} + {x \over {2\pi }}} \right\rfloor - {x \over {2\pi }}} \right) $$

You are doing a Hermite interpolation, since you consider that the function is odd, and therefore you use only sines.
After that you obtain implicitly that $f(\pi )=0$, as all its even derivatives, and impose 1st derivative to be $-1$ at $x= \pi $, and then the 3rd and 5th to be null.

Intuitively speaking, you are developing a local approximation to $g(x) \; |\, x= \pi $, a sort of Taylor series but with trigonometric polynomials in place of the normal ones.

For sure the $f_{n} (x)$ will improve the convergence of Newton method, and the improvement will be of the order of the Taylor series, since for instance $$ \sin \left( {3x} \right) = 3\cos ^2 x\sin x - \sin ^3 x = 3\sin x - 4\sin ^3 x $$ which means that you can convert your approximation into $$ f_n (x) = \sum\limits_{k = 1}^n {a_{\,k} \sin \left( {kx} \right)} = \sum\limits_{k = 1}^n {b_{\,k} \sin ^{\,k} x} = \sum\limits_{k = 1}^n {c_{\,k} x^{\,k} } + O\left( {x^{\,n + 1} } \right) $$ i.e. the difference with the truncated Taylor series will be of the order of $O(x^{n+1})$.

The Fourier series is different, as it can be thought as a global (on the whole period) approximation, in the least squares acception.

Clearly both will converge to $g(x)$ for large $n$, even because the sines ensures that your $f(x)$ is null at $x=0, 2\pi $, same as the Fourier series.

Answer 3

This answer addresses the convergence of $f_n(x)$ to $\pi - x$, it does not address whether this is actually a good way to compute $\pi$.

The function $f_n(x)$ is the unique sum $\sum_{k=1}^n a_k \sin(kx)$ which matches the function $\pi-x$ at $x=\pi$ up to the first $n$ derivatives. I will give an explicit formula for $f_n(x)$ and show that it converges to $\pi-x$.

Throughout this answer, I take $\log$ to have a branch cut on the negative real axis and real values on positive real axis. I note that, for $x \in (0, 2 \pi)$, I have $$\pi - x = i \log (1-e^{i x}) - i \log ( 1-e^{-ix}).$$ It's convenient to rewrite this as $$i \log \frac{1-e^{i x}}{2} - i \log \frac{ 1-e^{-ix}}{2} = i \log \left( 1 - \frac{1+e^{ix}}{2} \right) - i \log \left( 1 - \frac{1+e^{-ix}}{2} \right)$$ or, expanding in Taylor series, $$\pi-x = i \sum_{k=1}^{\infty} \frac{1}{k} \left[ \left(\frac{1+e^{-ix}}{2} \right)^k - \left(\frac{1+e^{ix}}{2} \right)^k \right] \ \mbox{for}\ 0 < x < \pi. \ (\ast)$$ Note that this series does converge for all $x$ in the range, as $\left| \tfrac{1+e^{\pm ix}}{2} \right| < 1$.

Now, truncate this sum to define $$g_n(x) = i \sum_{k=1}^{n} \frac{1}{k} \left[ \left(\frac{1+e^{-ix}}{2} \right)^k - \left(\frac{1+e^{ix}}{2} \right)^k \right] .$$ Since the Taylor series converges, $\lim_{n \to \infty} g_n(x) = \pi - x$. I claim that $g_n(x)$ is the OP's $f_n(x)$.

Clearly, $g_n(x)$ is a linear combination of $\sin kx$ and $\cos kx$ for $0 \leq k \leq n$. Also, since $g_n$ is clearly an odd function, the cosine terms drop out, so $g_n(x)$ is of the form $\sum_{k=1}^n a_k \sin kx$.

It remains to check that $g_n$ matches $\pi - x$ to order $n$ at $x = \pi$. The difference between $g_n(x)$ and $\pi-x$ is the terms that were deleted from $(\ast)$, with $k>n$. Each of these vanishes to order $>n$ at $x = \pi$.

So $g_n(x)$ is $f_n(x)$, and we know that $g_n(x) \to \pi-x$ because the Taylor series of $\log$ converges.

Moral: If you have defined a function by matching derivatives of some other function, try to invoke Taylor series.