Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Numerical methods for linear least squares
Résumé
Numerical methods for linear least squares entails the numerical analysis of linear least squares problems.
A general approach to the least squares problem can be described as follows. Suppose that we can find an n by m matrix S
such that XS is an
orthogonal projection onto the image of X. Then a solution to our minimization problem is given by
simply because
is exactly a sought for orthogonal projection of onto an image of X
(see the picture below and note that as explained in the
next section the image of X is just a subspace generated by column vectors of X).
A few popular ways to find such a matrix S are described below.
The equation
is known as the normal equation.
The algebraic solution of the normal equations with a full-rank matrix XTX can be written as
where X+ is the Moore–Penrose pseudoinverse of X. Although this equation is correct and can work in many applications, it is not computationally efficient to invert the normal-equations matrix (the Gramian matrix). An exception occurs in numerical smoothing and differentiation where an analytical expression is required.
If the matrix XTX is well-conditioned and positive definite, implying that it has full rank, the normal equations can be solved directly by using the Cholesky decomposition RTR, where R is an upper triangular matrix, giving:
The solution is obtained in two stages, a forward substitution step, solving for z:
followed by a backward substitution, solving for :
Both substitutions are facilitated by the triangular nature of R.
Orthogonal decomposition methods of solving the least squares problem are slower than the normal equations method but are more numerically stable because they avoid forming the product XTX.
The residuals are written in matrix notation as
The matrix X is subjected to an orthogonal decomposition, e.g., the QR decomposition as follows.
where Q is an m×m orthogonal matrix (QTQ=I) and R is an n×n upper triangular matrix with .
The residual vector is left-multiplied by QT.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.