Newton: model je kvadratika
Gradient dává rovinu, a rovina nemá minimum — proto se u nejstrmějšího spádu musí délka kroku hádat. Vezmeme-li o člen víc, dostaneme kvadratiku, a ta minimum má. Stačí ho spočítat:
Křivost je kladná, model má minimum a krok míří dolů.
Kvadratická konvergence — a co to znamená
V okolí minima Newton zdvojnásobuje počet platných číslic každým krokem. Z chyby 10⁻² se stane 10⁻⁴, pak 10⁻⁸, pak 10⁻¹⁶ a je konec. Proto je na kvadratické funkci hotový na jeden krok: model tam není přiblížení, model je ta funkce.
A tři důvody, proč to není samozřejmá volba
- Hessián stojí peníze. Pro n proměnných je to n(n+1)/2 druhých derivací; numericky to je O(n²) vyhodnocení funkce na každý krok.
- Daleko od minima může být křivost záporná. Pak má model maximum místo minima a krok míří vzhůru. V obrázku výše je to vidět přímo.
- Newton hledá „∇f = 0", ne minimum. Do sedla dojde stejně ochotně jako do minima a je tam spokojený.
Řešení druhého problému je zárodek celé zbylé labky. Když Hessián není pozitivně definitní, přičte se k němu násobek jednotkové matice, dokud definitní nebude:
Velké τ přebije zakřivení a krok se otočí k nejstrmějšímu spádu; malé τ nechá Newtona být. Přesně tenhle nápad se o dvě kapitoly dál jmenuje Levenberg-Marquardt — jen tam má τ jméno μ a mění se podle toho, jak dobře model předpovídá.