Алгоритм Левенберга–Марквардта (англ. Levenberg–Marquardt algorithm, LMA або просто LM), також відомий як метод сгасних найменших квадратів (англ. damped least-squares, DLS) використовується у математиці та обчислювальній техніці для розв'язування нелінійних задач найменших квадратів. Такі задачі мінімізації особливо актуальні при підборі кривої методом найменших квадратів. LMA інтерполює між алгоритмом Гаусса–Ньютона (GNA) та методом градієнтного спуску. LMA є більш надійним, ніж GNA, що означає, що в багатьох випадках він знаходить рішення, навіть якщо воно починається дуже далеко від кінцевого мінімуму. Для нормальної роботи функцій і розумних стартових параметрів LMA, як правило, повільніше, ніж GNA. LMA також можна розглядати як Гаусса–Ньютона, використовуючи підхід довіри до регіону.
Алгоритм був вперше опублікований у 1944 році [en], під час роботи у Франкфордському армійському арсеналі. У 1963 році його знову відкрили [en], який працював статистиком у DuPont, і незалежно Жірард, Вінн і Моррісон.
LMA використовується в багатьох програмних додатках для розв'язання загальних задач [en]. Використовуючи алгоритм Гаусса–Ньютона, він часто сходиться швидше, ніж методи першого порядку. Однак, як і інші алгоритми ітераційної оптимізації, LMA знаходить лише локальний мінімум, який не обов'язково є глобальним мінімумом.
Проблема
Основне застосування алгоритму Левенберга–Марквардта полягає в задачі [en] методом найменших квадратів: для заданого набору емпіричних пар незалежних і залежних змінних, знайти параметри модельної кривої так, щоб суму квадратів відхилень було зведено до мінімуму:
- набір вважається непорожнім.
Рішення
Як і інші алгоритми чисельної мінімізації, алгоритм Левенберга–Марквардта є ітераційною процедурою. Щоб почати мінімізацію, користувач повинен надати початкове припущення для вектора параметрів . У випадках лише з одним мінімумом, ненавчені стандартні припущення, як буде працювати нормально; у випадках з кількома мінімумами алгоритм сходить до глобального мінімуму лише в тому випадку, якщо початкове припущення вже дещо близько до остаточного рішення.
На кожному кроці ітерації вектор параметрів замінюється на нову оцінку . Щоб визначити , функція апроксимується його лінеаризацією:
де
є градієнтом (в даному випадку вектором рядка) з відношенням до .
Сума квадратних відхилень має свій мінімум при нульовому градієнті по відношенню до . Наведене вище наближення першого порядку дає
або у векторному позначенні,
Візьмемо похідну від з відношенням до і встановлення результату на нуль, що дає
де є матриця Якобі, у якій -й ряд дорівнює , і де і є векторами з -ї компоненти і відповідно. Наведений вище вираз отримано для підпадає під метод Гаусса–Ньютона. Матриця Якобі, як визначено вище, є (загалом) не квадратною матрицею, а прямокутною матрицею розміру , де — кількість параметрів (розмір вектора ). Матричне множення дає необхідну квадратну матрицю і добуток матриці-вектору з правого боку дають вектор розміру . В результаті виходить набір лінійних рівнянь, які можна розв'язувати для .А
Внесок Левенберга полягає в тому, щоб замінити це рівняння на «згасну версію»:
де є одиничною матрицею, що дає приріст до розрахункового вектора параметрів .
Коефіцієнт (невід'ємного) демпфування коригується на кожній ітерації. Якщо зменшення є швидким, можна використовувати менше значення, наближаючи алгоритм до алгоритму Гаусса–Ньютона, тоді як, якщо ітерація дає недостатнє зменшення залишку, можна збільшити, наблизивши на крок до напрямку градієнтного спуску. Зверніть увагу, що градієнт з відношенням до дорівнює . Тому для великих значень , крок буде зроблено приблизно в напрямку, протилежному градієнту. Якщо будь-яка довжина обчисленого кроку або зменшення суми квадратів з останнього вектора параметрів падають нижче попередньо визначених меж, ітерація зупиняється та останній вектор параметра вважається рішенням.
Коли коефіцієнт демпфування є великим відносно , інвертувати не потрібно, оскільки оновлення добре апроксимується невеликим кроком градієнта .
Щоб зробити масштаб рішення інваріантним, алгоритм Марквардта розв'язав модифіковану задачу з кожним компонентом градієнта, масштабованим відповідно до кривизни. Це забезпечує більший рух уздовж напрямків, де градієнт менший, що дозволяє уникнути повільної збіжності в напрямку малого градієнта. Флетчер у своїй статті 1971 року Модифікована підпрограма Марквардта для нелінійних найменших квадратів спростив форму, замінивши ідентичну матрицю з діагональною матрицею, що складається з діагональних елементів :
Подібний коефіцієнт демпфування з'являється в регуляризації Тихонова, яка використовується для розв'язування лінійних неправильних задач, а також у регресії хребта, методиці оцінки в статистиці.
Вибір параметра демпфування
Для кращого вибору параметра демпфування були висунуті різні більш-менш евристичні аргументи . Існують теоретичні аргументи, які показують, чому деякі з цих варіантів гарантують локальну збіжність алгоритму; однак ці варіанти можуть призвести до того, що глобальна збіжність алгоритму страждає від небажаних властивостей найкрутішого спуску, зокрема, дуже повільної збіжності, близької до оптимальної.
Абсолютні значення будь-якого вибору залежать від того, наскільки добре масштабована початкова проблема. Марквардт рекомендував починати зі значення і фактор . Спочатку налаштування і обчислення залишкової суми квадратів через один крок від початкової точки з коефіцієнтом демпфування а по-друге з . Якщо обидва ці показники гірші за початкову точку, то згасання збільшується шляхом послідовного множення на поки не буде знайдено кращу точку з новим коефіцієнтом демпфування для деяких .
Якщо використати коефіцієнт демпфування це призводить до зменшення квадрата залишку, то це приймається за нове значення (і нове оптимальне розташування приймається як те, що отримано з цим коефіцієнтом демпфування) і процес продовжується; якщо використовувати це призведе до гіршого залишку, але використання призведе до кращого залишку, тоді залишається без змін, а новий оптимум приймається за значення, отримане с як демпфуючий фактор.
Ефективна стратегія для контролю параметра демпфування, що називається відкладеним задоволенням, полягає у збільшенні параметра на невелику величину для кожного кроку на підйом і зменшення на велику величину для кожного кроку вниз. Ідея цієї стратегії полягає в тому, щоб уникнути занадто швидкого спуску на початку оптимізації, отже, обмежуючи кроки, доступні в майбутніх ітераціях, і, отже, сповільнюючи зближення. Збільшення в 2 рази і зменшення в 3 рази виявилося ефективним у більшості випадків, тоді як для великих проблем більш екстремальні значення можуть працювати краще, зі збільшенням у 1,5 раза та зменшенням у 5 раз.
Геодезичне прискорення
При інтерпретації кроку Левенберга–Марквардта як швидкості вздовж геодезичної траєкторії в просторі параметрів можна покращити метод, додавши член другого порядку, що враховує прискорення вздовж геодезичної
де є рішенням
Оскільки цей член геодезичного прискорення залежить лише від похідної за напрямком вздовж напрямку швидкості , він не вимагає обчислення повної похідної матриці другого порядку, вимагаючи лише невеликих накладних обчислювальних витрат. Оскільки похідна другого порядку може бути досить складним виразом, може бути зручно замінити її наближенням скінченної різниці
де і вже були обчислені за допомогою алгоритму, тому для обчислення потрібна лише одна додаткова оцінка функції . Вибір скінченного різницевого кроку може вплинути на стабільність алгоритму, вибір значення близько 0,1 зазвичай є розумним.
Оскільки прискорення може вказувати в напрямку, протилежному швидкості, щоб запобігти зупинці методу, якщо демпфування занадто мале, додається додатковий критерій прискорення, щоб прийняти крок, який вимагає, що
де зазвичай фіксується до значення менше ніж 1, з меншими значеннями для складніших задач.
Додавання геодезичного члена прискорення може дозволити суттєво збільшити швидкість збіжності, і це особливо корисно, коли алгоритм рухається через вузькі каньйони в ландшафті цільової функції, де дозволені кроки менші, а точність вища завдяки другому порядку термін дає значні покращення.
Приклад
У цьому прикладі ми намагаємося підібрати функції використовуючи алгоритм Левенберга–Марквардта, реалізований в GNU Octave, як функцію leasqr. Графіки показують, що вони все краще відповідають параметрам , що використовується на початковій кривій. Лише тоді, коли параметри останнього графіка вибрано найближчими до оригіналу, криві точно підходять. Це рівняння є прикладом дуже чутливих початкових умов для алгоритму Левенберга–Марквардта. Однією з причин такої чутливості є існування кількох мінімумів — функції що має мінімуми при значенні параметра і .
Див. також
- [en]
- Метод Нелдера – Міда
- Варіанти алгоритму Левенберга–Марквардта також використовувалися для розв'язування нелінійних систем рівнянь.
Примітки
- [en]A Method for the Solution of Certain Non-Linear Problems in Least Squares. Quarterly of Applied Mathematics. 2 (2): 164—168. 1944. doi:10.1090/qam/10666.
- [en].An Algorithm for Least-Squares Estimation of Nonlinear Parameters. SIAM Journal on Applied Mathematics. 11 (2): 431—441. doi:10.1137/0111030.
- Girard, André (1958). Excerpt from Revue d'optique théorique et instrumentale. Rev. Opt. 37: 225—241, 397—424.
- Wynne, C. G. (1959). Lens Designing by Electronic Digital Computer: I. Proc. Phys. Soc. Lond. 73 (5): 777—787. Bibcode:1959PPS....73..777W. doi:10.1088/0370-1328/73/5/310.
- Morrison, David D. (1960). Methods for nonlinear least squares problems and convergence proofs. Proceedings of the Jet Propulsion Laboratory Seminar on Tracking Programs and Orbit Determination: 1—9.
- Wiliamowski, Bogdan; Yu, Hao (June 2010). (PDF). IEEE Transactions on Neural Networks and Learning Systems. 21 (6). Архів оригіналу (PDF) за 21 січня 2022. Процитовано 21 травня 2022.
- Transtrum, Mark K; Machta, Benjamin B; Sethna, James P (2011). Geometry of nonlinear least squares with applications to sloppy models and optimization. Physical Review E. APS. 83 (3): 036701. arXiv:1010.1449. Bibcode:2011PhRvE..83c6701T. doi:10.1103/PhysRevE.83.036701. PMID 21517619. S2CID 15361707.
- Transtrum, Mark K; Sethna, James P (2012). Improvements to the Levenberg-Marquardt algorithm for nonlinear least-squares minimization. arXiv:1201.5885 [physics.data-an].
- . GNU Scientific Library. Архів оригіналу за 14 квітня 2020.
- Kanzow, Christian; Yamashita, Nobuo; Fukushima, Masao (2004). Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints. Journal of Computational and Applied Mathematics. 172 (2): 375—397. Bibcode:2004JCoAM.172..375K. doi:10.1016/j.cam.2004.02.013.
Література
- Moré, Jorge J.; Sorensen, Daniel C. (1983). Computing a Trust-Region Step (PDF). SIAM J. Sci. Stat. Comput. 4 (3): 553—572. doi:10.1137/0904038.
- Gill, Philip E.; (1978). Algorithms for the solution of the nonlinear least-squares problem. . 15 (5): 977—992. Bibcode:1978SJNA...15..977G. doi:10.1137/0715063.
- Pujol, Jose (2007). The solution of nonlinear inverse problems and the Levenberg-Marquardt method. Geophysics. SEG. 72 (4): W1—W16. Bibcode:2007Geop...72W...1P. doi:10.1190/1.2732552.[недоступне посилання з 01.02.2020]
- Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (вид. 2nd). Springer. ISBN .
Зовнішні посилання
- Numerical Recipes in C, Chapter 15.5: Nonlinear models
- C. T. Kelley, Iterative Methods for Optimization, SIAM Frontiers in Applied Mathematics, no 18, 1999, . Online copy
- A tutorial by Ananth Ranganathan
- K. Madsen, H. B. Nielsen, O. Tingleff, Methods for Non-Linear Least Squares Problems (nonlinear least-squares tutorial; L-M code: analytic Jacobian secant)
- T. Strutz: Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). 2nd edition, Springer Vieweg, 2016, .
- H. P. Gavin, The Levenberg-Marquardt method for nonlinear least-squares curve-fitting problems (MATLAB implementation included)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Levenberga Markvardta angl Levenberg Marquardt algorithm LMA abo prosto LM takozh vidomij yak metod sgasnih najmenshih kvadrativ angl damped least squares DLS vikoristovuyetsya u matematici ta obchislyuvalnij tehnici dlya rozv yazuvannya nelinijnih zadach najmenshih kvadrativ Taki zadachi minimizaciyi osoblivo aktualni pri pidbori krivoyi metodom najmenshih kvadrativ LMA interpolyuye mizh algoritmom Gaussa Nyutona GNA ta metodom gradiyentnogo spusku LMA ye bilsh nadijnim nizh GNA sho oznachaye sho v bagatoh vipadkah vin znahodit rishennya navit yaksho vono pochinayetsya duzhe daleko vid kincevogo minimumu Dlya normalnoyi roboti funkcij i rozumnih startovih parametriv LMA yak pravilo povilnishe nizh GNA LMA takozh mozhna rozglyadati yak Gaussa Nyutona vikoristovuyuchi pidhid doviri do regionu Algoritm buv vpershe opublikovanij u 1944 roci en pid chas roboti u Frankfordskomu armijskomu arsenali U 1963 roci jogo znovu vidkrili en yakij pracyuvav statistikom u DuPont i nezalezhno Zhirard Vinn i Morrison LMA vikoristovuyetsya v bagatoh programnih dodatkah dlya rozv yazannya zagalnih zadach en Vikoristovuyuchi algoritm Gaussa Nyutona vin chasto shoditsya shvidshe nizh metodi pershogo poryadku Odnak yak i inshi algoritmi iteracijnoyi optimizaciyi LMA znahodit lishe lokalnij minimum yakij ne obov yazkovo ye globalnim minimumom ProblemaOsnovne zastosuvannya algoritmu Levenberga Markvardta polyagaye v zadachi en metodom najmenshih kvadrativ dlya zadanogo naboru m displaystyle m empirichnih par x i y i displaystyle left x i y i right nezalezhnih i zalezhnih zminnih znajti parametri b displaystyle boldsymbol beta modelnoyi krivoyi f x b displaystyle f left x boldsymbol beta right tak shob sumu kvadrativ vidhilen S b displaystyle S left boldsymbol beta right bulo zvedeno do minimumu b argmin b S b argmin b i 1 m y i f x i b 2 displaystyle hat boldsymbol beta in operatorname argmin limits boldsymbol beta S left boldsymbol beta right equiv operatorname argmin limits boldsymbol beta sum i 1 m left y i f left x i boldsymbol beta right right 2 nabir vvazhayetsya neporozhnim RishennyaYak i inshi algoritmi chiselnoyi minimizaciyi algoritm Levenberga Markvardta ye iteracijnoyu proceduroyu Shob pochati minimizaciyu koristuvach povinen nadati pochatkove pripushennya dlya vektora parametriv b displaystyle boldsymbol beta U vipadkah lishe z odnim minimumom nenavcheni standartni pripushennya yak b T 1 1 1 displaystyle boldsymbol beta text T begin pmatrix 1 1 dots 1 end pmatrix bude pracyuvati normalno u vipadkah z kilkoma minimumami algoritm shodit do globalnogo minimumu lishe v tomu vipadku yaksho pochatkove pripushennya vzhe desho blizko do ostatochnogo rishennya Na kozhnomu kroci iteraciyi vektor parametriv b displaystyle boldsymbol beta zaminyuyetsya na novu ocinku b d displaystyle boldsymbol beta boldsymbol delta Shob viznachiti d displaystyle boldsymbol delta funkciya f x i b d displaystyle f left x i boldsymbol beta boldsymbol delta right aproksimuyetsya jogo linearizaciyeyu f x i b d f x i b J i d displaystyle f left x i boldsymbol beta boldsymbol delta right approx f left x i boldsymbol beta right mathbf J i boldsymbol delta de J i f x i b b displaystyle mathbf J i frac partial f left x i boldsymbol beta right partial boldsymbol beta ye gradiyentom v danomu vipadku vektorom ryadka f displaystyle f z vidnoshennyam do b displaystyle boldsymbol beta Suma S b displaystyle S left boldsymbol beta right kvadratnih vidhilen maye svij minimum pri nulovomu gradiyenti po vidnoshennyu do b displaystyle boldsymbol beta Navedene vishe nablizhennya pershogo poryadku f x i b d displaystyle f left x i boldsymbol beta boldsymbol delta right daye S b d i 1 m y i f x i b J i d 2 displaystyle S left boldsymbol beta boldsymbol delta right approx sum i 1 m left y i f left x i boldsymbol beta right mathbf J i boldsymbol delta right 2 abo u vektornomu poznachenni S b d y f b J d 2 y f b J d T y f b J d y f b T y f b y f b T J d J d T y f b d T J T J d y f b T y f b 2 y f b T J d d T J T J d displaystyle begin aligned S left boldsymbol beta boldsymbol delta right amp approx left mathbf y mathbf f left boldsymbol beta right mathbf J boldsymbol delta right 2 amp left mathbf y mathbf f left boldsymbol beta right mathbf J boldsymbol delta right mathrm T left mathbf y mathbf f left boldsymbol beta right mathbf J boldsymbol delta right amp left mathbf y mathbf f left boldsymbol beta right right mathrm T left mathbf y mathbf f left boldsymbol beta right right left mathbf y mathbf f left boldsymbol beta right right mathrm T mathbf J boldsymbol delta left mathbf J boldsymbol delta right mathrm T left mathbf y mathbf f left boldsymbol beta right right boldsymbol delta mathrm T mathbf J mathrm T mathbf J boldsymbol delta amp left mathbf y mathbf f left boldsymbol beta right right mathrm T left mathbf y mathbf f left boldsymbol beta right right 2 left mathbf y mathbf f left boldsymbol beta right right mathrm T mathbf J boldsymbol delta boldsymbol delta mathrm T mathbf J mathrm T mathbf J boldsymbol delta end aligned Vizmemo pohidnu vid S b d displaystyle S left boldsymbol beta boldsymbol delta right z vidnoshennyam do d displaystyle boldsymbol delta i vstanovlennya rezultatu na nul sho daye J T J d J T y f b displaystyle left mathbf J mathrm T mathbf J right boldsymbol delta mathbf J mathrm T left mathbf y mathbf f left boldsymbol beta right right de J displaystyle mathbf J ye matricya Yakobi u yakij i displaystyle i j ryad dorivnyuye J i displaystyle mathbf J i i de f b displaystyle mathbf f left boldsymbol beta right i y displaystyle mathbf y ye vektorami z i displaystyle i yi komponenti f x i b displaystyle f left x i boldsymbol beta right i y i displaystyle y i vidpovidno Navedenij vishe viraz otrimano dlya b displaystyle boldsymbol beta pidpadaye pid metod Gaussa Nyutona Matricya Yakobi yak viznacheno vishe ye zagalom ne kvadratnoyu matriceyu a pryamokutnoyu matriceyu rozmiru m n displaystyle m times n de n displaystyle n kilkist parametriv rozmir vektora b displaystyle boldsymbol beta Matrichne mnozhennya J T J displaystyle left mathbf J mathrm T mathbf J right daye neobhidnu n n displaystyle n times n kvadratnu matricyu i dobutok matrici vektoru z pravogo boku dayut vektor rozmiru n displaystyle n V rezultati vihodit nabir n displaystyle n linijnih rivnyan yaki mozhna rozv yazuvati dlya d displaystyle boldsymbol delta A Vnesok Levenberga polyagaye v tomu shob zaminiti ce rivnyannya na zgasnu versiyu J T J l I d J T y f b displaystyle left mathbf J mathrm T mathbf J lambda mathbf I right boldsymbol delta mathbf J mathrm T left mathbf y mathbf f left boldsymbol beta right right de I displaystyle mathbf I ye odinichnoyu matriceyu sho daye pririst d displaystyle boldsymbol delta do rozrahunkovogo vektora parametriv b displaystyle boldsymbol beta Koeficiyent nevid yemnogo dempfuvannya l displaystyle lambda koriguyetsya na kozhnij iteraciyi Yaksho zmenshennya S displaystyle S ye shvidkim mozhna vikoristovuvati menshe znachennya nablizhayuchi algoritm do algoritmu Gaussa Nyutona todi yak yaksho iteraciya daye nedostatnye zmenshennya zalishku l displaystyle lambda mozhna zbilshiti nablizivshi na krok do napryamku gradiyentnogo spusku Zvernit uvagu sho gradiyent S displaystyle S z vidnoshennyam do b displaystyle boldsymbol beta dorivnyuye 2 J T y f b T displaystyle 2 left mathbf J mathrm T left mathbf y mathbf f left boldsymbol beta right right right mathrm T Tomu dlya velikih znachen l displaystyle lambda krok bude zrobleno priblizno v napryamku protilezhnomu gradiyentu Yaksho bud yaka dovzhina obchislenogo kroku d displaystyle boldsymbol delta abo zmenshennya sumi kvadrativ z ostannogo vektora parametriv b d displaystyle boldsymbol beta boldsymbol delta padayut nizhche poperedno viznachenih mezh iteraciya zupinyayetsya ta ostannij vektor parametra b displaystyle boldsymbol beta vvazhayetsya rishennyam Koli koeficiyent dempfuvannya l displaystyle lambda ye velikim vidnosno J T J displaystyle mathbf J mathrm T mathbf J invertuvati J T J l I displaystyle mathbf J mathrm T mathbf J lambda mathbf I ne potribno oskilki onovlennya dobre aproksimuyetsya nevelikim krokom gradiyenta l 1 J T y f b displaystyle lambda 1 mathbf J mathrm T left mathbf y mathbf f left boldsymbol beta right right Shob zrobiti masshtab rishennya invariantnim algoritm Markvardta rozv yazav modifikovanu zadachu z kozhnim komponentom gradiyenta masshtabovanim vidpovidno do krivizni Ce zabezpechuye bilshij ruh uzdovzh napryamkiv de gradiyent menshij sho dozvolyaye uniknuti povilnoyi zbizhnosti v napryamku malogo gradiyenta Fletcher u svoyij statti 1971 roku Modifikovana pidprograma Markvardta dlya nelinijnih najmenshih kvadrativ sprostiv formu zaminivshi identichnu matricyu I displaystyle mathbf I z diagonalnoyu matriceyu sho skladayetsya z diagonalnih elementiv J T J displaystyle mathbf J text T mathbf J J T J l diag J T J d J T y f b displaystyle left mathbf J mathrm T mathbf J lambda operatorname diag left mathbf J mathrm T mathbf J right right boldsymbol delta mathbf J mathrm T left mathbf y mathbf f left boldsymbol beta right right Podibnij koeficiyent dempfuvannya z yavlyayetsya v regulyarizaciyi Tihonova yaka vikoristovuyetsya dlya rozv yazuvannya linijnih nepravilnih zadach a takozh u regresiyi hrebta metodici ocinki v statistici Vibir parametra dempfuvannya Dlya krashogo viboru parametra dempfuvannya buli visunuti rizni bilsh mensh evristichni argumenti l displaystyle lambda Isnuyut teoretichni argumenti yaki pokazuyut chomu deyaki z cih variantiv garantuyut lokalnu zbizhnist algoritmu odnak ci varianti mozhut prizvesti do togo sho globalna zbizhnist algoritmu strazhdaye vid nebazhanih vlastivostej najkrutishogo spusku zokrema duzhe povilnoyi zbizhnosti blizkoyi do optimalnoyi Absolyutni znachennya bud yakogo viboru zalezhat vid togo naskilki dobre masshtabovana pochatkova problema Markvardt rekomenduvav pochinati zi znachennya l 0 displaystyle lambda 0 i faktor n gt 1 displaystyle nu gt 1 Spochatku nalashtuvannya l l 0 displaystyle lambda lambda 0 i obchislennya zalishkovoyi sumi kvadrativ S b displaystyle S left boldsymbol beta right cherez odin krok vid pochatkovoyi tochki z koeficiyentom dempfuvannya l l 0 displaystyle lambda lambda 0 a po druge z l 0 n displaystyle lambda 0 nu Yaksho obidva ci pokazniki girshi za pochatkovu tochku to zgasannya zbilshuyetsya shlyahom poslidovnogo mnozhennya na n displaystyle nu poki ne bude znajdeno krashu tochku z novim koeficiyentom dempfuvannya l 0 n k displaystyle lambda 0 nu k dlya deyakih k displaystyle k Yaksho vikoristati koeficiyent dempfuvannya l n displaystyle lambda nu ce prizvodit do zmenshennya kvadrata zalishku to ce prijmayetsya za nove znachennya l displaystyle lambda i nove optimalne roztashuvannya prijmayetsya yak te sho otrimano z cim koeficiyentom dempfuvannya i proces prodovzhuyetsya yaksho vikoristovuvati l n displaystyle lambda nu ce prizvede do girshogo zalishku ale vikoristannya l displaystyle lambda prizvede do krashogo zalishku todi l displaystyle lambda zalishayetsya bez zmin a novij optimum prijmayetsya za znachennya otrimane s l displaystyle lambda yak dempfuyuchij faktor Efektivna strategiya dlya kontrolyu parametra dempfuvannya sho nazivayetsya vidkladenim zadovolennyam polyagaye u zbilshenni parametra na neveliku velichinu dlya kozhnogo kroku na pidjom i zmenshennya na veliku velichinu dlya kozhnogo kroku vniz Ideya ciyeyi strategiyi polyagaye v tomu shob uniknuti zanadto shvidkogo spusku na pochatku optimizaciyi otzhe obmezhuyuchi kroki dostupni v majbutnih iteraciyah i otzhe spovilnyuyuchi zblizhennya Zbilshennya v 2 razi i zmenshennya v 3 razi viyavilosya efektivnim u bilshosti vipadkiv todi yak dlya velikih problem bilsh ekstremalni znachennya mozhut pracyuvati krashe zi zbilshennyam u 1 5 raza ta zmenshennyam u 5 raz Geodezichne priskorennya Pri interpretaciyi kroku Levenberga Markvardta yak shvidkosti v k displaystyle boldsymbol v k vzdovzh geodezichnoyi trayektoriyi v prostori parametriv mozhna pokrashiti metod dodavshi chlen drugogo poryadku sho vrahovuye priskorennya a k displaystyle boldsymbol a k vzdovzh geodezichnoyi v k 1 2 a k displaystyle boldsymbol v k frac 1 2 boldsymbol a k de a k displaystyle boldsymbol a k ye rishennyam J k a k f v v displaystyle boldsymbol J k boldsymbol a k f vv Oskilki cej chlen geodezichnogo priskorennya zalezhit lishe vid pohidnoyi za napryamkom f v v m n v m v n m n f x displaystyle f vv sum mu nu v mu v nu partial mu partial nu f boldsymbol x vzdovzh napryamku shvidkosti v displaystyle boldsymbol v vin ne vimagaye obchislennya povnoyi pohidnoyi matrici drugogo poryadku vimagayuchi lishe nevelikih nakladnih obchislyuvalnih vitrat Oskilki pohidna drugogo poryadku mozhe buti dosit skladnim virazom mozhe buti zruchno zaminiti yiyi nablizhennyam skinchennoyi riznici f v v i f i x h d 2 f i x f i x h d h 2 2 h f i x h d f i x h J i d displaystyle begin aligned f vv i amp approx frac f i boldsymbol x h boldsymbol delta 2f i boldsymbol x f i boldsymbol x h boldsymbol delta h 2 amp frac 2 h left frac f i boldsymbol x h boldsymbol delta f i boldsymbol x h boldsymbol J i boldsymbol delta right end aligned de f x displaystyle f boldsymbol x i J displaystyle boldsymbol J vzhe buli obchisleni za dopomogoyu algoritmu tomu dlya obchislennya potribna lishe odna dodatkova ocinka funkciyi f x h d displaystyle f boldsymbol x h boldsymbol delta Vibir skinchennogo riznicevogo kroku h displaystyle h mozhe vplinuti na stabilnist algoritmu vibir znachennya blizko 0 1 zazvichaj ye rozumnim Oskilki priskorennya mozhe vkazuvati v napryamku protilezhnomu shvidkosti shob zapobigti zupinci metodu yaksho dempfuvannya zanadto male dodayetsya dodatkovij kriterij priskorennya shob prijnyati krok yakij vimagaye sho 2 a k v k a displaystyle frac 2 left boldsymbol a k right left boldsymbol v k right leq alpha de a displaystyle alpha zazvichaj fiksuyetsya do znachennya menshe nizh 1 z menshimi znachennyami dlya skladnishih zadach Dodavannya geodezichnogo chlena priskorennya mozhe dozvoliti suttyevo zbilshiti shvidkist zbizhnosti i ce osoblivo korisno koli algoritm ruhayetsya cherez vuzki kanjoni v landshafti cilovoyi funkciyi de dozvoleni kroki menshi a tochnist visha zavdyaki drugomu poryadku termin daye znachni pokrashennya PrikladPogano pidhodit Krashe pidhodit Najkrashe pidhodit U comu prikladi mi namagayemosya pidibrati funkciyi y a cos b X b sin a X displaystyle y a cos left bX right b sin left aX right vikoristovuyuchi algoritm Levenberga Markvardta realizovanij v GNU Octave yak funkciyu leasqr Grafiki pokazuyut sho voni vse krashe vidpovidayut parametram a 100 displaystyle a 100 b 102 displaystyle b 102 sho vikoristovuyetsya na pochatkovij krivij Lishe todi koli parametri ostannogo grafika vibrano najblizhchimi do originalu krivi tochno pidhodyat Ce rivnyannya ye prikladom duzhe chutlivih pochatkovih umov dlya algoritmu Levenberga Markvardta Odniyeyu z prichin takoyi chutlivosti ye isnuvannya kilkoh minimumiv funkciyi cos b x displaystyle cos left beta x right sho maye minimumi pri znachenni parametra b displaystyle hat beta i b 2 n p displaystyle hat beta 2n pi Div takozh en Metod Neldera Mida Varianti algoritmu Levenberga Markvardta takozh vikoristovuvalisya dlya rozv yazuvannya nelinijnih sistem rivnyan Primitki en A Method for the Solution of Certain Non Linear Problems in Least Squares Quarterly of Applied Mathematics 2 2 164 168 1944 doi 10 1090 qam 10666 en An Algorithm for Least Squares Estimation of Nonlinear Parameters SIAM Journal on Applied Mathematics 11 2 431 441 doi 10 1137 0111030 Girard Andre 1958 Excerpt from Revue d optique theorique et instrumentale Rev Opt 37 225 241 397 424 Wynne C G 1959 Lens Designing by Electronic Digital Computer I Proc Phys Soc Lond 73 5 777 787 Bibcode 1959PPS 73 777W doi 10 1088 0370 1328 73 5 310 Morrison David D 1960 Methods for nonlinear least squares problems and convergence proofs Proceedings of the Jet Propulsion Laboratory Seminar on Tracking Programs and Orbit Determination 1 9 Wiliamowski Bogdan Yu Hao June 2010 PDF IEEE Transactions on Neural Networks and Learning Systems 21 6 Arhiv originalu PDF za 21 sichnya 2022 Procitovano 21 travnya 2022 Transtrum Mark K Machta Benjamin B Sethna James P 2011 Geometry of nonlinear least squares with applications to sloppy models and optimization Physical Review E APS 83 3 036701 arXiv 1010 1449 Bibcode 2011PhRvE 83c6701T doi 10 1103 PhysRevE 83 036701 PMID 21517619 S2CID 15361707 Transtrum Mark K Sethna James P 2012 Improvements to the Levenberg Marquardt algorithm for nonlinear least squares minimization arXiv 1201 5885 physics data an GNU Scientific Library Arhiv originalu za 14 kvitnya 2020 Kanzow Christian Yamashita Nobuo Fukushima Masao 2004 Levenberg Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints Journal of Computational and Applied Mathematics 172 2 375 397 Bibcode 2004JCoAM 172 375K doi 10 1016 j cam 2004 02 013 LiteraturaMore Jorge J Sorensen Daniel C 1983 Computing a Trust Region Step PDF SIAM J Sci Stat Comput 4 3 553 572 doi 10 1137 0904038 Gill Philip E 1978 Algorithms for the solution of the nonlinear least squares problem 15 5 977 992 Bibcode 1978SJNA 15 977G doi 10 1137 0715063 Pujol Jose 2007 The solution of nonlinear inverse problems and the Levenberg Marquardt method Geophysics SEG 72 4 W1 W16 Bibcode 2007Geop 72W 1P doi 10 1190 1 2732552 nedostupne posilannya z 01 02 2020 Nocedal Jorge Wright Stephen J 2006 Numerical Optimization vid 2nd Springer ISBN 978 0 387 30303 1 Zovnishni posilannyaNumerical Recipes in C Chapter 15 5 Nonlinear models C T Kelley Iterative Methods for Optimization SIAM Frontiers in Applied Mathematics no 18 1999 ISBN 0 89871 433 8 Online copy A tutorial by Ananth Ranganathan K Madsen H B Nielsen O Tingleff Methods for Non Linear Least Squares Problems nonlinear least squares tutorial L M code analytic Jacobian secant T Strutz Data Fitting and Uncertainty A practical introduction to weighted least squares and beyond 2nd edition Springer Vieweg 2016 ISBN 978 3 658 11455 8 H P Gavin The Levenberg Marquardt method for nonlinear least squares curve fitting problems MATLAB implementation included