Jump to content

Main menu Navigation ●Main page ●Contents ●Current events ●Random article ●About Wikipedia ●Contact us ●Donate Contribute ●Help ●Learn to edit ●Community portal ●Recent changes ●Upload file

●Create account ●Log in ●Create account ● Log in Pages for logged out editors learn more ●Contributions ●Talk

(Top) 1 On a two-dimensional rectangular grid 2 Example 3 Methods of solution 4 Applications 5 Footnotes 6 References

Discrete Poisson equation

Add links ●Article ●Talk ●Read ●Edit ●View history Tools Actions ●Read ●Edit ●View history General ●What links here ●Related changes ●Upload file ●Special pages ●Permanent link ●Page information ●Cite this page ●Get shortened URL ●Download QR code ●Wikidata item Print/export ●Download as PDF ●Printable version Appearance From Wikipedia, the free encyclopedia

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (April 2009) (Learn how and when to remove this message)

Inmathematics, the discrete Poisson equation is the finite difference analog of the Poisson equation. In it, the discrete Laplace operator takes the place of the Laplace operator. The discrete Poisson equation is frequently used in numerical analysis as a stand-in for the continuous Poisson equation, although it is also studied in its own right as a topic in discrete mathematics.

On a two-dimensional rectangular grid[edit]

Using the finite difference numerical method to discretize the 2-dimensional Poisson equation (assuming a uniform spatial discretization, $\Delta x=\Delta y$ ) on an $m \times n$ grid gives the following formula:^[1]

({\nabla }^{2}u)_{ij}={\frac {1}{\Delta x^{2}}}(u_{i+1,j}+u_{i-1,j}+u_{i,j+1}+u_{i,j-1}-4u_{ij})=g_{ij}

({\nabla }^{2}u)_{ij}={\frac {1}{\Delta x^{2}}}(u_{i+1,j}+u_{i-1,j}+u_{i,j+1}+u_{i,j-1}-4u_{ij})=g_{ij}

where

2\leq i\leq m-1

and

2\leq j\leq n-1

. The preferred arrangement of the solution vector is to use natural ordering which, prior to removing boundary elements, would look like:

\mathbf {u} ={\begin{bmatrix}u_{11},u_{21},\ldots ,u_{m1},u_{12},u_{22},\ldots ,u_{m2},\ldots ,u_{mn}\end{bmatrix}}^{\mathsf {T}}

\mathbf {u} ={\begin{bmatrix}u_{11},u_{21},\ldots ,u_{m1},u_{12},u_{22},\ldots ,u_{m2},\ldots ,u_{mn}\end{bmatrix}}^{\mathsf {T}}

This will result in an $mn \times mn$ linear system:

A\mathbf {u} =\mathbf {b}

A\mathbf {u} =\mathbf {b}

where

A={\begin{bmatrix}~D&-I&~0&~0&~0&\cdots &~0\\-I&~D&-I&~0&~0&\cdots &~0\\~0&-I&~D&-I&~0&\cdots &~0\\\vdots &\ddots &\ddots &\ddots &\ddots &\ddots &\vdots \\~0&\cdots &~0&-I&~D&-I&~0\\~0&\cdots &\cdots &~0&-I&~D&-I\\~0&\cdots &\cdots &\cdots &~0&-I&~D\end{bmatrix}},

A={\begin{bmatrix}~D&-I&~0&~0&~0&\cdots &~0\\-I&~D&-I&~0&~0&\cdots &~0\\~0&-I&~D&-I&~0&\cdots &~0\\\vdots &\ddots &\ddots &\ddots &\ddots &\ddots &\vdots \\~0&\cdots &~0&-I&~D&-I&~0\\~0&\cdots &\cdots &~0&-I&~D&-I\\~0&\cdots &\cdots &\cdots &~0&-I&~D\end{bmatrix}},

$I$ is the $m \times m$ identity matrix, and $D$ , also $m \times m$ , is given by:^[2]

D={\begin{bmatrix}~4&-1&~0&~0&~0&\cdots &~0\\-1&~4&-1&~0&~0&\cdots &~0\\~0&-1&~4&-1&~0&\cdots &~0\\\vdots &\ddots &\ddots &\ddots &\ddots &\ddots &\vdots \\~0&\cdots &~0&-1&~4&-1&~0\\~0&\cdots &\cdots &~0&-1&~4&-1\\~0&\cdots &\cdots &\cdots &~0&-1&~4\end{bmatrix}},

D={\begin{bmatrix}~4&-1&~0&~0&~0&\cdots &~0\\-1&~4&-1&~0&~0&\cdots &~0\\~0&-1&~4&-1&~0&\cdots &~0\\\vdots &\ddots &\ddots &\ddots &\ddots &\ddots &\vdots \\~0&\cdots &~0&-1&~4&-1&~0\\~0&\cdots &\cdots &~0&-1&~4&-1\\~0&\cdots &\cdots &\cdots &~0&-1&~4\end{bmatrix}},

and

\mathbf {b}

is defined by

\mathbf {b} =-\Delta x^{2}{\begin{bmatrix}g_{11},g_{21},\ldots ,g_{m1},g_{12},g_{22},\ldots ,g_{m2},\ldots ,g_{mn}\end{bmatrix}}^{\mathsf {T}}.

\mathbf {b} =-\Delta x^{2}{\begin{bmatrix}g_{11},g_{21},\ldots ,g_{m1},g_{12},g_{22},\ldots ,g_{m2},\ldots ,g_{mn}\end{bmatrix}}^{\mathsf {T}}.

For each $u_{ij}$ equation, the columns of $D$ correspond to a block of $m$ components in $u$ :

{\begin{bmatrix}u_{1j},&u_{2j},&\ldots ,&u_{i-1,j},&u_{ij},&u_{i+1,j},&\ldots ,&u_{mj}\end{bmatrix}}^{\mathsf {T}}

{\begin{bmatrix}u_{1j},&u_{2j},&\ldots ,&u_{i-1,j},&u_{ij},&u_{i+1,j},&\ldots ,&u_{mj}\end{bmatrix}}^{\mathsf {T}}

while the columns of

I

to the left and right of

D

each correspond to other blocks of

m

components within

u

{\begin{bmatrix}u_{1,j-1},&u_{2,j-1},&\ldots ,&u_{i-1,j-1},&u_{i,j-1},&u_{i+1,j-1},&\ldots ,&u_{m,j-1}\end{bmatrix}}^{\mathsf {T}}

{\begin{bmatrix}u_{1,j-1},&u_{2,j-1},&\ldots ,&u_{i-1,j-1},&u_{i,j-1},&u_{i+1,j-1},&\ldots ,&u_{m,j-1}\end{bmatrix}}^{\mathsf {T}}

and

{\begin{bmatrix}u_{1,j+1},&u_{2,j+1},&\ldots ,&u_{i-1,j+1},&u_{i,j+1},&u_{i+1,j+1},&\ldots ,&u_{m,j+1}\end{bmatrix}}^{\mathsf {T}}

{\begin{bmatrix}u_{1,j+1},&u_{2,j+1},&\ldots ,&u_{i-1,j+1},&u_{i,j+1},&u_{i+1,j+1},&\ldots ,&u_{m,j+1}\end{bmatrix}}^{\mathsf {T}}

respectively.

From the above, it can be inferred that there are $n$ block columns of $m$ in $A$ . It is important to note that prescribed values of $u$ (usually lying on the boundary) would have their corresponding elements removed from $I$ and $D$ . For the common case that all the nodes on the boundary are set, we have $2\leq i\leq m-1$ and $2\leq j\leq n-1$ , and the system would have the dimensions $(m - 2)(n - 2) \times (m - 2)(n - 2)$ , where $D$ and $I$ would have dimensions $(m - 2) \times (m - 2)$ .

Example[edit]

For a 3×3 ( $m=3$ and $n=3$ ) grid with all the boundary nodes prescribed, the system would look like:

{\begin{bmatrix}U\end{bmatrix}}={\begin{bmatrix}u_{22},u_{32},u_{42},u_{23},u_{33},u_{43},u_{24},u_{34},u_{44}\end{bmatrix}}^{\mathsf {T}}

{\begin{bmatrix}U\end{bmatrix}}={\begin{bmatrix}u_{22},u_{32},u_{42},u_{23},u_{33},u_{43},u_{24},u_{34},u_{44}\end{bmatrix}}^{\mathsf {T}}

with

A=\left[{\begin{array}{ccc|ccc|ccc}~4&-1&~0&-1&~0&~0&~0&~0&~0\\-1&~4&-1&~0&-1&~0&~0&~0&~0\\~0&-1&~4&~0&~0&-1&~0&~0&~0\\\hline -1&~0&~0&~4&-1&~0&-1&~0&~0\\~0&-1&~0&-1&~4&-1&~0&-1&~0\\~0&~0&-1&~0&-1&~4&~0&~0&-1\\\hline ~0&~0&~0&-1&~0&~0&~4&-1&~0\\~0&~0&~0&~0&-1&~0&-1&~4&-1\\~0&~0&~0&~0&~0&-1&~0&-1&~4\end{array}}\right]

A=\left[{\begin{array}{ccc|ccc|ccc}~4&-1&~0&-1&~0&~0&~0&~0&~0\\-1&~4&-1&~0&-1&~0&~0&~0&~0\\~0&-1&~4&~0&~0&-1&~0&~0&~0\\\hline -1&~0&~0&~4&-1&~0&-1&~0&~0\\~0&-1&~0&-1&~4&-1&~0&-1&~0\\~0&~0&-1&~0&-1&~4&~0&~0&-1\\\hline ~0&~0&~0&-1&~0&~0&~4&-1&~0\\~0&~0&~0&~0&-1&~0&-1&~4&-1\\~0&~0&~0&~0&~0&-1&~0&-1&~4\end{array}}\right]

and

\mathbf {b} =\left[{\begin{array}{l}-\Delta x^{2}g_{22}+u_{12}+u_{21}\\-\Delta x^{2}g_{32}+u_{31}~~~~~~~~\\-\Delta x^{2}g_{42}+u_{52}+u_{41}\\-\Delta x^{2}g_{23}+u_{13}~~~~~~~~\\-\Delta x^{2}g_{33}~~~~~~~~~~~~~~~~\\-\Delta x^{2}g_{43}+u_{53}~~~~~~~~\\-\Delta x^{2}g_{24}+u_{14}+u_{25}\\-\Delta x^{2}g_{34}+u_{35}~~~~~~~~\\-\Delta x^{2}g_{44}+u_{54}+u_{45}\end{array}}\right].

\mathbf {b} =\left[{\begin{array}{l}-\Delta x^{2}g_{22}+u_{12}+u_{21}\\-\Delta x^{2}g_{32}+u_{31}~~~~~~~~\\-\Delta x^{2}g_{42}+u_{52}+u_{41}\\-\Delta x^{2}g_{23}+u_{13}~~~~~~~~\\-\Delta x^{2}g_{33}~~~~~~~~~~~~~~~~\\-\Delta x^{2}g_{43}+u_{53}~~~~~~~~\\-\Delta x^{2}g_{24}+u_{14}+u_{25}\\-\Delta x^{2}g_{34}+u_{35}~~~~~~~~\\-\Delta x^{2}g_{44}+u_{54}+u_{45}\end{array}}\right].

As can be seen, the boundary $u$ 's are brought to the right-hand-side of the equation.^[3] The entire system is $9 \times 9$ while $D$ and $I$ are $3 \times 3$ and given by:

D={\begin{bmatrix}~4&-1&~0\\-1&~4&-1\\~0&-1&~4\\\end{bmatrix}}

D={\begin{bmatrix}~4&-1&~0\\-1&~4&-1\\~0&-1&~4\\\end{bmatrix}}

and

-I={\begin{bmatrix}-1&~0&~0\\~0&-1&~0\\~0&~0&-1\end{bmatrix}}.

-I={\begin{bmatrix}-1&~0&~0\\~0&-1&~0\\~0&~0&-1\end{bmatrix}}.

Methods of solution[edit]

Because ${\begin{bmatrix}A\end{bmatrix}}$ is block tridiagonal and sparse, many methods of solution have been developed to optimally solve this linear system for ${\begin{bmatrix}U\end{bmatrix}}$ . Among the methods are a generalized Thomas algorithm with a resulting computational complexity of $O(n^{2.5})$ , cyclic reduction, successive overrelaxation that has a complexity of $O(n^{1.5})$ , and Fast Fourier transforms which is ${\displaystyle O(n\log($ . An optimal ${\displaystyle O($ solution can also be computed using multigrid methods.^[4]

Poisson convergence of various iterative methods with infinity norms of residuals against iteration count and computer time.

Applications[edit]

Incomputational fluid dynamics, for the solution of an incompressible flow problem, the incompressibility condition acts as a constraint for the pressure. There is no explicit form available for pressure in this case due to a strong coupling of the velocity and pressure fields. In this condition, by taking the divergence of all terms in the momentum equation, one obtains the pressure poisson equation.

For an incompressible flow this constraint is given by:

{\frac {\partial v_{x}}{\partial x}}+{\frac {\partial v_{y}}{\partial y}}+{\frac {\partial v_{z}}{\partial z}}=0

{\frac {\partial v_{x}}{\partial x}}+{\frac {\partial v_{y}}{\partial y}}+{\frac {\partial v_{z}}{\partial z}}=0

where

v_{x}

is the velocity in the

x

direction,

v_{y}

is velocity in

y

and

v_{z}

is the velocity in the

z

direction. Taking divergence of the momentum equation and using the incompressibility constraint, the pressure Poisson equation is formed given by:

\nabla ^{2}p=f(\nu ,V)

\nabla ^{2}p=f(\nu ,V)

where

\nu

is the kinematic viscosity of the fluid and

V

is the velocity vector.^[5]

The discrete Poisson's equation arises in the theory of Markov chains. It appears as the relative value function for the dynamic programming equation in a Markov decision process, and as the control variate for application in simulation variance reduction.^[6]^[7]^[8]

Footnotes[edit]

^ Hoffman, Joe (2001), "Chapter 9. Elliptic partial differential equations", Numerical Methods for Engineers and Scientists (2nd ed.), McGraw–Hill, ISBN 0-8247-0443-6.

^ Golub, Gene H. and C. F. Van Loan, Matrix Computations, 3rd Ed., The Johns Hopkins University Press, Baltimore, 1996, pages 177–180.

^ Cheny, Ward and David Kincaid, Numerical Mathematics and Computing 2nd Ed., Brooks/Cole Publishing Company, Pacific Grove, 1985, pages 443–448.

^ CS267: Notes for Lectures 15 and 16, Mar 5 and 7, 1996, https://people.eecs.berkeley.edu/~demmel/cs267/lecture24/lecture24.html

^ Fletcher, Clive A. J., Computational Techniques for Fluid Dynamics: Vol I, 2nd Ed., Springer-Verlag, Berlin, 1991, page 334–339.

^ S. P. Meyn and R.L. Tweedie, 2005. Markov Chains and Stochastic Stability. Second edition to appear, Cambridge University Press, 2009.

^ S. P. Meyn, 2007. Control Techniques for Complex Networks Archived December 16, 2014, at the Wayback Machine, Cambridge University Press, 2007.

^ Asmussen, Søren, Glynn, Peter W., 2007. "Stochastic Simulation: Algorithms and Analysis". Springer. Series: Stochastic Modelling and Applied Probability, Vol. 57, 2007.

References[edit]

Hoffman, Joe D., Numerical Methods for Engineers and Scientists, 4th Ed., McGraw–Hill Inc., New York, 1992.
Sweet, Roland A., SIAM Journal on Numerical Analysis, Vol. 11, No. 3 , June 1974, 506–520.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 20.4. Fourier and Cyclic Reduction Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Archived from the original on August 11, 2011. Retrieved August 18, 2011.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Discrete_Poisson_equation&oldid=1217966922" Categories: ●Finite differences ●Numerical differential equations Hidden categories: ●Webarchive template wayback links ●Use American English from March 2019 ●All Wikipedia articles written in American English ●Articles with short description ●Short description is different from Wikidata ●Use mdy dates from March 2019 ●Articles lacking in-text citations from April 2009 ●All articles lacking in-text citations ●This page was last edited on 8 April 2024, at 23:46 (UTC). ●Text is available under the Creative Commons Attribution-ShareAlike License 4.0; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. ●Privacy policy ●About Wikipedia ●Disclaimers ●Contact Wikipedia ●Code of Conduct ●Developers ●Statistics ●Cookie statement ●Mobile view