Tridiagonal Linear System Solver

Solves tridiagonal linear systems A*x=rhs efficiently.

trisolve(a, b, d, rhs)

Arguments

a

diagonal of the tridiagonal matrix A.

b, d

upper and lower secondary diagonal of A.

rhs

right hand side of the linear system A*x=rhs.

Details

Solves tridiagonal linear systems A*x=rhs by applying Givens transformations.

By only storing the three diagonals, trisolve has memory requirements of 3*n instead of n^2 and is faster than the standard solve function for larger matrices.

Value

Returns the solution of the tridiagonal linear system as vector.

Note

Has applications for spline approximations and for solving boundary value problems (ordinary differential equations).

References

Gander, W. (1992). Computermathematik. Birkhaeuser Verlag, Basel.

See also

qrSolve

Examples

set.seed(8237)
a <- rep(1, 100)
e <- runif(99); f <- rnorm(99)
x <- rep(seq(0.1, 0.9, by = 0.2), times = 20)
A <- diag(100) + Diag(e, 1) + Diag(f, -1)
rhs <- A %*% x
s <- trisolve(a, e, f, rhs)
s[1:10]                         #=> 0.1 0.3 0.5 0.7 0.9 0.1 0.3 0.5 0.7 0.9
#>  [1] 0.1 0.3 0.5 0.7 0.9 0.1 0.3 0.5 0.7 0.9
s[91:100]                       #=> 0.1 0.3 0.5 0.7 0.9 0.1 0.3 0.5 0.7 0.9
#>  [1] 0.1 0.3 0.5 0.7 0.9 0.1 0.3 0.5 0.7 0.9