Solving Overdetermined System Using Pseudoinverse

/0 Comments/in /by

The system of linear equations becomes overdetermined system if there are more equations than unknowns. It usually does not have solutions.

From the Solving System of Linear Equations, the system of linear equations can be written in the matrix form as:

AX = B
Where:
A is m x n matrix of coefficients.
X is n x 1 matrix of unknowns.
B is m x 1 matrix of constant terms.

So, the system becomes overdetermined when m > n.
To solve this kind of system, we need to find X such that the residual vector

R = B – AX

is as small as possible.

The solution X given be the least squares method minimizes ||R||2 = ||B – AX||2. This solution is Least-Squares Solution.

Least-Squares Solution with Pseudoinverse

From:
AX = B
When m > n, so:
ATAX = ATB
Then
X = (ATA)-1ATB
(ATA)-1AT is called pseudo inverse of A

 

Solving with MathPACK Solver

MathPACK Solver provides inv or pinv function finding invert matrix. If the input matrix to the function, is not squared matrix, the pseudo invert will be returned from the function.

Function Signature

U = inv(A);
U = pinv(A);

Example

Find the least-squares solution of the following system of equations:
x1 – x2 = 2
x1 + x2 = 4
2x1 + x2 = 8


    »A = [1,-1; 1, 1; 2, 1]; 

    »B = [2; 4; 8]; 
    »X = pinv(A)*B 
    X = 
        3.2857 
        1.1429 
So, the values of unknown x1 and x2 are:
x1 = 3.2857
x2 = 1.1429

Solving Homogeneous System

/0 Comments/in /by

A system of linear equations is homogeneous if all of the constant terms are zero. From Solving System of Linear Equations, the general form of homogeneous system of linear equations can be written as:

a11x1 + a12x2 + a13x3 + … + a1nxn = 0
a21x1 + a22x2 + a23x3 + … + a2nxn = 0
… … … …
am1x1 + am2x2 + am3x3 + … + amnxn = 0

which can be written in matrix form

AX = 0

Every homogeneous system of linear equations has at least one solution, which is X = 0. It is called zero solution or trivial solution.

  • If det(A) is non-zero, then it is the unique solution.
  • if det(A) is zero, then there is an infinite number of solutions.

An important technique for solving a homogeneous system of linear equations AX = 0 is to form the augmented matrix M = [ A | 0 ] and reduce M to reduced row echelon form.

Solving with MathPACK Solver

To reduce the augmented matrix M to reduced row echelon form, you can use the function rref() in MathPACK Solver.

Function Signature

U = rref(A)

 

Example

Solve the homogeneous linear system of equations.
x1 + x2 – 2x3 = 0
3x1 + 2x2 + 4x3 = 0
4x1 + 3x2 + 2x3 = 0
From the given system of linear equations, we can write it in the matrix form
AX = 0
Where:
A = [1, 1, -2; 3, 2, 4; 4, 3, 2];
X = [x1;x2;x3];
So, we can create matrix A and construct augmented matrix M by:

»A = [1, 1, -2; 3, 2, 4; 4, 3, 2]; 
»M = zeros(3, 4); 
»M(1:3,1:3) = A;
Reduce M to reduced row echelon form using rref bundled function

»rref(M) 
ans = 
    1 0 8 0  
    0 1 -10 0 
    0 0 0 0 
Rewrite system in the equations form.
x1 + 0 + 8x3 = 0
0 + x2 – 10x3 = 0
Thus:
x1 = – 8x3
x2 = 10x3
Let s=x3, then
x1 = – 8s
x2 = 10s
x3 = s
The solution vector X will be:
X = [-8; 10; 1]s

Solving System of Linear Equations

/0 Comments/in /by

A system of linear equations is a collection of linear equations involving the same set of variables.

For example:
5x + 2y – 3z = 1
-2x – y + 7z = 8
4x – 13y + z = -10

is a system of three equations in the three variables x, y and z.

A general form of system of m linear equations with n unknowns can be written as:

a11x1 + a12x2 + a13x3 + … + a1nxn = b1
a21x1 + a22x2 + a23x3 + … + a2nxn = b2
… … … …
am1x1 + am2x2 + am3x3 + … + amnxn = bm

From above system of linear equations, x1, x2, x3, …, xn are unknown, a11, a12, a13, … amn are coefficients of the system, and b1, b2, b3, …, bn are the constant terms. If all constant terms are zero, the system of linear equations is called homogeneous system (see Solving Homogeneous System).

Matrix Equation

The system of linear equations is equivalent to a matrix equation of the form

AX=B
Where:
A is m x n matrix of coefficients. Element of matrix A at i th-row and j th-column is aij.
X is n x 1 matrix (column vector with n entries). Element of matrix X at i th-row is xi.
B is m x 1 matrix (column vector with m entries). Element of matrix B at i th-row is bi.

 

Solving with MathPACK Solver

MathPACK Solver can solve the system of linear equations for finding the values of unknowns (matrix X) by using linsolve function. The system of linear equations must be written in the form of Matrix Equation described in previous section and the number of linear equations must be equal to number of unknowns (A must be square matrix : m = n).

Function Signature

X = linsolve(A, B);

Example

5x + 2y – 3z = 1
-2x – y + 7z = 8
4x – 13y + z = -10
So, the following expressions must be executed in MathPACK Solver console

»A = [5, 2, -3; -2, -1,7; 4, -13, 1]; 
»B = [1; 8; -10]; 
»X = linsolve(A, B) 
ans = 
    0.6571  
    1.0857  
    1.4857 
 
So, the solution will be:
x = 0.6571
y = 1.0857
z = 1.4857