Solving the system is find a vector x satisfying the linear equation Ax = b.
More...
Functions |
void | forward_substitution_ones (size_t n, double **const L, double *const x, double *const b) |
| Forward substitution for lower triangular matrices (Lx = b) where the diagonal of L are 1's.
|
void * | forward_substitution (size_t n, double **const L, double *const x, double *const b, double tol) |
| Forward substitution for lower triangular matrices (Lx = b)
|
void * | back_substitution (size_t n, double **const U, double *const x, double *const b, double tol) |
| Back substitution for upper triangular matrices (Ux = b)
|
void * | solve_qr (size_t m, size_t n, double **const A, double *const x, double *const b, double tol) |
| QR solve linear system (QRx = b)
|
void * | solve_lu (size_t m, size_t n, double **const A, double *const x, double *const b, double tol) |
| LU solve linear system (LUx = b)
|
void * | solve (size_t m, size_t n, double **const A, double *const x, double *const b, double tol, void *(*s)(size_t, size_t, double **const, double *const, double *const, double)) |
| solve a linear system (Ax = b) with the pointer to a solve function
|
solve_ptr | get_solve_with_lu () |
solve_ptr | get_solve_with_qr () |
Detailed Description
Solving the system is find a vector x satisfying the linear equation Ax = b.
The standard algorithm for solving a system of linear equations is based on Gaussian elimination with some modifications. Firstly, it is essential to avoid division by small numbers, which may lead to inaccurate results. This can be done by reordering the equations if necessary, a process known as pivoting. Secondly, the algorithm does not exactly do Gaussian elimination, but it computes the LU factorization of the matrix A. Other useful algorithm for solving a linear system is to compute QR factorization of the matrix A. This leads to the class of direct methods.
If the matrix A has some special structure, this can be exploited to obtain faster or more accurate algorithms. For instance, systems with a symmetric matrix or a symmetric positive definite matrix or a strictly diagonaly dominant matrix, ... Special methods exist also for matrices with many zero elements (so-called sparse matrices).
A completely different approach is often taken for very large systems, which would otherwise take too much time or memory. The idea is to start with an initial approximation to the solution (which does not have to be accurate at all), and to change this approximation in several steps to bring it closer to the true solution. Once the approximation is sufficiently accurate, this is taken to be the solution to the system. For instance, Jacobi method, Gauss-Seidel method, Successive over-relaxation (SOR) method, ... This leads to the class of iterative methods.
In this module, we implement some of these methods
Function Documentation
void* back_substitution |
( |
size_t |
n, |
|
|
double **const |
U, |
|
|
double *const |
x, |
|
|
double *const |
b, |
|
|
double |
tol |
|
) |
| |
Back substitution for upper triangular matrices (Ux = b)
- Parameters:
-
[in] | n | Dimension of matrix and vectors |
[in] | U | Upper triangular matrix |
[in] | b | Constant terms |
[out] | x | Unknowns |
[in] | tol | Tolerance |
- Return values:
-
NULL | If some diagonal's element is less than or equal to tolerance |
1 | Otherwise |
- Precondition:
- The pointers are not NULL
- The tolerance is positive
- Postcondition:
- The vector x has the solution
- Note:
- The complexity is
void* forward_substitution |
( |
size_t |
n, |
|
|
double **const |
L, |
|
|
double *const |
x, |
|
|
double *const |
b, |
|
|
double |
tol |
|
) |
| |
Forward substitution for lower triangular matrices (Lx = b)
- Parameters:
-
[in] | n | Dimension of matrix and vectors |
[in] | L | Lower triangular matrix |
[in] | b | Constant terms |
[out] | x | Unknowns |
[in] | tol | Tolerance |
- Return values:
-
NULL | If some diagonal's element is less than or equal to tolerance |
1 | Otherwise |
- Precondition:
- The pointers are not NULL
- The tolerance is positive
- Postcondition:
- The vector x has the solution
Forward substitution for lower triangular matrices (Lx = b) where the diagonal of L are 1's.
- Parameters:
-
[in] | n | Dimension of matrix and vectors |
[in] | L | Lower triangular matrix with 1's in its diagonal |
[in] | b | Constant terms |
[out] | x | Unknowns |
- Precondition:
- The pointers are not NULL
- Postcondition:
- The vector x has the solution
void * solve |
( |
size_t |
m, |
|
|
size_t |
n, |
|
|
double **const |
A, |
|
|
double *const |
x, |
|
|
double *const |
b, |
|
|
double |
tol, |
|
|
void *(*)(size_t, size_t, double **const, double *const, double *const, double) |
s |
|
) |
| |
solve a linear system (Ax = b) with the pointer to a solve function
- Parameters:
-
[in] | n | Dimension of matrix and vectors |
[in,out] | A | Matrix's system |
[in] | b | Constant terms |
[out] | x | Unknowns |
[in] | tol | Tolerance |
[in] | s | Pointer to a function that solve the linear system |
- Returns:
- The value that is returned by the pointer to the solve function
- Precondition:
- The dimension is greater than one
- Postcondition:
- The x vector has the solution
- See also:
- SOLVE_WITH_LU and SOLVE_WITH_QR
References solve_lu(), solve_qr(), SOLVE_WITH_LU, and SOLVE_WITH_QR.
void* solve_lu |
( |
size_t |
m, |
|
|
size_t |
n, |
|
|
double **const |
A, |
|
|
double *const |
x, |
|
|
double *const |
b, |
|
|
double |
tol |
|
) |
| |
void* solve_qr |
( |
size_t |
m, |
|
|
size_t |
n, |
|
|
double **const |
A, |
|
|
double *const |
x, |
|
|
double *const |
b, |
|
|
double |
tol |
|
) |
| |
QR solve linear system (QRx = b)
- Parameters:
-
[in] | n | Dimension of matrix and vectors |
[in,out] | A | Matrix's system |
[in,out] | b | Constant terms |
[out] | x | Unknowns |
- Return values:
-
NULL | When QR factorization was unsuccessful or could not be allocated memory |
1 | Otherwise |
- Precondition:
- The dimension is greater than one
- Postcondition:
- The x vector has the solution
- Note:
- The vector of constant terms will be modified
- The unknowns pointer x and constant terms pointer b can be the same
- See also:
- qr
References back_substitution(), premult_Q_vector(), and qr().