Levenbergo-Markardo algoritmas
Levenbergo-Markardo algoritmas yra skaitinis funkcijos (dažniausiai netiesinės) minimizavimo problemos matematinis sprendimas virš funkcijos parametrų erdvės.
Ši minimizavimo problema iškyla mažiausių kvadratų (angl. least squares) kreivės apibrėžimo paieškoje (žiūrėkite: netiesinis programavimas).
Levenbergo-Markardo algoritmas (LMA) interpoliuoja tarp Gauso-Niutono algoritmo (GNA) ir gradientinio nuolydžio metodo. LMA yra labiau atsparus nei GNA. Tai reiškia, kad daugelyje atvejų jis suranda sprendimą, net jei pradžios taškas buvo labai toli nuo galutinio minimumo. Kitą vertus, gerai besielgiančioms funkcijoms ir su gerais pradiniais parametrais, LMA linkęs veikti šiek tiek lėčiau už GNA.
LMA yra labai populiarus kreivių funkcijų paieškos algoritmas; daugumoje programinės įrangos, kuri turi pagrindinius kreivių funkcijų radimo įrankius, realizuotas ir LMA.
Problema redaguoti
Algoritmo pagrindinė užduotis yra mažiausių kvadratų apibrėžimo problema: turint aibę empirinių duomenų porų (ti, yi), optimizuoti modelio kreivės f(t|p) parametrus p taip, kad išvestinių kvadratų suma : pasidarytų mažiausia.
![{\displaystyle S(\mathbf {p} )=\sum _{i=1}^{m}[y_{i}-f(t_{i}\mid \mathbf {p} )]^{2}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3cbbee26c63710dcab64423cf300a85f108d5119)
(Apie notaciją: vengiama naudoti raidę x, nes kartais ji naudojama vietoj p, o kartais vietoj t).
Sprendimas redaguoti
Kaip ir kiti skaitiniai algoritmai, Levenbergo-Markardo algoritmas yra iteratyvi procedūra. Pradedant minimizaciją, vartotojas turi pateikti pradines reikšmes parametro vektoriui p, jas galima parinkti ir atsitiktinai. Bendru atveju standartinis pradinių duomenų apibrėžimas kaip pT=(1,1,…,1) suveiks gerai; kitais atvejais algoritmas konverguoja tik tada, kai parametrų vektorius jau yra sąlyginai arti galutinio sprendinio.
Kiekviename iteracijos žingsnyje parametro vektorius p yra pakeičiamas naujai apskaičiuotu p + q. Siekiant nustatyti q , funkcijos fi( p+q ) yra aproksimuojamos pagal jų linearizacijas
- f(p + q) ≈ f(p) + Jq
kur J yra funkcijos f su parametru p Jakobianas.
Kvadratų sumos S minimume mes turime ∇qS = 0. Apskaičiavus lygties dešiniosios pusės išvestinę ir prilyginus ją nuliui, gauname:
- (JTJ)q = −JTf
iš kur galime apskaičiuoti q transponuojant JTJ. LMA pagrindas yra šios lygties pakeitimas 'prislopintu' variantu
- (JTJ + λ.I)q = −JTf.
Slopinimo koeficientas (neneigiamas) λ yra koreguojamas kiekvienoje iteracijoje. Sparčiai mažėjant S galima naudoti mažesnę reikšmę. Taip algoritmas supanašės su GNA. Kitu atveju, jei iteracija nepakankamai sumažina liekaną, λ reikšmė gali būti padidinta, taip priartinant žingsniu arčiau prie gradientinio nuolydžio krypties. Panašus slopinimo koeficientas yra ir Tichonovo reguliarizavime, kuris naudojamas sprendžiant tiesines blogai suformuluotas problemas.
Jeigu gauto žingsnio ilgis arba kvadratų sumos redukcijos iki parametro vektoriaus p tampa trumpesnis už apibrėžtą minimumą, iteravimas nutraukiamas. Paskutinis parametro vektorius p yra laikomas sprendimu.