Direct Solver

$\def \hieruit {\quad \Longrightarrow \quad}$ We will take a closer look at the procedure which forms the matrix $(1-M^2)$ out of the tri-diagonal matrix $A$. It is assumed that the tri-diagonal system matrix $A$ has been (re)normalized. Then the general form of such a matrix is: $$ \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & a_{43}/a_{44} & 1 & a_{45}/a_{44} & & & \\ & & a_{54}/a_{55} & 1 & a_{56}/a_{55} & & \\ & & & a_{65}/a_{66} & 1 & a_{67}/a_{66} & \\ & & & & . & . & . \end{array} \right] = A = I - M $$ The matrix $M^2$ is calculated. Concentrate on row $(5)$ and columns $(4,5,6)$: $$ \left[ \begin{array}{cccccc} . & . & & & & \\ & . & . & . & & \\ & & \displaystyle - \frac{a_{54}}{a_{55}} & 0 & \displaystyle - \frac{a_{56}}{a_{55}} & \\ & & & . & . & . \\ & & & & & \end{array} \right] \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & \displaystyle - \frac{a_{43}}{a_{44}} & 0 & \displaystyle - \frac{a_{45}}{a_{44}} & & & \\ & & \displaystyle - \frac{a_{54}}{a_{55}} & 0 & \displaystyle - \frac{a_{56}}{a_{55}} & & \\ & & & \displaystyle - \frac{a_{65}}{a_{66}} & 0 & \displaystyle - \frac{a_{67}}{a_{66}} & \\ & & & & . & . & . \end{array} \right] $$ $$ = \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & & . & . & . & & \\ & \displaystyle \frac{a_{54}}{a_{55}} \frac{a_{43}}{a_{44}} & 0 & \displaystyle \frac{a_{54}}{a_{55}} \frac{a_{45}}{a_{44}} + \frac{a_{56}}{a_{55}} \frac{a_{65}}{a_{66}} & 0 & \displaystyle \frac{a_{56}}{a_{55}} \frac{a_{67}}{a_{66}} & \\ & & & . & . & . & \\ & & & & . & . & . \end{array} \right] $$ Completing further one step of the Newton-Raphson procedure results in: $$ I - M^2 = \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & & . & . & . & & \\ & \displaystyle - \frac{a_{54}}{a_{55}} \frac{a_{43}}{a_{44}} & 0 & \displaystyle 1 - \frac{a_{54}}{a_{55}} \frac{a_{45}}{a_{44}} - \frac{a_{56}}{a_{55}} \frac{a_{65}}{a_{66}} & 0 & \displaystyle - \frac{a_{56}}{a_{55}} \frac{a_{67}}{a_{66}} & \\ & & & . & . & . & \\ & & & & . & . & . \end{array} \right] $$ It is shown in the following sequence that a Newton-Raphson step for coarsening the grid is equivalent with an Gaussian elimination step for even grid points. Hence the method as a whole is equivalent with a direct solution method for the linear equations system. This explains why an exact solution is found in the first place. $$ \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & a_{43}/a_{44} & 1 & a_{45}/a_{44} & & & \\ & & a_{54}/a_{55} & 1 & a_{56}/a_{55} & & \\ & & & a_{65}/a_{66} & 1 & a_{67}/a_{66} & \\ & & & & . & . & . \end{array} \right] = A $$ Use the first and the last row for pivoting the middle row. This is equivalent with: \begin{eqnarray*} T_4 = - a_{43}/a_{44} . T_3 - a_{45}/a_{44} . T_5 \\ T_6 = - a_{65}/a_{66} . T_5 - a_{67}/a_{66} . T_7 \end{eqnarray*} Substitute in the row with index $(5)$: $$ a_{54}/a_{55} . T_4 + 1 . T_5 + a_{56}/a_{55} . T_6 = 0 \hieruit $$ $$ \frac{a_{54}}{a_{55}} \left[ - \frac{a_{43}}{a_{44}} T_3 - \frac{a_{45}}{a_{44}} T_5 \right] + T_5 + \frac{a_{56}}{a_{55}} \left[ - \frac{a_{65}}{a_{66}} T_5 - \frac{a_{67}}{a_{66}} T_7 \right] $$ $$ = - \frac{a_{54}}{a_{55}} \frac{a_{43}}{a_{44}} T_3 + \left[ 1 - \frac{a_{54}}{a_{55}} \frac{a_{45}}{a_{44}} - \frac{a_{56}}{a_{55}} \frac{a_{65}}{a_{66}} \right] T_5 - \frac{a_{56}}{a_{55}} \frac{a_{67}}{a_{66}} T_7 = 0 $$ When written in matrix form, the abovementioned equivalence becomes evident: $$ \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & & . & . & . & & \\ & \displaystyle - \frac{a_{54}}{a_{55}} \frac{a_{43}}{a_{44}} & 0 & \displaystyle 1 - \frac{a_{54}}{a_{55}} \frac{a_{45}}{a_{44}} - \frac{a_{56}}{a_{55}} \frac{a_{65}}{a_{66}} & 0 & \displaystyle - \frac{a_{56}}{a_{55}} \frac{a_{67}}{a_{66}} & \\ & & & . & . & . & \\ & & & & . & . & . \end{array} \right] \left[ \begin{array}{c} . \\ . \\ T_3 \\ T_4 \\ T_5 \\ T_6 \\ T_7 \\ . \end{array} \right] $$