On the propagation of errors in the inversion of certain tridiagonal matrices

Abstract:

When the differential equation of heat conduction is replaced by the implicit difference analog, one is led to the solution of Ay = b where A is a tridiagonal matrix whose elements on the principal diagonal are = 2 + 2r and whose elements off the principal diagonal are = -r. The system of equations may be solved by the following algorithm: \[ {\beta _k} = u = {r^2}\beta _{k - 1}^{ - 1}, {\beta _1} = {u_1} ;\qquad {\gamma _k} = - r{\beta ^{ - 1}};\qquad {z_k} = ({b_k} + r{z_{k - 1}})\beta _k^{ - 1}, {z_1} = {b_1}{u^{ - 1}};\qquad {y_k} = {z_k} - {\gamma _k}{y_{k + 1}},\qquad {y_M} = {z_M}.\] An upper bound of the round-off errors in the computed values of the ${y_k}$’s is obtained. An actual test case showed that the theoretical upper bound is about four times larger than the true round-off error. Moreover, the theoretical upper bound does not seem to vary appreciably with r.