next up previous
Next: 5. Partial Differential Equations Up: 4.3 Boundary Value Problems Previous: 4.3.1 Shooting Method


4.3.2 Relaxation Method

Discretize $x$ to transform a given DE into a set of algebraic equations. For example, applying DDST to
$\displaystyle \frac{d^{2}y}{dx^{2}}$ $\textstyle =$ $\displaystyle b(x,y)$  

we find
$\displaystyle \frac{d^{2}y}{dx^{2}}$ $\textstyle \approx$ $\displaystyle \frac{1}{(\Delta x)^{2}}[y_{i+1}-2y_{i}+y_{i-1}]$  

which leads to the set of equations
$\displaystyle y_{i+1}-2y_{i}+y_{i-1}-b_{i}(\Delta x)^{2}$ $\textstyle =$ $\displaystyle 0\,,\;\;i=2,\dots M-1$  

Since we have a BVP, $y_{1}$ and $y_{M}$ will be given.

Let $\mbox{$\bf y$}^{(1)} \equiv \{y_{i}\}$ be an inaccurate (estimated?) solution. The error components
$\displaystyle e_{i}$ $\textstyle =$ $\displaystyle y_{i+1}-2y_{i}+y_{i-1}-b_{i}(\Delta x)^{2}\,,\;\;i=2,\dots M-1$  

together with $e_{1}=e_{M}=0$ then define an error vector $\mbox{$\bf e$}^{(1)}$.
How to modify $\mbox{$\bf y$}^{(1)}$ to make $\mbox{$\bf e$}^{(1)}$ disappear? $\Longrightarrow$ Expand $e_{i}$ linearly:
$\displaystyle e_{i}(y_{i-1}+\Delta y_{i-1},y_{i}+\Delta y_{i},y_{i+1}+\Delta y_{i+1})$ $\textstyle \approx$    
    $\displaystyle \approx e_{i} + \frac{\partial e_{i}}{\partial y_{i-1}} \Delta y_...
...al y_{i}} \Delta y_{i}
+ \frac{\partial e_{i}}{\partial y_{i+1}} \Delta y_{i+1}$  
    $\displaystyle \equiv e_{i} +\alpha_{i} \Delta y_{i-1}
+\beta_{i} \Delta y_{i} + \gamma_{i} \Delta y_{i+1} \;\;(i=1,\dots M)$  

This modified error vector is called $\mbox{$\bf e$}^{(2)}$. We want it to vanish, $\mbox{$\bf e$}^{(2)}=0$:
$\displaystyle \mbox{${\bf A}$} \cdot \Delta \mbox{$\bf y$}$ $\textstyle =$ $\displaystyle - \mbox{$\bf e$}^{(1)}
\;\;\;\;{\rm with}\;\;\;
\mbox{${\bf A}$}=...
... \gamma_{2} & 0 \\
& \ddots & \ddots & \ddots \\
&& 0 & 1
\end{array} \right)$  

Thus our system of equations is tridiagonal: $\Longrightarrow$Recursion technique!





EXAMPLE:
$\displaystyle \frac{d^{2}y}{dx^{2}}$ $\textstyle =$ $\displaystyle -\frac{1}{(1+y)^{2}}
\;\;\;\;{\rm with} \;\;\;y(0)=y(1)=0$  

DDST leads to $
e_{i} = y_{i+1}-2y_{i}+y_{i-1}+(\Delta x)^{2}/(1+y_{i})^{2}
$. Expand:
$\displaystyle \alpha_{i}$ $\textstyle \equiv$ $\displaystyle \frac{\partial e_{i}}{\partial y_{i-1}} =1\,;
\hspace{1em}
\gamma...
...-2\left[ 1+ \frac{(\Delta x)^{2}}{(1+y_{i})^{3}} \right]
\, \;\;\;i=2,\dots M-1$  

Start the downwards recursion: $g_{M-1}=-\alpha_{M}/\beta_{M}=0$ and $h_{M-1}=-e_{M}/\beta_{M}=0$.
$\displaystyle g_{i-1}$ $\textstyle =$ $\displaystyle \frac{-\alpha_{i}}{\beta_{i}+\gamma_{i}g_{i}}=
\frac{-1}{\beta_{i}+g_{i}}\,;\;\;
h_{i-1}=\frac{-e_{i}-h_{i}}{\beta_{i}+g_{i}}$  

brings us down to $g_{1},h_{1}$. Putting
$\displaystyle \Delta y_{1}$ $\textstyle =$ $\displaystyle \frac{-e_{1}-\gamma_{1}h_{1}}{\beta_{1}+\gamma_{1}g_{1}}=e_{1}
(=0)$  

we take the upwards recursion
$\displaystyle \Delta y_{i+1}$ $\textstyle =$ $\displaystyle g_{i}\Delta y_{i}+h_{i}\,;\;\;i=1,\dots M-1$  

Improve $y_{i} \longrightarrow y_{i}+\Delta y_{i}$ and iterate.

next up previous
Next: 5. Partial Differential Equations Up: 4.3 Boundary Value Problems Previous: 4.3.1 Shooting Method
Franz J. Vesely Oct 2005
See also:
"Computational Physics - An Introduction," Kluwer-Plenum 2001