Poisson Equation

We want to solve:

subject to some Dirichlet boundary conditions.

Five-point method

For this method we will assume that the boundary is rectangular
because finite difference gets a bit messed up otherwise.

We use finite differences to discretize the equation.

ie we get

Now let and to get

Now we make into a column vector,
and rewrite the system of equations into
(note that and are boundary conditions and should be on rhs).
If we fill the column vector in a natural way
(column by column in the grid)
then the matrix looks like this (in block matrix format):

We investigate this matrix, and try to prove that
this discrete version does converge to the actual solution when is small.

Lemma

For any ordering of the grid points,
the matrix is symmetric and negative definite.

Proof

Firstly note that for all .
Now for , if and are neighbours then ,
otherwise , so is symmetric and has real eigenvalues.
Now by Gershgorin Theorem the eigen values are at most
(each row will have at most 4 entries that are ).
Suppose now we have an eigenvalue 0 with eigenvector .
Suppose for some , is the max absolute component of .
Then all its neighbours have so .
We can traverse the whole grid like this,
thus all the components have the same norm.
But then there is a row of where for only values of ,
so in that row we cannot have .

Proposition (eigenvalues)

The eigenvalues of are

where and

Proof

Fix and and we define and . We prove that $$
v_{i,j}=\sin ix \sin jy

### Theorem (convergence) Subject to sufficient smoothness of the function $f$ and the boundary conditions $\phi$, there exists a number $c>0$, independent of $h=\frac{1}{m+1}$, such that $||e||\leq ch$. #### Proof Note that the exact solution satisfies our recursion relation up to an addition of some $\eta_{i,j}=O(h^{4})$. Subtracting our numerical approximation we find the recursive formula for errors:

e_{i-1,j}+e_{i+1,j}+e_{i,j-1}+e_{i,j+1}-4e_{i,j}=h^2f_{i,j}+\eta_{i,j}

\begin{align}
||\eta ||^2&=\sum_{i=1}^{m} \sum_{j=1}^{m} |\eta_{i,j}|^2\leq c^2m^2h^8<c^2 \frac{1}{h^2}h^8=c^2h^6\
&\implies ||\eta||\leq ch^3
\end{align}

||A^{-1}||=\frac{1}{4} \max \left{ \left(\sin^2{k\pi h\over 2}+\sin^2{l\pi h\over 2}\right)^{-1} \right} \leq \frac{1}{8\sin^2\left( \frac{\pi h}{2} \right)}\leq \frac{1}{8h^2}

||e||\leq ||A^{-1}||\cdot||\eta||\leq \frac{ch}{8}

### Hockney method We want to solve this FAST. Note that $B$ is a [[Algebra/Vector Spaces/TST matrix]] and so we can diagonalize it, say $B=QDQ$ where $D$ is the diagonal of eigenvalues. Set $v_{k}=Qu_{k}$ and $c_{k}=Qu_{k}$ to find:

\begin{pmatrix}
D & I & \
I & D & \ddots \
& \ddots & \ddots & I \
& & I & D
\end{pmatrix}
\begin{pmatrix}
v_{1} \
v_{2} \
\vdots \
v_{m}
\end{pmatrix}

\begin{pmatrix}
c_{1} \
c_{2} \
\vdots \
c_{m}
\end{pmatrix}

A\sim\begin{pmatrix}
\Lambda_{1} & \
& \Lambda_{2} & & \
& & \ddots & \
& & & \Lambda_{m}
\end{pmatrix}\quad %quad
\quad %quad

\Lambda_{i}=\begin{pmatrix}
\lambda_{i} & 1 \
1 & \lambda_{i} & \ddots & \
& \ddots & \ddots & 1\
& & 1 & \lambda_{i}
\end{pmatrix}

(Qy){l}=\sum{j=1}^{m} \sin \frac{\pi jl}{m+1}y_{j}=\mathrm{Im}\sum_{j=0}^{2m+1} \exp \frac{2i\pi jl}{2m+2}y_{j}