## Wednesday, 21 August 2013

### Three-diagonal periodic system

Three-diagonal periodic system of linear equations can be solved in a similar way as the pure three-diagonal system. The difference is that now we have additional two coefficients in the matrix of the system ($a_0\ne0$, $c_n \ne0$). This form of a system is common when the boundary conditions are periodic (e.g. periodic cubic splines). The solution is again based on the Gaussian elimination, but because of the additional matrix elements, it requires some more steps. The system is strictly diagonal dominant. It can be proved that it has a unique solution.

There is n+1 equation. Our goal is to solve it for n+1 value of $x_i$. The matrix of the system (size $n+1\times n+1$) is of the following form (additional coefficients are shown in bold font):

\begin{equation}\left(\begin{matrix} b_0 & c_0 & 0   & \dots & 0   & 0  & \mathbf{a_0} \\
a_1 & b_1 & c_1 & \dots & 0   & 0  & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots   & \vdots  & \vdots  \\
0 & 0 & 0 & \dots & a_{n-1} & b_{n-1} & c_{n-1}  \\
\mathbf{c_n} & 0 & 0 & \dots & 0 & a_{n} & b_n \end{matrix}\right)
\left(\begin{matrix} x_0 \\ x_1 \\ \vdots \\ x_{n-1}  \\x_{n}\end{matrix}\right) = \left(\begin{matrix} d_0 \\ d_1 \\ \vdots \\ d_{n-1}  \\d_{n}\end{matrix}\right)
\label{eq:matrix}\nonumber\end{equation}

or in the form of the individual equations ($n+1$ equation with $n+1$ unknown $x_i$):

\begin{eqnarray}
b_0 x_0 + c_0 x_1 + a_0 x_n &=& d_0,\nonumber\\
a_1 x_0 + b_1 x_1 + c_1 x_2 &=& d_1,\nonumber\\
\dots &=& \dots, \nonumber\\
a_i x_{i-1}+ b_i x_i + c_i x_{i+1} &=& d_i,\nonumber\\
\dots &=& \dots ,\nonumber\\
a_{n-1} x_{n-2} +b_{n-1} x_{n-1} + c_{n-1} x_{n} &=& d_{n-1},\nonumber\\
c_n x_{0} + a_{n} x_{n-1} +b_{n} x_{n} &=& d_{n}.\nonumber
\end{eqnarray}

## Saturday, 17 August 2013

### Three-diagonal system of linear equations

In this post I'll show a fast and accurate solution for the three-diagonal system of linear equations based on Gaussian elimination. In the matrix notation the system has the following form:

\begin{equation}\left(\begin{matrix} b_0 & c_0 & 0   & \dots & 0   & 0  & 0 \\
a_1 & b_1 & c_1 & \dots & 0   & 0  & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots   & \vdots  & \vdots  \\
0 & 0 & 0 & \dots & a_{n-1} & b_{n-1} & c_{n-1}  \\
0 & 0 & 0 & \dots & 0 & a_{n} & b_n \end{matrix}\right)
\left(\begin{matrix} x_0 \\ x_1 \\ \vdots \\ x_{n-1}  \\x_{n}\end{matrix}\right) = \left(\begin{matrix} d_0 \\ d_1 \\ \vdots \\ d_{n-1}  \\d_{n}\end{matrix}\right)
\label{eq:matrix00}\nonumber\end{equation}

or in the form of the individual equations ($n+1$ equation with $n+1$ unknown $x_i$):

\begin{eqnarray}
b_0 x_0 + c_0 x_1 &=& d_0,\nonumber\\
a_1 x_0 + b_1 x_1 + c_1 x_2 &=& d_1,\nonumber\\
\dots &=& \dots, \nonumber\\
a_i x_{i-1}+ b_i x_i + c_i x_{i+1} &=& d_i,\nonumber\\
\dots &=& \dots ,\nonumber\\
a_{n-1} x_{n-2} +b_{n-1} x_{n-1} + c_{n-1} x_{n} &=& d_{n-1},\nonumber\\
a_{n} x_{n-1} +b_{n} x_{n} &=& d_{n}.\nonumber
\end{eqnarray}