Thursday, 2 February 2012

Finding a particular solution of a second order linear inhomogeneous recurrence equation

Approximation theory and methods did not really fit in the "big picture" of my study plan last year, not only because I am notoriously bad at numerical calculations. Having invested a lot of effort in developing intuition for the behaviour of analytic functions, I was suddenly confronted with the cubic splines which seemed to have all those properties, that well-mannered functions would be never allowed to possess.
Nicely, but artificially glued together of several pieces of cubics, smooth only up to the second derivative, vanishing on the entire intervals, now this is what seems really counter-intuitive.

The following is the kind of problem I got stuck with for a while. The task is to express a function, say $$f(x)=x^2$$ in terms of cubic B-splines on the entire real axis. I am omitting a lot of background material focusing on one particular idea that arises in the solution.

$$x^2=\sum_{p=-\infty}^{\infty}\lambda_p B_p(x)$$
Since $$B^3_p(x)$$ has a supporting interval $$[p, p+3+1]=[p,p+4]$$ of length 4 outside which it vanishes, we can start by expressing the function in terms of $$B_{-3} , B_{-2}, B_{-1} ,B_{0}$$ on $$[0.1]$$ and then try to extend the result. Calculating the expressions for the splines on $$[0.1]$$:
$$B_{-3}(x)=-\frac{1}{24}\left(x-1\right)^{3}$$
$$B_{-2}(x)=\frac{1}{24}\left(3x^{3}-6x^{2}+4\right)$$
$$B_{-1}(x)=\frac{1}{24}\left(-3x^{3}+3x^{2}+3x+1\right)$$
$$B_0(x)=\frac{1}{24}x^{3}$$
multiplying by the respective coefficients, summing and equating powers of $$x$$ on each side we arrive at the following system of equations:
$$\begin{cases} -\lambda_{-3}+3\lambda_{-2}-3\lambda_{-1}+\lambda_{0} & =0\\ 3\lambda_{-3}-6\lambda_{-2}+3\lambda_{-1} & =0\\ -3\lambda_{-3}+3\lambda_{-1} & =24\\ \lambda_{-3}+4\lambda_{-2}+\lambda_{-1} & =0\end{cases}$$

Having the solution (guaranteed by the Schoenberg-Whitney theorem): $$(\lambda_{-3},\lambda_{-2},\lambda_{-1},\lambda_0)=(\frac{8}{3},\frac{-4}{3},\frac{8}{3},\frac{44}{3})$$
Now we want to find all coefficients on each of the intervals $$[\xi_p,\xi_p+4]$$ for the points $${\xi_i=ih;i=\pm1,\pm2....}$$. From the general expression for the B-spline it can be deduced that
$$B_p(\xi_{p+1})=\frac{1}{24h}$$
$$B_p(\xi_{p+2})=\frac{1}{6h}$$
$$B_p(\xi_{p+3})=\frac{1}{24h}$$
which for $$h=1$$ leads to the following recurrence relation:
$$\lambda_{j-1}+4\lambda_{j-2}+\lambda_{j-3}=24j^2$$
or, after changing the index
$$\lambda_{j}+4\lambda_{j+1}+\lambda_{j+2}=24(j+3)^2$$
Now here is the trick that I came up with. The last expression can be thought of as a "second-order linear inhomogeneous recurrence relation". The advantage of this approach is that the structure of the solution instantly becomes clear.
The general solution of the corresponding homogeneous relation
$$\lambda_{j}+4\lambda_{j+1}+\lambda_{j+2}=0$$
is derived using the standard method of solving this type of recurrencies and is given by the following expression:
$$\lambda^h_j=\alpha\left(-2-\sqrt{3}\right)^{j}+\beta\left(-2+\sqrt{3}\right)^{j}$$
It can also be found using generating functions. Not surprisingly it depends on 2 arbitary constants, as it takes 2 initial terms, $$\lambda_0$$ and $$\lambda_{-1}$$ to reconstruct the whole sequence from the three-term recurrency. Applying the general ideas from the linear systems we deduce that in order to obtain the general solution of the inhomogeneous recurrency we have to add a particular solution to the expression above.
Since the RHS is the quadratic polynomial it makes sence to look for the particular solution in the form:
$$\lambda^p_j=aj^2+bj+c$$
Substituting this into the original recurrency and gatherig together the powers of $$j$$ we obtain:
$$6aj^2+(12a+6b)j+8a+6b+6c=24j^2+144j+216$$
which after equating powers gives the solution $$(a,b,c)=(4,16,\frac{44}{3})$$
Thus the general solution of the inhomogeneous equation is given by the following formula:
$$\lambda_j=\alpha\left(-2-\sqrt{3}\right)^{j}+\beta\left(-2+\sqrt{3}\right)^{j}+4j^2+16j+\frac{44}{3}$$
Now we can use the values of $$\lambda_0$$ and $$\lambda_{-1}$$ to determine the constants (bearing in mind that $$\left(-2-\sqrt{3}\right)\left(-2+\sqrt{3}\right)=-1$$):
$$\frac{44}{3}=\alpha+\beta+\frac{44}{3}$$
$$\frac{8}{3}= -\alpha\left(-2+\sqrt{3}\right)-\beta\left(-2-\sqrt{3}\right)+\frac{8}{3}$$
which gives $$\alpha=\beta=0$$. Thus finally:
$$\lambda_j=4j^2+16j+\frac{44}{3}$$
which is the solution of the original problem.