Кубическая интерполяция (метод Дэвидона)

Пред­ло­жен­ный Дэ­ви­до­ном бы­ст­рый ме­тод од­но­мер­но­го по­ис­ка ми­ни­му­ма, по­доб­но рас­смо­т­рен­но­му вы­ше ме­то­ду ква­д­ра­тичной ин­тер­по­ля­ции, ос­но­ван на ло­каль­ной за­ме­не ми­ни­ми­зи­ру­е­мой функ­ции мно­гочле­ном. От­личие за­ключает­ся, во-пер­вых, в том, что ис­поль­зу­ет­ся мно­гочлен не вто­рой, а треть­ей сте­пе­ни, а во-вто­рых — в спо­со­бе по­стро­е­ния это­го мно­гочле­на.

Мно­гочлен вто­рой сте­пе­ни яв­ля­ет­ся про­стей­шим мно­гочле­ном, спо­соб­ным об­ла­дать ми­ни­му­мом (или ма­к­си­му­мом). При этом па­ра­бо­ла все­гда сим­мет­рична от­но­си­тель­но точки экс­тре­му­ма. Для ми­ни­ми­зи­ру­е­мой функ­ции про­из­воль­но­го ви­да (воз­мо­ж­но, не­сим­мет­ричной) ква­д­ра­тичный ин­тер­по­ля­ци­он­ный мно­гочлен обес­печива­ет удо­в­ле­тво­ри­тель­ную ап­про­к­си­ма­цию лишь в не­по­сред­ст­вен­ной бли­зо­сти от экс­тре­маль­ной точки (там, где мо­ж­но пре­не­б­речь чле­на­ми тре­тье­го и бо­лее вы­со­ких по­ряд­ков в раз­ло­же­нии f(x) в ряд Тей­ло­ра). По этой причине ско­рость схо­ди­мо­сти ме­то­да ква­д­ра­тичной ин­тер­по­ля­ции ста­но­вит­ся до­с­та­точно вы­со­кой толь­ко в кон­це про­цес­са, ко­г­да ин­тер­вал не­оп­ре­де­лен­но­сти мал.

Мно­гочлен треть­ей сте­пе­ни спо­со­бен вос­про­из­ве­сти асим­мет­рию ми­ни­ми­зи­ру­е­мой функ­ции вбли­зи точки экс­тре­му­ма. Он по­з­во­ля­ет ап­про­к­си­ми­ро­вать f(x) на бо­лее ши­ро­ком ин­тер­ва­ле и в пре­де­ле да­ет не ква­д­ра­тичную, а ку­бичес­кую ско­рость схо­ди­мо­сти к ис­ко­мо­му ре­ше­нию. По­э­то­му ме­тод Дэ­ви­до­на обычно при­ме­ня­ют как са­мо­сто­я­тель­ный ме­тод по­ис­ка ми­ни­му­ма, не ком­би­ни­руя его с ка­кой-ли­бо пред­ва­ри­тель­ной про­це­ду­рой сжа­тия ин­тер­ва­ла не­оп­ре­де­лен­но­сти.

По­сколь­ку мно­гочлен треть­ей сте­пе­ни со­дер­жит четы­ре ко­эф­фи­ци­ен­та, то для его по­стро­е­ния не­об­хо­ди­мо иметь четы­ре не­за­ви­си­мые ве­личины, ха­ра­к­те­ри­зу­ю­щие фор­му ап­про­к­си­ми­ру­е­мой функ­ции. Это мо­гут быть, на­при­мер, значения f(x) в четы­рех раз­ных точках, по­з­во­ля­ю­щие по­стро­ить ку­бичес­кий ин­тер­по­ля­ци­он­ный мно­гочлен по схе­ме Ла­гран­жа. Од­на­ко та­кой ва­ри­ант не­удо­бен: ло­ка­ли­за­ция ми­ни­му­ма од­но­значно оп­ре­де­ля­ет­ся все­го тре­мя точка­ми; чет­вер­тая точка яв­ля­ет­ся из­бы­точной, и ее до­ба­в­ле­ние пло­хо сочета­ет­ся со стру­к­ту­рой ос­нов­ных ал­го­рит­мов ми­ни­ми­за­ции. В ме­то­де Дэ­ви­до­на мно­гочлен стро­ит­ся по двум точкам, но в этих точках бе­рут­ся значения не толь­ко са­мой функ­ции, но и ее пер­вой про­из­вод­ной f¢(x).

При вы­во­де расчет­ных фор­мул пред­по­ла­га­ет­ся, что начало отсчета и по­ло­жи­тель­ное на­пра­в­ле­ние пе­ре­мен­ной x мо­ж­но вы­би­рать про­из­воль­но. По­э­то­му ра­ди уп­ро­ще­ния вы­ра­же­ний бе­рут точки x₁=0 и x₂=q>0. Как мы уви­дим в даль­ней­шем, для тех ал­го­рит­мов, где при­ме­ня­ет­ся ме­тод Дэ­ви­до­на, это ог­ра­ничение яв­ля­ет­ся впол­не ес­те­ст­вен­ным.

Пусть за­да­ны значения:

f(x₁)ºf(0)=f₁, f¢(0)=g₁;

f(x₂)ºf(q)=f₂, f¢(q)=g₂.

То­г­да ко­эф­фи­ци­ен­ты ап­про­к­си­ми­ру­ю­ще­го мно­гочле­на P₃(x)=a+bx+cx²+dx³ мо­ж­но най­ти из урав­не­ний:

a =f₁,
a + bq+cq²+dq³ =f₂,
b =g₁,
b+2cq+3dq² =g₂.

Эти уравнения имеют следующее решение:

, (6)

где .

Точки экс­тре­му­мов ку­бичес­ко­го мно­гочле­на P₃(x) яв­ля­ют­ся ре­ше­ни­я­ми ква­д­рат­но­го урав­не­ния b+2cx+3dx²=0. Учиты­вая вы­ра­же­ния (6) для ко­эф­фи­ци­ен­тов, по­лучим ре­ше­ния в ви­де:

,

где .

Ми­ни­му­му от­вечает ре­ше­ние со зна­ком “+” в чис­ли­те­ле:

. (7)

В этом лег­ко убе­дить­ся, под­ста­вив (7) в вы­ра­же­ние для вто­рой про­из­вод­ной (с учетом (6)):

.

Ве­личина r да­ет от­но­си­тель­ное по­ло­же­ние ми­ни­му­ма, вы­ра­жен­ное в еди­ни­цах дли­ны от­ре­з­ка [0, q]. По­сколь­ку для по­стро­е­ния мно­гочле­на вы­би­ра­ют точки, ох­ва­ты­ва­ю­щие ми­ни­мум с двух сто­рон, то g₁ и g₂ име­ют про­ти­во­по­ло­ж­ные зна­ки. По­э­то­му на пра­к­ти­ке вме­сто (7) при­ме­ня­ют эк­ви­ва­лент­ную фор­му­лу, бо­лее ус­тойчивую к вычис­ли­тель­ным ошиб­кам:

. (7a)

Осо­бен­ность ал­го­рит­ма Дэ­ви­до­на со­сто­ит в том, что по­иск начина­ет­ся без пред­ва­ри­тель­ной ло­ка­ли­за­ции ми­ни­му­ма, т. е. пер­во­началь­но за­да­на толь­ко ис­ход­ная точка (началь­ное при­бли­же­ние) x=0. Пе­ред вы­пол­не­ни­ем пер­во­го ша­га не­об­хо­ди­мо ка­ким-то об­ра­зом вы­брать вто­рую точку x=q. Этот вы­бор про­из­во­дит­ся на ос­но­ва­нии оцен­ки значения функ­ции в точке ми­ни­му­ма f_min, ко­то­рую дол­жен пре­до­с­та­вить поль­зо­ва­тель. Значение q оп­ре­де­ля­ют по фор­му­ле

, (8)

Рис. 4. Оценка положения конечной точки на первом шаге метода Дэвидона.

где f₁ и g₁ – зна­че­ния функ­ции и ее про­из­вод­ной в на­чаль­ной точке, а L – ог­ра­ни­чи­тель ша­га, пре­д­у­смо­т­рен­ный на тот случай, ес­ли за­дан­ная оцен­ка f_min ока­жет­ся не­ре­а­ли­стич­ной, или же ве­ли­чи­на g₁ слиш­ком ма­ла (си­ту­а­цию g₁=0 мо­ж­но ис­к­лю­чить из рас­смо­т­ре­ния, так как это оз­на­ча­ло бы, что ми­ни­мум на­хо­дит­ся в ис­ход­ной точке). Смысл фор­му­лы (8) ил­лю­ст­ри­ру­ет­ся рис. 4.

Та­ким об­ра­зом, при­ме­няя ме­тод Дэ­ви­до­на, не­об­хо­ди­мо обес­пе­чить воз­мож­ность рас­че­та зна­че­ний ми­ни­ми­зи­ру­е­мой функ­ции и ее пер­вой про­из­вод­ной, а так­же за­дать на­чаль­ную точку и оцен­ку f_min. По­с­лед­нее об­сто­я­тель­ст­во вы­зы­ва­ет у поль­зо­ва­те­лей наи­боль­шие за­труд­не­ния, по­сколь­ку зна­че­ние функ­ции в точке ми­ни­му­ма, как пра­ви­ло, за­ра­нее не­из­ве­ст­но. Не­об­хо­ди­мо подчерк­нуть, что здесь не тре­бу­ет­ся точ­ное зна­че­ние f_min. Речь идет лишь об ори­ен­ти­ро­воч­ной оцен­ке, ис­хо­дя из об­щих пред­ста­в­ле­ний о по­ряд­ке ве­личины и ха­ра­к­те­ре по­ве­де­ния ми­ни­ми­зи­ру­е­мой функ­ции. Фак­ти­чес­ки, значение f_min обес­пе­чи­ва­ет лишь вы­бор ра­зум­но­го мас­шта­ба при вы­пол­не­нии пер­во­го проб­но­го ша­га вдоль оси x. Из­ме­не­ние этой ве­личины в ту или дру­гую сто­ро­ну в не­сколь­ко раз обычно ни­как не ска­зы­ва­ет­ся на даль­ней­шем по­ве­де­нии ал­го­рит­ма; в худ­шем слу­чае бу­дет сде­ла­но 1-2 лиш­них ша­га. К то­му же от гру­бых оши­бок стра­ху­ет за­ло­жен­ный в ал­го­рит­ме па­ра­метр-ог­ра­ни­чи­тель L.

Об­щая схе­ма ал­го­рит­ма Дэ­ви­до­на та­ко­ва. Пред­по­ла­га­ет­ся, что в на­чаль­ной точ­ке пер­вая про­из­вод­ная от­ри­ца­тель­на (g₁<0), т. е. ось x на­пра­в­ле­на в сто­ро­ну убы­ва­ния функ­ции. Ес­ли это не так, на­пра­в­ле­ние оси ме­ня­ет­ся на про­ти­во­по­ло­ж­ное. За­тем по фор­му­ле (8) оце­ни­ва­ет­ся на­чаль­ное зна­че­ние q и в точке x=q вычис­ля­ет­ся g₂=f¢(q). Ес­ли g₂>0, то x=q ле­жит с дру­гой сто­ро­ны от ми­ни­му­ма по срав­не­нию с на­чаль­ной точ­кой; сле­до­ва­тель­но, ми­ни­мум ло­ка­ли­зо­ван, и под­го­тов­ка к пер­во­му ша­гу за­кончена. В про­тив­ном случае (g₂<0) ве­личина q, очевид­но, слиш­ком ма­ла. По­э­то­му q уд­ва­и­ва­ет­ся и вновь про­ве­ря­ет­ся знак g₂. Эти дей­ст­вия по­в­то­ря­ют­ся до тех пор, по­ка g₂ не ста­нет по­ло­жи­тель­ным. За­тем начина­ет­ся ос­нов­ная часть ал­го­рит­ма. На ка­ж­дом ша­ге по фор­му­ле (7а) оце­ни­ва­ет­ся по­ло­же­ние ми­ни­му­ма x=rq. В си­лу вы­бо­ра ис­ход­ных точек ми­ни­мум за­ключен вну­т­ри от­ре­з­ка [0, q], так что 0<r<1. Точка rq де­лит от­ре­зок [0, q] на две час­ти. Ес­ли f¢(rq)>0, то q за­ме­ня­ет­ся на rq, в про­тив­ном случае началь­ная точка пе­ре­но­сит­ся в точку rq (ины­ми сло­ва­ми, в за­ви­си­мо­сти от зна­ка про­из­вод­ной для сле­ду­ю­ще­го ша­га вы­би­ра­ет­ся ле­вая или пра­вая часть от­ре­з­ка). Про­цесс про­дол­жа­ет­ся до тех пор, по­ка значение про­из­вод­ной, дли­на от­ре­з­ка или по­ни­же­ние зна­че­ния функ­ции не ста­нут мень­ше за­дан­но­го пре­де­ла (кон­крет­ная фор­ма кри­те­рия окон­ча­ния по­ис­ка за­ви­сит от ре­ша­е­мой за­дачи).

Поиск по сайту: