const empty = require('../../util/empty');
const {
INVALID_MATRIX,
INVALID_UPPER_TRIANGULAR_MATRIX,
INVALID_SQUARE_MATRIX,
SIZE_INCOMPATIBLE,
NO_UNIQUE_SOLUTION,
} = require('../../Error');
/**
* Solve system of linear equations Ux = y using backward substitution,
* where U is an upper triangular matrix.
* If there is no unique solutions, an error is thrown.
* @memberof Matrix
* @static
* @param {Matrix} U - Any n x n upper triangular Matrix
* @param {Matrix} y - Any n x 1 Matrix
* @returns {Matrix} n x 1 Matrix which is the solution of Ux = y
*/
function backward(U, y) {
if (!(U instanceof this) || !(y instanceof this)) {
throw new Error(INVALID_MATRIX);
}
if (!U.isUpperTriangular()) {
throw new Error(INVALID_UPPER_TRIANGULAR_MATRIX);
}
if (!U.isSquare()) {
throw new Error(INVALID_SQUARE_MATRIX);
}
const size = U.size()[0];
const [yrow, ycol] = y.size();
const matrixU = U._matrix;
const matrixY = y._matrix;
if (yrow !== size || ycol !== 1) {
throw new Error(SIZE_INCOMPATIBLE);
}
const EPSILON = 1 / ((10 ** U._digit) * 2);
for (let i = 0; i < size; i++) {
if (Math.abs(matrixU[i][i]) < EPSILON) {
throw new Error(NO_UNIQUE_SOLUTION);
}
}
const coefficients = empty(size, 1);
for (let i = size - 1; i >= 0; i--) {
let summation = 0;
for (let j = i + 1; j < size; j++) {
summation += coefficients[j][0] * matrixU[i][j];
}
coefficients[i][0] = (matrixY[i][0] - summation) / matrixU[i][i];
}
return new this(coefficients);
};
module.exports = backward;