Metoda nejmenších čtverců

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

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.

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

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

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 Moore-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ů

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

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

Má-li matice lineárně závislé sloupce, jedinou spolehlivou metodou je singulární rozklad a v podstatě explicitní sestavení Moore-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

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

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

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

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

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

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.

Reference

  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

Externí odkazy