Хамгийн эгц буух арга (Англи хэл дээрх "хамгийн эгц буух арга") нь оновчлолын асуудлыг шийдвэрлэх давталтын тоон арга (эхний дараалал) бөгөөд энэ нь зорилгын функцийн экстремумыг (хамгийн бага ба хамгийн их) тодорхойлох боломжийг олгодог.

нь бодит домэйн дээрх функцийн аргументын утгууд (хяналттай параметрүүд) юм.

Харгалзан үзэж буй аргын дагуу зорилгын функцийн экстремум (хамгийн их эсвэл хамгийн бага) нь функцийн хамгийн хурдан өсөлт (бууралт) чиглэлд тодорхойлогддог. функцийн градиент (эсрэг градиент) чиглэлд. Нэг цэг дэх градиент функц нь координатын тэнхлэгүүд дээрх проекцууд нь координаттай холбоотой функцийн хэсэгчилсэн деривативууд болох вектор юм.

Энд i, j,…, n нь координатын тэнхлэгтэй параллель нэгж векторууд юм.

Суурь цэг дээрх градиент нь гадаргуу дээр хатуу ортогональ байх ба түүний чиглэл нь функцийн хамгийн хурдан өсөлтийн чиглэлийг, харин эсрэг чиглэл (антиградиент) нь функцийн хамгийн хурдан буурах чиглэлийг харуулдаг.

Хамгийн эгц буух арга бол градиент буух аргын цаашдын хөгжил юм. Ерөнхийдөө функцийн экстремумыг олох үйл явц нь давтагдах процедур бөгөөд үүнийг дараах байдлаар бичнэ.

Энд "+" тэмдэг нь функцийн хамгийн ихийг олоход, "-" тэмдэг нь функцийн хамгийн бага утгыг олоход хэрэглэгддэг;

Нэгж чиглэлийн векторыг томъёогоор тодорхойлно.

- градиент модуль нь градиент эсвэл эсрэг градиентийн чиглэлд функцийн өсөлт, бууралтын хурдыг тодорхойлдог.

Алхам хэмжээг тодорхойлдог тогтмол бөгөөд бүх i-р чиглэлд ижил байна.

Алхам хэмжээ нь хөдөлгөөний чиглэлд, өөрөөр хэлбэл градиент эсвэл эсрэг градиентийн чиглэлд нэг хэмжээст оновчлолын асуудлыг шийдсэний үр дүнд зорилгын функцын f(x)-ийн хамгийн бага нөхцлөөс сонгогдоно.

Өөрөөр хэлбэл, алхамын хэмжээг энэ тэгшитгэлийг шийдэх замаар тодорхойлно.

Тиймээс тооцооллын үе шатыг сонгосон бөгөөд ингэснээр функц сайжиртал хөдөлгөөнийг хийж, улмаар хэзээ нэгэн цагт туйлын цэгт хүрнэ. Энэ үед хайлтын чиглэлийг дахин тодорхойлж (градиент ашиглан) зорилгын функцийн шинэ оновчтой цэгийг эрэлхийлэх гэх мэт. Тиймээс энэ аргын хувьд хайлт нь илүү том алхмуудаар явагддаг бөгөөд функцийн градиентийг цөөн тооны цэгүүдэд тооцдог.

Хоёр хувьсагчийн функцийн хувьд энэ арга нь дараах геометрийн тайлбартай байна: цэгээс хөдөлгөөний чиглэл нь цэг дээрх түвшний шугамд хүрдэг. Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Хөрш зэргэлдээх цэгүүд дээр буух чиглэлийн векторуудын ортогональ байх нөхцөлийг дараах илэрхийллээр бичнэ.

f(x) функцийн тэнцүү түвшний шугамын график дээр хамгийн эгц буух аргыг ашиглан туйлын цэг хүртэлх хөдөлгөөний траекторийг үзүүлэв.

Оновчтой шийдлийн эрэл хайгуул нь давталтын тооцооллын үе шатанд (хэд хэдэн шалгуур) дуусна.

Хайлтын зам нь одоогийн хайлтын цэгийн жижиг хэсэгт хэвээр байна:

Зорилгын функцийн өсөлт өөрчлөгдөхгүй:

Орон нутгийн хамгийн бага цэг дэх зорилгын функцийн градиент тэг болно.

Градиент уруудах арга нь жалга даган явахад маш удаан байдаг бөгөөд зорилгын функц дэх хувьсагчдын тоо нэмэгдэх тусам аргын энэ зан үйл нь ердийн шинж чанартай болдог гэдгийг тэмдэглэх нь зүйтэй. Жалга нь хотгор бөгөөд түүний түвшний шугамууд нь хагас тэнхлэг бүхий эллипс хэлбэртэй байдаг бөгөөд олон дахин ялгаатай байдаг. Жалга байгаа тохиолдолд уруудах зам нь жижиг алхам бүхий зигзаг шугам хэлбэртэй байдаг бөгөөд үүний үр дүнд буух хурд хамгийн бага хэмжээнд хүртэл удааширдаг. Энэ нь эдгээр функцүүдийн эсрэг градиентийн чиглэл нь чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайж байгаа нь тооцооллын нэмэлт сааталд хүргэдэгтэй холбон тайлбарлаж байна. Үүний үр дүнд алгоритм нь тооцооллын үр ашгийг алддаг.

Жалга функц

Градиент арга нь олон тооны өөрчлөлтүүдийн хамт судалж буй объектын оновчтой байдлыг хайх нийтлэг бөгөөд үр дүнтэй арга юм. Градиент хайлтын сул тал (мөн дээр дурдсан аргууд) нь үүнийг ашиглах үед зөвхөн функцийн орон нутгийн экстремумыг илрүүлэх боломжтой юм. Орон нутгийн бусад экстремумуудыг олохын тулд бусад эхлэлийн цэгүүдээс хайх шаардлагатай. Мөн градиент аргуудын нэгдэх хурд нь градиент тооцооллын нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм.

Тооцооллын арга

Алхам 1:Функцийн градиентийг тооцоолох аналитик илэрхийллийн тодорхойлолт (бэлгэдэл хэлбэрээр)

Алхам 2: Анхны ойролцоо утгыг тохируулна уу

Алхам 3:Сүүлийн хайлтын чиглэлийг дахин тохируулахын тулд алгоритмын процедурыг дахин эхлүүлэх хэрэгцээ тодорхойлогддог. Дахин эхлүүлсний үр дүнд хамгийн эгц буух чиглэлд дахин хайлт хийж байна.

Зураг 3. Хамгийн эгц буух аргын геометрийн тайлбар. Алхам бүрт дараагийн давталт нь L туяа дээрх функцийн хамгийн бага цэг байхаар сонгогдоно.

Градиент аргын энэ хувилбар нь дараахь зүйлийг харгалзан үзсэн алхамыг сонгоход үндэслэсэн болно. Тухайн цэгээс бид энэ чиглэлд, өөрөөр хэлбэл туяа дээрх f функцийн хамгийн бага хэмжээнд хүрэх хүртэл эсрэг градиентийн чиглэлд шилжих болно.

Өөрөөр хэлбэл, дараагийн давталт нь L туяа дээрх f функцийн хамгийн бага цэг байхаар сонгосон (3-р зургийг үз). Градиент аргын энэ хувилбарыг хамгийн эгц буух арга гэж нэрлэдэг. Дашрамд хэлэхэд, энэ аргаар зэргэлдээх алхмуудын чиглэл нь ортогональ гэдгийг анхаарна уу.

Хамгийн эгц буух арга нь алхам бүрт нэг хэмжээст оновчлолын асуудлыг шийдэхийг шаарддаг. Практикаас харахад энэ арга нь тогтмол алхамтай градиент аргаас цөөн тооны үйл ажиллагаа шаарддаг.

Харин ерөнхий нөхцөлд хамгийн эгц буух аргын онолын нэгдэх хурд нь тогтмол (оновчтой) алхамтай градиент аргын нэгдэх хурдаас өндөргүй байна.

Тоон жишээнүүд

Тогтмол алхамтай градиент буурах арга

Тогтмол алхамтай градиент буурах аргын нийлэлтийг судлахын тулд дараахь функцийг сонгосон.

Хүлээн авсан үр дүнгээс харахад хэрэв цоорхой нь хэтэрхий том бол арга нь зөрүүтэй бол энэ нь аажмаар нийлж, нарийвчлал нь муу болно гэж дүгнэж болно. Арга нийлж байгаа алхамуудаас хамгийн том алхамыг сонгох шаардлагатай.

Алхам хуваах градиент арга

Алхам хуваах (2) бүхий градиент буурах аргын нийлэлтийг судлахын тулд дараах функцийг сонгосон.

Анхны ойролцоолсон цэг (10,10).

Ашигласан зогсоох шалгуур:

Туршилтын үр дүнг хүснэгтэд үзүүлэв.

Хүлээн авсан үр дүнгээс бид параметрийн оновчтой сонголтын талаар дүгнэж болно: Хэдийгээр энэ арга нь параметрийн сонголтод маш мэдрэмтгий биш юм.

Хамгийн огцом буух арга

Хамгийн эгц буух аргын нэгдлийг судлахын тулд дараах функцийг сонгосон.

Анхны ойролцоолсон цэг (10,10). Ашигласан зогсоох шалгуур:

Нэг хэмжээст оновчлолын асуудлыг шийдэхийн тулд алтан зүсэлтийн аргыг ашигласан.

Энэ арга нь 9 давталтаар 6e-8 нарийвчлалтай болсон.

Эндээс бид хамгийн эгц уруудах арга нь шатаар хуваах градиент арга болон тогтмол шаталсан градиент уруудах аргаас илүү хурдан нийлдэг гэж дүгнэж болно.

Хамгийн эгц буух аргын сул тал нь нэг хэмжээст оновчлолын асуудлыг шийдэхийг шаарддаг.

Градиент буурах аргуудыг програмчлахдаа параметрүүдийг сонгохдоо болгоомжтой байх хэрэгтэй

• · Тогтмол алхамтай градиент буурах арга: алхмыг 0.01-ээс бага сонгох хэрэгтэй, эс тэгвээс арга нь зөрөх (судлах функцээс хамааран арга нь ийм алхамтай байсан ч зөрөөтэй байж болно).
• · Алхам хуваах градиент арга нь параметрийн сонголтод тийм ч мэдрэмтгий биш юм. Параметрүүдийг сонгох сонголтуудын нэг:
• · Хамгийн эгц буух арга: Алтан харьцааны аргыг (боломжтой бол) нэг хэмжээст оновчлолын арга болгон ашиглаж болно.

Коньюгат градиент арга нь олон хэмжээст орон зайд хязгаарлалтгүй оновчлолын давталтын арга юм. Аргын гол давуу тал нь квадрат оновчлолын асуудлыг хязгаарлагдмал тооны алхмаар шийддэгт оршино. Тиймээс эхлээд квадрат функцийг оновчтой болгох коньюгат градиент аргыг тайлбарлаж, давтагдах томьёо гаргаж, нийлэх хурдны тооцооллыг өгсөн болно. Үүний дараа дурын функцийг оновчтой болгохын тулд нэмэлт аргыг хэрхэн ерөнхийд нь харуулж, аргын янз бүрийн хувилбаруудыг авч үзэж, нэгдмэл байдлын талаар ярилцав.

Оновчлолын асуудлын талаархи мэдэгдэл

Олонлог өгөгдөх ба энэ олонлог дээр зорилгын функц тодорхойлогдоно. Оновчлолын асуудал нь олонлог дээрх зорилгын функцийн яг дээд буюу яг доод хязгаарыг олохоос бүрдэнэ. Зорилгын функцийн доод хязгаарт хүрэх цэгүүдийн багцыг зааж өгсөн болно.

Хэрэв, оновчлолын асуудлыг хязгаарлалтгүй гэж нэрлэдэг. Хэрэв, оновчлолын асуудлыг хязгаарлагдмал гэж нэрлэдэг.

Квадрат функциональд зориулсан коньюгат градиент арга

Аргын тухай мэдэгдэл

Дараах оновчлолын асуудлыг авч үзье.

Энд тэгш хэмтэй эерэг тодорхой хэмжээний матриц байна. Энэ оновчлолын бодлогыг квадрат гэж нэрлэдэг. Үүнийг анхаарна уу. Функцийн экстремумын нөхцөл нь системтэй тэнцүү байна Функц нь тэгшитгэлээр тодорхойлогдсон нэг цэгт доод хязгаартаа хүрдэг. Тиймээс энэ оновчлолын асуудал нь шугаман тэгшитгэлийн системийг шийдвэрлэхэд хүргэсэн коньюгат градиент аргын санаа нь дараах байдалтай байна. Дараа нь аль ч цэгийн хувьд векторыг суурь болгон өргөжүүлж, хэлбэрээр дүрсэлж болно

Дараагийн ойртолт бүрийг дараах томъёогоор тооцоолно.

Тодорхойлолт. Хоёр вектор ба тэгш хэмтэй В матрицтай холбоотой коньюгат гэнэ

Коньюгат градиент аргад суурь байгуулах аргыг тайлбарлая. Давталт бүрт дараах дүрмийг сонгоно.

Үндсэн векторуудыг дараах томъёогоор тооцоолно.

Коэффициентийг Векторууд ба А-тай холбосон байхаар сонгоно.

Хэрэв бид -ээр тэмдэглэвэл хэд хэдэн хялбаршуулсаны дараа коньюгат градиент аргыг практикт хэрэглэхэд ашигласан эцсийн томъёог олж авна.

Коньюгат градиент аргын хувьд дараах теоремыг баримтална: Теорем Let, энд хэмжээтэй тэгш хэмтэй эерэг тодорхой матриц байна. Дараа нь коньюгат градиент арга нь алхам алхмаар нэгдэх ба дараах харилцааг хангана.

Аргын нэгдэл

Хэрэв бүх тооцоо үнэн зөв, анхны өгөгдөл нь үнэн зөв байвал уг арга нь системийг давтахаас илүүгүй хугацаанд шийдвэрлэхэд нийлдэг бөгөөд системийн хэмжээс хаана байна. Илүү нарийвчилсан дүн шинжилгээ нь давталтын тоо нь А матрицын өөр өөр хувийн утгуудын тооноос хэтрэхгүй болохыг харуулж байна. Нэгдэх хурдыг тооцоолохын тулд дараах (нэлээн бүдүүлэг) тооцоолол зөв байна.

Энэ нь матрицын хамгийн их ба хамгийн бага хувийн утгуудын тооцооллыг мэддэг бол нийлэх хурдыг тооцоолох боломжийг олгодог. Практикт дараахь зогсоох шалгуурыг ихэвчлэн ашигладаг.

Тооцооллын нарийн төвөгтэй байдал

Аргын давталт бүрт үйлдлүүд хийгддэг. Бүтээгдэхүүнийг тооцоолохын тулд ийм тооны үйлдлүүдийг хийх шаардлагатай байдаг - энэ нь давталт бүрт хамгийн их цаг хугацаа шаардсан процедур юм. Бусад тооцоололд O(n) үйлдэл шаардлагатай. Аргын нийт тооцооллын нарийн төвөгтэй байдал нь давталтын тоо n-ээс ихгүй тул давтагдахгүй.

Тоон жишээ

Коньюгат градиент аргыг ашиглан энэ системийн шийдлийг хоёр давталтаар олж авдаг системийг шийдэхийн тулд коньюгат градиент аргыг хэрэглэцгээе. Матрицын хувийн утга нь 5, 5, -5 - тэдгээрийн дунд хоёр өөр байдаг тул онолын тооцоогоор давталтын тоо хоёроос хэтрэхгүй байх ёстой.

Коньюгат градиент арга нь эерэг тодорхой матрицтай SLAE-ийг шийдвэрлэх хамгийн үр дүнтэй аргуудын нэг юм. Энэ арга нь хязгаарлагдмал тооны алхмуудаар нэгдэхийг баталгаажуулдаг бөгөөд шаардлагатай нарийвчлалыг илүү эрт олж авах боломжтой. Гол асуудал нь алдааны хуримтлалаас болж суурь векторуудын ортогональ байдал зөрчигдөж, нэгдмэл байдлыг алдагдуулдаг.

Ерөнхийдөө коньюгат градиент арга

Одоо багасгасан функц нь квадрат биш тохиолдолд коньюгат градиент аргын өөрчлөлтийг авч үзье: Бид асуудлыг шийдэх болно.

Тасралтгүй ялгах функц. Энэ асуудлыг шийдэхийн тулд коньюгат градиент аргыг өөрчлөхийн тулд А матрицыг оруулаагүй томъёоны хувьд дараахь зүйлийг авах шаардлагатай.

гурван томъёоны аль нэгийг ашиглан тооцоолж болно:

1. - Флетчер-Ривзийн арга

• 2. - Полак-Рибьерийн арга

Хэрэв функц нь квадрат бөгөөд хатуу гүдгэр бол гурван томъёо бүгд ижил үр дүнг өгнө. Хэрэв дурын функц бол томъёо бүр нь коньюгат градиент аргын өөрийн гэсэн өөрчлөлттэй тохирч байна. Гурав дахь томъёог бараг ашигладаггүй, учир нь энэ нь аргын алхам бүрт функц болон функцийн Hessian-ийн тооцоог шаарддаг.

Хэрэв функц квадрат биш бол коньюгат градиент арга нь хязгаарлагдмал тооны алхмаар нийлэхгүй байж болно. Түүнээс гадна алхам бүрт үнэн зөв тооцоолох нь зөвхөн ховор тохиолдолд л боломжтой байдаг. Тиймээс алдааны хуримтлал нь векторууд функцийн бууралтын чиглэлийг заахаа болиход хүргэдэг. Дараа нь тэд зарим алхамд итгэдэг. Үүнийг хүлээн авах бүх тооны багцыг дараах байдлаар тэмдэглэнэ. Тоонуудыг аргын шинэчлэлтийн мөч гэж нэрлэдэг. Практикт орон зайн хэмжээ хаана байхыг ихэвчлэн сонгодог.

Аргын нэгдэл

Флетчер-Ривзийн аргын хувьд багасгаж буй функцэд тийм ч хатуу нөхцөл тавьдаггүй нэгдэх теорем байдаг: Теорем. Дараах нөхцлийг хангасан байх ёстой.

Төрөл бүрийн зүйл хязгаарлагдмал

Дериватив нь Липшицийн нөхцлийг зарим хөршийн тогтмол тоогоор хангадаг

олонлог M: .

Полак-Райберийн аргын хувьд нэгдмэл байдал нь хатуу гүдгэр функц гэсэн таамаглалаар нотлогддог. Ерөнхий тохиолдолд Полак-Рейберийн аргын нэгдмэл байдлыг нотлох боломжгүй юм. Үүний эсрэгээр дараах теорем үнэн болно: Теорем. Полак-Райберийн аргад алхам бүрийн утгыг яг нарийн тооцдог гэж үзье. Дараа нь функц, анхны таамаглал байдаг.

Гэсэн хэдий ч практик дээр Полак-Райберийн арга илүү сайн ажилладаг. Практикт хамгийн түгээмэл зогсоох шалгуурууд: Градиент норм нь тодорхой босго хэмжээнээс бага болно. Функцийн утга m дараалсан давталтуудад бараг өөрчлөгдөөгүй хэвээр байна.

Тооцооллын нарийн төвөгтэй байдал

Полак-Рейбер эсвэл Флетчер-Ривзийн аргуудын давталт бүрт функц болон түүний градиентыг нэг удаа тооцож, нэг хэмжээст оновчлолын асуудлыг шийддэг. Тиймээс коньюгат градиент аргын нэг алхмын нарийн төвөгтэй байдал нь хамгийн эгц буух аргын нэг алхамын нарийн төвөгтэй байдлын дарааллаар ижил байна. Практикт коньюгат градиент арга нь хамгийн сайн нэгдэх хурдыг харуулдаг.

Бид коньюгат градиент аргыг ашиглан функцийн хамгийн бага утгыг хайх болно

Энэ функцийн хамгийн бага нь 1 бөгөөд (5, 4) цэг дээр хүрнэ. Энэ функцийг жишээ болгон Полак-Райбер, Флетчер-Ривзийн аргуудыг харьцуулж үзье. Одоогийн алхам дээр градиентийн квадрат норм багасах үед хоёр аргын давталт зогсдог. Сонголт хийхэд алтан харьцааны аргыг ашигладаг

Коньюгат градиент аргын хоёр хувилбарыг хэрэгжүүлсэн: квадрат функцийг багасгах, дурын функцийг багасгах. Эхний тохиолдолд энэ аргыг вектор функцээр гүйцэтгэдэг Шийдвэр олох(матриц А, вектор b) Энд A ба b нь квадрат оновчлолын бодлогыг тодорхойлоход оролцсон матриц ба вектор юм. Дурын функцийг багасгахын тулд та вектор гэсэн хоёр функцийн аль нэгийг ашиглаж болно FletcherRievesMethod(int spaceSize, Function F, вектор (*GradF) (вектор )) вектор PolakRibiereMethod(int spaceSize, Function F, вектор (*GradF) (вектор )) Хоёр функцийн параметрүүд нь ижил бөгөөд дараах утгатай: spaceSize - зайны хэмжээ (багасгасан функцээс хамаарах хувьсагчийн тоо) F - багасгах функцийг заагч. Функц нь double хэлбэртэй байх ёстой<имя функции>(вектор ) GradF - багасгаж буй функцийн градиентийг тооцоолох функцийн заагч. Хоёр арга нь нэг хэмжээст оновчлолын асуудлыг шийдвэрлэхэд туслах функцийг ашигладаг. Хөтөлбөр нь алтан зүсэлтийн аргыг ашиглан нэг хэмжээст оновчлолыг хэрэгжүүлдэг.

Градиент буурах аргууд нь оновчлолын асуудлыг шийдвэрлэх нэлээд хүчирхэг хэрэгсэл юм. Аргуудын гол сул тал бол хэрэглэх боломж хязгаарлагдмал хүрээ юм. Коньюгат градиент арга нь градиент буурах аргуудын нэгэн адил зөвхөн нэг цэг дэх өсөлтийн шугаман хэсгийн мэдээллийг ашигладаг. Нэмж дурдахад, коньюгат градиент арга нь квадрат асуудлыг хязгаарлагдмал тооны алхамаар шийдвэрлэх боломжийг олгодог. Бусад олон асуудлын хувьд коньюгат градиент арга нь градиент буурах аргаас давж гардаг. Градиент аргын нэгдэл нь нэг хэмжээст оновчлолын асуудлыг хэр нарийвчлалтай шийдэж байгаагаас ихээхэн хамаарна. Боломжит аргын гогцоонуудыг шинэчлэлтүүдийг ашиглан шийддэг. Гэсэн хэдий ч хэрэв арга нь функцын локал минимумд орвол түүнээс зугтаж чадахгүй байх магадлалтай.

Хамгийн эгц буух арга нь хувьсах алхамтай градиент арга юм. Давталт бүрт f(x) функцийн хамгийн бага нөхцлөөс буух чиглэлд k алхамын хэмжээг сонгоно, өөрөөр хэлбэл.

Энэ нөхцөл нь f (x) функцийн утга буурах үед эсрэг градиентийн дагуух хөдөлгөөн явагдана гэсэн үг юм. Математикийн үүднээс авч үзвэл давталт бүрт функцээр нэг хэмжээст багасгах асуудлыг шийдэх шаардлагатай байдаг.

()=f (x (k) -f (x (k))))

Үүний тулд алтан харьцааны аргыг ашиглая.

Хамгийн эгц буух аргын алгоритм нь дараах байдалтай байна.

Х (0) эхлэлийн цэгийн координатыг зааж өгсөн болно.

x (k) , k = 0, 1, 2, ... цэг дээр f (x (k)) градиентийн утгыг тооцоолно.

Алхамны хэмжээ k нь функцийг ашиглан нэг хэмжээст багасгах замаар тодорхойлогддог

()=f (x (k) -f (x (k)))).

x (k) цэгийн координатыг дараах байдлаар тодорхойлно.

x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.

Давтагдах үйл явцыг зогсоох нөхцөлийг шалгана:

||f (x (k +1))|| .

Хэрэв энэ нь биелсэн бол тооцоолол зогсох болно. Үгүй бол бид 1-р алхам руу шилжинэ. Хамгийн эгц буух аргын геометрийн тайлбарыг Зураг дээр үзүүлэв. 1.

Цагаан будаа. 2.1. Хамгийн эгц буух аргын блок схем.

Програм дахь аргыг хэрэгжүүлэх:

Хамгийн огцом буух арга.

Цагаан будаа. 2.2. Хамгийн эгц буух аргыг хэрэгжүүлэх.

Дүгнэлт: Манай тохиолдолд арга нь 7 давталтаар нийлдэг. А7 цэг (0.6641; -1.3313) нь экстремум цэг юм. Холболтын чиглэлийн арга. Квадрат функцүүдийн хувьд нийлэх хугацаа нь төгсгөлтэй, n хувьсагчийн тоотой тэнцүү байх градиент аргыг үүсгэж болно.

Дараах тохиолдолд тодорхой чиглэлийг дуудаж, зарим эерэг тодорхой Hess матрицын H-тэй холбоноё.

Тэгэхээр H нэгжийн хувьд коньюгат чиглэл нь тэдгээрийн перпендикуляр гэсэн үг юм. Ерөнхий тохиолдолд H нь ач холбогдолгүй юм. Ерөнхий тохиолдолд коньюгаци гэдэг нь Гесс матрицыг векторт хэрэглэхийг хэлнэ - энэ нь энэ векторыг ямар нэгэн өнцгөөр эргүүлэх, сунгах эсвэл шахах гэсэн үг юм.

Одоо вектор нь ортогональ, өөрөөр хэлбэл коньюгаци гэдэг нь векторын ортогональ байдал биш, харин эргүүлсэн векторын ортогональ байдал юм.e.i.

Цагаан будаа. 2.3. Коньюгат чиглэлийн аргын блок диаграмм.

Хөтөлбөрт аргын хэрэгжилт: Хамтарсан чиглэлийн арга.

Цагаан будаа. 2.4. Коньюгат чиглэлийн аргын хэрэгжилт.

Цагаан будаа. 2.5. Коньюгат чиглэлийн аргын график.

Дүгнэлт: А3 цэг (0.6666; -1.3333) нь 3 давталтаар олдсон ба экстремум цэг юм.

3. Хязгаарлалт байгаа үед функцийн хамгийн бага ба хамгийн их утгыг тодорхойлох аргуудын шинжилгээ

Ерөнхий хязгаарлагдмал оновчлолын асуудал дараах байдалтай байгааг санаарай.

f(x) ® мин, x О W,

Энд W нь R m-ийн зохих дэд олонлог юм. Тэгш байдлын төрлийн хязгаарлалттай асуудлын дэд анги нь  олонлог нь хэлбэрийн хязгаарлалтаар тодорхойлогддогоороо ялгагдана.

f i (x) = 0, энд f i: R m ®R (i = 1, …, k).

ТиймээсW = (x О R m: f i (x) = 0, i = 1, …, k).

f функцийн хувьд “0” индекс бичих нь бидэнд тохиромжтой байх болно. Тиймээс тэгш байдлын төрлийн хязгаарлалттай оновчлолын бодлогыг дараах байдлаар бичнэ

f 0 (x) ® мин, (3.1)

f i (x) = 0, i = 1, …, k. (3.2)

Хэрэв бид одоо f(x) = (f 1 (x), ..., f k (x)) хэлбэртэй координатын тэмдэглэгээ нь R k утгууд бүхий R m дээрх функцийг f гэж тэмдэглэвэл ( 3.1)–(3.2) бид мөн хэлбэрээр бичиж болно

f 0 (x) ® min, f(x) = Q.

Геометрийн хувьд тэгш байдлын төрлийн хязгаарлалттай асуудал нь олон талт  дээрх f 0 функцийн графикийн хамгийн доод цэгийг олох бодлого юм (3.1-р зургийг үз).

Бүх хязгаарлалтыг хангасан оноог (өөрөөр хэлбэл олонлогийн  цэгүүд) ихэвчлэн зөвшөөрөгдөх гэж нэрлэдэг. Зөвшөөрөгдөх x* цэгийг f i (x) = 0, i = 1, ..., k (эсвэл (3.1)–(3.2) асуудлын шийдэл) хязгаарлалтын дор f 0 функцийн нөхцөлт минимум гэж нэрлэдэг. бүх зөвшөөрөгдөх цэгийн хувьд x f 0 (x *)  f 0 (x). (3.3)

Хэрэв (3.3) нь зөвхөн x* цэгийн V x * зарим хөршид байрлах зөвшөөрөгдөх х-д хангагдсан бол бид орон нутгийн нөхцөлт минимумыг ярьж байна. Нөхцөлтэй хатуу орон нутгийн болон дэлхийн минимумуудын ойлголтыг байгалийн жамаар тодорхойлдог.

Тэмдэглэл: Энэ лекцэнд хамгийн эгц буух арга, Давидон-Флетчер-Пауэллийн арга зэрэг олон параметрт оновчлолын аргуудыг өргөнөөр тусгасан болно. Нэмж дурдахад хамгийн үр дүнтэйг тодорхойлохын тулд дээрх аргуудын харьцуулсан шинжилгээг хийж, тэдгээрийн давуу болон сул талуудыг тодорхойлсон; мөн түүнчлэн жалгын арга, олон талт арга зэрэг олон хэмжээст оновчлолын асуудлыг авч үздэг.

1. Хамгийн огцом буух арга

Энэ аргын мөн чанар нь өмнө дурдсан аргыг ашиглах явдал юм координат буух аргаөгөгдсөн цэгээс тэнхлэгүүдийн аль нэгтэй параллель чиглэлд энэ чиглэлийн хамгийн бага цэг хүртэл хайлт хийнэ. Дараа нь хайлтыг нөгөө тэнхлэгтэй параллель чиглэлд хийх гэх мэт. Мэдээжийн хэрэг, чиглэлүүд нь тодорхой байна. Үе шат бүрт хамгийн бага цэгийг хайх нь "хамгийн сайн" чиглэлийн дагуу явагдахын тулд энэ аргыг өөрчлөхийг оролдох нь үндэслэлтэй юм шиг санагдаж байна. Аль чиглэл нь "хамгийн сайн" нь тодорхойгүй, гэхдээ энэ нь мэдэгдэж байна градиент чиглэлфункцийн хамгийн хурдан өсөлтийн чиглэл юм. Тиймээс эсрэг чиглэл нь функцийн хамгийн хурдан буурах чиглэл юм. Энэ өмчийг дараах байдлаар зөвтгөж болно.

Бид x цэгээс дараагийн x + hd цэг рүү шилжиж байна гэж бодъё, энд d нь тодорхой чиглэл, h нь тодорхой урттай алхам юм. Үүний үр дүнд (x 1, x 2, ..., x n) цэгээс цэг хүртэл хөдөлгөөнийг хийдэг. (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Хаана

Функцийн утгын өөрчлөлтийг харилцаа холбоогоор тодорхойлно

Нэгдүгээр эрэмбийн zx i хүртэл, хэсэгчилсэн деривативыг x цэгт тооцдог. df функцийн өөрчлөлтийн хамгийн их утгыг олж авахын тулд (1.2) тэгшитгэлийг хангах d i чиглэлийг хэрхэн сонгох вэ? Энд хязгаарлалттай хамгийн их болгох асуудал үүсдэг. Лагранжийн үржүүлэгчийн аргыг хэрэглэж, түүний тусламжтайгаар функцийг тодорхойлно

Хязгаарлагдмал (1.2) хангадаг df утга нь функц ажиллах үед дээд цэгтээ хүрдэг

Дээд талдаа хүрдэг. Түүний дериватив

Тиймээс,

(1.6)

Дараа нь di ~ df/dx i ба d чиглэл нь x цэгийн V/(x) чиглэлтэй параллель байна.

Тиймээс, орон нутгийн хамгийн том өсөлтӨгөгдсөн жижиг алхамын h функц нь d нь Vf(x) эсвэл g(x) -ийн чиглэл байх үед үүсдэг. Тиймээс хамгийн эгц буух чиглэл нь чиглэл юм

Илүү энгийн хэлбэрээр (1.3) тэгшитгэлийг дараах байдлаар бичиж болно.

Vf(x) ба dx векторуудын хоорондох өнцөг хаана байна. Өгөгдсөн dx утгын хувьд dx-ийн чиглэл нь -Vf(x) -ийн чиглэлтэй давхцахыг сонгож df-ийг багасгана.

Сэтгэгдэл. Градиент чиглэлтогтмол түвшний шугамын аль ч цэгт перпендикуляр, учир нь энэ шугамын дагуу функц тогтмол байна. Тиймээс (d 1, d 2, ..., d n) нь түвшний шугамын дагуух жижиг алхам бол

Тиймээс

(1.8)

Давталт бүрт хамгийн эгц буух аргыг хэрэглэх үед алхамын хэмжээ А к функцийн хамгийн бага нөхцлөөс сонгогдоно f(x)уруудах чиглэлд, өөрөөр хэлбэл.

f(x[к] -а к f"(x[к])) = f(x[к] -af"(x[к])) .

Энэ нөхцөл нь функцийн утга хүртэл антиградиентийн дагуух хөдөлгөөн явагдана гэсэн үг юм f(x)буурдаг. Математикийн үүднээс авч үзвэл давталт бүрт нэг хэмжээст багасгах асуудлыг шийдэх шаардлагатай байдаг. Афункцууд

j (а) = f(x[к]-af"(x[к])) .

Хамгийн эгц буух аргын алгоритм нь дараах байдалтай байна.

• 1. Эхлэх цэгийн координатыг тогтооно X.
• 2. цэг дээр X[к], k = 0, 1, 2, ... градиентийн утгыг тооцоолно f"(x[к]) .
• 3. Алхам хэмжээ нь тодорхойлогддог а k, нэг хэмжээст багасгах замаар Афункцууд j (а) = f(x[к]-af"(x[к])).
• 4. Цэгийн координатыг тодорхойлно X[k+ 1]:

X би [k+ 1]= x би [к] -А к f" би (X[к]), i = 1,..., х.

5. Стерацийн процессыг зогсоох нөхцөлийг шалгана. Хэрэв тэдгээр нь биелсэн бол тооцоолол зогсох болно. Үгүй бол 1-р алхам руу очно уу.

Харж байгаа аргад цэгээс хөдөлгөөний чиглэл X[к] цэг дээрх түвшний шугамд хүрнэ x[k+ 1] (Зураг 2.9). Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Үнэхээр алхам а k-ийг багасгах замаар сонгоно Афункцууд? (а) = f(x[к] -af"(x[к])) . Функцийн хамгийн бага байх шаардлагатай нөхцөл г j (a)/da = 0.Нарийн төвөгтэй функцийн деривативыг тооцоолсны дараа бид зэргэлдээх цэгүүд дэх буурах чиглэлийн векторуудын ортогональ байдлын нөхцөлийг олж авна.

г j (a)/da = -f"(x[k+ 1]f"(x[к]) = 0.

Цагаан будаа. 2.9.

Градиент аргууд нь гөлгөр гүдгэр функцүүдийн хувьд өндөр хурдтай (геометрийн прогрессийн хурд) хамгийн бага хэмжээнд нийлдэг. Ийм функцууд хамгийн их байдаг Мба хамгийн бага мХоёрдахь деривативын матрицын хувийн утга (Гессийн матриц)

бие биенээсээ бага зэрэг ялгаатай, өөрөөр хэлбэл матриц N(x)сайн нөхцөлтэй. Хувийн утгууд l i гэдгийг санаарай. би =1, …, n, матрицууд нь шинж чанарын тэгшитгэлийн үндэс юм

Гэсэн хэдий ч практикт, дүрмээр бол багасгаж буй функцууд нь хоёр дахь деривативын тохиромжгүй матрицтай байдаг. (т/м<< 1). Зарим чиглэлийн дагуух ийм функцүүдийн утга нь бусад чиглэлээс хамаагүй хурдан (заримдаа хэд хэдэн дарааллаар) өөрчлөгддөг. Тэдний түвшний гадаргуу нь хамгийн энгийн тохиолдолд хүчтэй сунадаг (Зураг 2.10), илүү төвөгтэй тохиолдолд нугалж, жалга мэт харагдана. Ийм шинж чанартай функцуудыг нэрлэдэг гуу жалга.Эдгээр функцүүдийн эсрэг градиентийн чиглэл (2.10-р зургийг үз) чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайдаг бөгөөд энэ нь нэгдэх хурдыг удаашруулахад хүргэдэг.

Цагаан будаа. 2.10.

Градиент аргуудын нэгдэх хурд нь градиент тооцооллын нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм. Дээрх шалтгааны улмаас градиент аргуудыг асуудлыг шийдвэрлэх эхний шатанд бусад илүү үр дүнтэй аргуудтай хослуулан ашигладаг. Энэ тохиолдолд гол зүйл Xхамгийн бага цэгээс хол байгаа бөгөөд антиградиентийн чиглэлийн алхамууд нь функцийг мэдэгдэхүйц бууруулах боломжийг олгодог.