%%%%		-*- Mode: LaTeX -*-
%%%% Author:    J. Robert Buchanan
%%%% Address:   Department of Mathematics
%%%%		Millersville University
%%%%            P.O. Box 1002
%%%%            Millersville, PA 17551-0302
%%%% Phone:     717-871-7305
%%%% FAX:	717-871-7948
%%%%
%%%% Email:     Robert.Buchanan@millersville.edu
%%%%
%%%% Date:      04/05/2025
%%%%
%%%% Purpose:   Laplace's and Poisson's Equations
%%%%

\documentclass[10pt]{beamer}

\mode<presentation>
{
  %\usetheme{Warsaw}
  \usetheme{default}
  %\usetheme{CambridgeUS}
  % or ...

  %\setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}


\usepackage[english]{babel}
% or whatever

\usepackage[latin1]{inputenc}
% or whatever

\usepackage{times}
\usepackage[T1]{fontenc}
% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.


\title{Laplace's and Poisson's Equations}
\subtitle{\textit{Partial Differential Equations}} % (optional)


\author % (optional, use only with lots of authors)
{J~Robert~Buchanan}
% - Use the \inst{?} command only if the authors have different
%   affiliation.

\institute[Millersville University of Pennsylvania]
% (optional, but mostly needed)
{
  Department of Mathematics
}
% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.

\date{ % (optional)
Fall
%Spring
%Summer
\the\year}

\subject{Talks}
% This is only inserted into the PDF information catalog. Can be left
% out. 



% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}



% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

%\begin{frame}
%  \frametitle{Outline}
%  \tableofcontents
  % You might wish to add the option [pausesections]
%\end{frame}


% Since this a solution template for a generic talk, very little can
% be said about how it should be structured. However, the talk length
% of between 15min and 45min and the theme suggest that you stick to
% the following rules:  

% - Exactly two or three sections (other than the summary).
% - At *most* three subsections per section.
% - Talk about 30s to 2min per frame. So there should be between about
%   15 and 30 frames, all told.

%\section{Introduction}

\begin{frame}\frametitle{Objectives}

In this lesson we will:
\begin{itemize}
\item develop a 5-point approximation to the Laplacian differential
  operator,
\item explore the structure of the system of algebraic equations
  induces by the 5-point approximation,
\item develop a 9-point approximation to the Laplacian differential
  operator, and
\item explore the structure of the system of algebraic equations
  induces by the 9-point approximation.
\end{itemize}

\end{frame}
%%

\begin{frame}\frametitle{Numerical Approximation}

\begin{itemize}
\item Suppose the plane has been gridded with a spacing of $h > 0$ in
both the $x$ and $y$ directions.
\item Let $u_{i}^{j} = u(i \, h, j \, h)$ for some integers $i$ and $j$,
then
\begin{align*}
u_{xx} + u_{yy}
	= {} & \frac{u(x+h, y) - 2 u(x,y) + u(x-h, y)}{h^{2}}	\\
	& + \frac{u(x, y+h) - 2 u(x,y) + u(x,y-h)}{h^{2}}
	+ O(h^{2})	.
\end{align*}
\item Poisson's equation can be approximated by the finite difference
formula
\[
%\label{eq:findiff:poisson5pt}
\frac{1}{h^{2}} (u_{i+1}^{j} + u_{i-1}^{j} - 4 u_{i}^{j} + u_{i}^{j+1}
+ u_{i}^{j-1})
	= f(i \, h, j \, k)	,
\]
which has $O(h^{2})$ truncation error.
\item The five-point differencing approximation to the Laplacian
will be denoted as
$\Delta_{5} u_{i}^{j}$.
\end{itemize}

\end{frame}
%%

\begin{frame}\frametitle{Stencil}

\begin{center}
\resizebox{0.85\columnwidth}{!}{\includegraphics{laplace5pt}}
\end{center}

\end{frame}
%%

\begin{frame}\frametitle{Linear System}

If the domain of Poisson's equation is the rectangle $R = \{ (x, y) \,
| \, 0 < x < N \, h, \, 0 < y < M \, h \}$ and the boundary conditions
are Dirichlet type with $u(x, y) = g(x, y)$ on $\partial R$ then the
finite difference approximation can be written in the form of a linear
system $A \, \mathbf{u} = \mathbf{b}$.

\vspace*{0.10in}

The vector of unknowns $\mathbf{u}$ contains $(M-1)(N-1)$ elements
arranged in what is called the
\textbf{natural ordering} of the interior
nodes,
\[
\mathbf{u}
	= \left( u_{1}^{1}, \ldots, u_{N-1}^{1},
u_{1}^{2}, \ldots, u_{N-1}^{2}, \ldots,
u_{1}^{M-1}, \ldots, u_{N-1}^{M-1} \right)^{T}
\]

\end{frame}
%%

\begin{frame}\frametitle{Natural Ordering of Nodes}

\begin{center}
\resizebox{0.75\textwidth}{!}{\includegraphics{LaplaceRect}}
\end{center}
Assuming Dirichlet boundary conditions, the boundary points in the
discretization have values given by
\[
u_{i}^{0} = g(i \, h, 0)	,	\quad
u_{i}^{M} = g(i \, h, M \, h)	,	\quad
u_{0}^{j} = g(0, j \, h)	,	\mbox{ and }
u_{N}^{j} = g(N \, h, j)
\]
for $i = 1, 2, \ldots, N-1$ and $j = 1, 2, \ldots, M-1$.

\end{frame}
%%

\begin{frame}\frametitle{Matrix Form}
\fontsize{9pt}{10.8}\selectfont

Matrix $A$ is a square matrix with $(M-1)^{2} (N-1)^{2}$ entries.
Let $\hat{A}$ be the $(N-1) \times (N-1)$ tridiagonal matrix:
\[
\hat{A}
	= \left[ \begin{array}{rrrrrrr}
4 & -1 & 0 & \cdots & 0 & 0 & 0	\\
-1 & 4 & -1 & \cdots & 0 & 0 & 0	\\
\vdots & \vdots & \vdots & {} & \vdots & \vdots & \vdots	\\
0 & 0 & 0 & \cdots & -1 & 4 & -1	\\
0 & 0 & 0 & \cdots & 0 & -1 & 4
\end{array} \right],
\]
let $I$ be the $(N-1) \times (N-1)$ identity matrix, and let $0$
represent the $(N-1) \times (N-1)$ matrix of all zero entries.
Matrix $A$ has the block structure,
\[
%\label{eq:findiff:5ptLaplacianmatrixA}
A
	= \left[ \begin{array}{ccccccc}
\hat{A} & -I & 0 & \cdots & 0 & 0 & 0	\\
-I & \hat{A} & -I & \cdots & 0 & 0 & 0	\\
\vdots & \vdots & \vdots & {} & \vdots & \vdots & \vdots	\\
0 & 0 & 0 & \cdots & -I & \hat{A} & -I	\\
0 & 0 & 0 & \cdots & 0 & -I & \hat{A}
\end{array} \right]	.
\]
There are $M-1$ blocks in each row or column.
Note that $A$ is strictly diagonally dominant, thus ensuring there is
a unique solution to the linear system $A \, \mathbf{u} = \mathbf{b}$.

\end{frame}
%%

\begin{frame}\frametitle{Vector $\mathbf{b}$}

Vector $\mathbf{b}$ also has $(M-1)(N-1)$ elements.
Using the natural ordering of the interior points
\begin{align*}
\mathbf{b}
	= {} & -h^{2} \left(
f_{1}^{1}, f_{2}^{1}, \ldots, f_{N-1}^{1},
f_{1}^{2}, f_{2}^{2}, \ldots, f_{N-1}^{2},
\ldots,
f_{1}^{M-1}, f_{2}^{M-1}, \ldots, f_{N-1}^{M-1} 
\right)^{T}	\\
	&+ \left(
g_{1}^{0}, g_{2}^{0}, \ldots, g_{N-1}^{0},
\underbrace{0, \ldots, 0}_{(N-1)(M-3)},
g_{1}^{M}, g_{2}^{M}, \ldots, g_{N-1}^{M}
\right)^{T}	\\
	&+ \left(
g_{0}^{1}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{1},
g_{0}^{2}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{2},
\ldots,
g_{0}^{M-1}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{M-1}
\right)^{T}
\end{align*}
where to save space $f_{i}^{j} = f(i \, h, j \, h)$ and $g_{i}^{j} =
g(i \, h, j \, h)$.

\end{frame}
%%

\begin{frame}\frametitle{Example}

%\label{xmp:findiff:poisson5pt}
Derive the linear system of equations for approximating the solution
to the following boundary value problem using the 5-point
approximation:
\begin{align*}
\Delta u
	&= e^{x - y}
\mbox{ on $R$}	\\
u(x, y)
	&= x \, y
\mbox{ on $\partial R$.}
\end{align*}
Let the domain of the boundary value problem be $R = \{ (x, y) \, | \,
0 < x < 4, \, 0 < y < 3 \}$.
Use $h = 1$ for simplicity.

\end{frame}
%%

\begin{frame}\frametitle{Solution}

\begin{align*}
4 u_{1}^{1} - u_{2}^{1} - u_{1}^{2}
	&= -1	\\
-u_{1}^{1} + 4 u_{2}^{1} - u_{3}^{1} - u_{2}^{2}
	&= -e	\\
-u_{2}^{1} + 4 u_{3}^{1} - u_{3}^{2}
	&= 4 - e^{2}	\\
-u_{1}^{1} + 4 u_{1}^{2} - u_{2}^{2}
	&= 3 - e^{-1}	\\
-u_{2}^{1} - u_{1}^{2} + 4 u_{2}^{2} - u_{3}^{2}
	&= 5	\\
-u_{3}^{1} - u_{2}^{2} + 4 u_{3}^{2}
	&= 17 - e	.
\end{align*}

\end{frame}
%%

\begin{frame}\frametitle{$9$-Point Approximation}

A nine-point $O(h^{4})$ finite difference representation of
$\Delta u$ is
\begin{align*}
%\label{eq:findiff:ninepoint}
6 h^{2} \Delta_{9} u_{i}^{j}
	= {} & 4 \left( u_{i-1}^{j} + u_{i+1}^{j} + u_{i}^{j-1} + u_{i}^{j+1} \right) - 20 u_{i}^{j}	\\
	&+ \left( u_{i-1}^{j-1} + u_{i+1}^{j-1} + u_{i-1}^{j+1} + u_{i+1}^{j+1}
            \right)	.
\end{align*}

\vspace*{0.10in}

There exists a $9$-point approximation to Poisson's equation.
\[
%\label{eq:findiff:9pointPoissonknownf}
\Delta_{9} u_{i}^{j}
	= f(i \, h, j \, h) + \frac{h^{2}}{12} \Delta f(i \, h, j \, h)	.
\]
This is a finite difference approximation to Poisson's equation with a
truncation error of $O(h^{4})$.

\end{frame}
%%

\begin{frame}\frametitle{$9$-Point Approximation}

Practical use of the $9$-point approximation requires that
function $f$ be known and its Laplacian can be calculated.
If $f$ is only represented by a table of values, the three-point
differencing formula yields the $O(h^{4})$ discrete approximation to
Poisson's equation:
\[
%\label{eq:findiff:9pointPoissonunknownf}
\Delta_{9} u_{i}^{j}
	= \frac{1}{12} \left( f_{i-1}^{j} + f_{i+1}^{j} + 8 f_{i}^{j} +
              f_{i}^{j-1} + f_{i}^{j+1} \right)	,
\]
where $f_{i}^{j} = f(i \, h, j \, h)$.

Multiplying both sides by $-6
h^{2}$ enables the linear system to be written as
\begin{align*}
20 u_{i}^{j}
	&-
4 (u_{i-1}^{j} + u_{i+1}^{j} + u_{i}^{j-1} + u_{i}^{j+1})
	- (u_{i-1}^{j-1} + u_{i+1}^{j-1} + u_{i-1}^{j+1} + u_{i+1}^{j+1})	\\
%\label{eq:findiff:9pointsystem}
	&=
-\frac{h^{2}}{2} ( f_{i-1}^{j} + f_{i+1}^{j} + 8 f_{i}^{j} +
              f_{i}^{j-1} + f_{i}^{j+1} )
\end{align*}
for $i = 1, 2, \ldots, N-1$ and $j = 1, 2, \ldots, M-1$.

\end{frame}
%%

\begin{frame}\frametitle{Matrix/Vector Form}

If the boundary conditions are of Dirichlet type, the linear system
of equations can be
written in matrix form as
\[
A \, \mathbf{u}
	= -(h^{2}/2) B \, \mathbf{f} + \mathbf{b}
\]
where $A$ is an $(M-1)(N-1) \times (M-1)(N-1)$ block banded matrix,
\[
%\label{eq:findiff:9ptLaplacianmatrixA}
A = \left[ \begin{array}{ccccccc}
\hat{A} & -\hat{B} & 0 & \cdots & 0 & 0 & 0	\\
-\hat{B} & \hat{A} & -\hat{B} & \cdots & 0 & 0 & 0	\\
\vdots & \vdots & \vdots & {} & \vdots & \vdots & \vdots	\\
0 & 0 & 0 & \cdots & -\hat{B} & \hat{A} & -\hat{B}	\\
0 & 0 & 0 & \cdots & 0 & -\hat{B} & \hat{A}
\end{array} \right]	.
\]
Each block denoted by $\hat{A}$, $\hat{B}$, or $0$ is an $(N-1) \times
(N-1)$ matrix.

\end{frame}
%%

\begin{frame}\frametitle{Blocks}

As before $0$ denotes the matrix of all zero entries.
Matrices $\hat{A}$ and $\hat{B}$ are tridiagonal matrices with the
following structures,
\[
\hat{A}
	= \left[ \begin{array}{ccccccc}
20 & -4 & 0 & \cdots & 0 & 0 & 0	\\
-4 & 20 & -4 & \cdots & 0 & 0 & 0	\\
\vdots & \vdots & \vdots & {} & \vdots & \vdots & \vdots	\\
0 & 0 & 0 & \cdots & -4 & 20 & -4	\\
0 & 0 & 0 & \cdots & 0 & -4 & 20
\end{array} \right]
\]
and
\[
\hat{B}
	= \left[ \begin{array}{ccccccc}
4 & 1 & 0 & \cdots & 0 & 0 & 0	\\
1 & 4 & 1 & \cdots & 0 & 0 & 0	\\
\vdots & \vdots & \vdots & {} & \vdots & \vdots & \vdots	\\
0 & 0 & 0 & \cdots & 1 & 4 & 1	\\
0 & 0 & 0 & \cdots & 0 & 1 & 4
\end{array} \right]	.
\]

\end{frame}
%%

\begin{frame}\frametitle{Blocks}

Matrix $B$ is also $(M-1)(N-1) \times (M-1)(N-1)$ with a block
banded structure,
\[
B
	= \left[ \begin{array}{ccccccc}
\hat{C} & I & 0 & \cdots & 0 & 0 & 0	\\
I & \hat{C} & I & \cdots & 0 & 0 & 0	\\
\vdots & \vdots & \vdots & {} & \vdots & \vdots & \vdots	\\
0 & 0 & 0 & \cdots & I & \hat{C} & I	\\
0 & 0 & 0 & \cdots & 0 & I & \hat{C}
\end{array} \right]	.
\]
Each block denoted by $\hat{C}$, $I$, or $0$ is an $(N-1) \times
(N-1)$ matrix.
Matrix $I$ is an identity matrix.
Matrix $\hat{C}$ is a tridiagonal matrix with the
following structure:
\[
\hat{C}
	= \left[ \begin{array}{ccccccc}
8 & 1 & 0 & \cdots & 0 & 0 & 0	\\
1 & 8 & 1 & \cdots & 0 & 0 & 0	\\
\vdots & \vdots & \vdots & {} & \vdots & \vdots & \vdots	\\
0 & 0 & 0 & \cdots & 1 & 8 & 1	\\
0 & 0 & 0 & \cdots & 0 & 1 & 8
\end{array} \right]	.
\]

\end{frame}
%%

\begin{frame}\frametitle{Vector $\mathbf{b}$}
\fontsize{9pt}{10.8}\selectfont

Vector $\mathbf{b}$ contains $(M-1)(N-1)$ elements and will be
written as the sum of three vectors, $\mathbf{b} = \mathbf{f}_{0} +
\mathbf{g}_{4} + \mathbf{g}$ where
\begin{align*}
\mathbf{f}_{0}
	= {} & -\frac{h^{2}}{2} \left(
f_{0}^{1}, \underbrace{0, \ldots, 0}_{N-3}, f_{N}^{1},
f_{0}^{2}, \underbrace{0, \ldots, 0}_{N-3}, f_{N}^{2},
\ldots,
f_{0}^{M-1}, \underbrace{0, \ldots, 0}_{N-3}, f_{N}^{M-1}
\right)^{T}	\\
	&- \frac{h^{2}}{2} \left(
f_{1}^{0}, f_{2}^{0}, \ldots, f_{N-1}^{0},
\underbrace{0, \ldots, 0}_{(N-1)(M-3)},
f_{1}^{M}, f_{2}^{M}, \ldots, f_{N-1}^{M}
\right)^{T}
\end{align*}
has elements which depend on the right-hand side of Poisson's
equation.
\begin{align*}
\label{eq:findiff:vectorg4}
\mathbf{g}_{4}
	= {} & 4 \left(
g_{1}^{0}, g_{2}^{0}, \ldots, g_{N-1}^{0},
\underbrace{0, \ldots, 0}_{(N-1)(M-3)},
g_{1}^{M}, g_{2}^{M}, \ldots, g_{N-1}^{M}
\right)^{T}	\\
	&+ 4 \left(
g_{0}^{1}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{1},
g_{0}^{2}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{2},
\ldots,
g_{0}^{M-1}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{M-1}
\right)^{T}
\end{align*}

\end{frame}
%%

\begin{frame}\frametitle{Vector $\mathbf{b}$}

\begin{align*}
%\label{eq:findiff:vectorg}
\mathbf{g}
	= {} & \left(
g_{0}^{0}, g_{1}^{0}, \ldots, g_{N-2}^{0},
\underbrace{0, \ldots, 0}_{(N-1)(M-3)},
g_{0}^{M}, g_{1}^{M}, \ldots, g_{N-2}^{M}
\right)^{T}	\\
	&+ \left(
g_{2}^{0}, g_{3}^{0}, \ldots, g_{N}^{0},
\underbrace{0, \ldots, 0}_{(N-1)(M-3)},
g_{2}^{M}, g_{3}^{M}, \ldots, g_{N}^{M}
\right)^{T}	\\
	&+ \left(
g_{0}^{2}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{2},
g_{0}^{3}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{3},
\ldots,
g_{0}^{M-1}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{M-1},
\underbrace{0, \ldots, 0}_{N-1}
\right)^{T}	\\
	&+ \left(
\underbrace{0, \ldots, 0}_{N-1},
g_{0}^{1}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{1},
g_{0}^{2}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{2},
\ldots,
g_{0}^{M-2}, \underbrace{0, \ldots, 0}_{N-3}, g_{N}^{M-2},
\right)^{T}	.
\end{align*}

\end{frame}
%%

\begin{frame}\frametitle{Example}

%\label{xmp:findiff:ninepoint}
Derive the linear system of equations for approximating the solution
to the following boundary value problem using the 9-point
approximation:
\begin{align*}
\Delta u
	&= e^{x - y}
\mbox{ on $R$}	\\
u(x, y)
	&= x \, y
\mbox{ on $\partial R$.}
\end{align*}
Let the domain of the boundary value problem be $R = \{ (x, y) \, | \,
0 < x < 4, \, 0 < y < 3 \}$.
Use $h = 1$ for simplicity.

\end{frame}
%%

\begin{frame}\frametitle{Solution}

\begin{align*}
-20 u_{1}^{1} + u_{2}^{1} + u_{1}^{2} + 4 u_{2}^{2}
	&= 4 + e^{-1} + e	\\
u_{1}^{1} - 20 u_{2}^{1} + u_{3}^{1} + 4 u_{1}^{2} + u_{2}^{2} + 4 u_{3}^{2}
	&= 1 + 4 e + e^{2}	\\
u_{2}^{1} - 20 u_{3}^{1} + 4 u_{2}^{2} + u_{3}^{2}
	&= -36 + e + 4 e^{2} + e^{3}  \\
u_{1}^{1} + 4 u_{2}^{1} - 20 u_{1}^{2} + u_{2}^{2}
	&= -26 + e^{-2} + e^{-1}	\\
4 u_{1}^{1} + u_{2}^{1} + 4 u_{3}^{1} + u_{1}^{2} - 20 u_{2}^{2} + u_{3}^{2}
	&= -50 + e^{-1} + e	\\
4 u_{2}^{1} + u_{3}^{1} + u_{2}^{2} - 20 u_{3}^{2}
	&= -104 + 4 e + e^{2}	.
\end{align*}

\end{frame}
%%

%\begin{frame}\frametitle{Homework}

%\begin{itemize}
%\item Read Section $x.y$
%\item Exercises: 
%\end{itemize}

%\end{frame}
%%

%%%
\end{document}

%%%%
%%%% EOF
%%%%
