Solve linear equation A*x = b (exactly if possible, or otherwise in a least square sense; A may be non-square and may be rank deficient)

Wolfram Language



This information is part of the Modelica Standard Library maintained by the Modelica Association.


x = Matrices.leastSquares(A,b);


Returns a solution of equation A*x = b in a least square sense (A may be rank deficient):

minimize | A*x - b |

Several different cases can be distinguished (note, rank is an output argument of this function):

size(A,1) = size(A,2)

A solution is returned for a regular, as well as a singular matrix A:

  • rank = size(A,1):
    A is regular and the returned solution x fulfills the equation A*x = b uniquely.
  • rank < size(A,1):
    A is singular and no unique solution for equation A*x = b exists.
    • If an infinite number of solutions exists, the one is selected that fulfills the equation and at the same time has the minimum norm |x| for all solution vectors that fulfill the equation.
    • If no solution exists, x is selected such that |A*x - b| is as small as possible (but A*x - b is not zero).

size(A,1) > size(A,2):

The equation A*x = b has no unique solution. The solution x is selected such that |A*x - b| is as small as possible. If rank = size(A,2), this minimum norm solution is unique. If rank < size(A,2), there are an infinite number of solutions leading to the same minimum value of |A*x - b|. From these infinite number of solutions, the one with the minimum norm |x| is selected. This gives a unique solution that minimizes both |A*x - b| and |x|.

size(A,1) < size(A,2):

  • rank = size(A,1):
    There are an infinite number of solutions that fulfill the equation A*x = b. From this infinite number, the unique solution is selected that minimizes |x|.
  • rank < size(A,1):
    There is either no solution of equation A*x = b, or there are again an infinite number of solutions. The unique solution x is returned that minimizes both |A*x - b| and |x|.

Note, the solution is computed with the LAPACK function "dgelsy", i.e., QR or LQ factorization of A with column pivoting.

Algorithmic details

The function first computes a QR factorization with column pivoting:

A * P = Q * [ R11 R12 ]
            [  0  R22 ]

with R11 defined as the largest leading submatrix whose estimated condition number is less than 1/rcond. The order of R11, rank, is the effective rank of A.

Then, R22 is considered to be negligible, and R12 is annihilated by orthogonal transformations from the right, arriving at the complete orthogonal factorization:

A * P = Q * [ T11 0 ] * Z
            [  0  0 ]

The minimum-norm solution is then

x = P * Z' [ inv(T11)*Q1'*b ]
           [        0       ]

where Q1 consists of the first "rank" columns of Q.

See also

Matrices.leastSquares2 (same as leastSquares, but with a right hand side matrix),
Matrices.solve (for square, regular matrices A)


(x, rank) = leastSquares(A, b, rcond)

Inputs (3)


Type: Real[:,:]

Description: Matrix A


Type: Real[size(A, 1)]

Description: Vector b


Default Value: 100 * Modelica.Constants.eps

Type: Real

Description: Reciprocal condition number to estimate the rank of A

Outputs (2)


Type: Real[size(A, 2)]

Description: Vector x such that min|A*x-b|^2 if size(A,1) >= size(A,2) or min|x|^2 and A*x=b, if size(A,1) < size(A,2)


Type: Integer

Description: Rank of A