Шийдлийг Word форматаар боловсруулсан болно.:

Жишээ нь: x 1 2 +x 1 x 2, x1^2+x1*x2 гэж бичнэ. Хайлтын чиглэлийг үүсгэнэилүү их хэмжээгээр
багасгаж байгаа функцийн геометрт харгалзах. Тодорхойлолт. Хоёр n хэмжээст вектор х ба у гэж нэрлэдэгхосолсон А матрицын хувьд (эсвэл А-коньюгат), хэрэвскаляр бүтээгдэхүүн

(x, Aу) = 0 . Энд А нь n x n хэмжээтэй тэгш хэмтэй эерэг тодорхой матриц юм.

d k чиглэл нь өмнө нь баригдсан бүх чиглэлтэй A-коньюгат байхаар сонгосон.

Флетчер-Ривзийн аргын алгоритм

Аргын нэгдэл

Жишээ. Коньюгат градиент аргыг ашиглан функцийн минимумыг ол: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10.
Шийдэл. Хайлтын чиглэлийн хувьд одоогийн цэг дээрх градиент векторыг сонгоно уу:

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

1. Хамтарсан чиглэлийн аргуудын тухай ойлголт.

Квадрат функцийг багасгах асуудлыг авч үзье

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

Бид тэгээс өөр векторууд нь харилцан уялдаатай (А матрицын хувьд) гэж хэлэх болно.

Квадрат функцийг багасгах коньюгат чиглэлийн аргаар (10.33) бид аргыг хэлнэ.

Үүнд чиглэлүүд нь харилцан уялдаатай байдаг ба алхамууд

Нэг хэмжээст багасгах асуудлын шийдэл болгон олж авсан болно:

Теорем 10.4. Холболтын чиглэлийн арга нь квадрат функцийн хамгийн бага цэгийг (10 33) алхам алхмаар олох боломжийг олгодог.

Коньюгат чиглэлийн аргууд нь нэгдмэл чиглэлийг бий болгох арга замаар бие биенээсээ ялгаатай байдаг. Тэдгээрийн хамгийн алдартай нь коньюгат градиент арга юм.

2. Коньюгат градиент арга.

Энэ аргын хувьд чиглэл нь дүрмийг бий болгодог

Энэ аргын эхний алхам нь хамгийн эгц буух аргын алхамтай давхцаж байгаа тул. Чиглэлүүд (10.34) үнэхээр байгаа гэдгийг (бид үүнийг хийхгүй) харуулж болно

A матрицын хувьд коньюгат. Түүнээс гадна градиентууд нь харилцан ортогональ болж хувирдаг.

Жишээ 10.5. Квадрат функцийг багасгахын тулд коньюгат градиент аргыг ашиглацгаая - Жишээ 10.1. Үүнийг хаана хэлбэрээр бичье

Анхны ойролцоо тооцоог авч үзье

Аргын 1-р алхам нь хамгийн эгц буух аргын эхний алхамтай давхцдаг. Тиймээс (жишээ 10.1-ийг үзнэ үү)

2-р алхам. Тооцоолъё

Учир нь шийдэл нь хоёр үе шаттайгаар олддог.

3. Квадрат бус функцийг багасгах коньюгат градиент арга.

Энэ аргыг дур зоргоороо багасгахын тулд ашиглахын тулд жигд функцкоэффициентийг тооцоолох томъёог (10.35) хэлбэрт шилжүүлэв

эсвэл харах

Томъёоны (10 36), (10.37) давуу тал нь А матрицыг тодорхой агуулаагүйд оршино.

Уг функцийг томъёоны дагуу коньюгат градиент аргаар багасгасан

Коэффициентийг (10.36), (10.37) томъёоны аль нэгийг ашиглан тооцоолно.

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

Нэг хэмжээст багасгах бодлогуудыг (10.40) тоогоор шийдвэрлэх шаардлагатай. Коньюгат градиент аргын хувьд коэффициентийг ихэвчлэн (10.36), (10.37) томъёогоор тооцоолдоггүй, харин үүнийг тооцдог болохыг бид бас тэмдэглэж байна. тэгтэй тэнцүү. Энэ тохиолдолд дараагийн алхам нь хамгийн эгц буух аргыг ашиглан хийгддэг. Энэхүү аргын "шинэчлэх" нь тооцооллын алдааны нөлөөллийг бууруулах боломжийг бидэнд олгодог.

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

Дээд суллах аргын зэрэгцээ хувилбарын үр ашгийг үнэлэх тооцооллын туршилтыг танилцуулгад заасан нөхцлөөр хийсэн. Тэгш хэмтэй эерэг тодорхой матрицыг бий болгохын тулд дэд матрицын элементүүдийг 0-ээс 1-ийн хооронд, дэд матрицын элементүүдийн утгыг матрицын тэгш хэмээс болон , мөн дээрх элементүүдээс олж авсан. үндсэн диагональ (дэд матриц) нь матрицын хэмжээнээс - хүртэлх мужид үүсгэгдсэн.

Зогсоох шалгуурын хувьд бид нарийвчлалын (7.51) зогсоох шалгуурыг давталтын параметрээр ашигласан. Бүх туршилтуудад энэ арга нь 11 давталтаар шаардлагатай нарийвчлалтай шийдлийг олсон. Өмнөх туршилтуудын хувьд бид хурдатгалтай харьцуулахад хурдатгалыг засах болно зэрэгцээ програм, нэг хэлхээнд ажиллаж байна.

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

Туршилтууд нь сайн хурдатгалыг харуулж байна (8 утас дээр 4 орчим).

Коньюгат градиент арга Хэмжээний тэгш хэмтэй эерэг тодорхой матрицтай шугаман тэгшитгэлийн системийг (7.49) авч үзье. Суурьконьюгат градиент арга байнадараагийн өмч

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

Тэг болж байна. Иймд (7.49) системийн шийдлийг болзолгүй багасгах бодлогын (7.56) шийдэл болгон хайж болно.

Дараалсан алгоритм

Багасгах асуудлыг (7.56) шийдвэрлэхийн тулд дараах давталтын процессыг зохион байгуулна.

Бэлтгэл үе шатыг () томъёогоор тодорхойлно

Үндсэн алхамууд

) томъёогоор тодорхойлогдоно

Энд ойролцоогоор 3-р зөрүү байна, коэффициентийг коньюгацийн нөхцлөөс олно.

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

нэг давталтаар гүйцэтгэсэн үйлдлийн тоо

Үйл ажиллагаа. Эерэг тодорхой тэгш хэмтэй матрицтай шугаман тэгшитгэлийн системийн яг шийдлийг олохын тулд n-ээс илүүгүй давталт хийх шаардлагатай тул яг шийдлийг олох алгоритмын нарийн төвөгтэй байдал нь дараах дарааллаар байгааг харуулж байна. . Гэсэн хэдий ч дугуйралтын алдаанаас болж энэ үйл явцихэвчлэн давтагдах гэж үздэг, ердийн зогсоох нөхцөл (7.51) хангагдсан үед эсвэл үлдэгдэл харьцангуй нормын бага байх нөхцөл хангагдсан үед процесс дуусдаг.

Зэрэгцээ тооцоолох зохион байгуулалт

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

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

Нарийн төвөгтэй байдлын доод эрэмбийн нэмэлт тооцоо нь янз бүрийн вектор боловсруулах үйлдлүүд (скаляр үржвэр, нэмэх, хасах, скаляраар үржүүлэх) юм. Ийм тооцооллын зохион байгуулалт нь мэдээжийн хэрэг сонгосон зүйлтэй нийцэж байх ёстой зэрэгцээ байдлаарматрицыг вектороор үржүүлэх үйлдлийг гүйцэтгэх.

Үүссэн зэрэгцээ тооцооллын үр ашгийг цаашид шинжлэхийн тулд бид матрицыг хэвтээ хуваах замаар матриц-векторын үржүүлгийн зэрэгцээ алгоритмыг сонгоно. Энэ тохиолдолд тооцоолол багатай вектор дээрх үйлдлүүд мөн олон урсгалтай горимд хийгдэнэ.

Тооцооллын хүчин чармайлт дараалсан аргаконьюгат градиентийг хамаарлаар тодорхойлно (7.58). Гүйцэтгэлийн хугацааг тодорхойлъё зэрэгцээ хэрэгжилтконьюгат градиент арга. Туузны хэвтээ матриц хуваах схемийг ашиглах үед матрицыг вектороор үржүүлэх зэрэгцээ үйлдлийн тооцооллын нарийн төвөгтэй байдал нь:

Векторын урт нь хаана байна, утаснуудын тоо, зэрэгцээ хэсэг үүсгэх, хаах нэмэлт зардал юм.

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

Аргын давталтын тоо хаана байна.

Тооцооллын туршилтын үр дүн

Оршил хэсэгт заасан нөхцлөөр тэгш хэмт эерэг тодорхой матрицтай шугаман тэгшитгэлийн системийг шийдвэрлэх коньюгат градиент аргын зэрэгцээ хувилбарын үр нөлөөг үнэлэх тооцооллын туршилтыг хийсэн. Матрицын үндсэн диагональ дээрх элементүүд ) -аас хүртэлх мужид үүссэн бөгөөд энэ нь матрицын хэмжээ, үлдсэн элементүүд нь 0-ээс 1-ийн хооронд тэгш хэмтэй байдлаар үүсгэгдсэн. Нарийвчлалын зогсоох шалгуур (7.51) параметртэй. зогсоох шалгуур болгон ашигласан

Тооцооллын туршилтын үр дүнг Хүснэгт 7.21-д үзүүлэв (алгоритмуудын ажиллах хугацааг секундээр харуулав).

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

Давталт бүрт хамгийн эгц буух аргыг хэрэглэх үед алхамын хэмжээ А к функцийн хамгийн бага нөхцлөөс сонгогдоно 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-ийг багасгах замаар сонгоно Афункцууд q (а) = f(x[к] -af"(x[к])) . Урьдчилсан нөхцөлхамгийн бага функц г j (a)/da = 0.Деривативыг тооцоолсны дараа нарийн төвөгтэй функц, бид зэргэлдээх цэгүүд дэх удам чиглэлийн векторуудын ортогональ байдлын нөхцөлийг олж авна.

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

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

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

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

Туршилтууд нь сайн хурдатгалыг харуулж байна (8 утас дээр 4 орчим).

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

f(x) = (x, Hx) + (b, x) + a

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

Тодорхойлолтоор бол хоёр Туршилтын үр дүн (дээд тайвшруулах арга)- хэмжээст вектор XТэгээд цагтдуудсан Тодорхойлолт. Хоёр n хэмжээст вектор х ба у гэж нэрлэдэгматрицтай харьцангуй Х(эсвэл Х-коньюгат), хэрэв скаляр үржвэр бол (х, За) = 0.Энд N -хэмжээтэй тэгш хэмтэй эерэг тодорхой матриц П X П.

Коньюгат градиент аргын хамгийн чухал асуудлуудын нэг бол чиглэлийг үр дүнтэй барих асуудал юм. Флетчер-Ривзийн арга нь алхам бүрт антиградиентийг хувиргах замаар энэ асуудлыг шийддэг -f(x[к]) чиглэлд х[к], Х-Өмнө нь олдсон чиглэлтэй хослуулах Р, Р, ..., Р[к-1]. Эхлээд энэ аргыг квадрат функцийг багасгах асуудалтай холбон авч үзье.

Чиглэл Р[к]-ийг дараах томъёогоор тооцоолно.

х[к] = -f"(x[к]) +b k-1 х[к-l], к>= 1;

х = -е"(х) .

b утгууд к-1 чиглэлийг сонгосон байхаар х[к], Р[к-1] байсан Х-холбоо:

(х[к], HP[к- 1])= 0.

Үүний үр дүнд квадрат функцийн хувьд

давталттай багасгах үйл явц нь хэлбэртэй байна

x[к+l] =x[к]+a к х[к],

Хаана Р[к] - уруудах чиглэл к-м алхам; А к - алхамын хэмжээ. Сүүлийнх нь функцийн хамгийн бага нөхцлөөс сонгогдоно f(x) By Ахөдөлгөөний чиглэлд, өөрөөр хэлбэл нэг хэмжээст багасгах асуудлыг шийдсэний үр дүнд:

f(x[к] + А к Р[к]) = f(x[к] + ар [к]) .

Квадрат функцийн хувьд

Fletcher-Reeves коньюгат градиент аргын алгоритм нь дараах байдалтай байна.

1. Цэг дээр Xтооцоолсон х = -f"(x) .

2. Асаалттай к- m алхам, дээрх томъёог ашиглан алхамыг тодорхойлно Ак . ба хугацаа X[k+ 1].

3. Утга тооцоолсон f(x[к+1]) Тэгээд f"(x[к+1]) .

4. Хэрэв f"(x) = 0, дараа нь цэг X[к+1] нь функцийн хамгийн бага цэг юм f(x).Үгүй бол шинэ чиглэл тодорхойлогддог х[к+l] харилцаанаас

дараагийн давталт руу шилжих шилжилтийг хийж байна. Энэ процедур нь квадрат функцийн хамгийн бага утгыг олох болно Палхам. Квадрат бус функцийг багасгах үед Флетчер-Ривзийн арга нь төгсгөлөөс давтагдах шинж чанартай болдог. Энэ тохиолдолд дараа нь (p+ 1) 1-4-р процедурын давталт нь солих замаар мөчлөгөөр давтагдана Xдээр X[П+1] ба тооцоолол нь өгөгдсөн тоо хаана байна гэж төгсдөг. Энэ тохиолдолд аргын дараах өөрчлөлтийг ашиглана.

x[к+l] = x[к]+a к х[к],

х[к] = -f"(x[к])+ б к- 1 х[к-l], к>= 1;

х= -f"( x);

f(x[к] + а к х[к]) = f(x[к] +ap[к];

Энд I- олон индексүүд: I= (0, n, 2 p, цалин, ...), өөрөөр хэлбэл арга бүр шинэчлэгддэг Палхам.

Коньюгат градиент аргын геометрийн утга нь дараах байдалтай байна (Зураг 2.11). Өгөгдсөн эхлэлийн цэгээс Xчиглэлд буух ажлыг гүйцэтгэдэг Р = -f"(x). Яг цэг дээр Xградиент векторыг тодорхойлно f"(x). Учир нь Xчиглэл дэх функцын хамгийн бага цэг юм Р, Тэр f"(x) вектор руу ортогональ Р. Дараа нь вектор олдоно Р , Х-тэй нийлэх Р. Дараа нь чигийн дагуу функцийн хамгийн бага утгыг олно Ргэх мэт.

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

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

Зөвхөн градиент тооцоололд суурилсан градиент аргууд Р(x), алхамын интервал дээр шугаман бус функцийг орлуулдаг тул эхний эрэмбийн аргууд юм Р(x) шугаман.

Зөвхөн эхний төдийгүй хоёр дахь деривативыг ашигладаг хоёр дахь эрэмбийн аргууд Р(x) одоогийн цэг дээр. Гэсэн хэдий ч эдгээр аргууд нь шийдвэрлэхэд хэцүү байдаг - нэг цэг дээр хоёрдахь деривативыг тооцоолох, үүнээс гадна хоёрдахь деривативын матриц нь оновчтой байдлаас хол байх нь муу нөхцөлтэй байж болно.

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

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

Аргын алгоритмыг дараах байдлаар бичиж болно (вектор хэлбэрээр):

x 1 = x 0 – h grad R(x 0),

x i+1 = x i – h .

α утгыг илэрхийллээс ойролцоогоор олж болно

Алгоритм нь дараах байдлаар ажиллана. Эхлэх цэгээс X 0 мин хайж байна Р(x) градиентийн чиглэлд (хамгийн эгц буух аргыг ашиглан), дараа нь олсон цэгээс эхлээд хайлтын чиглэл min-ийг хоёр дахь илэрхийллээр тодорхойлно. Чиглэл дэх хамгийн бага хэмжээг хайх ажлыг ямар ч аргаар хийж болно: та хамгийн багадаа сканнердах алхамыг тохируулахгүйгээр дараалсан сканнердах аргыг ашиглаж болох тул чиглэлд хамгийн багадаа хүрэх нарийвчлал нь алхамын хэмжээнээс хамаарна. h.

Квадрат функцийн хувьд Р(x) шийдлийг олох боломжтой Палхамууд (П- асуудлын хэмжээс). Бусад функцүүдийн хувьд хайлт нь удаашралтай байх бөгөөд зарим тохиолдолд хамгийн оновчтой хэмжээнд хүрэхгүй байж магадгүй юм хүчтэй нөлөөтооцооллын алдаа.

Коньюгат градиент аргыг ашиглан хоёр хэмжээст функцын хамгийн бага утгыг хайх боломжит траекторуудын нэгийг Зураг дээр үзүүлэв. 1.

Минимумыг олох коньюгат градиент аргын алгоритм.

Эхний шат.Градиент аргын гүйцэтгэл.

Анхны ойролцоо утгыг тохируулна уу x 1 0 ,X 20 . Шалгуур үзүүлэлтийн утгыг тодорхойлох Р(x 1 0 ,X 20). k = 0 гэж тохируулаад эхний шатны 1-р алхам руу орно.

1-р алхам. Тэгээд
.

Алхам 2.Хэрэв градиент модуль

Алхам 3.

x k+1 = xк – h град Р(xк)).

Алхам 4. Р(x 1 к +1 , X 2 к +1). Хэрэв Р(x 1 к +1 , X 2 к +1)< Р(x 1к, X 2 k), дараа нь k = k+1 гэж тохируулаад 3-р алхам руу орно. Хэрэв Р(x 1 к +1 , X 2 k +1) ≥ Р(x 1к, X 2 к), дараа нь үндсэн шат руу яв.

Үндсэн үе шат.

1-р алхам. R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k , x 2 k + g), R (x 1 k , x 2 k)-ийг тооцоол. . Алгоритмын дагуу төв эсвэл хосолсон түүврээс хэсэгчилсэн деривативын утгыг тооцоолно. Тэгээд . Градиентийн модулийн утгыг тооцоол
.

Алхам 2.Хэрэв градиент модуль
, дараа нь тооцооллыг зогсоож, цэгийг (x 1 k, x 2 k) оновчтой цэг гэж үзнэ. Үгүй бол 3-р алхам руу очно уу.

Алхам 3.α коэффициентийг томъёогоор тооцоол.

Алхам 4.Томъёог ашиглан тооцоолж ажлын алхамыг гүйцэтгэнэ

x k+1 = x k – h .

Алхам 5.Шалгуур үзүүлэлтийн утгыг тодорхойлох Р(x 1 к +1 , X 2 к +1). k = k+1 гэж тохируулаад 1-р алхам руу орно.

Жишээ.

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

Хүснэгт 5

Хамгийн сайн цэг олдлоо. Энэ үед бид деривативуудыг тооцоолно: dR/ dx 1 = –2.908; dR/ dx 2 =1.600; Өмнөх цэг дэх градиентийн нөлөөллийг харгалзан үзсэн α коэффициентийг тооцоолно: α = 3.31920 ∙ 3.3192/8.3104 2 =0.160. Бид аргын алгоритмын дагуу ажлын алхам хийдэг, бид олж авдаг X 1 = 0,502, X 2 = 1.368. Дараа нь бүх зүйл ижил аргаар давтагдана. Доор, хүснэгтэд. 6 дараагийн алхмуудын одоогийн хайлтын координатыг харуулав.

Хүснэгт 6