Verfahren zur Lösung eines überbestimmten Systems von N Gleichungen zur Bestimmung von n Unbekannten x₁, x₂, …, x_n aus N beobachteten Meßwerten \begin{eqnarray}\begin{array}{ccc}{g}_{i}({x}_{1},{x}_{2},\mathrm{...},{x}_{n})={\ell}_{i} & i=1,2,\mathrm{...},N & n\lt N.\end{array}\end{eqnarray}

Typischerweise kann ein solches überbestimmtes Gleichungssystem nicht exakt gelöst werden. Stattdessen versucht man bei der Methode der kleinsten Quadrate, eine Lösung x₁, x₂, …, x_n so zu bestimmen, daß die Summe der Quadrate der in den einzelnen Gleichungen auftretenden Abweichungen \begin{eqnarray}{r}_{i}={\ell}_{i}-{g}_{i}({x}_{1},{x}_{2},\mathrm{...},{x}_{n})\end{eqnarray}

minimal ist. Mit anderen Worten: Mit r = (r₁, r₂,…, r_N)^T ∈ ℝ^N minimiere \begin{eqnarray}F(x)={r}^{{\rm T}}r={\displaystyle \sum _{i=1}^{N}({ \ell }_{i}-{g}_{i}({x}_{1},{x}_{2},\mathrm{...},{x}_{n}))^{2}}.\end{eqnarray}

Die notwendige Bedingungen zur Minimierung der Funktion F sind dann gerade \begin{eqnarray}\begin{array}{cc}\displaystyle\frac{\partial F(x)}{\partial {x}_{i}}=0, & i=1,\mathrm{...},n,\end{array}\end{eqnarray}

d. h., der Gradient von F muß verschwinden.

Sind die Funktionen g_i nichtlinear in den x_j, so ergibt sich ein System von n nichtlinearen Gleichungen, welches nur schwer zu lösen ist. Man verwendet hier dann häufig die Gauß-Newton-Methode zur Lösung. Sind die Funktionen g_i hingegen linear in den x_j, \begin{eqnarray}{g}_{i}({x}_{1},{x}_{2},\mathrm{...},{x}_{n})=\displaystyle \sum _{k=1}^{n}{\alpha }_{ik}{x}_{k}\end{eqnarray}

(wobei die a_ik Skalare oder Funktionen sein können), so erhält man mit \(A={({a}_{ik})}_{i=1,\mathrm{...},N}^{k=1,\mathrm{...},n}\) und ℓ = (ℓ₁, ℓ₂, …, ℓ_N)^T ∈ ℝ^N\begin{eqnarray}F(x)={x}^{T}{A}^{T}Ax+2{ \ell }^{T}Ax+{ \ell }^{{\rm T}} {\ell} \end{eqnarray}

und als notwendige Bedingung für ein Minimum von F die Normalgleichungen \begin{eqnarray}{A}^{T}Ax+{A}^{T} {\ell} =0.\end{eqnarray}

Da A^TA eine symmetrische Matrix ist, kann die Normalgleichung mittels des Cholesky-Verfahrens gelöst werden. Bei der Lösung der Normalgleichung können numerische Probleme auftreten, wenn die Konditionszahl der Matrix A^TA sehr groß ist. Die Lösung x hat dann relativ große Fehler. Zudem sind Rundungsfehler bereits bei der Berechnung von A^TA und A^Tℓ Berechnung vo unvermeidlich.

Numerisch besser ist es, das zu min r^Tr äquivalente Ausgleichsproblem \begin{eqnarray}\mathop{\min }\limits_{x\to {{\mathbb{R}}}^{n}}|| {\ell} -Ax|{|}_{2}^{2}\end{eqnarray}

zu betrachten und dieses mittels der QR-Zerlegung von A zu lösen. Berechnet man die QR-Zerlegung von A = QR, so gilt \begin{eqnarray}|| {\ell} -Ax|{|}_{2}^{2}=||{Q}^{T} {\ell} -Rx|{|}_{2}^{2},\end{eqnarray}

da Q eine orthogonale Matrix ist. Hat A vollen Spaltenrang, d. h. Rang(A) = n, dann hat R ∈ ℝ^N×n die Form

mit einer oberen Dreiecksmatrix \(\hat{R}\in {{\mathbb{R}}}^{n\times n}\). Setzt man \begin{eqnarray}{Q}^{T} {\ell} =\left(\begin{array}{c}b \\ c\end{array}\right),b\in {{\mathbb{R}}}^{n},c\in {{\mathbb{R}}}^{N-n},\end{eqnarray}

dann folgt \begin{eqnarray}{\Vert \ell -Ax\Vert }_{2}^{2}={\Vert b-\hat{R}x\Vert }_{2}^{2}+{\Vert c\Vert }_{2}^{2}.\end{eqnarray}

Dieser Ausdruck wird minimal für x ∈ ℝⁿ mit \(\hat{R}x=b\). Dieses x läßt sch leicht durch Rückwärtseinsetzen gewinnen.

Hat A nicht vollen Spaltenrang, d. h. Rang(A) = r < n, dann existieren unendlich viele Lösungen des Ausgleichsproblems \(\mathop{\min }\limits_{x}|| {\ell} -Ax|{|}_{2}^{2}\). In diesem Fall wählt man i. allg. unter allen minimierenden Lösungen x diejenige mit kleinster 2-Norm als Lösung des Ausgleichsproblems. Zur Berechnung verwendet man die Singulärwertzerlegung A = UΣV^T, wobei U ∈ ℝ^N×N und V ∈ ℝ^n×n orthogonale Matrizen, und Σ eine Diagonalmatrix der Form

ist. Schreibt man U = (u₁, …, u_N), u_j ∈ ℝ^N und V = (v₁, …, v_n), v_j ∈ ℝⁿ, dann minimiert \begin{eqnarray}x=\displaystyle \sum _{i=1}^{r}\frac{{u}_{i}^{T} {\ell} }{{\sigma }_{i}}{v}_{i}\end{eqnarray}

gerade \(|| {\ell} -Ax|{|}_{2}^{2}\) und hat die kleinste 2-Norm aller minimierenden Lösungen.

Die Methode der kleinsten Quadrate geht auf Gauß zurück und fand zunächst vorwiegend in der Ausgleichsrechnung Verwendung. Die Grundaufgabe der Ausgleichsrechnung besteht darin, an N Punkte (x_i, y_i), i = 1, …, n, der Ebene eine Funktion \(f(x;\overrightarrow{\gamma })\), x ∈ ℝ¹, die bis auf k unbekannte Parameter \(\overrightarrow{\gamma }=({\gamma }_{1},\mathrm{...},{\gamma }_{k})\in {{\mathbb{R}}}^{k}\), k < n, vollständig gegeben ist, möglichst gut durch geeignete Wahl der Parameter \(\overrightarrow{\gamma }\) anzupassen. Die Methode fand Einzug in die mathematische Statistik, als R.A.Fisher die Maximum-Likelihood-Methode eingeführt und ihren Zusammenhang zur Methode der kleinsten Quadrate hergestellt hat. Sie wird hier vor allem in der Regressionsanalyse zur Konstruktion von Punktschätzungen für die Parameter der Ausgleichsfunktion, die in der Regressions-analyse als Regressionsfunktion bezeichnet wird, angewendet.