Knowledge Base Wiki

Minstakvadratmetoden (även minsta-kvadrat-metoden eller minsta kvadrat-metoden) används bland annat vid regressionsanalys för att minimera felet i en funktion som ska anpassas utifrån observerade värden. Exempel på tillämpningar är

Utifrån gjorda folkräkningar vill man förutsäga befolkningsökningen i ett område genom att göra folkmängden till en funktion av tiden.
Inom hydrologi vill man beräkna hur stort skyfall som inträffar en gång var hundrade år, till exempel för att kunna dimensionera en mindre damm (se även frekvensanalys). I detta fall görs regnmängden till en funktion av återkomsttiden.

Minstakvadratmetoden har en linjär och en icke-linjär variant beroende på om residualerna (”felen”) är linjära eller inte med avseende på alla obekanta. Den linjära varianten tillämpas inom regressionsanalys och har en sluten form. Den icke-linjära bygger vanligen på iterativa metoder. Vid varje iteration approximeras lösningen med en linjär lösning, varför de grundläggande beräkningarna är snarlika i båda fallen.

Historik

På nyårsdagen 1801 upptäckte den italienske astronomen Giuseppe Piazzi dvärgplaneten Ceres. Under 40 dagar kunde han följa dess väg, tills Ceres försvann bakom solen. Under året hade många forskare utan framgång försökt att beräkna banan baserat på Piazzis iakttagelser - under antagandet att banan var cirkulär, eftersom endast sådana bandelar kunde bestämmas matematiskt utifrån de observerade positionerna vid denna tidpunkt. Den 24-årige Carl Friedrich Gauss kunde dock beräkna elliptiska banor utifrån tre olika observationer. Med tillgång till betydligt fler spårpunkter, använde han sin minstakvadratmetod för att öka noggrannheten. När småplaneterna på nytt observerades av Franz Xaver von Zach och Heinrich Wilhelm Olbers i december 1801, i exakt de positioner som förutsagts av Gauss, var detta inte bara en stor framgång för Gauss metod, utan ledde även till ett återupprättande av Piazzis rykte, som skadats på grund av konflikten med omloppsbanor beräknade under antagandet att banorna var cirkulära^[1]. Minstakvadratmetoden blev snabbt standardförfarandet vid behandlingen av astronomiska och geodetiska mätresultat.

Minstakvadratmetoden tillskrivs vanligen Carl Friedrich Gauss (1795),^[2] men publicerades först av Adrien-Marie Legendre.^[3]

Anpassning av en funktion till observerade data

En vanlig modell för att representera en mätserie

(x_{1},\ y_{1}),\ (x_{2},\ y_{2}),\,\dots ,\ (x_{n},\ y_{n})

i form av en funktion, är en linjärkombination av m kända (valda) funktioner

f(t)=c_{1}f_{1}(t)+c_{2}f_{2}(t)+\dots +c_{m}f_{m}(t)

där koefficienterna c₁, c₂, ... , c_m skall bestämmas för att i minstakvadratmetodens mening bäst anpassa kurvan f till mätserien, vilket innebär att summan

\sum _{i=1}^{n}\ [y_{i}-f(x_{i})]^{2}

skall minimeras.

För en lösning konstrueras först den så kallade designmatrisen

A={\begin{bmatrix}f_{1}(x_{1})&f_{2}(x_{1})&\cdots &f_{m}(x_{1})\\f_{1}(x_{2})&f_{2}(x_{2})&\cdots &f_{m}(x_{2})\\\vdots &\vdots &\vdots &\vdots \\f_{1}(x_{n})&f_{2}(x_{n})&\cdots &f_{m}(x_{n})\\\end{bmatrix}}

Med

\mathbf {c} ={\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{m}\\\end{bmatrix}},\quad \mathbf {y} ={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n}\\\end{bmatrix}}

Avståndet ("felet") mellan datapunkter och approximerande kurva mäts i "vertikal" led och inte som punkternas vinkelräta avstånd till kurvan

kan ett linjärt ekvationssystem (vanligen överbestämt, normalt är n betydligt större än m) i m obekanta skrivas

A\cdot \mathbf {c} =\mathbf {y}

Att lösa detta ekvationssystem i minstakvadratmetodens mening är ekvivalent med att lösa normalekvationen

A^{T}A\,\mathbf {c} =A^{T}\,\mathbf {y}

där A^T är transponatet till A.

Om A och y har samma antal rader och om kolumnvektorerna i A är linjärt oberoende, har normalekvationen en entydig lösning c_min, för vilken gäller

\|A\mathbf {\,} c-\mathbf {y} \|^{2}\geq \|A\,\mathbf {c} _{min}-\mathbf {y} \|^{2}

det vill säga, c_min är minimumpunkten till funktionen

\mathbf {c} \rightarrow \|A\,\mathbf {c} -\mathbf {y} \|^{2}

Det kvadratiska medelfelet beräknas som

\epsilon =\|A\,\mathbf {c} _{min}-\mathbf {y} \|/{\sqrt {n}}

Anpassning av polynom

För att anpassa ett polynom av grad m

c_{0}+c_{1}x+\dots +c_{m}x^{m}

till datamängden

(x_{1},\ y_{1}),\ (x_{2},\ y_{2}),\,\dots ,\ (x_{n},\ y_{n})

sätts polynomets monom (med alla c_i = 1) med beräknade värden in som rader i designmatrisen

A={\begin{bmatrix}1&x_{1}^{1}&\cdots &x_{1}^{m}\\1&x_{2}^{1}&\cdots &x_{2}^{m}\\\vdots &\vdots &\vdots &\vdots \\1&x_{n}^{1}&\cdots &x_{n}^{m}\end{bmatrix}}

De sökta koefficienterna c och alla y-värden bildar kolumnvektorerna

\mathbf {c} ={\begin{bmatrix}c_{0}\\c_{1}\\\vdots \\c_{m}\end{bmatrix}},\quad \mathbf {y} ={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n}\end{bmatrix}}

Därefter löses vanligen normalekvationen

A^{T}A\cdot \mathbf {c} =A^{T}\cdot \mathbf {y}

Val av polynomets grad

Givet värdet av datamängdens storlek, n, hur skall det approximerande polynomets grad m väljas? Grundantagandet är^[4] att m < n, eller åtminstone att datamängden med tillräcklig noggrannhet kan approximeras av ett sådant polynom. Om m ≥ n förbättras inte approximationen. Är m = n - 1 är lösningen exakt, men i detta fall förloras en vanligen önskvärd egenskap hos polynomet, nämligen förmågan att filtrera bort detaljer orsakade av mätfel och andra störningar (till exempel numeriska fel).

Normalekvationen

Ett vektorrum V spänns upp av A:s kolonnvektorer, i detta fall u och v. Vektorn b tillhör inte V varför ekvationssystemet A c = b saknar lösning. A c_min - b är ortogonal mot alla vektorer i V.
c_min kan ses som de koefficienter som minimerar "längden" av vektorn A c - b

Som en orientering beskrivs kortfattat en bakgrund till normalekvationen

A^{T}A\,\mathbf {c} =A^{T}\mathbf {b}

i form av ett specialfall (illustrerbart) med tre linjära ekvationer och två obekanta koefficienter. Antag att

A={\begin{bmatrix}u_{1}&v_{1}\\u_{2}&v_{2}\\u_{3}&v_{3}\\\end{bmatrix}}\ =\ {\begin{bmatrix}\mathbf {u} &\mathbf {v} \\\end{bmatrix}},

\mathbf {c} ={\begin{bmatrix}c_{1}\\c_{2}\\\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}

och att kolonnvektorerna u och v i A spänner upp vektorrummet V (här, ett plan i R³). I allmänhet tillhör inte b vektorrummet V, varför ekvationen A c - b = 0 i allmänhet saknar lösning. Det är emellertid möjligt att söka en approximativ lösning, till exempel i minstakvadratmetodens mening, alltså en lösning till minimumproblemet

\min _{\mathbf {c} }\,\|A\,\mathbf {c} -\mathbf {b} \|^{2}

Detta minimum föreligger när A c - b är ortogonal mot vektorerna i V, det vill säga då skalärprodukterna av A c - b och varje vektor i V är noll. Men raderna i A:s transponat tillhör V och då matrisprodukten av A:s transponat och A c - b är definierad, ger detta

A^{T}(A\,\mathbf {c} -\mathbf {b} )=0\quad \Rightarrow \quad A^{T}A\,\mathbf {c} =A^{T}\mathbf {b}

och det sökta värdet på c, c_min, måste således satisfiera detta ekvationssystem. Om matrisen A^TA är inverterbar (om och endast om, kolonnerna i A är linjärt oberoende) är lösningen

\mathbf {c} _{min}=(A^{T}A)^{-1}A^{T}\,\mathbf {b}

och det går att visa att c_min uppfyller

\|A\,\mathbf {c} -\mathbf {b} \|^{2}\geq \|A\,\mathbf {c} _{min}-\mathbf {b} \|^{2}

Dessa resultat är i huvudsak tillämpbara på allmänna rektangulära matriser A.

Lösningar om designmatrisens kolonner är ortogonala

Sök en lösning till ekvationen $A\cdot \mathbf {c} =\mathbf {b}$ om

A={\begin{bmatrix}1&-12\\1&-4\\1&2\\1&14\end{bmatrix}}={\begin{bmatrix}\mathbf {u} &\mathbf {v} \end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}-2\\4\\2\\12\end{bmatrix}}

Eftersom kolonnerna i A är ortogonala ( $\mathbf {u} \cdot \mathbf {v} =0$ ) ges den ortogonala projektionen av b på A:s kolonnrum av

{\hat {\mathbf {b} }}={\frac {\mathbf {b} \cdot \mathbf {u} }{\mathbf {u} \cdot \mathbf {u} }}\mathbf {u} +{\frac {\mathbf {b} \cdot \mathbf {v} }{\mathbf {v} \cdot \mathbf {v} }}\mathbf {v} =4\mathbf {u} +{\frac {1}{2}}\mathbf {v} ={\begin{bmatrix}4\\4\\4\\4\end{bmatrix}}+{\begin{bmatrix}-6\\-2\\1\\7\end{bmatrix}}={\begin{bmatrix}-2\\2\\5\\11\end{bmatrix}}\quad (1)

Då den ortogonala projektionen ${\mathbf {\hat {b}} }$ är känd går det att lösa $A\cdot \mathbf {\hat {c}} =\mathbf {\hat {b}}$ . Enligt (1) är $\mathbf {\hat {c}} ={\begin{bmatrix}4\\{\cfrac {1}{2}}\end{bmatrix}}$ , vilket i minstakvadratmetodens mening också är lösningen till $A\cdot \mathbf {c} =\mathbf {b}$ .

Matriser där kolonnerna är ortogonala förekommer relativt ofta i problem inom linjär regression^[5].

Exempel

Anpassning av en rät linje

Vilken rät linje

y=c_{1}x+c_{0}

ger bästa anpassningen till mätserien

(x_{1},\ y_{1}),\ (x_{2},\ y_{2}),\,...\,,\ (x_{n},\ y_{n})

I detta fall blir designmatrisen

A={\begin{bmatrix}1&x_{1}\\1&x_{2}\\\vdots &\vdots \\1&x_{n}\end{bmatrix}}

och y-värdena och de sökta koefficienterna placeras i

\mathbf {y} ={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n}\end{bmatrix}},\quad \mathbf {c} ={\begin{bmatrix}c_{0}\\c_{1}\end{bmatrix}}

Därefter löses

A^{T}A\cdot \mathbf {c} =A^{T}\cdot \mathbf {y}

med avseende på c.

Anpassning av ett andragradspolynom

Givet datapunkterna (1,10), (2,8), (3,11), (4,17), (5,24) söks de koefficienter till andragradspolynomet

y=c_{2}x^{2}+c_{1}x+c_{0}

som enligt minstakvadratmetoden är bäst anpassade till observationerna.

Designmatrisen och vektorn för y-värdena är

A={\begin{bmatrix}1&1&1\\1&2&4\\1&3&9\\1&4&16\\1&5&25\end{bmatrix}},\quad \mathbf {y} ={\begin{bmatrix}10\\8\\11\\17\\24\end{bmatrix}}

A^{T}A={\begin{bmatrix}5&15&55\\15&55&225\\55&225&979\end{bmatrix}},\quad A^{T}\mathbf {y} ={\begin{bmatrix}70\\247\\1013\end{bmatrix}}

Normalekvationen löses med avseende på c

A^{T}A{\begin{bmatrix}c_{0}\\c_{1}\\c_{2}\end{bmatrix}}=A^{T}\mathbf {y} \quad \Rightarrow \quad {\begin{matrix}c_{0}=&13{,}4\\c_{1}=&-5{,}3\\c_{2}=&1{,}5\end{matrix}}

och det anpassade andragradspolynomet är således

y=1{,}5x^{2}-5{,}3x+13{,}4

Jämförelse mellan observerade och minstakvadratanpassade y-värden.
x	uppmätt y	anpassat y	felet	felet i kvadrat
1	10	9,6	-0,4	0,16
2	8	8,8	0,8	0,64
3	11	11,0	0,0	0,00
4	17	16,2	-0,8	0,64
5	24	24,4	0,4	0,16
Summa:				1,60

Av alla möjliga andragradspolynom har inget en summa av felen i kvadrat som understiger 1,6.

Anpassning av ellips

Kan datapunkterna (-9, 2), (-2, 5), (3, 6), (7, 4), (9, 1), (8, -4), (1, -5), (-4, -5), (-8, -3), (-9, -1) på ett meningsfullt sätt beskrivas av en ellips? Minstakvadratmetoden kan användas för att anpassa en ellips till datamängden. Ekvationen för en ellips är

{\frac {x^{2}}{a^{2}}}+{\frac {y^{2}}{b^{2}}}=1

där a, b är ellipsaxlarnas längder.

De beräknade värdena för ellipsekvationens termer (med a och b = 1) sätts in i designmatrisens rader och värdena i ellipsekvationens högerled sätts in i kolumnvektorn b:

A={\begin{bmatrix}x_{1}^{2}&y_{1}^{2}\\x_{2}^{2}&y_{2}^{2}\\\vdots &\vdots \\x_{n}^{2}&y_{n}^{2}\end{bmatrix}}\ ={\begin{bmatrix}81&4\\4&25\\\vdots &\vdots \\81&1\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}

A^{T}A={\begin{bmatrix}30630&3719\\3719&3782\\\end{bmatrix}},\quad A^{T}\mathbf {b} ={\begin{bmatrix}450\\158\end{bmatrix}}

Normalekvationen löses

A^{T}A{\begin{bmatrix}c_{1}\\c_{2}\end{bmatrix}}=A^{T}\mathbf {b} \quad \Rightarrow \quad {\begin{matrix}c_{1}=0.010923\\c_{2}=0.031036\end{matrix}}

och därmed är

a={\sqrt {\frac {1}{c_{1}}}}=9.5681

b={\sqrt {\frac {1}{c_{2}}}}=5.6764

Anpassning av en yta

Anpassning av en yta i R³,

z(x,y)=c_{1}\,x^{3}+c_{2}\,y^{3}+c_{3}\,x\,y

till datapunkterna (x, y, z-koordinater i R³)

(2, 4, 33), (-1, 1, 2), (1, -3, 7), (4, 4, 88), (-2, -3, 26), (-3, 1, 13), (-1, -1, 4), (4, 1, 36)

Designmatrisen A konstrueras och datapunkternas z-värden placeras i kolonnvektorn z:

A={\begin{bmatrix}x_{1}^{3}&y_{1}^{3}&x_{1}\,y_{1}\\x_{2}^{3}&y_{2}^{3}&x_{2}\,y_{2}\\\vdots &\vdots &\vdots \\x_{n}^{3}&y_{n}^{3}&x_{n}\,y_{n}\end{bmatrix}}\ ={\begin{bmatrix}8&64&8\\-1&1&-1\\\vdots &\vdots &\vdots \\64&1&4\end{bmatrix}}

\mathbf {z} ={\begin{bmatrix}z_{1}\\z_{2}\\\vdots \\z_{n}\end{bmatrix}}={\begin{bmatrix}33\\2\\\vdots \\36\end{bmatrix}}

Normalekvationen kan nu ställas upp och lösas:

A^{T}A{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}=A^{T}\mathbf {z} \quad \Rightarrow \quad {\begin{matrix}c_{1}=&0.218245\\c_{2}=&-0.033352\\c_{3}=&4.241390\end{matrix}}

Referenser

Noter

^ Moritz Cantor: Gauß: Karl Friedrich G.. Allgemeine Deutsche Biographie. Band 8, Duncker & Humblot, Leipzig 1878, S. 430–445., S. 436
^ Bretscher, Otto (1995). Linear Algebra With Applications (3rd). Upper Saddle River, NJ: Prentice Hall
^ Stigler, Stephen M. (1981). ”Gauss and the Invention of Least Squares”. Ann. Stat. 9 (3): sid. 465–474. doi:10.1214/aos/1176345451. http://projecteuclid.org/euclid.aos/1176345451.
^ Anthony Ralston and Philip Rabinowitz (1978). A First Cource In Numerical Analysis, Second Edition, ISBN 0-07-051158-6
^ Linear Algebra and its Applications, David C. Lay ISBN 978-1-292-09223-2

[1] Moritz Cantor: Gauß: Karl Friedrich G.. Allgemeine Deutsche Biographie. Band 8, Duncker & Humblot, Leipzig 1878, S. 430–445., S. 436

[brertscher-2] Bretscher, Otto (1995). Linear Algebra With Applications (3rd). Upper Saddle River, NJ: Prentice Hall

[3] Stigler, Stephen M. (1981). ”Gauss and the Invention of Least Squares”. Ann. Stat. 9 (3): sid. 465–474. doi:10.1214/aos/1176345451. http://projecteuclid.org/euclid.aos/1176345451.

[4] Anthony Ralston and Philip Rabinowitz (1978). A First Cource In Numerical Analysis, Second Edition, ISBN 0-07-051158-6

[5] Linear Algebra and its Applications, David C. Lay ISBN 978-1-292-09223-2

[1]

[2]

[3]

[4]

[5]