Solve the recurrence relation $y_{n+1}-2y_n+y_{n-1}-\frac h2(y_{n+1}-y_{n-1})-2h^2y_n=0$

Question

I am solving the recurrence relation $$ y_{n+1}-2y_n+y_{n-1}-\frac h2(y_{n+1}-y_{n-1})-2h^2y_n=0. $$ In the question, it is suggested that this is related to the DE $y''-y'-2y=0$, but I have no clue why it is related.

By the standard method, I solve the characteristic equation and get some awful roots. $$ n=\frac{2+2h^2\pm h^2\sqrt{4h^2+9}}{2-h} $$

Any hints?

Answer 1

I'm not entirely sure what you're asking... How is the equation related to the ODE? Or how to find $y_n$? I answered the first, if you're looking for the second, please clarify

First

How is it related to the ODE? Take the Taylor series about $n$ so

$$y_{n+1} = y_n + h y'_n + \frac{h^2}{2} y''_n + \frac{h^3}{3!} y^{(3)}_n + \frac{h^4}{4!} y^{(4)}_n + \cdots$$

$$y_{n-1} = y_n - h y'_n + \frac{h^2}{2} y''_n - \frac{h^3}{3!} y^{(3)}_n + \frac{h^4}{4!} y^{(4)}_n + \cdots$$

Looking at the expression in parts

$$y_{n+1} - 2 y_n + y_{n-1} = \left( y_n + h y'_n + \frac{h^2}{2} y''_n + \frac{h^3}{3!} y^{(3)}_n + \frac{h^4}{4!} y^{(4)}_n + \cdots \right) - 2 y_n + \left( y_n - h y'_n + \frac{h^2}{2} y''_n - \frac{h^3}{3!} y^{(3)}_n + \frac{h^4}{4!} y^{(4)}_n + \cdots \right)$$

now grouping terms on their power of $h$

$$y_{n+1} - 2 y_n + y_{n-1} = \left( y_n - 2 y_n + y_n \right) + h \left( y'_n - y'_n \right) + h^2 \left( \frac{1}{2} y''_n + \frac{1}{2} y''_n \right) + h^3 \left( \frac{1}{3!} y^{(3)}_n - \frac{1}{3!} y^{(3)}_n \right) + h^4 \left( \frac{1}{4!} y^{(4)}_n + \frac{1}{4!} y^{(4)}_n \right) + \cdots$$

canceling out like terms and dividing through by $h^2$

$$\frac{y_{n+1} - 2 y_n + y_{n-1}}{h^2} = y''_n + h^2 \frac{2}{4!} y^{(4)}_n + \cdots$$

so

$$\frac{y_{n+1} - 2 y_n + y_{n-1}}{h^2}$$

is the order 2 finite difference approximation of $y''$ (order 2 because the $y^{(4)}_n$ term is scaled by $h^2$. This can be written as

$$\frac{y_{n+1} - 2 y_n + y_{n-1}}{h^2} = y_n'' + \mathcal{O}\left(h^2\right)$$

performing a similar analysis, we can see that the second set of terms is an approximation of the first derivative (also order 2)

$$\frac{y_{n+1} - y_{n-1}}{h} = y'_n + \mathcal{O}\left(h^2\right)$$

Therefore, the original expression is an order 2 finite difference approximation of the ODE.

Answer 2

The characteristic roots of $$ (2-h)y_{n+1}-4(1+h^2)y_n+(2+h)y_{n-1}=0 $$ are $$ n=\frac{-b\pm\sqrt{b^2-4ac}}{2a}=\frac{4(1+h^2)\pm\sqrt{16(1+h^2)^2-4(4-h^2)}}{2(2-h)} \\ =\frac{2(1+h^2)\pm h\sqrt{9+4h^2}}{2-h}=e^{h/2\pm 3h/2+O(h^2)} $$ which is as expected for the differential equation with characteristic roots $-1$ and $2$.

Note that if you extract $h^2$ from under the root, then you get a factor $|h|=h$ in front of the root.

Discretization is an ugly business, there is no promise to get nice terms in computing an exact solution of the discretization.

Answer 3

If it is not mandatory to follow the suggestion (after all it is a suggestion!), you should just ignore it... It is a really bad suggestion since it is not easier to solve the differential equation in stead of the difference equation!

After computing the roots of the characteristic polynomial you get two independent solutions of the homogeneous equation... The general solution is simply of the form

$$ y_n = c_1 \left( \frac{-2 -2 h^2-h\sqrt{4 h^2+9}}{h-2}\right)^n+c_2 \left( \frac{-2 -2 h^2+h\sqrt{4 h^2+9}}{h-2}\right)^n. $$