Algoritm Gauss-Newton

Regresia unei curbe cu un model de vârf asimetric, utilizând algoritmul Gauss-Newton cu un factor de amortizare

\alpha

{\ displaystyle \ alpha}

\ alfa

variabil.
Deasupra: date brute și curbă model.
Mai jos: evoluția sumei normalizate a pătratelor reziduurilor.

Algoritmul Gauss-Newton este o metodă iterativă pentru rezolvarea problemelor celor mai mici pătrate și a regresiilor neliniare . Este o versiune modificată a metodei Newton pentru găsirea unui minim de funcție . Spre deosebire de acesta din urmă, algoritmul Gauss - Newton poate fi utilizat doar pentru a minimiza o sumă de funcții pătrate, dar are avantajul că nu sunt necesare derivate secundare, adesea dificil de calculat.

Problemele celor mai mici pătrate neliniare apar, de exemplu, în regresia neliniară , unde parametrii sunt căutați astfel încât modelul să fie în acord cu observațiile disponibile.

Numele metodei provine de la matematicienii Carl Friedrich Gauss și Isaac Newton .

Descriere

La tine acasa $m$ ${\ displaystyle m}$ $m$ funcții ${\boldsymbol {r}}=(r_{1},\ldots ,r_{m})$ ${\ displaystyle {\ boldsymbol {r}} = (r_ {1}, \ ldots, r_ {m})}$ ${\ displaystyle {\ boldsymbol {r}} = (r_ {1}, \ ldots, r_ {m})}$ (deseori numite reziduuri) de $n$ ${\ displaystyle n}$ $n$ variabile ${\boldsymbol {\beta }}=(\beta _{1},\ldots ,\beta _{n})$ ${\ displaystyle {\ boldsymbol {\ beta}} = (\ beta _ {1}, \ ldots, \ beta _ {n})}$ ${\ displaystyle {\ boldsymbol {\ beta}} = (\ beta _ {1}, \ ldots, \ beta _ {n})}$ , cu $m\geq n$ ${\ displaystyle m \ geq n}$ ${\ displaystyle m \ geq n}$ , algoritmul Gauss - Newton găsește iterativ valorile variabilelor pentru a minimiza următoarea sumă de pătrate: ^[1]

S({\boldsymbol {\beta }})=\sum _{i=1}^{m}r_{i}^{2}({\boldsymbol {\beta }}).

{\ displaystyle S ({\ boldsymbol {\ beta}}) = \ sum _ {i = 1} ^ {m} r_ {i} ^ {2} ({\ boldsymbol {\ beta}}).}

{\ displaystyle S ({\ boldsymbol {\ beta}}) = \ sum _ {i = 1} ^ {m} r_ {i} ^ {2} ({\ boldsymbol {\ beta}}).}

Incepand cu ${\boldsymbol {\beta }}^{(0)}$ ${\ displaystyle {\ boldsymbol {\ beta}} ^ {(0)}}$ ${\ displaystyle {\ boldsymbol {\ beta}} ^ {(0)}}$ ca estimare inițială pentru minim, metoda funcționează iterativ

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\left(\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {J_{r}} \right)^{-1}\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {r} ({\boldsymbol {\beta }}^{(s)}),

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} - \ left (\ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ right) ^ {- 1} \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}),}

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} - \ left (\ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ right) ^ {- 1} \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}),}

unde, dacă ${\boldsymbol {r}}$ ${\ displaystyle {\ boldsymbol {r}}}$ ${\ displaystyle {\ boldsymbol {r}}}$ Și ${\boldsymbol {\beta }}$ ${\ displaystyle {\ boldsymbol {\ beta}}}$ ${\ boldsymbol \ beta}$ sunt vectori de coloană, elementele matricei iacobiene sunt

(\mathbf {J_{r}} )_{ij}={\frac {\partial r_{i}({\boldsymbol {\beta }}^{(s)})}{\partial \beta _{j}}},

{\ displaystyle (\ mathbf {J_ {r}}) _ {ij} = {\ frac {\ partial r_ {i} ({\ boldsymbol {\ beta}} ^ {(s)})} {\ partial \ beta _ {j}}},}

{\ displaystyle (\ mathbf {J_ {r}}) _ {ij} = {\ frac {\ partial r_ {i} ({\ boldsymbol {\ beta}} ^ {(s)})} {\ partial \ beta _ {j}}},}

și simbolul $^{\mathsf {T}}$ ${\ displaystyle ^ {\ mathsf {T}}}$ ${\ displaystyle ^ {\ mathsf {T}}}$ indică matricea transpusă .

De sine $m=n$ ${\ displaystyle m = n}$ $m = n$ , iterația simplifică și devine

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\left(\mathbf {J_{r}} \right)^{-1}\mathbf {r} ({\boldsymbol {\beta }}^{(s)}),

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} - \ left (\ mathbf {J_ {r}} \ right) ^ {-1} \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}),}

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} - \ left (\ mathbf {J_ {r}} \ right) ^ {-1} \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}),}

care este o generalizare directă multidimensională a metodei tangentei .

În regresia datelor, unde scopul este de a găsi valorile parametrilor ${\boldsymbol {\beta }}$ ${\ displaystyle {\ boldsymbol {\ beta}}}$ ${\ displaystyle {\ boldsymbol {\ beta}}}$ astfel încât o anumită funcție de model $y=f(x,{\boldsymbol {\beta }})$ ${\ displaystyle y = f (x, {\ boldsymbol {\ beta}})}$ ${\ displaystyle y = f (x, {\ boldsymbol {\ beta}})}$ este pe cât posibil în conformitate cu seria de puncte $(x_{i},y_{i})$ ${\ displaystyle (x_ {i}, y_ {i})}$ $(x_i, y_i)$ , funcții $r_{i}$ ${\ displaystyle r_ {i}}$ $re$ sunt reziduurile:

r_{i}({\boldsymbol {\beta }})=y_{i}-f(x_{i},{\boldsymbol {\beta }}).

{\ displaystyle r_ {i} ({\ boldsymbol {\ beta}}) = y_ {i} -f (x_ {i}, {\ boldsymbol {\ beta}}).}

{\ displaystyle r_ {i} ({\ boldsymbol {\ beta}}) = y_ {i} -f (x_ {i}, {\ boldsymbol {\ beta}}).}

Apoi, metoda Gauss - Newton poate fi exprimată în termeni de Jacobian ${\boldsymbol {J}}_{f}$ ${\ displaystyle {\ boldsymbol {J}} _ {f}}$ ${\ displaystyle {\ boldsymbol {J}} _ {f}}$ a funcției $f$ ${\ displaystyle f}$ $f$ ca

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}+\left(\mathbf {J_{f}} ^{\mathsf {T}}\mathbf {J_{f}} \right)^{-1}\mathbf {J_{f}} ^{\mathsf {T}}\mathbf {r} ({\boldsymbol {\beta }}^{(s)}).

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} + \ left (\ mathbf {J_ {f}} ^ {\ mathsf {T}} \ mathbf {J_ {f}} \ right) ^ {- 1} \ mathbf {J_ {f}} ^ {\ mathsf {T}} \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}).}

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} + \ left (\ mathbf {J_ {f}} ^ {\ mathsf {T}} \ mathbf {J_ {f}} \ right) ^ {- 1} \ mathbf {J_ {f}} ^ {\ mathsf {T}} \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}).}

Rețineți că $\left(\mathbf {J_{f}} ^{\mathsf {T}}\mathbf {J_{f}} \right)^{-1}\mathbf {J_{f}} ^{\mathsf {T}}$ ${\ displaystyle \ left (\ mathbf {J_ {f}} ^ {\ mathsf {T}} \ mathbf {J_ {f}} \ right) ^ {- 1} \ mathbf {J_ {f}} ^ {\ mathsf {T}}}$ ${\ displaystyle \ left (\ mathbf {J_ {f}} ^ {\ mathsf {T}} \ mathbf {J_ {f}} \ right) ^ {- 1} \ mathbf {J_ {f}} ^ {\ mathsf {T}}}$ este pseudo-inversul lui $\mathbf {J_{f}}$ ${\ displaystyle \ mathbf {J_ {f}}}$ ${\ displaystyle \ mathbf {J_ {f}}}$ . În algoritm, presupunerea $m\geq n$ ${\ displaystyle m \ geq n}$ ${\ displaystyle m \ geq n}$ este necesar, altfel matricea $\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {J_{r}}$ ${\ displaystyle \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}}$ ${\ displaystyle \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}}$ nu este inversabilă și ecuațiile nu pot fi rezolvate (cel puțin într-un mod unic).

Algoritmul Gauss - Newton este obținut din aproximarea liniară a vectorului funcțiilor $r_{i}$ ${\ displaystyle r_ {i}}$ $re$ folosind teorema lui Taylor . De fapt, la fiecare iterație obținem:

\mathbf {r} ({\boldsymbol {\beta }})\approx \mathbf {r} ({\boldsymbol {\beta }}^{(s)})+\mathbf {J_{r}} ({\boldsymbol {\beta }}^{(s)})\Delta

{\ displaystyle \ mathbf {r} ({\ boldsymbol {\ beta}}) \ approx \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}) + \ mathbf {J_ {r}} ({\ boldsymbol {\ beta}} ^ {(s)}) \ Delta}

{\ displaystyle \ mathbf {r} ({\ boldsymbol {\ beta}}) \ approx \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}) + \ mathbf {J_ {r}} ({\ boldsymbol {\ beta}} ^ {(s)}) \ Delta}

cu $\Delta ={\boldsymbol {\beta }}-{\boldsymbol {\beta }}^{(s)}$ ${\ displaystyle \ Delta = {\ boldsymbol {\ beta}} - {\ boldsymbol {\ beta}} ^ {(s)}}$ ${\ displaystyle \ Delta = {\ boldsymbol {\ beta}} - {\ boldsymbol {\ beta}} ^ {(s)}}$ . A găsi $\Delta$ ${\ displaystyle \ Delta}$ $\ Delta$ care minimizează suma pătratelor din partea dreaptă, adică

\min \left\|\mathbf {r} ({\boldsymbol {\beta }}^{(s)})+\mathbf {J_{r}} ({\boldsymbol {\beta }}^{(s)})\Delta \right\|_{2}^{2},

{\ displaystyle \ min \ left \ | \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}) + \ mathbf {J_ {r}} ({\ boldsymbol {\ beta}} ^ { (s)}) \ Delta \ right \ | _ {2} ^ {2},}

{\ displaystyle \ min \ left \ | \ mathbf {r} ({\ boldsymbol {\ beta}} ^ {(s)}) + \ mathbf {J_ {r}} ({\ boldsymbol {\ beta}} ^ { (s)}) \ Delta \ right \ | _ {2} ^ {2},}

este o problemă liniară cu cele mai mici pătrate, care este rezolvată explicit.

Ecuațiile normale sunt $n$ ${\ displaystyle n}$ $n$ ecuații liniare simultane în increment $\Delta$ ${\ displaystyle \ Delta}$ $\ Delta$ incognito. Ele pot fi rezolvate într-un singur pas, folosind descompunerea Cholesky sau, chiar mai bine, factorizarea QR a $\mathbf {J_{r}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ . Pentru sistemele mari, o metodă iterativă , cum ar fi cea a gradientului conjugat , poate fi mai eficientă. Dacă există o dependență liniară între coloanele din $\mathbf {J_{r}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ , iterațiile vor eșua din cauza singularității lui $\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {J_{r}}$ ${\ displaystyle \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}}$ ${\ displaystyle \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}}$ .

Exemplu

Cea mai bună curbă de potrivire obținută (în albastru), cu

{\hat {\beta }}_{1}=0.362

{\ displaystyle {\ hat {\ beta}} _ {1} = 0,362}

{\ displaystyle {\ hat {\ beta}} _ {1} = 0,362}

și

{\hat {\beta }}_{2}=0.556

{\ displaystyle {\ hat {\ beta}} _ {2} = 0,556}

{\ displaystyle {\ hat {\ beta}} _ {2} = 0,556}

, împreună cu datele observate (în roșu).

În acest exemplu, algoritmul Gauss - Newton este utilizat pentru regresia vitezei $V.$ ${\ displaystyle V}$ $V.$ formarea produsului într-o reacție catalizată de enzime în raport cu concentrația substratului $[S]$ ${\ displaystyle [S]}$ ${\ displaystyle [S]}$ , conform modelului Michaelis-Menten . Datele măsurate sunt prezentate în tabelul următor. Incertitudinile fiecărei măsuri au fost stabilite egale cu 1.

$the$ ${\ displaystyle i}$ $the$	1	2	3	4	5	6	7
$[S]$ ${\ displaystyle [S]}$ ${\ displaystyle [S]}$	0,038	0,194	0,425	0,626	1.253	2.500	3.740
V.	0,050	0,127	0,094	0,2122	0,2729	0,2665	0,3317

Funcția model este de formă

V={\frac {V_{\text{max}}[S]}{K_{M}+[S]}}

{\ displaystyle V = {\ frac {V _ {\ text {max}} [S]} {K_ {M} + [S]}}}

{\ displaystyle V = {\ frac {V _ {\ text {max}} [S]} {K_ {M} + [S]}}}

cu parametri $V_{\text{max}}$ ${\ displaystyle V _ {\ text {max}}}$ ${\ displaystyle V _ {\ text {max}}}$ Și $K_{M}$ ${\ displaystyle K_ {M}}$ ${\ displaystyle K_ {M}}$ să fie determinată prin algoritm.

Lasa-i sa fie $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ Și $y_{i}$ ${\ displaystyle y_ {i}}$ $y_ {i}$ valorile de $[S]$ ${\ displaystyle [S]}$ ${\ displaystyle [S]}$ Și $V.$ ${\ displaystyle V}$ $V.$ respectiv în tabel, cu $i=1,\dots ,7$ ${\ displaystyle i = 1, \ dots, 7}$ ${\ displaystyle i = 1, \ dots, 7}$ . Lasa-i sa fie $\beta _{1}=V_{\text{max}}$ ${\ displaystyle \ beta _ {1} = V _ {\ text {max}}}$ ${\ displaystyle \ beta _ {1} = V _ {\ text {max}}}$ Și $\beta _{2}=K_{M}$ ${\ displaystyle \ beta _ {2} = K_ {M}}$ ${\ displaystyle \ beta _ {2} = K_ {M}}$ . Se vor găsi reciproc $\beta _{1}$ ${\ displaystyle \ beta _ {1}}$ $\ beta_1$ Și $\beta _{2}$ ${\ displaystyle \ beta _ {2}}$ $\ beta _ {2}$ astfel încât suma pătratelor reziduurilor

r_{i}=y_{i}-{\frac {\beta _{1}x_{i}}{\beta _{2}+x_{i}}}\quad (i=1,\dots ,7)

{\ displaystyle r_ {i} = y_ {i} - {\ frac {\ beta _ {1} x_ {i}} {\ beta _ {2} + x_ {i}}} \ quad (i = 1, \ puncte, 7)}

{\ displaystyle r_ {i} = y_ {i} - {\ frac {\ beta _ {1} x_ {i}} {\ beta _ {2} + x_ {i}}} \ quad (i = 1, \ puncte, 7)}

este minim.

Jacobianul $\mathbf {J_{r}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ a vectorului rezidual $r_{i}$ ${\ displaystyle r_ {i}}$ $re$ cu privire la necunoscute $\beta _{j}$ ${\ displaystyle \ beta _ {j}}$ ${\ displaystyle \ beta _ {j}}$ este o matrice $7\times 2$ ${\ displaystyle 7 \ times 2}$ ${\ displaystyle 7 \ times 2}$ în care în $the$ ${\ displaystyle i}$ $the$ se găsește a treia linie

{\frac {\partial r_{i}}{\partial \beta _{1}}}=-{\frac {x_{i}}{\beta _{2}+x_{i}}};{\frac {\partial r_{i}}{\partial \beta _{2}}}={\frac {\beta _{1}x_{i}}{(\beta _{2}+x_{i})^{2}}}.

{\ displaystyle {\ frac {\ partial r_ {i}} {\ partial \ beta _ {1}}} = - {\ frac {x_ {i}} {\ beta _ {2} + x_ {i}}} ; {\ frac {\ partial r_ {i}} {\ partial \ beta _ {2}}} = {\ frac {\ beta _ {1} x_ {i}} {(\ beta _ {2} + x_ { i}) ^ {2}}}.}

{\ displaystyle {\ frac {\ partial r_ {i}} {\ partial \ beta _ {1}}} = - {\ frac {x_ {i}} {\ beta _ {2} + x_ {i}}} ; {\ frac {\ partial r_ {i}} {\ partial \ beta _ {2}}} = {\ frac {\ beta _ {1} x_ {i}} {(\ beta _ {2} + x_ { i}) ^ {2}}}.}

Începând cu o estimare inițială $\beta _{1}^{(0)}=0.9$ ${\ displaystyle \ beta _ {1} ^ {(0)} = 0.9}$ ${\ displaystyle \ beta _ {1} ^ {(0)} = 0.9}$ Și $\beta _{2}^{(0)}=0.2$ ${\ displaystyle \ beta _ {2} ^ {(0)} = 0.2}$ ${\ displaystyle \ beta _ {2} ^ {(0)} = 0.2}$ , după cinci iterații ale algoritmului Gauss - Newton, se obțin valorile optime ${\hat {\beta }}_{1}=0.362$ ${\ displaystyle {\ hat {\ beta}} _ {1} = 0,362}$ ${\ displaystyle {\ hat {\ beta}} _ {1} = 0,362}$ Și ${\hat {\beta }}_{2}=0.556$ ${\ displaystyle {\ hat {\ beta}} _ {2} = 0,556}$ ${\ displaystyle {\ hat {\ beta}} _ {2} = 0,556}$ . Suma pătratelor reziduale descinde de la valoarea inițială a $1.445$ ${\ displaystyle 1.445}$ ${\ displaystyle 1.445}$ până la cea finală a $0.00784$ ${\ displaystyle 0.00784}$ ${\ displaystyle 0.00784}$ . Graficul din figură arată datele din tabel împreună cu curba modelului cu parametrii optimi obținuți de algoritm. Mai jos este un tabel cu valori intermediare ale $\beta _{1}$ ${\ displaystyle \ beta _ {1}}$ $\ beta_1$ Și $\beta _{2}$ ${\ displaystyle \ beta _ {2}}$ $\ beta _ {2}$ în timpul algoritmului.

Repetare $the$ ${\ displaystyle i}$ $the$	$\beta _{1}^{(i)}$ ${\ displaystyle \ beta _ {1} ^ {(i)}}$ ${\ displaystyle \ beta _ {1} ^ {(i)}}$	$\beta _{2}^{(i)}$ ${\ displaystyle \ beta _ {2} ^ {(i)}}$ ${\ displaystyle \ beta _ {2} ^ {(i)}}$	$S(\mathbf {\beta ^{(i)}} )$ ${\ displaystyle S (\ mathbf {\ beta ^ {(i)}})}$ ${\ displaystyle S (\ mathbf {\ beta ^ {(i)}})}$
1	0,33266293	0,26017391	0,015072
2	0.34280925	0,42607918	0,008458
3	0,35777522	0,52950844	0,007864
4	0,36140546	0.5536581	0,007844
5	0,36180308	0.55607253	0,007844
6	0,36183442	0.55625246	0,007844

Convergența metodei

Se poate arăta ^[2] că creșterea $\Delta$ ${\ displaystyle \ Delta}$ $\ Delta$ este o direcție de coborâre pentru $S.$ ${\ displaystyle S}$ $S.$ , și, dacă algoritmul converge, limita este un punct staționar de $S.$ ${\ displaystyle S}$ $S.$ . Cu toate acestea, convergența nu este garantată, nici măcar convergența locală ca în metoda tangentă sau în condiții comune Wolfe. ^[3]

Rata de convergență Gauss - Newton poate deveni pătratică. ^[4] Algoritmul ar putea converge, de asemenea, lent sau deloc dacă estimarea inițială este departe de minim sau de matrice $\mathbf {J_{r}^{\mathsf {T}}J_{r}}$ ${\ displaystyle \ mathbf {J_ {r} ^ {\ mathsf {T}} J_ {r}}}$ ${\ displaystyle \ mathbf {J_ {r} ^ {\ mathsf {T}} J_ {r}}}$ este prost condiționat . De exemplu, luați în considerare problema cu $m=2$ ${\ displaystyle m = 2}$ ${\ displaystyle m = 2}$ ecuații e $n=1$ ${\ displaystyle n = 1}$ $n = 1$ variabile, date de

{\begin{aligned}r_{1}(\beta )&=\beta +1,\\r_{2}(\beta )&=\lambda \beta ^{2}+\beta -1.\end{aligned}}

{\ displaystyle {\ begin {align} r_ {1} (\ beta) & = \ beta +1, \\ r_ {2} (\ beta) & = \ lambda \ beta ^ {2} + \ beta -1. \ end {align}}}

{\ displaystyle {\ begin {align} r_ {1} (\ beta) & = \ beta +1, \\ r_ {2} (\ beta) & = \ lambda \ beta ^ {2} + \ beta -1. \ end {align}}}

Minimul este pentru $\beta =0$ ${\ displaystyle \ beta = 0}$ ${\ displaystyle \ beta = 0}$ . (De fapt, minimul este pentru $\beta =-1$ ${\ displaystyle \ beta = -1}$ ${\ displaystyle \ beta = -1}$ de sine $\lambda =2$ ${\ displaystyle \ lambda = 2}$ ${\ displaystyle \ lambda = 2}$ , atâta timp cât $S(0)=1^{2}+(-1)^{2}=2$ ${\ displaystyle S (0) = 1 ^ {2} + (- 1) ^ {2} = 2}$ ${\ displaystyle S (0) = 1 ^ {2} + (- 1) ^ {2} = 2}$ , dar $S(-1)=0$ ${\ displaystyle S (-1) = 0}$ ${\ displaystyle S (-1) = 0}$ .) De sine $\lambda =0$ ${\ displaystyle \ lambda = 0}$ $\ lambda = 0$ , atunci problema devine liniară și metoda găsește minimul într-o singură iterație. De sine $|\lambda |<1$ ${\ displaystyle | \ lambda | <1}$ ${\ displaystyle | \ lambda | <1}$ , atunci algoritmul converge liniar și eroarea scade asimptotic cu un factor $|\lambda |$ ${\ displaystyle | \ lambda |}$ ${\ displaystyle | \ lambda |}$ la fiecare iterație. Cu toate acestea, dacă $|\lambda |>1$ ${\ displaystyle | \ lambda |> 1}$ ${\ displaystyle | \ lambda |> 1}$ , nici măcar nu există convergență locală. ^[5]

Derivarea din metoda lui Newton

În această secțiune, algoritmul Gauss - Newton va fi derivat din metoda Newton pentru optimizarea funcției. În consecință, rata de convergență a algoritmului Gauss - Newton poate fi pătratică în anumite condiții de regularitate. În general (în condiții mai slabe), convergența este liniară. ^[6]

Relația de recurență pentru metoda lui Newton pentru minimizarea funcției $S.$ ${\ displaystyle S}$ $S.$ de parametri ${\boldsymbol {\beta }}$ ${\ displaystyle {\ boldsymbol {\ beta}}}$ ${\ displaystyle {\ boldsymbol {\ beta}}}$ Și

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\mathbf {H} ^{-1}\mathbf {g} ,

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} - \ mathbf {H} ^ {- 1} \ mathbf {g} ,}

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} - \ mathbf {H} ^ {- 1} \ mathbf {g} ,}

unde este $\mathbf {g}$ ${\ displaystyle \ mathbf {g}}$ ${\ mathbf g}$ indică vectorul gradient al $S.$ ${\ displaystyle S}$ $S.$ , Și $\mathbf {H}$ ${\ displaystyle \ mathbf {H}}$ $\ mathbf H$ matricea sa hesiană . Atâta timp cât $S=\sum _{i=1}^{m}r_{i}^{2}$ ${\ displaystyle S = \ sum _ {i = 1} ^ {m} r_ {i} ^ {2}}$ ${\ displaystyle S = \ sum _ {i = 1} ^ {m} r_ {i} ^ {2}}$ , gradientul este dat de

g_{j}=2\sum _{i=1}^{m}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}.

{\ displaystyle g_ {j} = 2 \ sum _ {i = 1} ^ {m} r_ {i} {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}}.}

{\ displaystyle g_ {j} = 2 \ sum _ {i = 1} ^ {m} r_ {i} {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}}.}

Elementele din Hessian sunt calculate prin derivarea componentelor gradientului, $g_{j}$ ${\ displaystyle g_ {j}}$ $g_ {j}$ , în comparație cu $\beta _{k}$ ${\ displaystyle \ beta _ {k}}$ $\ beta _ {k}$ :

H_{jk}=2\sum _{i=1}^{m}\left({\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}+r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}\right).

{\ displaystyle H_ {jk} = 2 \ sum _ {i = 1} ^ {m} \ left ({\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}} {\ frac { \ partial r_ {i}} {\ partial \ beta _ {k}}} + r_ {i} {\ frac {\ partial ^ {2} r_ {i}} {\ partial \ beta _ {j} \ partial \ beta _ {k}}} \ right).}

{\ displaystyle H_ {jk} = 2 \ sum _ {i = 1} ^ {m} \ left ({\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}} {\ frac { \ partial r_ {i}} {\ partial \ beta _ {k}}} + r_ {i} {\ frac {\ partial ^ {2} r_ {i}} {\ partial \ beta _ {j} \ partial \ beta _ {k}}} \ right).}

Metoda Gauss - Newton se obține prin neglijarea termenilor cu derivatele secundare (a doua din expresie). Adică matricea Hessian este aproximată ca

H_{jk}\approx 2\sum _{i=1}^{m}J_{ij}J_{ik},

{\ displaystyle H_ {jk} \ approx 2 \ sum _ {i = 1} ^ {m} J_ {ij} J_ {ik},}

{\ displaystyle H_ {jk} \ approx 2 \ sum _ {i = 1} ^ {m} J_ {ij} J_ {ik},}

unde este $J_{ij}={\frac {\partial r_{i}}{\partial \beta _{j}}}$ ${\ displaystyle J_ {ij} = {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}}}$ ${\ displaystyle J_ {ij} = {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}}}$ sunt elementele iacobianului $\mathbf {J_{r}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ ${\ displaystyle \ mathbf {J_ {r}}}$ . Puteți rescrie gradientul și Hessianul aproximativ în notație matricială ca

\mathbf {g} =2\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {r} ,\quad \mathbf {H} \approx 2\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}} .

{\ displaystyle \ mathbf {g} = 2 \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {r}, \ quad \ mathbf {H} \ approx 2 \ mathbf { J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}.}

{\ displaystyle \ mathbf {g} = 2 \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {r}, \ quad \ mathbf {H} \ approx 2 \ mathbf { J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}.}

Înlocuim aceste expresii în relația de recurență anterioară, astfel încât să obținem ecuațiile algoritmului

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}+\Delta ;\quad \Delta =-\left(\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {J_{r}} \right)^{-1}\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {r} .

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} + \ Delta; \ quad \ Delta = - \ left (\ mathbf { J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ right) ^ {- 1} \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {r} .}

{\ displaystyle {\ boldsymbol {\ beta}} ^ {(s + 1)} = {\ boldsymbol {\ beta}} ^ {(s)} + \ Delta; \ quad \ Delta = - \ left (\ mathbf { J_ {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ right) ^ {- 1} \ mathbf {J_ {r}} ^ {\ mathsf {T}} \ mathbf {r} .}

Convergența metodei Gauss - Newton nu este garantată în toate situațiile. Aproximarea

\left|r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}\right|\ll \left|{\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}\right|,

{\ displaystyle \ left | r_ {i} {\ frac {\ partial ^ {2} r_ {i}} {\ partial \ beta _ {j} \ partial \ beta _ {k}}} \ right | \ ll \ left | {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}} {\ frac {\ partial r_ {i}} {\ partial \ beta _ {k}}} \ right |, }

{\ displaystyle \ left | r_ {i} {\ frac {\ partial ^ {2} r_ {i}} {\ partial \ beta _ {j} \ partial \ beta _ {k}}} \ right | \ ll \ left | {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}} {\ frac {\ partial r_ {i}} {\ partial \ beta _ {k}}} \ right |, }

care servește pentru a neglija derivatele secundare poate fi valabil în două cazuri, astfel încât să se aștepte convergența algoritmului: ^[7]

Valorile funcției $r_{i}$ ${\ displaystyle r_ {i}}$ $re$ sunt mici, cel puțin în jurul valorii minime.
Funcțiile sunt cvasi-liniare, astfel încât ${\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}$ ${\ displaystyle {\ frac {\ partial ^ {2} r_ {i}} {\ partial \ beta _ {j} \ partial \ beta _ {k}}}}$ ${\ displaystyle {\ frac {\ partial ^ {2} r_ {i}} {\ partial \ beta _ {j} \ partial \ beta _ {k}}}}$ este relativ mic.

Versiuni îmbunătățite ale algoritmului

Cu algoritmul Gauss - Newton, suma pătratelor reziduurilor $S.$ ${\ displaystyle S}$ $S.$ este posibil să nu scadă cu fiecare interacțiune. Cu toate acestea, din moment ce $\Delta$ ${\ displaystyle \ Delta}$ $\ Delta$ este o direcție de coborâre, cu excepția cazului în care $S({\boldsymbol {\beta }}^{s})$ ${\ displaystyle S ({\ boldsymbol {\ beta}} ^ {s})}$ ${\ displaystyle S ({\ boldsymbol {\ beta}} ^ {s})}$ este un punct staționar, susține că $S({\boldsymbol {\beta }}^{s}+\alpha \Delta )<S({\boldsymbol {\beta }}^{s})$ ${\ displaystyle S ({\ boldsymbol {\ beta}} ^ {s} + \ alpha \ Delta) <S ({\ boldsymbol {\ beta}} ^ {s})}$ ${\ displaystyle S ({\ boldsymbol {\ beta}} ^ {s} + \ alpha \ Delta) <S ({\ boldsymbol {\ beta}} ^ {s})}$ pentru fiecare $\alpha >0$ ${\ displaystyle \ alpha> 0}$ $\ alpha> 0$ suficient de mic. Deci, dacă metoda divergă, o soluție este să folosești o fracție $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ a sporului $\Delta$ ${\ displaystyle \ Delta}$ $\ Delta$ , folosind următoarea formulă:

{\boldsymbol {\beta }}^{s+1}={\boldsymbol {\beta }}^{s}+\alpha \Delta .

{\ displaystyle {\ boldsymbol {\ beta}} ^ {s + 1} = {\ boldsymbol {\ beta}} ^ {s} + \ alpha \ Delta.}

{\ displaystyle {\ boldsymbol {\ beta}} ^ {s + 1} = {\ boldsymbol {\ beta}} ^ {s} + \ alpha \ Delta.}

.

Cu alte cuvinte, vectorul de creștere este prea lung, dar este direcționat în jos, astfel încât avansarea doar o fracțiune a drumului va scădea valoarea funcției obiective $S.$ ${\ displaystyle S}$ $S.$ . Se poate găsi valoarea optimă a $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ folosind un algoritm de căutare pe linie , adică valoarea $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ este determinată de găsirea a ceea ce minimizează $S.$ ${\ displaystyle S}$ $S.$ , de obicei cu o metodă de căutare directă în interval $0<\alpha <1$ ${\ displaystyle 0 <\ alpha <1}$ ${\ displaystyle 0 <\ alpha <1}$ .

Unde fracția optimă $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ este aproape de zero, o metodă alternativă pentru tratamentul divergenței este utilizarea algoritmului Levenberg-Marquardt , cunoscut și ca „metoda regiunii de încredere”. ^[1] Ecuațiile normale sunt modificate astfel încât creșterea să fie rotită spre direcția de scădere maximă ,

\left(\mathbf {J^{\mathrm {T} }J+\lambda D} \right)\Delta =-\mathbf {J} ^{\mathrm {T} }\mathbf {r} ,

{\ displaystyle \ left (\ mathbf {J ^ {\ mathrm {T}} J + \ lambda D} \ right) \ Delta = - \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r}, }

{\ displaystyle \ left (\ mathbf {J ^ {\ mathrm {T}} J + \ lambda D} \ right) \ Delta = - \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r}, }

unde este $\mathbf {D}$ ${\ displaystyle \ mathbf {D}}$ $\ mathbf D$ este o matrice diagonală pozitivă. Rețineți că atunci când $\mathbf {D}$ ${\ displaystyle \ mathbf {D}}$ $\ mathbf D$ este matricea identității $\mathbf {I}$ ${\ displaystyle \ mathbf {I}}$ ${\ displaystyle \ mathbf {I}}$ Și $\lambda \to +\infty$ ${\ displaystyle \ lambda \ to + \ infty}$ ${\ displaystyle \ lambda \ to + \ infty}$ , asa de $\lambda \Delta =\lambda \left(\mathbf {J^{\mathrm {T} }J} +\lambda \mathbf {I} \right)^{-1}\left(-\mathbf {J} ^{\mathrm {T} }\mathbf {r} \right)=\left(\mathbf {I} -\mathbf {J^{\mathrm {T} }J} /\lambda +\cdots \right)\left(-\mathbf {J} ^{\mathrm {T} }\mathbf {r} \right)\to -\mathbf {J} ^{\mathrm {T} }\mathbf {r}$ ${\ displaystyle \ lambda \ Delta = \ lambda \ left (\ mathbf {J ^ {\ mathrm {T}} J} + \ lambda \ mathbf {I} \ right) ^ {- 1} \ left (- \ mathbf { J} ^ {\ mathrm {T}} \ mathbf {r} \ right) = \ left (\ mathbf {I} - \ mathbf {J ^ {\ mathrm {T}} J} / \ lambda + \ cdots \ right ) \ left (- \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r} \ right) \ to - \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r}}$ ${\ displaystyle \ lambda \ Delta = \ lambda \ left (\ mathbf {J ^ {\ mathrm {T}} J} + \ lambda \ mathbf {I} \ right) ^ {- 1} \ left (- \ mathbf { J} ^ {\ mathrm {T}} \ mathbf {r} \ right) = \ left (\ mathbf {I} - \ mathbf {J ^ {\ mathrm {T}} J} / \ lambda + \ cdots \ right ) \ left (- \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r} \ right) \ to - \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r}}$ , de unde și direcția $\Delta$ ${\ displaystyle \ Delta}$ $\ Delta$ se apropie de direcția gradientului negativ $-\mathbf {J} ^{\mathrm {T} }\mathbf {r}$ ${\ displaystyle - \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r}}$ ${\ displaystyle - \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {r}}$ .

Parametrul Marquardt $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ poate fi optimizat printr-o căutare pe linie, dar este foarte ineficient, deoarece vectorul de increment trebuie recalculat la fiecare modificare a $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ . O strategie mai eficientă este aceasta: când metoda divergă, parametrul Marquardt este crescut atâta timp cât există o scădere a $S.$ ${\ displaystyle S}$ $S.$ . Apoi valoarea este păstrată de la o iterație la alta, dar este scăzută până la atingerea unei valori limită, când parametrul Marquardt poate fi setat egal cu 0; minimizarea $S.$ ${\ displaystyle S}$ $S.$ de aceea devine o optimizare standard Gauss - Newton.

Optimizare pe scară largă

Pentru optimizarea pe scară largă, algoritmul Gauss - Newton prezintă un interes deosebit, deoarece, în general, susține (deși nu întotdeauna) matricea $\mathbf {J} _{\mathbf {r} }$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}}}$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}}}$ este mult mai împrăștiat decât Hessianul aproximativ $\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}}$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}}$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}}}$ . În aceste cazuri, pasul algoritmului se face cu o metodă iterativă aproximativă potrivită pentru probleme mari și împrăștiate, cum ar fi metoda gradientului conjugat .

Pentru ca această abordare să funcționeze, aveți nevoie de cel puțin un mod eficient de a calcula calculul produsului

\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}} \mathbf {p}

{\ displaystyle \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ mathbf {p}}

{\ displaystyle \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ mathbf {p}}

pentru un transportator $\mathbf {p}$ ${\ displaystyle \ mathbf {p}}$ ${\ mathbf p}$ . Pentru stocarea cu matrice rară, este, în general, practic să stocați rândurile de $\mathbf {J} _{\mathbf {r} }$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}}}$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}}}$ într-o formă comprimată (adică fără elementele nule), dar făcând calculul direct al produsului precedent oarecum complicat datorită transpunerii. Cu toate acestea, dacă se definește pe sine $\mathbf {c_{i}}$ ${\ displaystyle \ mathbf {c_ {i}}}$ ${\ displaystyle \ mathbf {c_ {i}}}$ ca linia $the$ ${\ displaystyle i}$ $the$ -alea din matrice $\mathbf {J} _{\mathbf {r} }$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}}}$ ${\ displaystyle \ mathbf {J} _ {\ mathbf {r}}}$ , are loc următoarea relație simplă:

\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}} \mathbf {p} =\sum _{i}\mathbf {c} _{i}(\mathbf {c} _{i}\cdot \mathbf {p} ),

{\ displaystyle \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ mathbf {p} = \ sum _ {i} \ mathbf {c} _ {i} (\ mathbf {c} _ {i} \ cdot \ mathbf {p}),}

{\ displaystyle \ mathbf {J} _ {\ mathbf {r}} ^ {\ mathsf {T}} \ mathbf {J_ {r}} \ mathbf {p} = \ sum _ {i} \ mathbf {c} _ {i} (\ mathbf {c} _ {i} \ cdot \ mathbf {p}),}

astfel încât fiecare rând să contribuie aditiv și independent la produs. Pe lângă memorarea foarte practică, această expresie este potrivită pentru calcul paralel . Rețineți că fiecare linie $\mathbf {c_{i}}$ ${\ displaystyle \ mathbf {c_ {i}}}$ ${\ displaystyle \ mathbf {c_ {i}}}$ este gradientul reziduului respectiv $r_{i}$ ${\ displaystyle r_ {i}}$ $re$ ; ținând cont de acest lucru, forma anterioară subliniază faptul că reziduurile contribuie la problemă independent unul de celălalt.

Algoritmi înrudiți

Într-o metodă cvasi-Newton, cum ar fi cea datorată lui Davidon, Fletcher și Powell sau Broyden - Fletcher - Goldfarb - Shanno (metoda BFGS), o estimare a lui Hessian este calculată numeric ${\frac {\partial ^{2}S}{\partial \beta _{j}\partial \beta _{k}}}$ ${\ displaystyle {\ frac {\ partial ^ {2} S} {\ partial \ beta _ {j} \ partial \ beta _ {k}}}}$ ${\ displaystyle {\ frac {\ partial ^ {2} S} {\ partial \ beta _ {j} \ partial \ beta _ {k}}}}$ folosind doar primele derivate ${\frac {\partial r_{i}}{\partial \beta _{j}}}$ ${\ displaystyle {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}}}$ ${\ displaystyle {\ frac {\ partial r_ {i}} {\ partial \ beta _ {j}}}}$ , astfel încât abia după $n$ ${\ displaystyle n}$ $n$ cicluri de rafinare metoda se apropie de cea a lui Newton în termeni de performanță. Rețineți că metodele cvasi-newtoniene pot reduce funcțiile arbitrare la valori reale, în timp ce Gauss - Newton, Levenberg - Marquardt etc. ele rezolvă doar probleme neliniare cu cele mai mici pătrate.

O altă metodă de rezolvare a problemelor minime folosind doar primele derivate este coborârea gradientului . Cu toate acestea, ultima metodă nu ia în considerare derivatele secundare nici măcar aproximativ, deci este extrem de ineficientă pentru multe funcții, mai ales dacă parametrii au o corelație puternică.

Notă

^ ^a ^b Björck (1996)
^ Björck (1996), p. 260.
^ Mascarenhas, Divergența metodelor BFGS și Gauss Newton , în Mathematical Programming , vol. 147, nr. 1, 2013, pp. 253–276, DOI : 10.1007 / s10107-013-0720-6 , arXiv : 1309.7922 .
^ Björck (1996), p. 341, 342.
^ Fletcher (1987), p. 113.
^ Copie arhivată , la henley.ac.uk . Accesat la 2 noiembrie 2018 (Arhivat din original la 4 august 2016) .
^ Nocedal (1999), p. 259.

Bibliografie

A. Björck, Metode numerice pentru problemele celor mai mici pătrate , SIAM, Philadelphia, 1996, ISBN 0-89871-360-9 .
Roger Fletcher,Metode practice de optimizare , 2nd, New York, John Wiley & Sons , 1987, ISBN 978-0-471-91547-8 .
Jorge Nocedal și Wright, Stephen, Optimizare numerică , New York: Springer, 1999, ISBN 0-387-98793-2 .

linkuri externe

Implementări

Artelys Knitro este un rezolvator neliniar cu implementarea metodei Gauss - Newton. Este scris în limbaj C și are interfețe pentru C ++ / C # / Java / Python / MATLAB / R.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[ab-1] Björck (1996)

[2] Björck (1996), p. 260.

[3] Mascarenhas, Divergența metodelor BFGS și Gauss Newton , în Mathematical Programming , vol. 147, nr. 1, 2013, pp. 253–276, DOI : 10.1007 / s10107-013-0720-6 , arXiv : 1309.7922 .

[4] Björck (1996), p. 341, 342.

[5] Fletcher (1987), p. 113.

[6] Copie arhivată , la henley.ac.uk . Accesat la 2 noiembrie 2018 (Arhivat din original la 4 august 2016) .

[7] Nocedal (1999), p. 259.

[1]

[2]

[3]

[4]

[5]

[6]

[7]