Broydensova metoda - Broydens method - Wikipedia

V numerické analýze Broydenova metoda je kvazi-Newtonova metoda pro hledání kořenů v k proměnné. Původně to popsal C. G. Broyden v roce 1965.^[1]

Newtonova metoda k řešení F(X) = 0 používá Jacobian matrix, J, při každé iteraci. Výpočet této Jacobian je však obtížná a nákladná operace. Myšlenkou Broydenovy metody je spočítat celý Jacobian pouze při první iteraci a provádět aktualizace první řady při jiných iteracích.

V roce 1979 Gay prokázal, že když je Broydenova metoda aplikována na lineární systém velikosti n × n, končí v 2 n kroky,^[2] ačkoli jako všechny kvazi-Newtonovy metody nemusí konvergovat pro nelineární systémy.

Popis metody

Řešení rovnice s jednou proměnnou

V metodě secant nahradíme první derivaci F′ na X_n s konečný rozdíl přiblížení:

${ displaystyle f '(x_ {n}) simeq { frac {f (x_ {n}) - f (x_ {n-1})} {x_ {n} -x_ {n-1}}}, }$

a postupovat podobně jako Newtonova metoda:

${ displaystyle x_ {n + 1} = x_ {n} - { frac {f (x_ {n})} {f ^ { prime} (x_ {n})}}}$

kde n je iterační index.

Řešení soustavy nelineárních rovnic

Zvažte systém k nelineární rovnice

${ displaystyle mathbf {f} ( mathbf {x}) = mathbf {0},}$

kde F je vektorová funkce vektoru X:

${ displaystyle mathbf {x} = (x_ {1}, x_ {2}, x_ {3}, dotsc, x_ {k}),}$

${ displaystyle mathbf {f} ( mathbf {x}) = { big (} f_ {1} (x_ {1}, x_ {2}, dotsc, x_ {k}), f_ {2} ( x_ {1}, x_ {2}, dotsc, x_ {k}), dotsc, f_ {k} (x_ {1}, x_ {2}, dotsc, x_ {k}) { big)} .}$

U takových problémů dává Broyden zevšeobecnění jednorozměrné Newtonovy metody a nahrazuje derivaci Jacobian J. Jacobská matice je stanovena iterativně na základě sekansová rovnice v aproximaci konečných rozdílů:

${ displaystyle mathbf {J} _ {n} ( mathbf {x} _ {n} - mathbf {x} _ {n-1}) simeq mathbf {f} ( mathbf {x} _ { n}) - mathbf {f} ( mathbf {x} _ {n-1}),}$

kde n je iterační index. Pro jasnost definujeme:

${ displaystyle mathbf {f} _ {n} = mathbf {f} ( mathbf {x} _ {n}),}$

${ displaystyle Delta mathbf {x} _ {n} = mathbf {x} _ {n} - mathbf {x} _ {n-1},}$

${ displaystyle Delta mathbf {f} _ {n} = mathbf {f} _ {n} - mathbf {f} _ {n-1},}$

takže výše uvedené může být přepsáno jako

${ displaystyle mathbf {J} _ {n} Delta mathbf {x} _ {n} simeq Delta mathbf {f} _ {n}.}$

Výše uvedená rovnice je podurčeno když k je větší než jedna. Broyden navrhuje použít současný odhad Jacobian matice J_n−1 a zdokonalit to přijetím řešení secanské rovnice, což je minimální modifikace J_n−1:

${ displaystyle mathbf {J} _ {n} = mathbf {J} _ {n-1} + { frac { Delta mathbf {f} _ {n} - mathbf {J} _ {n- 1} Delta mathbf {x} _ {n}} { | Delta mathbf {x} _ {n} | ^ {2}}} Delta mathbf {x} _ {n} ^ { mathrm {T}}.}$

Tím se minimalizuje následující Frobeniova norma:

${ displaystyle | mathbf {J} _ {n} - mathbf {J} _ {n-1} | _ { rm {F}}.}$

Poté můžeme postupovat směrem Newton:

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} - mathbf {J} _ {n} ^ {- 1} mathbf {f} ( mathbf {x} _ {n}).}$

Broyden také navrhl použít Sherman – Morrisonův vzorec přímo aktualizovat inverzi Jacobiho matice:

${ displaystyle mathbf {J} _ {n} ^ {- 1} = mathbf {J} _ {n-1} ^ {- 1} + { frac { Delta mathbf {x} _ {n} - mathbf {J} _ {n-1} ^ {- 1} Delta mathbf {f} _ {n}} { Delta mathbf {x} _ {n} ^ { mathrm {T}} mathbf {J} _ {n-1} ^ {- 1} Delta mathbf {f} _ {n}}} Delta mathbf {x} _ {n} ^ { mathrm {T}} mathbf { J} _ {n-1} ^ {- 1}.}$

Tato první metoda je obecně známá jako „dobrá Broydenova metoda“.

Podobnou techniku ​​lze odvodit pomocí mírně odlišné úpravy J_n−1. Tím se získá druhá metoda, takzvaná „špatná Broydenova metoda“ (ale viz^[3]):

${ displaystyle mathbf {J} _ {n} ^ {- 1} = mathbf {J} _ {n-1} ^ {- 1} + { frac { Delta mathbf {x} _ {n} - mathbf {J} _ {n-1} ^ {- 1} Delta mathbf {f} _ {n}} { | Delta mathbf {f} _ {n} | ^ {2}} } Delta mathbf {f} _ {n} ^ { mathrm {T}}.}$

Tím se minimalizuje odlišná norma Frobenius:

${ displaystyle | mathbf {J} _ {n} ^ {- 1} - mathbf {J} _ {n-1} ^ {- 1} | _ { rm {F}}.}$

Mnoho dalších kvazi-Newtonových schémat bylo navrženo v optimalizace, kde se hledá maximum nebo minimum nalezením kořene první derivace (spád ve více rozměrech). Jacobián přechodu se nazývá Hesián a je symetrický a do své aktualizace přidává další omezení.

Ostatní členové třídy Broyden

Broyden definoval nejen dvě metody, ale celou třídu metod. Ostatní členové této třídy byli přidáni jinými autory.

• The Aktualizace Davidon – Fletcher – Powell je jediným členem této třídy publikovaným před dvěma členy definovanými Broydenem.^[4]
• Schubertův nebo řídký Broydenův algoritmus - modifikace pro řídké Jacobian matice.^[5]
• Klement (2014) - používá méně iterací k řešení mnoha systémů rovnic.^[6][7]

Viz také

• Sekanční metoda
• Newtonova metoda
• Kvazi-Newtonova metoda
• Newtonova metoda v optimalizaci
• Davidon – Fletcher – Powellův vzorec
• Broyden – Fletcher – Goldfarb – Shanno (BFGS) metoda

Reference

Další čtení

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerické metody pro neomezenou optimalizaci a nelineární rovnice. Englewood Cliffs: Prentice Hall. str. 168–193. ISBN  0-13-627216-9.
• Fletcher, R. (1987). Praktické metody optimalizace (Druhé vydání.). New York: John Wiley & Sons. str.44–79. ISBN  0-471-91547-5.

externí odkazy

• Jednoduché základní vysvětlení: Příběh slepého lukostřelce