1.

Poisson’s Equation in 2D
We will now examine the general heat conduction equation,
q
Tt = κ∆T + .
ρc
in the 2-dimensional case, assuming a steady state problem (Tt = 0).
We get Poisson’s equation:
Poisson’s Equation in 2D
−uxx (x, y) − uyy (x, y) = f (x, y), (x, y) ∈ Ω = (0, 1) × (0, 1),
Analytic Solutions

where we used the unit square as computational domain. A Finite Difference . . .

A Linear System of . . .
Again, we will only deal with Dirichlet boundary conditions: Direct Solution of the LSE

Classification of PDE
u(x, y) = g(x, y) for x ∈ ∂Ω

Page 1 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
2. Analytic Solutions
We will concentrate on the homogenous equation,
−uxx (x, y) − uyy (x, y) = 0, (x, y) ∈ Ω = (0, 1) × (0, 1),
and consider the boundary conditions

u(0, y) = u(1, y) = 0 0 ≤ y ≤ 1,
u(x, 0) = 0 0 ≤ x ≤ 1, Poisson’s Equation in 2D

u(x, 1) = g(x) 0 < x < 1. Analytic Solutions

A Finite Difference . . .

A Linear System of . . .
2.1. Separation of Variables – revisited
Direct Solution of the LSE
Similar to the 1D heat equation, we use the ansatz Classification of PDE

u(x, y) = X(x)Y (y)

to get
Xxx (x) Yyy (y)
− =
X(x) Y (y)
Consequently, left hand side and right hand side have to be equal to Page 2 of 16
a constant λ. Introduction to Scientific Computing
Poisson’s Equation in 2D
Michael Bader
2.2. Particular solutions
For the function X(x), we get the eigenvalue problem
−Xxx (x) = λX(x), 0 < x < 1,
X(0) = X(1) = 0.
We already know that the eigenvalues are
λk = (kπ)2 ,
Poisson’s Equation in 2D
and the respective eigenfunctions are Analytic Solutions

Xk (x) = sin(kπx). A Finite Difference . . .

A Linear System of . . .
The function Y (0) has to satisfy similar equations,
Direct Solution of the LSE

(Yk )yy (y) = λYk (y), 0 < y < 1, Classification of PDE

Yk (0) = 0,
however, note the absence of the minus sign!
√ √
Thus, Yk (y) is a linear combination of e λk y
and e− λk y
.
With Yk (0) = 0, we get the solution
Page 3 of 16
Yk (y) = sinh(kπy),
Introduction to Scientific Computing

which satisfies the boundary condition Yk (1) = sinh(kπ). Poisson’s Equation in 2D

Michael Bader
2.3. Fourier’s method
We have therefore computed particular solutions
uk (x, y) = sin(kπx) sinh(kπy)
that solve the boundary value problems
−uxx (x) − uyy (y) = 0 0 < x, y < 1,
u(0, y) = u(1, y) = 0, 0≤y≤1
u(x, 0) = 0, 0≤x≤1 Poisson’s Equation in 2D

u(x, 1) = sinh(kπ), 0 < x < 1. Analytic Solutions

A Finite Difference . . .

A Linear System of . . .
Thus, if we can represent the boundary function g(x) by
Direct Solution of the LSE
∞
Classification of PDE
X
g(x) = gk sin(kπx),
k=1

then the function

∞
X gk
u(x, y) = ck sin(kπx) sinh(kπy), ck =
k=1
sinh(kπ)
solves the given boundary problem for Page 4 of 16

u(x, 1) = g(x), 0 < x < 1. Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
3. A Finite Difference Scheme
3.1. Discretization of the computational domain
We use a rectangular, equidistant grid of n × n grid points with mesh
size h = n1 :
Ωh := {(ih, jh) : i, j = 1, . . . , n − 1}

Poisson’s Equation in 2D

Analytic Solutions
x i,j+1
A Finite Difference . . .
x i−1,j x i,j x i+1,j A Linear System of . . .

Direct Solution of the LSE

x i,j−1
Classification of PDE

hy
hx

• We have chosen h = hx = hy
Page 5 of 16
• function u will be computed at grid points xi,j ,
Introduction to Scientific Computing
i.e. we have unknowns ui,j ≈ u(xi,j ). Poisson’s Equation in 2D
Michael Bader
3.2. Discretization of the derivatives – Difference Quotients
Replace derivatives by difference quotients:
• first derivatives: forward, backward, or central differences
u(xk+1 ) − u(xk )





 hx
∂u u(xk ) − u(xk−1 )

(xk ) ≈
∂x  hx
 Poisson’s Equation in 2D


 u(x k+1 ) − u(xk−1 )
Analytic Solutions

2hx
A Finite Difference . . .

• second derivatives: standard second-order discretization (3- A Linear System of . . .

point-stencil) Direct Solution of the LSE

Classification of PDE
∂2u u(xk+1 ) − 2u(xk ) + u(xk−1 )
2
(xk ) ≈
∂x h2x

In stencil notation:
• [0 −1 1], [−1 1 0], or [−1 0 1] for the first derivatives
• [1 −2 1] for the second derivatives Page 6 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
3.3. 2D stencils
Using standard second order discretization, we get
ui+1,j − 2ui,j + ui−1,j ui,j+1 − 2ui,j + ui,j−1
(uxx + uyy )(xi,j ) ≈ +
h2 h2
Thus, discretization of the PDE
−uxx (x, y) − uyy (x, y) = f (x, y)
Poisson’s Equation in 2D
leads to the linear system of equations
Analytic Solutions
1
− 2 (ui+1,j + ui,j+1 − 4ui,j + ui,j−1 + ui−1,j ) = f (xi,j ) A Finite Difference . . .
h A Linear System of . . .

for i, j = 1, . . . , n − 1. Direct Solution of the LSE

Classification of PDE
This is often represented using a 2D stencil:
−1
 
−1
4
 −1 4 −1  −1 −1
−1
Page 7 of 16

−1 Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
4. A Linear System of Equations
4.1. Homogeneous Dirichlet boundary conditions
To account for homogeneous Dirichlet boundary conditions, we set

u0,j = un,j = ui,0 = ui,n = 0

for i, j = 0, . . . , n.
Poisson’s Equation in 2D
Altogether, we get the following linear system of equations: Analytic Solutions

u0,j = un,j = ui,0 = ui,n = 0 for i, j = 0, . . . , n A Finite Difference . . .

A Linear System of . . .
(ui+1,j + ui,j+1 − 4ui,j + ui,j−1 + ui−1,j )
− = f (xi,j ) for i, j = 1, . . . , n − 1 Direct Solution of the LSE
h2
Classification of PDE

This system has

• N = (n + 1) × (n + 1) unknowns ui,j , (i, j = 0, . . . , n);
• N = (n + 1) × (n + 1) equations.
Question: Is there a unique solution?
Page 8 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
4.2. LSE in matrix-vector notation
We can write the previous system of equation in matrix-vector nota-
tion,
Ah uh = fh ,
where
• uh is the vector
uh := (u1,1 , . . . , u1,n , u2,1 , . . . un−2,n−1 , un−1,1 , . . . , un−1,n−1 )T ,
Poisson’s Equation in 2D

• fh , similar to uh , is the vector of the right hand sides fi,j = Analytic Solutions

f (xi,j ); A Finite Difference . . .

A Linear System of . . .
• Ah is the following sparse matrix
Direct Solution of the LSE
4 −1 −1
 
Classification of PDE
. . ..
 −1 . . . . .
 


 ... ... ... ... 

1 

... ... ..

.

h2  −1 −1 

.. .. .. ..

. . . .
 
 
 . .. .. .. 
 . . −1  Page 9 of 16
−1 −1 4 Introduction to Scientific Computing
Poisson’s Equation in 2D
Michael Bader
Block-Tridiagonal Matrix:

Ah is more precisely described by the following block-tridiagonal ma-

trix:  
Bh −I 0 · · · 0
. . 
 −I Bh −I . . .. 

1  .. .. .. 
Ah = 2  0 . . . 0 
h 
 . .

 .. . . −I Bh −I 

Poisson’s Equation in 2D
0 · · · 0 −I Bh Analytic Solutions

where Bh and I are (n − 1) × (n − 1) matrices. A Finite Difference . . .

A Linear System of . . .
While I is the unity matrix, Bh is given by Direct Solution of the LSE
  Classification of PDE
4 −1 0 ···
0
.. 
...
 −1 4 −1 . 


Bh =  ... ... ... 
 0 0 
 . ..
 ..

. −1 4 −1 
0 · · · 0 −1 4
Page 10 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
4.3. Properties of the system matrix Ah
Resume:
• Ah is a sparse (n − 1)2 × (n − 1)2 -matrix, and has a so-called
band structure;
• Ah is block-tridiagonal
• all diagonal elements of Ah are 4;
Poisson’s Equation in 2D
• in each row, between 2 and 4 elements are non-zeroes (−1),
Analytic Solutions
depending on whether the respective unknown is close to the
A Finite Difference . . .
boundary;
A Linear System of . . .
Conclusions: Direct Solution of the LSE

• Ah is therefore diagonal dominant Classification of PDE

• As Ah is diagonal dominant, it is also positive definite.

• Thus, the system has a unique solution!

Page 11 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
5. Direct Solution of the LSE
5.1. Gaussian elimination for band matrices
• Ah is a band-matrix (band-width is n − 1)
• Gaussian elimination on a LSE of N unknowns usually requires
O(N 3 ) operations.
Poisson’s Equation in 2D
• for band matrices this reduces to
Analytic Solutions
2
O(N × bandwidth ) operations. A Finite Difference . . .

A Linear System of . . .

Solving our LSE using Gaussian elimination therefore requires Direct Solution of the LSE

Classification of PDE
O(N 2 ) = O(n4 ) operations.

The numerical error of our method is only O(n−2 ).

Thus, to reduce an error to half of its size, we have to
• use twice as many unknowns;
• wait four times as long!
Page 12 of 16

⇒ Faster methods to solve the LSE are needed! Introduction to Scientific Computing
Poisson’s Equation in 2D
Michael Bader
5.2. Faster methods
Direct methods:
• use a clever numbering of the unknowns (not line by line but
“divide and conquer”)
⇒ nested dissection, O(n3 )
• use eigenvectors of the matrix, and Fast Sine Transform
⇒ Fast Poisson Solvers, O(n2 log n) Poisson’s Equation in 2D

Analytic Solutions
Iterative methods:
A Finite Difference . . .
• solve system line by line, but do this again and again A Linear System of . . .
⇒ Jacobi or Gauss-Seidel relaxation, O(n4 ) Direct Solution of the LSE

Classification of PDE
• clever weghting of corrections
⇒ SOR (successive over-relaxation), O(n3 )
• reformulate LSE as minimization problem
⇒ Krylow methods, Conjugate Gradients, O(n3 )
• use different mesh sizes and combine their solutions
⇒ Multigrid methods, O(n2 ) Page 13 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
6. Classification of PDE
Classification similar to ODE:
• first/second/. . . order according to order of derivatives
• linear/non-linear

Example: General linear PDE of second order:

d X
X d d
X Poisson’s Equation in 2D

ai,j (~x) · uxi ,xj (~x) + ai (~x) · uxi (~x) + a(~x) · u(~x) = f (~x) Analytic Solutions
i=1 j=1 i=1 A Finite Difference . . .

A Linear System of . . .
Some linear PDE of second order:
Direct Solution of the LSE

• 1D heat equation: x1 =t,

b x2 =x
b Classification of PDE

• 2D Poisson equation: x1 =x,

b x2 =y
b
• 1D wave equation (utt = uxx ): x1 =t,
b x2 =x
b
• etc.

Page 14 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
6.1. Boundary Conditions
Among other things, elliptic, parabolic, and hyperbolic PDE differ in
the type of boundary or initial conditions they require.

Examples:
• Laplace equation, Poisson equation (elliptic):

−uxx − uyy = f Poisson’s Equation in 2D

⇒ boundary conditions Analytic Solutions

A Finite Difference . . .
• heat equation (parabolic): A Linear System of . . .

Direct Solution of the LSE

ut = ∆u
Classification of PDE
⇒ initial condition for t, boundary conditions for x
• wave equation (hyperbolic):

utt = ∆u

⇒ initial conditions for u and ut

Page 15 of 16

Introduction to Scientific Computing

Poisson’s Equation in 2D
Michael Bader
6.2. Elliptic, Parabolic, and Hyperbolic PDE
General linear PDE of second order:
X d
d X d
X
ai,j (~x) · uxi ,xj (~x) + ai (~x) · uxi (~x) + a(~x) · u(~x) = f (~x)
i=1 j=1 i=1

Three types of PDE:

• elliptic PDE:
the matrix A of the ai,j is positive or negative definite Poisson’s Equation in 2D

Analytic Solutions
• parabolic PDE: A Finite Difference . . .
one eigenvalue of A is zero, the others have the same sign, and
A Linear System of . . .
the rank of A together with the vector of the ai is full (d)
Direct Solution of the LSE
• hyperbolic PDE: Classification of PDE
A has 1 pos. and d − 1 neg. eigenvalues or vice versa.
If the ai,j are functions of ~x:
• elliptic in ~x:
the matrix A of the ai,j (~x) is positive or negative definite for a
certain ~x
Page 16 of 16
• elliptic:
the matrix A of the ai,j (~x) is positive or negative definite for all ~x Introduction to Scientific Computing
Poisson’s Equation in 2D
Michael Bader