= Solution
Use banded <Gaussian elimination> followed by <back substitution>. To distinguish the right-hand side from the upper-diagonal coefficients $b_i$, write it as $r_i$. If the modified <pivot elements> are nonzero, the <tridiagonal elimination recurrences> are
$$
p_1=a_1,\quad q_1=r_1,\qquad m_i=\frac{c_{i-1}}{p_{i-1}},\quad p_i=a_i-m_ib_{i-1},\quad q_i=r_i-m_iq_{i-1}\quad(2\le i\le n).
$$
They eliminate just the one entry below each <pivot element>. Solve the resulting upper <bidiagonal matrix> system by
$$
x_n=q_n/p_n,\qquad x_i=(q_i-b_ix_{i+1})/p_i\quad(i=n-1,\ldots,1).
$$
There is a bounded number of <arithmetic operations> per row in each sweep, giving \b[$O(n)$ <arithmetic operations> and $O(n)$ storage]. The unpivoted recurrences cost $8n-7$ <arithmetic operations> under the usual scalar-operation count.
For a general <tridiagonal matrix>, nonsingularity alone does not guarantee these <pivot elements>. If a zero or unsafe <pivot element> occurs, use <partial pivoting> between the current row and the next row. These are the only possible nonzero candidates in the current column; adjacent row swaps introduce at most a second upper diagonal. Tracking that <fill-in> keeps both <Gaussian elimination> and <back substitution> at $O(n)$ <arithmetic operations>. For example, $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ is invertible but requires a row swap. If the input is singular, report a zero final <pivot element>; a unique solution cannot be promised, and compatibility or free-variable analysis is a separate issue. No nonsingularity or safe-pivot assumption is silently inferred from the word <tridiagonal>.
Back to article page
