Discrete Poisson equation: Difference between revisions

Reverted to revision 495433419 by Kri: Solution to the system is independent of sign change. (TW)
m (A and D are matrices and do not need to be enclosed by brackets)
(Reverted to revision 495433419 by Kri: Solution to the system is independent of sign change. (TW))
 
:<math>
( {\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} -+ 4 u_{ij}) = g_{ij}
</math>
 
A =
\begin{bmatrix}
~D & -I & ~0 & ~0 & ~0 & \ldots & ~0 \\
-I & ~D & -I & ~0 & ~0 & \ldots & ~0 \\
~0 & -I & ~D & -I & ~0 & \ldots & ~0 \\
\vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\
~0 & \ldots & ~0 & -I & ~D & -I & ~0 \\
~0 & \ldots & \ldots & ~0 & -I & ~D & -I \\
~0 & \ldots & \ldots & \ldots & ~0 & -I & ~D
\end{bmatrix},
</math>
D =
\begin{bmatrix}
-~4 & ~-1 & ~0 & ~0 & ~0 & \ldots & ~0 \\
~-1 & -~4 & ~-1 & ~0 & ~0 & \ldots & ~0 \\
~0 & ~-1 & -~4 & ~-1 & ~0 & \ldots & ~0 \\
\vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\
~0 & \ldots & ~0 & ~-1 & -~4 & ~-1 & ~0 \\
~0 & \ldots & \ldots & ~0 & ~-1 & -~4 & ~-1 \\
~0 & \ldots & \ldots & \ldots & ~0 & ~-1 & -~4
\end{bmatrix},
</math>
 
:<math>
\begin{bmatrix} U \end{bmatrix} =
U =
\begin{bmatrix} u_{22}, u_{32}, u_{42}, u_{23}, u_{33}, u_{43}, u_{24}, u_{34}, u_{44}
\end{bmatrix}^{T}
A =
\begin{bmatrix}
-~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 \\
~-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 \\
~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{bmatrix}
</math>
b =
\begin{bmatrix}
-\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{bmatrix}.
</math>
D =
\begin{bmatrix}
-~4 & ~-1 & ~0 \\
~-1 & -~4 & ~-1 \\
~0 & ~-1 & -~4 \\
\end{bmatrix}
</math>
 
:<math>
-I =
\begin{bmatrix}
-1 & ~0 & ~0 \\
~0 & -1 & ~0 \\
~0 & ~0 & -1
\end{bmatrix}.
</math>
== Methods of solution ==
 
Because <math> \begin{bmatrix} A \end{bmatrix} </math> is block tridiagonal and sparse, many methods of solution
have been developed to optimally solve this linear system for <math> \begin{bmatrix} U \end{bmatrix} </math>.
Among the methods are a generalized [[Thomas algorithm]], [[cyclic reduction]], [[successive overrelaxation]], and [[Fourier transform]]s. A theoretically optimal <math> O(n) </math> solution can also be computed using [[multigrid methods]].