Diskret Poisson-ekvation

Inom matematiken är den diskreta Poisson-ekvationen den ändliga skillnadsanalogen till Poisson-ekvationen . I den tar den diskreta Laplace-operatören platsen för Laplace-operatören . Den diskreta Poisson-ekvationen används ofta i numerisk analys som en stand-in för den kontinuerliga Poisson-ekvationen, även om den också studeras i sin egen rätt som ett ämne i diskret matematik .

På ett tvådimensionellt rektangulärt rutnät

Genom att använda den numeriska metoden med ändlig skillnad för att diskretisera den 2-dimensionella Poisson-ekvationen (om man antar en enhetlig rumslig diskretisering, ${\displaystyle \Delta x=\Delta y} )$ på ett m × n rutnät ger följande formel:

$$({\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}$$

där $2\leq i\leq m-1$ och $2\leq j\leq n-1$ . Det föredragna arrangemanget av lösningsvektorn är att använda naturlig ordning som, innan man tar bort gränselement, skulle se ut så här:

$$\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}}$$

Detta kommer att resultera i ett mn × mn linjärt system:

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

var

$$_ 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$ är m × m identitetsmatrisen och $D$ , även m × m , ges av:

$$displaystyle 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}},}$$

och $\mathbf {b}$ definieras av

$$\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}}.$$

För varje ekvation av $u_{ij}$ motsvarar kolumnerna i ${\displaystyle D} ett block av$$m$ -komponenter i $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}}$$

medan kolumnerna i $I$ till vänster och höger om $D$ var och en motsvarar andra block av $m$ -komponenter inom $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}}$$

och

$${\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}}$$

respektive.

Av ovanstående kan man sluta sig till att det finns $n$ blockkolumner av $m$ i $A$ . Det är viktigt att notera att föreskrivna värden för $u$ (som vanligtvis ligger på gränsen) skulle få sina motsvarande element borttagna från $I$ och $D$ . För det vanliga fallet att alla noder på gränsen är satta, har vi $2\leq i\leq m-1$ och $2\leq j\leq n-1$ , och systemet skulle ha dimensionerna ( m − 2)( n − 2) × ( m − 2)( n − 2) , där $D$ och $I$ skulle ha dimensioner ( m − 2) × ( m − 2) .

Exempel

För ett 3×3 ( $m=3$ och $n=3$ ) rutnät med alla gränsnoder föreskrivna, skulle systemet se ut så här:

$${\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}}$$

med

$$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]$$

och

$$\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].$$

Som kan ses förs gränsen $u$ s till höger sida av ekvationen. Hela systemet är 9 × 9 medan $D$ och $I$ är 3 × 3 och ges av:

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

och

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

Metoder för lösning

Eftersom ${\begin{bmatrix}A\end{bmatrix}}$ är blocktridiagonal och gles, har många lösningsmetoder utvecklats för att optimalt lösa detta linjära system för [ $\displaystyle {\begin {bmatrix}U\end{bmatrix}}}$ . Bland metoderna finns en generaliserad Thomas-algoritm med en resulterande beräkningskomplexitet av ${\displaystyle O(n^{2.5})} ,$ cyklisk reduktion , successiv överrelaxation som har komplexiteten $O(n^{1.5})$ , och snabb Fourier-transform som är $O(n\log(n))$ . En optimal ${\displaystyle O(n)}-$ lösning kan också beräknas med multigrid-metoder .

Poisson-konvergens av olika iterativa metoder med oändlighetsnormer för residualer mot iterationsantal och datortid.

Ansökningar

Inom beräkningsvätskedynamik , för lösningen av ett inkompressibelt flödesproblem, fungerar inkompressibilitetsvillkoret som en begränsning för trycket. Det finns ingen explicit form tillgänglig för tryck i detta fall på grund av en stark koppling av hastighets- och tryckfälten. I detta tillstånd, genom att ta divergensen av alla termer i momentumekvationen, får man tryckgiftekvationen.

För ett inkompressibelt flöde ges denna begränsning av:

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

där $v_{x}$ är hastigheten i $x$ -riktningen, $v_{y}$ är hastigheten i $y$ och $v_ {z}$ är hastigheten i $z$ -riktningen. Om man tar divergens av momentumekvationen och använder inkompressibilitetsbegränsningen, bildas tryck Poisson-ekvationen ges av:

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

där $\nu$ är vätskans kinematiska viskositet och $V$ är hastighetsvektorn.

Den diskreta Poissons ekvation uppstår i teorin om Markov-kedjor . Det visas som den relativa värdefunktionen för den dynamiska programmeringsekvationen i en Markov-beslutsprocess , och som kontrollvarianten för tillämpning i simuleringsvariansreduktion.

Fotnoter

• Hoffman, Joe D., Numeriska metoder för ingenjörer och forskare, 4:e upplagan. , McGraw–Hill Inc., New York, 1992.
• Sweet, Roland A., SIAM Journal on Numerical Analysis, Vol. 11, nr 3 , juni 1974, 506-520.
•   Tryck, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Avsnitt 20.4. Fourier- och cykliska reduktionsmetoder" . Numeriska recept: The Art of Scientific Computing (3:e upplagan). New York: Cambridge University Press. ISBN 978-0-521-88068-8 .