Metoda nejmenších čtverců

matematicko-statistická metoda pro aproximaci řešení přeurčených soustav rovnic

Metoda nejmenších čtverců je matematicko-statistická metoda pro aproximaci řešení přeurčených soustav rovnic (tj. soustav, kde je více rovnic, než neznámých). „Nejmenší čtverce“ znamenají, že výsledné řešení má minimalizovat součet čtverců odchylek vůči každé rovnici. Metoda je v základní podobě určená pro řešení nekompatibilních soustav lineárních rovnic (v obecnější podobě hovoříme o nelineární metodě nejmenších čtverců), díky čemuž je fakticky ekvivalentní tzv. lineární regresi.

Graf zobrazuje proložení paraboly experimentálními daty zatíženými chybou. Koeficienty kvadratické funkce jsou nalezené metodou nejmenších čtverců.

S nejjednodušší aplikací metody nejmenších čtverců se setkáváme například při prokládání (aproximaci) naměřených jednorozměrných dat přímkou. Nepatrně složitější aplikací je proložení dat parabolou, obecným polynomem předem daného stupně, nebo obecnou lineární kombinací předem daných bázových funkcí. Fakt, že proložení dat polynomem libovolného, ale předem daného stupně je stále lineární regresí, je častým zdrojem nedorozumění a terminologických nejasností. Další jednoduchou aplikací je nalezení nejpravděpodobnějšího průsečíku několika přímek (jejichž matematický popis je zatížen chybou) v rovině. Metoda nejmenších čtverců má velmi mnoho dalších aplikací v nejširším okruhu vědních oborů, ve kterých se setkáváme s nepřesnými daty, od statistiky a ekonomie, přes geodézii až po zpracování signálů a teorii řízení.

Obecně metoda nejmenších čtverců slouží k eliminaci chyb, kterou provádí optimálně vzhledem k pevně danému jednoznačnému kritériu (viz níže). Optimálně eliminovat chyby v datech lze i vzhledem k jiným kriteriím, takový postup může vést na metody převoditelné na metodu nejmenších čtverců (při použití různých typů vážení, např. když je známo, že chyba některých měření se výrazně liší od zbytku), nebo na metody obecně nepřevoditelné (nebo obtížně převoditelné) na metodu nejmenších čtverců (např. úplný problém nejmenších čtverců).[1]

Historie editovat

Metodu nejmenších čtverců poprvé použil Carl Friedrich Gauss v roce 1795 pro eliminaci chyb při geodetickém vyměřování.

Odvození metody editovat

Uvažujme lineární aproximační problém

 

takový, že   (jinými slovy, neexistuje žádný vektor   takový, aby nastala rovnost); symbol   značí obor hodnot matice  , tedy lineární obal jejích sloupců. Metoda nejmenších čtverců hledá vektor   (LS je zkratkou anglického least squares) splňující

 

nebo ekvivalentně, opravu pravé strany   splňující

 

Zřejmě   a oprava pravé strany   je residuum odpovídající vektoru  . Označíme-li   jednotlivé komponenty vektoru  , pak z definice Eukleidovské normy přímo plyne

 

Takže minimalizujeme součet čtverců jednotlivých komponent vektoru  , tj. odchylek jednotlivých komponent pravé strany  . Nalezení vztahu pro vektor   splňující podmínku minimality můžeme provést buď pomocí derivací (hledáním lokálního extrému) nebo přímo pomocí Pythagorovy věty.

Minimalizace kvadratického funkcionálu: Residuum   je vektor, jehož normu minimalizujeme. Zřejmě

 

Úlohu tedy můžeme zapsat jako minimalizaci kvadratického funkcionálu, kde volné parametry minimalizace jsou komponenty vektoru  . Lokální extrém funkcionálu leží v bodě, kde se derivace funkcionálu podle všech komponent vektoru   rovnají nule. Z vlastností normy je zřejmé, že se jedná o lokální minimum, které je zároveň minimem globálním. V maticovém zápisu lze formálně použít derivaci podle vektoru  . Dostáváme

 

Ortogonalita: Hledáme vektor   s minimální normou, tj. eukleidovskou délkou. Z Pythagorovy věty vyplývá, že nejkratší vzdálenost dostaneme tehdy, pokud bude residuum   ortogonální na obor hodnot  . Minimality tedy dosáhneme požadavkem

 

Dosazením za residuum dostáváme

 

V obou případech tedy dostáváme, že hledaný vektor   je řešením tzv. normální soustavy rovnic

 

Za předpokladu, že   má lineárně nezávislé sloupce (ekvivalentně, že   je regulární), pak

 

Z předpokladu lineární nezávislosti sloupců přímo plyne, že řešení je jednoznačné.

Při praktickém výpočtu se ovšem normální soustava nikdy nesestavuje z důvodů numerické stability výpočtu. Použití zde odvozených vztahů pro praktický netriviální výpočet je jen obtížně ospravedlnitelné.[2]

Pokud má matice   lineárně závislé sloupce, je situace nepatrně komplikovanější. Řešení ve smyslu nejmenších čtverců tak jak je definované není jednoznačné. Zpravidla se pak uvažuje řešení ve smyslu nejmenších čtverců minimální v normě. Tedy mezi všemi přípustnými řešeními se hledá řešení s nejmenší normou. Opět užitím Pythagorovy věty můžeme minimalitu normy nahradit ortogonalitou. Řešení minimální v normě je pak ortogonální na nulový prostor matice  . Je tedy dáno vztahem

 

kde   je Mooreova–Penroseova pseudoinverze. V tomto kontextu je třeba zmínit, že určení (numerické) hodnosti matice, tj. faktu, zda jsou sloupce matice   (numericky) lineárně nezávisle, je samo o sobě velmi obtížná úloha.

V následujících odstavcích se seznámíme s nejdůležitějšími aplikacemi metody nejmenších čtverců, vesměs se však jedná pouze o návody jak sestavit matici   a pravou stranu   v konkrétních případech.

Řešení úlohy nejmenších čtverců editovat

Metod k nalezení řešení   pro daný aproximační problém   je celá řada a dají se rozdělit podle dvou zásadních kritérií:

  • velikost (a řídkost) problému (za velké považujeme zpravidla takové problémy, kdy s maticí   nelze z paměťových a časových důvodů pracovat jako s polem obsahujícím všech   čísel, u reálných problémů mohou být rozměry matic v řádech stovek milionů i vyšší),
  • hodnost matice  , neboli počet lineárně nezávislých sloupců (pokud má matice lineárně závislé sloupce je řešení výrazně komplikovanější).[2][3]

QR rozklad editovat

Mezi základní metody řešení patří QR rozklad (počítaný buď ortogonálními transformacemi, nebo Gram-Schmidtovým ortogonalizačním procesem). Předpokládejme, že matice   má lineárně nezávislé sloupce, pak existuje QR rozklad ve tvaru

 

kde   má ortonormální sloupce,   a   je horní trojúhelníková. Zřejmě platí   a  . Formálním dosazením do normální soustavy rovnic dostáváme

 

Po vynásobení maticí   zleva vidíme, že

 

Řešení tedy dostaneme snadno řešením soustavy s horní trojúhelníkovou maticí   (ta je mimochodem Choleského faktorem matice   ovšem spočteným numericky stabilní cestou).

Výpočet je použitelný pouze pokud má matice   (numericky) lineárně nezávislé sloupce (postup lze rozšířit i pro matice s lineárně závislými sloupci pomocí tzv. RRQR rozkladu, obecně tak získáme pouze aproximaci řešení). Matice   při nalezení vlastního řešení potřeba není, můžeme tedy bez problémů použít levnější (ovšem méně přesný) Gram-Schmidtův proces. Pro rozsáhlé úlohy s velkým počtem sloupců může snadno dojít k rychlému zaplnění trojúhelníkového faktoru, proto je tento postup pro tyto typy úloh prakticky nepoužitelný.

Nebezpečí skryté v postupu hledání řešení problému nejmenších čtverců pomocí explicitního sestavení matice   je dobře známe, viz např. Lauchliho matice.[4]

Singulární rozklad editovat

Má-li matice   lineárně závislé sloupce, jedinou spolehlivou metodou je singulární rozklad a v podstatě explicitní sestavení Mooreovy–Penroseovy pseudoinverze. Pokud  , a její ekonomický singulární rozklad je

 

což umožňuje přímo nalézt řešení ve smyslu nejmenších čtverců minimální v normě.

Výpočet je použitelný pouze pro malé úlohy vzhledem k velké výpočetní náročnosti singulárního rozkladu.

Iterační metody editovat

Pro řešení rozsáhlých úloh jsou standardem a jediným prakticky použitelným řešením iterační metody, zpravidla postavené na Krylovových podprostorech rostoucí dimenze. Klasickým představitelem je LSQR[5][6] a další odvozené algoritmy CGLS, CGNE.

Aplikace: Regresní analýza editovat

Související informace naleznete také v článku Lineární regrese.

Metoda nejmenších čtverců bývá často používána při regresní analýze pro aproximaci zadaných (naměřených) hodnot nějakou funkcí z předepsaného prostoru. Nejjednodušším příkladem je proložení (aproximace) dat přímkou, tedy lineární funkcí. Protože klasická metoda nejmenších čtverců vede vždy na lineární aproximační model (de-facto soustavu rovnic) je často považována za ekvivalent pojmu lineární regrese. To souvisí s faktem, že libovolný aproximační problém   lze interpretovat jako lineární regresi v  -rozměrném prostoru, kde jsme v bodě o souřadnicích   naměřili nějakou veličinu  ,   a naměřené hodnoty prokládáme nadrovinou.

Pro první přiblížení uvažujme závislost nějaké nezávisle proměnné (např. fyzikální veličiny)   na nezávisle proměnné  , tj.  . přičemž závislost má nějaký předem daný tvar, např.  , kde koeficienty   a   jsou známé. Pro identifikaci těchto koeficientů provedeme   měření veličiny   v přesně definovaných hodnotách nezávisle proměnné  . Získáme tak sadu   dvojic   přičemž hodnoty   jsou zatížené chybami měření. Dostaneme tak lineární aproximační problém

 

Metoda nejmenších čtverců hledá takové hodnoty koeficientů  ,  , aby součet čtverců „odchylek“ (reziduí) jejích funkčních hodnot od daných naměřených hodnot byl nejmenší možný.

Aproximace přímkou editovat

Pro proložení daných hodnot přímkou (lineární funkcí, polynomem prvního řádu) s rovnicí   dostaneme z normální soustavy rovnic vztahy

 

Aproximace parabolou editovat

Zadané hodnoty lze aproximovat parabolou (kvadratickou funkcí, polynomem druhého řádu) s rovnicí  . Optimální parametry   získáme opět řešením normální soustavy rovnic

 

Proložení bodů parabolou je lineární regresí kvadratické funkce (kvadratického modelu), zejména ve starší literatuře se můžeme setkat i s pojmem kvadratická regrese.[7]

Aproximace polynomem editovat

 
Ukázka aproximace zadaných bodů polynomem stupně s = 0,...,9.

Obdobně jako v případě paraboly, i při aproximaci polynomem   přímým dosazením hodnot  ,   získáme soustavu rovnic  . V maticovém zápisu

 

Přejdeme-li čistě formálně k normální soustavě rovnic (při řešení reálných problémů tuto soustavu nikdy nesestavujeme), dostáváme

 

která má vždy řešení. Pokud má matice   lineárně nezávislé sloupce, pak   je regulární a   je jednoznačným řešením původního problému ve smyslu nejmenších čtverců.

Proložení bodů polynomem (předem) daného stupně   je lineární regresí polynomu (polynomiálního modelu), zejména ve starší literatuře se můžeme setkat i s pojmem polynomiální (polynomická) regrese.[7]

Aplikace: Nalezení průsečíku několika nadrovin v prostoru editovat

 
Nalezení průsečíku tří přímek (zatížených chybami) metodou nejmenších čtverců

Opět se snažíme úlohu přeformulovat jako lineární aproximační problém  . Mechanismus lze nejsnáze ilustrovat na příkladu nalezení průsečíku několika přímek v rovině. Jsou dány tři přímky v rovině

 

které nemají společný průsečík. Zřejmě

 

a vektor   je nenulový pro libovolné   a  . Za předpokladu, že přímky nejsou známy přesně (jejich popis je zatížen chybami) a chyby jsou obsaženy pouze v konstantních členech (tedy v pravé straně   aproximačního problému), můžeme použít k nalezení nejpravděpodobnějšího místa průsečíku metodu nejmenších čtverců. Získáme tak bod

 

Všimněme si, že při přenásobení kterékoliv z rovnic definujících přímky nenulovou konstantou (různou od  ), pracujeme se stejnými přímkami ale hledaný bod vyjde jinde. Taková operace totiž není v problému nejmenších čtverců ekvivalentní operací, fakticky taková operace změní normu, ve které provádíme minimalizaci.

Odkazy editovat

Reference editovat

  1. Christopher C. Paige, Zdeněk Strakoš, Scaled Total Least Squares Fundamentals, Numerische Mathematik, 91, 2002, pp. 117-146.
  2. a b Åke Björck, Numerical Methods for Least Squares Problems, SIAM Publications, Philadelphia PA, 1996
  3. Charles L. Lawson, Richard J. Hanson, Solving Least Squares Problem, SIAM Publications, Philadelphia PA, 1995
  4. Lauchli matrix [online]. Matrix Market [cit. 2011-11-03]. Dostupné online. 
  5. Christopher C. Paige, Michael A. Saunders, LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares, ACM Transactions on Mathematical Software, 8(1), 1982.
  6. Christopher C. Paige, Michael A. Saunders, Algorithm 583: LSQR: Sparse Linear Equations and Least Squares Problems, ACM Transactions on Mathematical Software, 8(2), 1982.
  7. a b Jiří Likeš, Josef Machek, Matematická statistika, SNTL Praha 1988, s. 165-169

Související články editovat

Externí odkazy editovat