Output Summary 4 страница

19.5. Приложение: обзор теории цепей Маркова

вующего состояния системы. Если t₀ < f, <... < t_n (п = 0,1, 2,...) — моменты време­ни, то семейство случайных величин J4, } будет процессом Маркова тогда и только

тогда, когда оно обладает марковским свойством

Р{^ =*„|4,,_, =*„-„...,);„ =х₀} = Р{^ =х.\Ъ., =*.-i} для всех возможных значений случайных величин 4,,4,,. —. 4, •

Вероятность р, = = х_п\ 4,, = } называется переходной. Она представля­ет собой условную вероятность того, что система будет находиться в состоянии х_п в момент t_n, если в момент <„_, она находилась в состоянии х_п__г Эту вероятность называют также одношаговой переходной, поскольку она описывает изменение со­стояния системы между последовательными моментами времени t_ni и t_n. Анало­гично m-шаговая переходная вероятность определяется формулой

19.5.2. Цепи Маркова

Пусть Е₂, £. 0 = 0, 1, 2,...) — полная и взаимно исключающая группа со­стояний некоторой системы в любой момент времени. В исходный момент <₀ систе­ма может находиться в одном из этих состояний. Пусть я'⁰' (у = 0,1,2,...) — вероят­ность того, что в момент t₀ система находится в состоянии Е_г Предположим также, что рассматриваемая система является марковской.

Определим р,_у = Р{^,_ = у | ^ = /} как одношаговую вероятность перехода системы

из состояния г в момент времени <„., в состояние j в момент t_n и допустим, что эти вероятности постоянны во времени. Удобнее представить вероятности перехода из состояния £, в состояние E_f в матричном виде

'Роо	Poi	Рог	Роз
PlO	Рп	Р.2	Р,з
Р20	Р21	Р22	Ргз
Рзо	Р31	Рз2	Рзз

V ^{: : : :} "V Матрица Р называется однородной матрицей переходов (переходных вероятно­стей), поскольку все переходные вероятности p_tj фиксированы и не зависят от вре­мени. Вероятности р₀ должны удовлетворять условиям

^Pj- = 1 для всех (',

j

p_v > 0 для всех /' и у.

Матрица переходных вероятностей Р совместно с исходными вероятностями со­стояний полностью определяет цепь Маркова (или марковскую цепь). Обычно счита­ется, что цепь Маркова описывает переходный режим некоторой системы на одина­ковых интервалах времени. Однако иногда интервалы времени между переходами зависят от характеристик системы и, следовательно, могут быть неодинаковыми.

Глава 19. Марковские процессы принятия решений

Абсолютные и переходные вероятности. При заданных вероятностях состояний aJ°'J и матрице переходных вероятностей Р абсолютные вероятности состояний

системы после определенного числа переходов определяются следующим образом. Пусть |«у"'} — абсолютные вероятности состояний системы после га переходов, т.е.

в момент t_a. Величины |а'^п)| можно выразить в общем виде через и Р посред-

ством следующего соотношения:

(О (°) (°). (о). V (о)

Следовательно,

где р^ = ^_PtlPiJ — двухшаговая вероятность, или переходная вероятность второ-

I

го порядка, т.е. вероятность перехода из состояния k в состояние j в точности за два шага.

Подобным образом по индукции можно показать, что

где р!"' — «-шаговая переходная вероятность (или переходная вероятность га-го порядка), определяемая рекуррентной формулой

р\ -L.P* Рч-ii

В общем виде для произвольных i и; имеем

pMpW.о<«<„.

*

Эти уравнения известны как уравнения Колмогорова-Чепмена.

Элементы матриц переходов высших порядков Цр,'"'! можно получить непосред­ственно путем перемножения матриц. Так, например,

и в общем случае

|pW|=p-p = p-.

Следовательно, если абсолютные вероятности состояний определены в векторной форме как

то

a^w=a⁽V.

19.5. Приложение: обзор теории цепей Маркова

Пример 19.5.1

Рассмотрим цепь Маркова с двумя состояниями. Матрица переходных вероятно­стей имеет вид

Р =

0,2 0,8 0,6 0,4

и а'⁰' = (0,7, 0,3). Найдем а'", а'⁴¹ и а"

Р² =

^0,6 0,4

р4 ₌ р2р2 р₈₌р4р4

0.443 0,557 0,418 0,582)'

Таким образом,

0,2 0,8Y0,2 0,8W0,52 0,48 0,6 0,4J ^_t,0,36 0,64j'

0,52 0,48Y0,52 0,48> 0,36 0,64Д0,36 0,64^

0,443 0,557 Y0.443 0,557^1 _(0,4291 0,5709^1

0,418 0,582Д0.418 0,582J ~ [0,4284 0,5716J"

m f 0,2 0,8Л

a<" =(0,7,0,3)^ _o>4J = (0,32, 0,68),

,₄₎ (0,443 0,557^1

a¹ '=(0,7,0,3) =(0,436,0,564),

0,418 0,582

_m (0,4291 0,5709⁴;

a⁽⁸⁾ =(0,7,0,3) =(0,4289,0,5711). \0,4284 0,5716j

Отметим, что строки матрицы Р⁸ незначительно отличаются друг от друга. Кроме

(8) _{u п}8

того, вектор а также несущественно отличается от каждой из строк матрицы Р. Это связано с тем, что абсолютные вероятности состояний после выполнения не­скольких переходов практически не зависят от начальных вероятностей а^<0). В том случае, когда они действительно не будут зависеть от начальных вероятностей, их называют установившимися.

Классификация состояний марковских цепей. При рассмотрении цепей Марко­ва нас может интересовать поведение системы на коротком отрезке времени. В та­ком случае абсолютные вероятности вычисляются так, как показано в предыдущем разделе. Однако более важно изучить поведение системы на большом интервале времени, т.е. в условиях, когда число переходов стремится к бесконечности. В этом случае изложенный выше метод непригоден; требуется систематический подход, позволяющий прогнозировать долгосрочное поведение системы. Ниже вводятся определения состояний марковских цепей, которые необходимы для изучения дол­госрочного поведения системы.

Неприводимая марковская цепь. Цепь Маркова называется неприводимой, ес­ли любое состояние E_j может быть достигнуто из любого другого состояния £₍ за

конечное число переходов, т.е. при i Ф j p\f > 0 для 1 < п < оо. В этом случае все со­стояния цепи называются сообщающимися.

Глава 19. Марковские процессы принятия решений

Замкнутое множество состояний и поглощающие состояния. Множество С состояний цепи Маркова называется замкнутым, если система, однажды оказав­шаяся в одном из состояний этого множества, будет находиться в множестве С в течение бесконечного интервала времени. Частным случаем замкнутого множест­ва является единственное состояние £_у с переходной вероятностью р_м= \ ■ В этом

случае состояние E_j называется поглощающим. Все состояния неприводимой цепи должны образовывать замкнутое множество, и ни одно подмножество этого множе­ства не может быть замкнутым. Замкнутое множество С удовлетворяет всем усло­виям, характеризующим марковскую цепь, и, следовательно, его можно подверг­нуть независимому анализу.

Пример 19.5.2

Рассмотрим цепь Маркова со следующей матрицей переходных вероятностей

	(Л
р = 1
	ч0			и

Эта цепь графически представлена на рис. 19.1. Как видно из рисунка, четыре со­стояния не составляют неприводимую цепь, поскольку состояний 0, 1 и 2 нельзя достичь из состояния 3. Состояние 3 образует замкнутое множество и, таким обра­зом, является поглощающим. Можно также утверждать, что состояние 3 соответ­ствует неприводимой цепи Маркова.

Рис. 19.1. Различные виды состояний цепи Маркова

Первое время возвращения. Важным понятием в теории марковских цепей яв­ляется первое время возвращения. Система, первоначально находящаяся в со­стоянии E_jt может вернуться в первый раз в это же состояние через п шагов, п > 1. Число шагов, за которое система возвращается в состояние E_jt называется первым временем возвращения.

Обозначим через вероятность того, что первое возвращение в состояние E_j

состоится на га-м шагу. Тогда при заданной матрице переходных вероятностей

Р = ||p_iy|| /j"' можно определить следующим образом:

19.5. Приложение: обзор теории цепей Маркова

Г В ^J JJ J JJ rjj!

или

/<^2, = р⁽²⁾-/⁽У.

^J JJ " JJ ^J л г II

По индукции нетрудно показать, что

/<"> =»<">_ у /.-)„(.—).

Отсюда следует, что вероятность по крайней мере одного возвращения в состоя­ние E_j задается формулой

fjj ~ ^-jfji ■

Следовательно, система обязательно вернется в состояние j, если /. = 1. Обозначив через среднее время возвращения, получаем

»jj=t<^]-

Если f_B- < 1, то неизвестно, вернется ли система в состояние E_t, и, следователь­но, ц^=°°.

Исходя из определения первого времени возвращения, состояния марковской цепи можно классифицировать следующим образом.

1. Состояние является невозвратным, если у\ < 1, т.е. ц_;> =<х>.

2. Состояние является возвратным, если у\. = 1.

3. Возвратное состояние является нулевым, если ц_и= ос, и ненулевым, когда

< оо (т.е. конечно).

4. Состояние называется периодическим с периодом t, если возвращение в него возможно только через число шагов, кратное <: t, 2t, 3t,... Это означает, что

если п не делится на t без остатка, то pf = 0.

5. Возвратное состояние является эргодическим, если оно ненулевое и аперио­дическое.

Если все состояния цепи Маркова являются эргодическими, то цепь неприводи-ма. В этом случае распределение абсолютных вероятностей состояний

a^w=_a⁽V

всегда однозначно сходится к предельному распределению при п —» оо, где предель-

U (о)

ное распределение не зависит от начальных вероятностей л^к'. Справедлива следующая теорема.

Теорема 19.5.1. Все состояния в неприводимой бесконечной цепи Маркова мо­гут принадлежать к одному и только одному из следующих трех классов: невоз­

Глава 19. Марковские процессы принятия решений

вратных, возвратных нулевых или возвратных ненулевых состояний. Во всех случаях все состояния являются сообщающимися и имеют один и тот же период. В частном случае, когда в цепи конечное число состояний, она не может содер­жать только невозвратные или какие-либо нулевые состояния.

Предельные распределения в неприводимых цепях Маркова. Из приме­ра 19.5.1 видно, что с ростом числа переходов абсолютная вероятность состояний становится независимой от начального распределения. В данном разделе описы­вается метод вычисления предельного распределения вероятностей состояний в неприводимой цепи. Мы ограничимся рассмотрением только апериодических состояний, так как это единственный класс состояний, используемый в дальней­шем. Кроме того, анализ периодических состояний является довольно сложным.

Существование предельного распределения в неприводимой апериодической цепи зависит от класса ее состояний. Таким образом, рассматривая три класса со­стояний, указанных в теореме 19.5.1, можно сформулировать следующую теорему.

Теорема 19.5.2. Если в неприводимой апериодической цепи Маркова

а) все состояния невозвратные или нулевые, то р^^п) —> 0 при га —» оо для всех i и j и предельного распределения не существует,

б) все состояния эргодические, то

lima'"'= я,, у = 0, 1, 2,....

где n_j — предельное (установившееся) распределение. Вероятности n_j оп­ределяются однозначно и не зависят от я'⁰⁾. Величины щ можно опреде­лить из системы уравнении

Среднее время возвращения в состояние j при этом определяется формулой

Пример 19.5.3

Рассмотрим задачу из примера 19.5.1. Для определения установившегося распреде­ления вероятностей используем соотношения

я, =0,2;!, +0,6ti₂, 7i₂ =0,871, +0,4ti₂,

7t, + 7t₂ = 1.

¹ Заметим, что одно из уравнений n_t = ^jt,p^ является избыточным.

19.5. Приложение: обзор теории цепей Маркова

Решением будет я-, = 0,4286 и л_г = 0,5714. Эти результаты очень близки к значени­ям элементов вектора а⁽⁸⁾ (и строкам матрицы Р⁸) из примера 19.5.1. Далее получаем значения среднего времени возвращения в первое и второе состояния

р„= —= 2,3, р₂₂ = —= 1,75. я, я₂

Пример 19.5.4

Рассмотрим следующую цепь Маркова с тремя состояниями:

1 2

Р=1 2

а

0 ±

4 1 4 1 2

Такая матрица называется дважды стохастической, так как

1=1 у.|

где i — число состояний цепи Маркова. В таких случаях установившиеся вероят­ности равны л.,= 1/s для всех j. Поэтому для данной задачи л₀ = л_х = л₂ = 1/3.

УПРАЖНЕНИЯ 19.5

1. Определите класс состояний приведенных ниже цепей Маркова и найдите их стационарные распределения.

а)

fl		П 2
	3 4
		2)
'я	р			о4
Я		Р
Я			Р
я				Р
ll				0;

2. Найдите среднее время возвращения в каждое состояние цепи Маркова, за­данной следующей матрицей переходных вероятностей.

Глава 19. Марковские процессы принятия решений

(1 i Л 3 3 3

111 2 4 4'

111 U 5 5)

ЛИТЕРАТУРА

1. Derman С. Finite State Markovian Decision Process, Academic Press, New York, 1970.

2. Howard R. Dynamic Programming and Markov Processes, MIT Press, Cambridge, Mass., 1960. (Русский перевод: Ховард P. Динамическое программирование и марковские процессы. — М.: Сов. радио, 1964.)

Литература, добавленная при переводе

1. Дынкин Е. Б., Юшкевич А. А. Теоремы и задачи о процессах Маркова. — М.: Наука, 1967.

2. Кемени Дж., Снелл Дж. Конечные цепи Маркова. — М.: Наука, 1970.

ГЛАВА 20

КЛАССИЧЕСКАЯ ТЕОРИЯ ОПТИМИЗАЦИИ

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

В этой главе изложены необходимые и достаточные условия существования экс­тремумов функций при отсутствии ограничений на переменные задачи, методы Яко­ба и Лагранжа для решения задач с ограничениями на переменные в форме равенств, а также условия Куна-Таккера для задач с ограничениями в виде неравенств.

20.1. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ БЕЗ ОГРАНИЧЕНИЙ

Экстремальная точка функции /(X) определяет либо ее максимальное, либо ми­нимальное значение. С математической точки зрения точка 'Х.₀ = (х₁,x_jyxj является точкой максимума функции /(X), если неравенство

/(X₀ + h)</(X₀)

выполняется для всех h = (А,, А_;, А_п) таких, что |Aj достаточно малы при всех j. Другими словами, точка Х₀ является точкой максимума, если значения функции / в окрестности точки Х₀ не превышают /(Х₀). Аналогично точка Х₀ является точ­кой минимума функции /(X), если для определенного выше вектора h имеет место неравенство

/(X₀ + h)>/(X„).

На рис. 20.1 показаны точки максимума и минимума функции одной переменной f(x) на интервале [а, Ь]. Точки x_v х₂, х₃, х₄ и х_в составляют множество экстремаль­ных точек функции f(x). Здесь точки x_v х₃ и х₆ являются точками максимума, а точки х₂их₄ — точками минимума функции f(x). Поскольку

f(x₆) = max{/(^_t), f(x₃), /(*„)}, значение f(x₆) называется глобальным или абсолютным максимумом, а значения f{x_x) и f(x₃) — локальными или относительными максимумами. Подобным образом, значение f(x₄) является локальным, a f(x₂) — глобальным минимумом функции f(x).

Глава 20. Классическая теория оптимизации

а х_х х₂ х_г х₄ х₅ х₆ b х Рас. 20.1. Экстремумы функции одной переменной

Заметим, что хотя точка х₁ является точкой максимума функции f(x) (рис. 20.1), она отличается от остальных локальных максимумов f(x) тем, что по крайней мере в одной точке ее окрестности значение функции f(x) совпадает с f(x,). Точка х, по этой причине называется нестрогим (слабым) максимумом функции f(x), в отличие, например, от точки х₃, которая является строгим максимумом f(x). Нестрогий максимум, следовательно, подразумевает наличие (бесконечного коли­чества) различных точек, которым соответствует одно и то же максимальное значе­ние функции. Аналогичные результаты имеют место в точке x_t, где функция f(x) имеет нестрогий минимум. В общем случае Х₀ является точкой нестрогого макси­мума функции f(x), если /(Х„ + h) < /(Х₀), и точкой ее строгого максимума, если /(Х₀ + h) < /(Х₀), где h — вектор, определенный выше.

На рис. 20.1 легко заметить, что первая производная функции / (тангенс угла наклона касательной к графику функции) равна 0 во всех ее экстремальных точ­ках. Однако это условие выполняется и в точках перегиба и седловых точках функции /, таких как точка х_ь. Если точка, в которой угол наклона касательной к графику функции (градиент функции) равен нулю, не является в то же время точкой экстремума (максимума или минимума), то она автоматически должна быть точкой перегиба или седловой точкой.

20.1.1. Необходимые и достаточные условия существования экстремума

В этом разделе излагаются необходимые и достаточные условия существования экстремумов функции п переменных /(X). При этом предполагается, что первые и вторые частные производные функции f(X) непрерывны в каждой точке X.

Теорема 20.1.1. Необходимым условием того, что точка Х₀ является экстре­мальной точкой функции /(X), служит равенство

V/(X₀) = 0.

Доказательство. Из теоремы Тейлора следует, что при 0 < в< 1 имеет место разложение функции f(X)

/(Х„ + h) -/(Х₀) = V/(X₀)h + |h^rIIh |_Xi+0h,

20.1. Экстремальные задачи без ограничений

где h — вектор, определенный выше. Для достаточно малых значений остаточ­ный член yh^rHh является величиной порядка И¹. Следовательно,

/(x_{0 +} h)-/(x₀) = v/(x₀)h₊o(/,;) = v/(x₀)h.

Пусть Х₀ — точка минимума функции /(X). Докажем от противного, что гради­ент V/(X₀) функции /(X) в точке минимума Х₀ равен нулю. Пусть это условие не вы­полняется; тогда для некоторого j должно выполняться условие

дх_} дх_; Знак Л_у всегда можно выбрать таким образом, чтобы

а,*Ш_<0.

Полагая остальные Л_; равными нулю, из разложения Тейлора получаем неравенство

«X₀ + h)</(X₀).

Этот результат противоречит предположению, что Х₀ — точка минимума. Следова­тельно, величина V/(X₀) должна равняться нулю. Доказательство для точки мак­симума проводится аналогично.

Так как необходимое условие выполняется также в точках перегиба и седловых точках, точки, удовлетворяющие уравнению V/(X₀) = 0, называют стационарными. Следующая теорема устанавливает достаточные условия того, что стационарная точка Х₀ является экстремальной.

Теорема 20.1.2. Для того чтобы стационарная точка Х₀ была экстремальной, достаточно, чтобы матрица Гессе Н в точке Х₀ была

а) положительно определенной (тогда Х₀ — точка минимума);

б) отрицательно определенной (тогда Х₀ — точка максимума).

Доказательство. Согласно теореме Тейлора при 0 < в< 1 имеем

/(х, + ь) - /(х.) = v/(x,)h +U^Tm.

Поскольку X₀ — стационарная точка, по теореме 20.1.1 V/(X₀) = 0. Таким образом,

/(X_{0 +} h)-/(X₀) = ih^rHh|_x^₀„. Если Х₀ — точка минимума, то

f(X₀ + h)>/(X₀)

для всех ненулевых векторов h. Следовательно, в точке минимума Х₀ должно вы­полняться неравенство

ih^rHh|_Xi._oh>0.

Непрерывность вторых частных производных функции /(X) гарантирует, что вели­чина ih^rHh имеет один и тот же знак как в точке Х₀, так и X₀+r3i. Так как h^rHh ^ представляет собой квадратичную форму (см. раздел А.3), ее значение (и, следова­

Глава 20. Классическая теория оптимизации

тельно, h^rHh |_x^_oh) положительно тогда и только тогда, когда H|_Xi —положитель­но определенная матрица. Это означает, что положительная определенность мат­рицы Гессе в стационарной точке Х₀ является достаточным условием существова­ния в этой точке минимума. Путем аналогичных рассуждений доказывается, что стационарная точка является точкой максимума, если матрица Гессе в этой точке отрицательно определена.

Пример 20.1.1

Рассмотрим функцию

/(дс,,х₂,х,) =.V, + 2х_ъ + х,х₃ - х,² -х\- х\. Необходимое условие экстремума VJ[\) = 0 здесь принимает следующий вид.

^ = 1-2*. =0,

ох,

^- = х,-2х_г =0, дх₂

— = 2 + х₂-2х₃=0. сх₃

Решением этой системы уравнений является точка Х₀ = (1/2, 2/3, 4/3). Для проверки выполнения условия достаточности вычислим

' 52/	d2f	д2/ }
Эх,2	дх1дхг	dxtdx}	С
е2/	elL	о2/
OXjOX,	дх\	ох26х3
д2/	d2f	52/	V
ч ох,ох.	ох,ох2	дх] /

-2 1 1 -2

Угловые миноры матрицы Н |_х равны -2, 4 и -6 соответственно. В этом случае Н |_Xi

является отрицательно определенной матрицей (см. раздел А.З), откуда следует, что точка Х₀ = (1/2, 2/3, 4/3) является точкой максимума.

В общем случае, когда матрица Н |_х является неопределенной, точка Х₀ должна быть седловой. Если же матрица Н |_х оказывается полуопределенной, то соответ­ствующая точка Х₀ может как быть, так и не быть экстремальной. При этом фор­мулировка достаточного условия существования экстремума значительно услож­няется, ибо для этого необходимо учитывать члены более высоких порядков в разложении Тейлора.

Применим достаточные условия, полученные в теореме 20.1.2, к функции одной переменной. Пусть у₀ — стационарная точка функции тогда

20.1. Экстремальные задачи без ограничений

1) неравенство f(y₀)<0 является достаточным условием существования мак­симума в точке у₀;

2) неравенство / (i/₀) > 0 является достаточным условием существования мини­мума в точке у₀.

Если же для функции одной переменной / (у₀) = 0, то необходимо исследовать производные высших порядков в соответствии со следующей теоремой.

Теорема 20.1.3. Если в стационарной точке у_й функции f(y) первые (п- 1) ее производных равны нулю и f '"\у₀) *■ 0, то в точке у = у₀ функция f(y) имеет

1) точку перегиба, если п — нечетное;

2) точку максимума, если п — четное и f^M(y₀) < 0;

3) точку минимума, если п — четное и f ⁱⁿ\y₀) > 0.

Пример 20.1.3

Рассмотрим функцииДу) = у* п g(y) = у³. Для функцииДу) = у* имеем

/(у) -4/ = 0,

откуда получаем стационарную точкуу₀ = 0. Далее находим

/(О) =/"(0) =/^,3,(0) = 0. Так какfⁱ⁴\0) = 24 > 0, тоу₀ = 0 является точкой минимума (рис. 20.2). Для функции g{y) = у³ имеем

g'(y)=3.y² = 0.

Следовательно, точка у₀ = 0 является стационарной точкой. Поскольку g(0) =g (0) = 0, g^<3)(0) = 6 и не обращается в нуль, точкау₀ = 0 является точкой перегиба.

/О) //

	g(y)jy3
(	0 У

о

Рис. 20.2. Стационарные точки функций i(y) = у' и g(y) = у

УПРАЖНЕНИЯ 20.1.1

1. Найдите экстремальные точки следующих функций.

a) f(x) = х³ + х.

b) f(x) = х* + х².

c) f(x) = 4*⁴ - х² + 5.

Глава 20. Классическая теория оптимизации

d) /(*) = (Зх - 2)\2х - З)².

e) /(*) = 6л:⁵ -4х³ + 10.

2. Найдите экстремальные точки следующих функций.

a) /(X) = х,³ + х₂ - Зх,х₂.

b) /(Х) = 2х² + х₂ + х₃ +6(х, +х₂ + x,) + 2x,x₂x_s.

3. Проверьте, что функция

/ (х,, х₂, х,) = 2х,х₂х₃ - 4х,х, - 2х₂х₃ + х² + х₂ + х² - 2л:, - 4х₂ + 4х,

имеет стационарные точки (0, 3, 1), (0, 1, -1), (1, 2, 0), (2, 1, 1) и (2, 3, -1). Используйте достаточные условия для нахождения экстремумов функции.

4. Решите следующую систему уравнений путем превращения ее в задачу ми­нимизации нелинейной целевой функции при отсутствии ограничений на переменные.

х₂ - xf = 0, х₂ - х_х = 2.

(Подсказка, min / \x_v х₂) имеет место при /(*,, х₂) = 0.)

5. Докажите теорему 20.1.3.

20.1.2. Метод Ньютона-Рафсона

В общем случае использование необходимого условия экстремума V/(X) = 0 для поиска стационарных точек функции /(X) может быть сопряжено с трудностями, возникающими при численном решении соответствующей системы уравнений. Ме­тод Ньютона-Рафсона предлагает итерационную процедуру решения системы не­линейных уравнений. Несмотря на то что данный метод рассматривается в этом разделе именно в указанном контексте, на самом деле он относится к числу гради­ентных методов численного поиска экстремумов функций при отсутствии ограни­чений (см. раздел 21.1.2).