Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Метод Бройдена є квазіньютоновим методом для знаходження коренів системи рівнянь для n змінних Вперше він був описаний e

Метод Бройдена

Метод Бройдена

Метод Бройдена — є квазіньютоновим методом для знаходження коренів системи рівнянь для n змінних. Вперше він був описаний [en] у 1965 році.

Метод Ньютона для розв'язання системи рівнянь , де , використовує обчислення якобіана матриці J на кожній ітерації. Однак обчислення якобіана є важкою та дорогою операцією. Ідея методу Бройдена в тому, щоб обчислювати весь якобіан лише на першій ітерації та використовувати розв'язок методом хорд на наступних ітераціях.

У 1979 році Девід М. Гей довів, що коли метод Бройдена застосовати до лінійної системи розміру , то він завершується за 2n кроків, хоча, як і всі квазіньютоновські методи, він може не сходитися у випадку нелінійних систем.

Опис методу

Розв'язування рівняння з однією змінною

У методі хорд ми замінюємо першу похідну f′ у точці xn наближенням скінченною різницею:

image

і діємо подібно до методу Ньютона:

image

де n — індекс ітерації.

Розв'язування системи нелінійних рівнянь

Розглянемо систему з k нелінійних рівнянь

image

де f — вектор-функція вектора x:

image
image

Для таких задач Бройден дає узагальнення одновимірного методу Ньютона, замінюючи похідну якобіаном J. Матриця Якобі визначається ітеративно на основі рівняння хорди при наближенні скінченною різницею:

image

де n — індекс ітерації. Для наочності визначимо:

image
image
image

тому вищезазначене можна переписати як

image

Наведене вище рівняння є [en], якщо k більше одиниці. Бройден пропонує використати поточну оцінку матриці Якобі Jn−1 і вдосконалити її, взявши розв'язок рівняння хорди, яке є мінімальною модифікацією Jn−1:

image

Це мінімізує наступну норму Фробеніуса:

image

і ми можемо рухатися подібно до метода Ньютона:

image

Бройден також запропонував використовувати [en] для знаходження якобіана зворотної матриці Якобі:

image

Цей метод широко відомий як «хороший метод Бройдена».

Подібний результат можна отримати, використовуючи трохи іншу модифікацію Jn−1. Це дає інший метод, так званий «поганий метод Бройдена» (див.):

image

Це мінімізує іншу норму Фробеніуса:

image

Багато квазі-ньютонових методів було запропоновано для задач оптимізації, коли при пошуку максимуму або мінімуму, знаходять корінь першої похідної (багатовимірний градієнт). Якобіан градієнта називається Гессіаном і є симетричним, що накладає додаткові обмеження для його оновлення.

Клас методів Бройдена

На додаток до двох методів, описаних вище, Бройден визначив цілий клас споріднених методів.:578 Загалом, методи в класі Бройдена задаються у формі:150 imageде imageimage таimageі image для кожного image . Вибір image визначає метод.

Інші методи в класі Бройдена були представлені іншими авторами:

  • [en] є єдиним членом цього класу, опублікованим до двох методів, визначених Бройденом.:582 Для методу DFP, image.:150
  • Алгоритм Шуберта або розріджений Бройдена — модифікація для розріджених матриць Якобі.
  • Klement (2014) — використовує менше ітерацій для вирішення багатьох систем рівнянь.

Див. також

Примітки

  1. Broyden, C. G. (October 1965). A Class of Methods for Solving Nonlinear Simultaneous Equations (PDF). Mathematics of Computation. American Mathematical Society. 19 (92): 577—593. doi:10.1090/S0025-5718-1965-0198670-6. JSTOR 2003941.
  2. Gay, D. M. (August 1979). Some convergence properties of Broyden's method. SIAM Journal on Numerical Analysis. SIAM. 16 (4): 623—630. doi:10.1137/0716047.
  3. Kvaalen, Eric (November 1991). A faster Broyden method. BIT Numerical Mathematics. SIAM. 31 (2): 369—372. doi:10.1007/BF01931297.
  4. Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer New York. doi:10.1007/978-0-387-40065-5. ISBN .
  5. Schubert, L. K. (1 січня 1970). Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian. Mathematics of Computation. 24 (109): 27—30. doi:10.1090/S0025-5718-1970-0258276-9. ISSN 0025-5718.
  6. Klement, Jan (23 листопада 2014). On Using Quasi-Newton Algorithms of the Broyden Class for Model-to-Test Correlation. Journal of Aerospace Technology and Management (англ.). 6 (4): 407—414. doi:10.5028/jatm.v6i4.373. ISSN 2175-9146.
  7. Broyden class methods – File Exchange – MATLAB Central. www.mathworks.com. Процитовано 4 лютого 2016.

Література

  • ; (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. с. 168–193. ISBN .
  • Fletcher, R. (1987). Practical Methods of Optimization (вид. Second). New York: John Wiley & Sons. с. 44–79. ISBN .

Посилання

  • Просте базове пояснення: історія про сліпого стрільця

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Metod Brojdena ye kvazinyutonovim metodom dlya znahodzhennya koreniv sistemi rivnyan dlya n zminnih Vpershe vin buv opisanij en u 1965 roci Metod Nyutona dlya rozv yazannya sistemi rivnyan f i x 1 x 2 x n 0 displaystyle displaystyle f i x 1 x 2 ldots x n 0 de i 1 2 n displaystyle i 1 2 ldots n vikoristovuye obchislennya yakobiana matrici J na kozhnij iteraciyi Odnak obchislennya yakobiana ye vazhkoyu ta dorogoyu operaciyeyu Ideya metodu Brojdena v tomu shob obchislyuvati ves yakobian lishe na pershij iteraciyi ta vikoristovuvati rozv yazok metodom hord na nastupnih iteraciyah U 1979 roci Devid M Gej doviv sho koli metod Brojdena zastosovati do linijnoyi sistemi rozmiru n n displaystyle n times n to vin zavershuyetsya za 2n krokiv hocha yak i vsi kvazinyutonovski metodi vin mozhe ne shoditisya u vipadku nelinijnih sistem Opis metoduRozv yazuvannya rivnyannya z odniyeyu zminnoyu U metodi hord mi zaminyuyemo pershu pohidnu f u tochci xn nablizhennyam skinchennoyu rizniceyu f x n f x n f x n 1 x n x n 1 displaystyle f x n simeq frac f x n f x n 1 x n x n 1 i diyemo podibno do metodu Nyutona x n 1 x n f x n f x n displaystyle x n 1 x n frac f x n f prime x n de n indeks iteraciyi Rozv yazuvannya sistemi nelinijnih rivnyan Rozglyanemo sistemu z k nelinijnih rivnyan f x 0 displaystyle mathbf f mathbf x mathbf 0 de f vektor funkciya vektora x x x 1 x 2 x 3 x k displaystyle mathbf x x 1 x 2 x 3 dotsc x k f x f 1 x 1 x 2 x k f 2 x 1 x 2 x k f k x 1 x 2 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 Dlya takih zadach Brojden daye uzagalnennya odnovimirnogo metodu Nyutona zaminyuyuchi pohidnu yakobianom J Matricya Yakobi viznachayetsya iterativno na osnovi rivnyannya hordi pri nablizhenni skinchennoyu rizniceyu J n x n x n 1 f x n f x n 1 displaystyle mathbf J n mathbf x n mathbf x n 1 simeq mathbf f mathbf x n mathbf f mathbf x n 1 de n indeks iteraciyi Dlya naochnosti viznachimo f n f x n displaystyle mathbf f n mathbf f mathbf x n D x n x n x n 1 displaystyle Delta mathbf x n mathbf x n mathbf x n 1 D f n f n f n 1 displaystyle Delta mathbf f n mathbf f n mathbf f n 1 tomu vishezaznachene mozhna perepisati yak J n D x n D f n displaystyle mathbf J n Delta mathbf x n simeq Delta mathbf f n Navedene vishe rivnyannya ye en yaksho k bilshe odinici Brojden proponuye vikoristati potochnu ocinku matrici Yakobi Jn 1 i vdoskonaliti yiyi vzyavshi rozv yazok rivnyannya hordi yake ye minimalnoyu modifikaciyeyu Jn 1 J n J n 1 D f n J n 1 D x n D x n 2 D x n T 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 Ce minimizuye nastupnu normu Frobeniusa J n J n 1 F displaystyle mathbf J n mathbf J n 1 rm F i mi mozhemo ruhatisya podibno do metoda Nyutona x n 1 x n J n 1 f x n displaystyle mathbf x n 1 mathbf x n mathbf J n 1 mathbf f mathbf x n Brojden takozh zaproponuvav vikoristovuvati en dlya znahodzhennya yakobiana zvorotnoyi matrici Yakobi J n 1 J n 1 1 D x n J n 1 1 D f n D x n T J n 1 1 D f n D x n T J n 1 1 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 Cej metod shiroko vidomij yak horoshij metod Brojdena Podibnij rezultat mozhna otrimati vikoristovuyuchi trohi inshu modifikaciyu Jn 1 Ce daye inshij metod tak zvanij poganij metod Brojdena div J n 1 J n 1 1 D x n J n 1 1 D f n D f n 2 D f n T 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 Ce minimizuye inshu normu Frobeniusa J n 1 J n 1 1 F displaystyle mathbf J n 1 mathbf J n 1 1 rm F Bagato kvazi nyutonovih metodiv bulo zaproponovano dlya zadach optimizaciyi koli pri poshuku maksimumu abo minimumu znahodyat korin pershoyi pohidnoyi bagatovimirnij gradiyent Yakobian gradiyenta nazivayetsya Gessianom i ye simetrichnim sho nakladaye dodatkovi obmezhennya dlya jogo onovlennya Klas metodiv BrojdenaNa dodatok do dvoh metodiv opisanih vishe Brojden viznachiv cilij klas sporidnenih metodiv 578 Zagalom metodi v klasi Brojdena zadayutsya u formi 150 J k 1 J k J k s k s k T J k s k T J k s k y k y k T y k T s k ϕ k s k T J k s k v k v k T displaystyle mathbf J k 1 mathbf J k frac mathbf J k s k s k T mathbf J k s k T mathbf J k s k frac y k y k T y k T s k phi k left s k T mathbf J k s k right v k v k T de y k f x k 1 f x k displaystyle y k mathbf f mathbf x k 1 mathbf f mathbf x k s k x k 1 x k displaystyle s k mathbf x k 1 mathbf x k tav k y k y k T s k J k s k s k T J k s k displaystyle v k left frac y k y k T s k frac mathbf J k s k s k T mathbf J k s k right i ϕ k R displaystyle phi k in mathbb R dlya kozhnogo k 1 2 displaystyle k 1 2 Vibir ϕ k displaystyle phi k viznachaye metod Inshi metodi v klasi Brojdena buli predstavleni inshimi avtorami en ye yedinim chlenom cogo klasu opublikovanim do dvoh metodiv viznachenih Brojdenom 582 Dlya metodu DFP ϕ k 1 displaystyle phi k 1 150 Algoritm Shuberta abo rozridzhenij Brojdena modifikaciya dlya rozridzhenih matric Yakobi Klement 2014 vikoristovuye menshe iteracij dlya virishennya bagatoh sistem rivnyan Div takozhMetod hord Metod Nyutona Kvazi nyutoniv metod Metod Nyutona v optimizaciyi en Metod Brojdena Fletchera Goldfarba Shenno BFGS PrimitkiBroyden C G October 1965 A Class of Methods for Solving Nonlinear Simultaneous Equations PDF Mathematics of Computation American Mathematical Society 19 92 577 593 doi 10 1090 S0025 5718 1965 0198670 6 JSTOR 2003941 Gay D M August 1979 Some convergence properties of Broyden s method SIAM Journal on Numerical Analysis SIAM 16 4 623 630 doi 10 1137 0716047 Kvaalen Eric November 1991 A faster Broyden method BIT Numerical Mathematics SIAM 31 2 369 372 doi 10 1007 BF01931297 Nocedal Jorge Wright Stephen J 2006 Numerical Optimization Springer Series in Operations Research and Financial Engineering Springer New York doi 10 1007 978 0 387 40065 5 ISBN 978 0 387 30303 1 Schubert L K 1 sichnya 1970 Modification of a quasi Newton method for nonlinear equations with a sparse Jacobian Mathematics of Computation 24 109 27 30 doi 10 1090 S0025 5718 1970 0258276 9 ISSN 0025 5718 Klement Jan 23 listopada 2014 On Using Quasi Newton Algorithms of the Broyden Class for Model to Test Correlation Journal of Aerospace Technology and Management angl 6 4 407 414 doi 10 5028 jatm v6i4 373 ISSN 2175 9146 Broyden class methods File Exchange MATLAB Central www mathworks com Procitovano 4 lyutogo 2016 Literatura 1983 Numerical Methods for Unconstrained Optimization and Nonlinear Equations Englewood Cliffs Prentice Hall s 168 193 ISBN 0 13 627216 9 Fletcher R 1987 Practical Methods of Optimization vid Second New York John Wiley amp Sons s 44 79 ISBN 0 471 91547 5 PosilannyaProste bazove poyasnennya istoriya pro slipogo strilcya

Дата публікації:
Топ