and corresponds ot the system of equations.- -. .- -. .- -. | y1 | | b1 c1 0 . . . . . . 0 | | x1 | | y2 | | a2 b2 c2 | | x2 | | y3 | | 0 a3 b3 c3 | | x3 | | . | = | . . . . | | . | | . | | . . . . | | . | | . | | . . . . cm | | . | | yn | | 0 an bn | | xn | - - - - - -
with a_1 = 0 and c_n = 0. and with "_" denoting a subscript.a_i x_{i-1} + b_i x_i + c_i x_{i+1} = y_i
This is a special case that allows a very fast solution - one with a time complexity of O(N) - by using the tridiagonal matrix algorithm (also called the Thomas algorithm). A description of the algorithm can be found in a Wikipedia article. Basically, it uses row reduction to force all the elements below the diagonal to be zero. This provides a direct solution for x_n, and the values for other indices can be obtained by substitution. The example implementations in the Wikipedia article as seen on November 22, 2013 are incomplete: they do not handle the case in which a diagonal element (possibly modified by row reduction) is zero. In the matrix shown above, if b1 is zero, then both c1 and a2 must be non-zero (otherwise the matrix is singular). Since b1 is zero, c1 is the only non-zero element in row 1, so row reduction can be used to make a3 zero with a modified value of y3. Then x2 = y1/c1 and y1 = (y2 - b2y1/c1 - c2x3)/a2. One can then solve
where y'3 is the modified value of y3. To eliminate a corner case, explicit solutions are used for 2x2 and 1x1 matrices..- -. .- -. .- -. | y'3| | b3 c3 . . . 0 | | x3 | | . | = | a4 b4 c4 | | . | | . | | . . . | | . | | . | | . . . cm | | . | | yn | | 0 . . . an bn | | xn | - - - - - -
The implementation, which uses the Java convention of indices starting from 0 instead of 1, can represent the matrix as vectors a, b and c of length n representing the subdiagonal, diagonal and superdiagonal elements respectively. All are the same length, with a[0] and c[n-1] ignored. I.e., for the n by n matrix A that these vectors represent, a[i] = A[i][i-1], b[i] = A[i][i], and c[i] = A[i][i+1].
For the cyclic case, the matrix equation is
and corresponds to the system of equations.- -. .- -. .- -. | y1 | | b1 c1 0 . . . . . 0 a1 | | x1 | | y2 | | a2 b2 c2 | | x2 | | y3 | | 0 a3 b3 c3 | | x3 | | . | = | . . . . | | . | | . | | . . . . | | . | | . | | . . . . cm | | . | | yn | | cn 0 . . . 0 an bn | | xn | - - - - - -
The same technique works for a solution, but with additional elements that must be forced to a value of zero. and with a "fall-back" to LU Decomposition when one might have to divide by the value of a diagonal element that is zero.a_1 x_n + b_1 x_1 + c_1 x_2 = z_1 a_i x_{i-1} + b_i x_i + c_i x_{i+1} = z_i (for 1 < i < n) c_n x_1 + a_m x_m + b_n x_n = z_n
Solutions can be obtained by using static methods or instance methods. When instance methods are used, the constructor perform part of the calculation and store the results in tables used for each solution. This is more efficient when multiple solutions are needed, each for a different value of y, but slightly more costly if the solution is used for only a single value of y.
-
Constructor Summary
ConstructorsConstructorDescriptionTridiagonalSolver
(double[] a, double[] b, double[] c, boolean cyclic) Construct a TridiagonalSolver given the subdiagonal, diagonal, and superdiagonal elements for a tridiagonal system of equations.TridiagonalSolver
(double[] a, double[] b, double[] c, boolean cyclic, int n) Construct a TridiagonalSolver given the subdiagonal, diagonal, and superdiagonal elements for a tridiagonal system of equations, using the first n elements of the one-dimensional arrays specifying the system of equations. -
Method Summary
Modifier and TypeMethodDescriptionfinal void
solve
(double[] x, double[] y) Solve a tridiagonal system of equations y = Ax, whether cyclic or not.static double[]
solve
(double[] x, double[][] A, double[] y) Solve a tridiagonal matrix equation y=Ax for x where A is an n by n matrix.static double[]
solve
(double[] x, double[][] A, double[] y, int n) Solve a tridiagonal matrix equation y=Ax for x where A is an n by n matrix with n given explicitly.static double[]
solve
(double[] x, double[] a, double[] b, double[] c, double[] y) Solve a tridiagonal matrix equation y=Ax for x with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements.static double[]
solve
(double[] x, double[] a, double[] b, double[] c, double[] y, int n) Solve a tridiagonal matrix equation y=Ax for x where A is an n by n matrix with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements and with the value n specified explicitly.static double[]
solveCyclic
(double[] x, double[] a, double[] b, double[] c, double[] y) Solve a cyclic tridiagonal matrix equation y=Ax for x where A is an n by n matrix with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements.static double[]
solveCyclic
(double[] x, double[] a, double[] b, double[] c, double[] y, int n) Solve a cyclic tridiagonal matrix equation y=Ax for x where A is an n by n matrix with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements, and with n specified.
-
Constructor Details
-
TridiagonalSolver
public TridiagonalSolver(double[] a, double[] b, double[] c, boolean cyclic) throws IllegalArgumentException Construct a TridiagonalSolver given the subdiagonal, diagonal, and superdiagonal elements for a tridiagonal system of equations. If the cyclic argument's value is false, the system of equations can be represented by a matrix with subdiagonal, diagonal, and superdiagonal elements, and with the remaining elements set to 0. If the cyclic argument's value is true, the matrix is assumed to have nonzero elements at its lower-left and upper right corners, corresponding to the last value of c and the first value of a respectively.- Parameters:
a
- the subdiagonal elements of a tridiagonal matrix, with a[0] ignored if cyclic is false and used if cyclic is trueb
- the diagonal elements of the matrixc
- the superdiagonal elements of the matrix, with c[c.length-1] ignored if cyclic is false and used if cyclic is truecyclic
- true if the system of equations is cyclic; false otherwise- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-
TridiagonalSolver
public TridiagonalSolver(double[] a, double[] b, double[] c, boolean cyclic, int n) throws IllegalArgumentException Construct a TridiagonalSolver given the subdiagonal, diagonal, and superdiagonal elements for a tridiagonal system of equations, using the first n elements of the one-dimensional arrays specifying the system of equations. If the cyclic argument's value is false, the system of equations can be represented by a matrix with subdiagonal, diagonal, and superdiagonal elements, and with the remaining elements set to 0. If the cyclic argument's value is true, the matrix is assumed to have nonzero elements at its lower-left and upper right corners, corresponding to the last value of c and the first value of a respectively.Specifying the argument n explicitly is an optimization for allowing existing arrays to be reused.
- Parameters:
a
- the subdiagonal elements of a tridiagonal matrix, with a[0] ignored if cyclic is false and used if cyclic is trueb
- the diagonal elements of the matrixc
- the superdiagonal elements of the matrix, with c[n] ignored if cyclic is false and used if cyclic is truen
- number of elements in the arrays to usecyclic
- true if the system of equations is cyclic; false otherwise- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-
-
Method Details
-
solve
public static double[] solve(double[] x, double[] a, double[] b, double[] c, double[] y) throws IllegalArgumentException Solve a tridiagonal matrix equation y=Ax for x with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements. A is a matrix whose elements are all zero except for the diagonal, subdiagonal, and superdiagonal elements, which can have any value. The diagonal subdiagonal, and superdiagonal elements are described by arrays of length n. The first element of the subdiagonal vector and the (n-1) argument of the superdiagonal vector are ignored.If the arguments x and y are identical, the array y will be overwritten with the solution. The solutions are only for the non-cyclic case.
- Parameters:
x
- an array to hold the solutiona
- the subdiagonal elements of a tridiagonal matrix, with a[0] ignoredb
- the diagonal elements of the matrixc
- the superdiagonal elements of the matrix, with c[n-1] ignoredy
- an array to hold the known values- Returns:
- the solution for x of the equation y = Ax, contained in the array x or in a new array if x is null
- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-
solve
public static double[] solve(double[] x, double[] a, double[] b, double[] c, double[] y, int n) throws IllegalArgumentException Solve a tridiagonal matrix equation y=Ax for x where A is an n by n matrix with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements and with the value n specified explicitly. A is a matrix whose elements are all zero except for the diagonal, subdiagonal, and superdiagonal elements, which can have any value. The diagonal subdiagonal, and superdiagonal elements are described by arrays of length n. The first element of the subdiagonal vector and the (n-1) argument of the superdiagonal vector are ignored. The solutions are only for the non-cyclic case.If the arguments x and y are identical, the array y will be overwritten with the solution.
- Parameters:
x
- an array to hold the solutiona
- the subdiagonal elements of a tridiagonal matrix, with a[0] ignoredb
- the diagonal elements of the matrixc
- the superdiagonal elements of the matrix, with c[n-1] ignoredy
- a vector contain the known valuesn
- the number of rows and columns in the square matrix A- Returns:
- the solution for x of the equation y = Ax, contained in the array x or in a new array if x is null
- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-
solve
public final void solve(double[] x, double[] y) Solve a tridiagonal system of equations y = Ax, whether cyclic or not. If x and y are the same array, the output will overwrite the input.- Parameters:
x
- an output array to hold the solutiony
- an input array to hold the known values
-
solve
Solve a tridiagonal matrix equation y=Ax for x where A is an n by n matrix. A is a matrix whose elements are all zero except for the diagonal, subdiagonal, and superdiagonal elements, which can have any value.- Parameters:
x
- an array to hold the solutionA
- the n by n tridiagonal matrix (array sizes may be larger)y
- a vector contain the known values- Returns:
- the solution for x of the equation y = Ax, contained in the array x or in a new array if x is null
- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-
solve
public static double[] solve(double[] x, double[][] A, double[] y, int n) throws IllegalArgumentException Solve a tridiagonal matrix equation y=Ax for x where A is an n by n matrix with n given explicitly. A is a matrix whose elements are all zero except for the diagonal, subdiagonal, and superdiagonal elements, and the upper-right and lower-left elements, which can have any value.- Parameters:
x
- an array to hold the solutionA
- the n by n tridiagonal matrix (array sizes may be larger)y
- a vector contain the known valuesn
- the number of rows and columns in the square matrix A.- Returns:
- the solution for x of the equation y = Ax, contained in the array x or in a new array if x is null
- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-
solveCyclic
public static double[] solveCyclic(double[] x, double[] a, double[] b, double[] c, double[] y) Solve a cyclic tridiagonal matrix equation y=Ax for x where A is an n by n matrix with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements. A is a matrix whose elements are all zero except for the diagonal, subdiagonal, superdiagonal elements, and the upper-right and lower-left corner elements, all of which can have arbitrary values. The diagonal subdiagonal, and superdiagonal elements are described by arrays of length n. The first element of the subdiagonal vector is treated as the upper-right corner element and the last element of the superdiagonal vector is treated as the lower-left corner element.- Parameters:
x
- an array to hold the solutiona
- the subdiagonal elements of the cyclic tridiagonal matrix, except for a[0], which appears in the upper right-hand cornerb
- the diagonal elements of the cyclic tridiagonal matrixc
- the superdiagonal elements of the cyclic tridiagonal matrix except for c[n-1], which appears in the lower left-hand cornery
- a vector contain the known values- Returns:
- the solution for x of the equation y = Ax, contained in the array x or in a new array if x is null
- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-
solveCyclic
public static double[] solveCyclic(double[] x, double[] a, double[] b, double[] c, double[] y, int n) throws IllegalArgumentException Solve a cyclic tridiagonal matrix equation y=Ax for x where A is an n by n matrix with A represented by vectors giving the subdiagonal, diagonal, and superdiagonal elements, and with n specified. A is a matrix whose elements are all zero except for the diagonal, subdiagonal, superdiagonal elements, and the upper-right and lower-left corner elements, all of which can have arbitrary values. The diagonal subdiagonal, and superdiagonal elements are described by arrays of length at least n, with only the first n elements used. The first element of the subdiagonal vector is treated as the upper-right corner element and the last element of the superdiagonal vector is treated as the lower-left corner element.- Parameters:
x
- an array to hold the solutiona
- the subdiagonal elements of the cyclic tridiagonal matrix, except for a[0], which appears in the upper right-hand cornerb
- the diagonal elements of the cyclic tridiagonal matrixc
- the superdiagonal elements of the cyclic tridiagonal matrix except for c[n-1], which appears in the lower left-hand cornery
- a vector contain the known valuesn
- the number of rows and columns in the square matrix A- Returns:
- the solution for x of the equation y = Ax, contained in the array x or in a new array if x is null
- Throws:
IllegalArgumentException
- the system of equations is linearly dependent so there is no unique solution or a value is out of range
-