L.U. Decomposition

$ \def \XOR {\qquad \mbox{xor} \qquad} \def \kwart {\frac{1}{4}} \def \slechts {\quad \Longleftrightarrow \quad} \def \EN {\quad \mbox{and} \quad} \def \half {\frac{1}{2}} $ The product of the off-diagonal coefficients in an Upper or a Lower two-diagonal matrix is always zero. Therefore it is always in the safe domain $0 \le a.b \le 1/4$. This means, that, apart from the Rule of Positive Coefficients, there isn't any further restriction on the magnitude of $a$ and $b$. Now a Lower and an Upper matrix can always be multiplied with each other. The result will be a tri-diagonal matrix: $$ \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & -b & 1 & 0 & & & \\ & & -b & 1 & 0 & & \\ & & & -b & 1 & 0 & \\ & & & & . & . & . \end{array} \right] \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & 0 & 1 & -a & & & \\ & & 0 & 1 & -a & & \\ & & & 0 & 1 & -a & \\ & & & & . & . & . \end{array} \right] = $$ $$ \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & -b & 1+a.b & -a & & & \\ & & -b & 1+a.b & -a & & \\ & & & -b & 1+a.b & -a & \\ & & & & . & . & . \end{array} \right] $$ The reverse procedure of this is called an L.U. decomposition. It can be carried out in a way which is uniform for all rows of the tri-diagonal matrix, provided that the main diagonal is of the form $(1+a.b)$. Which means that the equations should not be normalized. One step of the pivoting process is shown below. Assume that row $(i)$ has been pivoted successfully. It has resulted in a row $(0 \quad 1 \quad -a)$, which is stored in the Upper matrix, and a pivot $(-b)$, which is stored in the Lower matrix. Then row $(i+1)$ will be pivoted as follows: $$ \left[ \begin{array}{ccccccc} . & . & . & & & & \\ & 0 & 1 & -a & & & \\ & & -b-(-b.1) & 1+a.b-(-b.-a) & -a & & \\ & & & -b & 1+a.b & -a & \\ & & & & . & . & . \end{array} \right] $$ We see that the pivot is again $(-b)$ and that row $(i+1)$ again becomes equal to $(0 \quad 1 \quad -a)$. Repeating the same process for all rows will result in an Upper and a Lower matrix, called the L.U. decomposition. The product of the Lower and the Upper matrix is equivalent to the original.
We have seen that there exist Upper and Lower solutions: $$ T_N.a^{N-i} = T_1.(1/a)^{i-1} \XOR T_1.b^{i-1} = T_N.(1/b)^i $$ We will demonstrate now that any linear superposition of these solutions is also a solution of the accompanying tri-diagonal system.
Substitute: $$ T_i = \lambda.(1/a)^{i-1} + \mu.b^{i-1} $$ Into the F.D. equation: $$ -b.T_{i-1} + (1+a.b).T_i - a.T_{i+1} $$ Giving, indeed: $$ (1+a.b) \left[ \lambda.(1/a)^{i-1} + \mu.b^{i-1} \right] $$ $$ -b \left[ \lambda.a.(1/a)^{i-1} + \mu.1/b.b^{i-1} \right] -a \left[ \lambda.1/a.(1/a)^{i-1} + \mu.b.b^{i-1} \right] = $$ $$ \lambda.(1/a)^{i-1} \left[ -b.a + (1+a.b) -a/a \right] + \mu.b^{i-1} \left[ -b/b + (1+a.b) -a.b \right] \equiv 0 $$ We seek a relationship between the coefficients $(a,b)$ in our tri-diagonal systems and the coefficients $(a,b)$ in the Upper and Lower matrices, which are formed by an L.U. decomposition of the former. The situation may seem somewhat confusing, because the Lower and Upper matrices as such are normed, while the accompanying tri-diagonal matrix in this chapter is not. Before using results from "The Hyperbolic Connection", we should take appropriate measures. Divide $(a,b)$ by the diagonal coefficient $(1+a.b)$ and then equate: \begin{eqnarray*} \frac{b}{1+a.b} = \frac{e^{+P/2.dx}}{e^{+Q/2.dx} + e^{-Q/2.dx}} \\ \frac{a}{1+a.b} = \frac{e^{-P/2.dx}}{e^{+Q/2.dx} + e^{-Q/2.dx}} \end{eqnarray*} The product of the off-diagonal coefficients becomes: $$ \frac{b}{1+a.b} \frac{b}{1+a.b} = \frac{a.b}{(1+a.b)^2} = \frac{1}{\left(e^{+Q/2.dx} + e^{-Q/2.dx}\right)^2} $$ Check out safe and dangerous domains first: $$ \frac{a.b}{(1+a.b)^2} \le \kwart \slechts 4.a.b \le 1 + 2.a.b + (a.b)^2 $$ $$ \slechts (a.b)^2 - 2.a.b + 1 = (a.b - 1)^2 \ge 0 $$ Proving once more that the dangerous domain doesn't exist anymore for the newly defined coefficients $(a,b)$. Now manipulate the right hand side, in such a way that it assumes the same form as the left hand side: $$ \frac{a.b}{(1+a.b)^2} = \frac{1}{\left(e^{+Q/2.dx} + e^{-Q/2.dx}\right)^2} = \frac{1}{e^{-Q.dx} \left(e^{+Q.dx} + 1\right)^2} = \frac{e^{Q.dx}}{\left(1 + e^{Q.dx}\right)^2} $$ We conclude therefrom that, for the newly defined coefficients: $$ a.b = e^{Q.dx} \quad \EN \quad \frac{b}{a} = e^{P.dx} $$ The latter result remains unchanged, namely.
Herewith we find new expressions for the off-diagonal coefficients in the L.U. decomposition: \begin{eqnarray*} b = \sqrt{\frac{b}{a}}.\sqrt{a.b} = e^{P/2.dx} e^{Q/2.dx} = e^{\half(P+Q).dx} \\ a = \sqrt{\frac{a}{b}}.\sqrt{a.b} = e^{-P/2.dx} e^{Q/2.dx} = e^{-\half(P-Q).dx} \end{eqnarray*} For the Analytical Solution we find: $$ T(x) = \lambda.a^{-x} + \mu.b^x = \lambda.e^{\half(P-Q).x} + \mu.e^{\half(P+Q).x} $$ It is evident herewith that the superposition of solutions of the Upper and Lower equations, forming the L.U. decomposition of the tri-diagonal system, is indeed identical with the general solution of the tri-diagonal system itself, as it has been found in "The Hyperbolic Connection".
Last but not least, it should be questioned what the governing equations are, corresponding with the Upper and the Lower matrices. To that end, we could set up Taylor expansions for the coefficients $a$ and $b$. But this would lead to finite difference schemes which are somewhat inconsistent with standard results from numerical analysis. This is the reason why the F.D. equations are modified as follows, before they serve as our starting point: $$ T_{i-1} - 1/b.T_i = 0 \XOR T_{i+1} - 1/a.T_i = 0 $$ The coefficients $1/a$ and $1/b$ are developed into a Taylor series expansion. Only terms up and including the first order are retained: \begin{eqnarray*} 1/b = e^{-\half(P+Q).dx} \approx 1 - \half (P + Q).dx \\ 1/a = e^{+\half(P-Q).dx} \approx 1 + \half (P - Q).dx \end{eqnarray*} Substitute in the Upper and Lower F.D. schemes. Then: $$ T_{i-1} - 1/b.T_i = T_{i-1} - \left[ 1 - \half (P + Q).dx \right]T_i = 0 $$ $$ \slechts - \frac{T_i - T_{i-1}}{dx} + \half (P+Q) . T_i = 0 \qquad \mbox{: forward scheme } \rightarrow $$ $$ T_{i+1} - 1/a.T_i = T_{i+1} - \left[ 1 + \half (P - Q).dx \right] T_i = 0 $$ $$ \slechts \frac{T_{i+1} - T_i}{dx} - \half (P-Q) . T_i = 0 \qquad \mbox{: backward scheme } \leftarrow $$ Taking the limit for $dx \rightarrow 0$ results in: $$ \frac{dT}{dx} - \half (P + Q) . T = 0 \XOR \frac{dT}{dx} - \half (P - Q) . T = 0 $$ Let $\alpha = (P+Q)/2$ and $\beta = (P-Q)/2$, then: $P = \alpha + \beta$ and $Q = \alpha - \beta$, thus assuring that $\alpha$ and $\beta$ can be arbitrary real numbers. Hence, in the limit for $(dx\rightarrow 0)$, the backward and the forward schemes boil down to differential equations which are both of the same type, namely: $$ \frac{dT}{dx} - \gamma . T = 0 \qquad \mbox{with arbitrary } \quad \gamma = \alpha , \beta $$ Note. It can be conceived that the L.U. decomposition of the tri-diagonal matrix into a Lower and an Upper matrix corresponds with a decomposition of the accompanying differential operator into a "lower" and an "upper" part: $$ \left[ \frac{d}{dx} - \half (P + Q) \right] \left[ \frac{d}{dx} - \half (P - Q) \right] = \frac{d^2}{dx^2} - P \frac{d}{dx} + \kwart (P^2-Q^2) $$