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

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

Таблица 7.20. Результаты экспериментов (метод верхней релаксации)

n	1 поток	Параллельный алгоритм
		2 потока		4 потока		6 потоков		8 потоков
		T	S	T	S	T	S	T	S
2500	0,73	0,47	1,57	0,30	2,48	0,25	2,93	0,22	3,35
5000	3,25	2,11	1,54	1,22	2,67	0,98	3,30	0,80	4,08
7500	7,72	5,05	1,53	3,18	2,43	2,36	3,28	1,84	4,19
10000	14,60	9,77	1,50	5,94	2,46	4,52	3,23	3,56	4,10
12500	25,54	17,63	1,45	10,44	2,45	7,35	3,48	5,79	4,41
15000	38,64	26,36	1,47	15,32	2,52	10,84	3,56	8,50	4,54

Рис. 7.50.

Эксперименты демонстрируют неплохое ускорение (порядка 4 на 8-и потоках).

Метод сопряженных градиентов

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

Обращается в ноль. Таким образом, решение системы (7.49) можно искать как решение задачи безусловной минимизации (7.56).

Последовательный алгоритм

С целью решения задачи минимизации (7.56) организуется следующий итерационный процесс.

Подготовительный шаг () определяется формулами

Где – произвольное начальное приближение; а коэффициент вычисляется как

Основные шаги (

) определяются формулами

Здесь – невязка -го приближения, коэффициент находят из условия сопряженности

Направлений и ; является решением задачи минимизации функции по направлению

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

Таким образом, выполнение итераций метода потребует

(7.58)

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

Организация параллельных вычислений

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

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

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

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

Вычислительная трудоемкость последовательного метода сопряженных градиентов определяется соотношением (7.58). Определим время выполнения параллельной реализации метода сопряженных градиентов. Вычислительная сложность параллельной операции умножения матрицы на вектор при использовании схемы ленточного горизонтального разделения матрицы составляет

Где – длина вектора, – число потоков, – накладные расходы на созда- ние и закрытие параллельной секции.

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

Где – число итераций метода.

Результаты вычислительных экспериментов

Вычислительные эксперименты для оценки эффективности параллельного варианта метода сопряженных градиентов для решения систем линейных уравнений с симметричной положительно определенной матрицей прово- дились при условиях, указанных во введении. Элементы на главной диагонали матрицы ) генерировались в диапазоне от до , где – размер матрицы, остальные элементы генерировались симметрично в диапазоне от 0 до 1. В качестве критерия остановки использовался критерий остановки по точности (7.51) с параметром

Результаты вычислительных экспериментов приведены в таблице 7.21 (время работы алгоритмов указано в секундах).

f (x )

		f (xk ) = f(x0 ) + ∑ α i Api .
		i= 1
	обе части	этого равенства скалярно на p k		учитывая
исчерпывающего спуска по направлению p k :(f (x k ), p k ) = 0			и A −ортогональность
векторов, получаем
		(f (x 0 ),p k )+ α k (Ap k ,p k )= 0.
		A положительно определена,	квадратичная
(Ap k , p k ) > 0 и для величины шагаα k получаем выражение (5.17).
	Последовательный исчерпывающий спуск			A –ортогональным

направлениям (5.16) приводит к точке минимума квадратичной формы не более чем за n шагов.

□ Доказать самостоятельно. Предположить, что существуют u k ≠ α k , и

получить, что они совпадают. ■

Вопрос о нахождении базиса из A –ортогональных векторов в пространствеE n

решается неоднозначно. В качестве такого базиса можно, например, взять ортогональный базис из собственных векторов матрицы A . Однако их поиск приn > 2 представляет собой самостоятельную и довольно сложную задачу.

и без предварительного построения векторов p 1 , ..., p n , последовательно находя их в процессе минимизации, как это было сделано выше в примере с минимизацией функции двух переменных. И в этом случае для квадратичной функции с положительно определенной матрицейA для нахождения минимума достаточно конечное число шагов. Если не является квадратичной функцией или

вспомогательные задачи одномерной минимизации решаются приближенно, потребуются дополнительные вычисления.

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

5.6. Метод сопряженных градиентов

При использовании методов градиентного и наискорейшего спуска в итерационной процедуре

антиградиента: p k = − f (x k ). Однако такой выбор направления убывания не всегда бывает удачным. В частности, для плохо обусловленных задач минимизации направление антиградиента в точкеx k может значительно отличаться от направления к точке минимумаx . В результате траектория приближения к точке минимума имеет зигзагообразный характер. Воспользуемся другим подходом, идея которого была изложена при построении метода сопряженных направлений. Будем определять направления спускаp k не только через вектор антиградиента− f (x k ) ,

в котором величина шага α k находится из условия исчерпывающего спуска по

направлению p k . Далее,		после вычисления очередной точки x k + 1 ,					k = 0, 1, ..., новое
направление поиска p k + 1		находится по формуле, отличной от антиградиента:
	pk + 1 = − f(xk + 1 ) + β k pk ,			k = 0, 1, ...,
где коэффициенты		выбираются так, чтобы при минимизации квадратичной
функции f (x ) с	положительно определенной					матрицей	A получалась
последовательность	A −ортогональных			векторов		p 0 ,p 1 , ....	Из условия
(Ap k + 1 ,p k )= 0имеем:
		β k=	(A f (x k + 1 ),p k )
			(Ap k ,p k )

Ранее, при обсуждении метода сопряженных направлений было показано, что

для квадратичной функции шаг исчерпывающего спуска по направлению p k равен

α k = −	(f (x k ),p k )
	(Ap k ,p k )
Утверждение . Итерационный процесс			(5.19)−(5.22) минимизации

квадратичной функции с положительно определенной симметрической матрицей

f (x )

A дает точки	x 0 , ...,x k	и векторы p 0 , ..., p k такие, что если				f (x i )≠ 0при
0 ≤i	то векторы		p 0 , ...,		A −ортогональны,		градиенты
f (x 0 ), ...,f (x i )	взаимно ортогональны.
Так как направления				являются A −ортогональными,

гарантирует нахождение точки минимума сильно выпуклой квадратичной функции не более чем за n шагов.

С учетом взаимной ортогональности градиентов f (x i ) и условий

исчерпывающего спуска по направлениям p k можно упростить выражения (5.21) и

(5.22) для α k

и β k . В результате получим,

что итерационный процесс метода

сопряженных градиентов описывается соотношениями

x k+ 1

X k +α k

p k ,k = 0, 1, ...;

x0 En ,

p0 = − f(x0 ) ,

f (x k + α k p k )= minf (x k

+ αp k ),

k = 0, 1, ...,

α> 0

p k+ 1

= − f (x k + 1 ) +β k

p k ,k = 0, 1, ...,

β k=

f (xk + 1 )

k = 1, 2, ...

f (xk )

Следует отметить, что выражение для коэффициента β k не содержит в явном виде матрицуA квадратичной формы. Поэтому метод сопряженных градиентов может применяться для минимизации неквадратичных функций.

Итерационный процесс (5.23)−(5.26) может не приводить к точке минимума неквадратичной функции за конечное число итераций. Более того, точное

определение α k из условия (5.22) возможно лишь в редких случаях, а вектораp k

на образуют, вообще говоря, A −ортогональную систему относительно какой-либо матрицыA . Поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Эти погрешности, накапливаясь, могут привести к

тому, что векторы p k перестанут указывать направление убывания функции и

сходимость метода может нарушаться. Поэтому в методе сопряженных градиентов применяется практический прием − через каждые N шагов производят обновление метода, полагаяβ m N = 0, m = 1, 2, ... . Номераm N называют моментами

обновления метода, или рестарта . Часто полагаютN = n − размерности пространстваE n . ЕслиN = 1 , то получается частный случай метода сопряженных градиентов − метод наискорейшего спуска.

Вблизи точки минимума дважды дифференцируемая функция с положительно определенной матрицей Гессе H (x ) , как правило, достаточно хорошо

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

Пример 5.7. Методом сопряженных градиентов найти точку минимума

функции f (x ) = 4 x 2 + 3 x 2 − 4 x x

из начальной точки x 0 = (0, 0) T .

□ Итерация 1.

Шаг 1. Положим ε = 0,01,

= (0, 0)T ,

и найдем f (x 0 ) = (1, 0) T . Перейдем к

Шаг 2. Положим k = 0,

= − f (x 0 ) = (− 1, 0) T . Перейдем к шагу 3.

f (x0

+ α p 0 )→ min.Получим

α 0 = 1/ 8 . – Здесь применили формулуα 0 = −

(f (x 0 ),p 0 )

(Ax 0 + b ,p 0 )

Перейдем

(Ap 0 ,p 0 )

(Ap 0 ,p 0 )

Шаг 4. Найдем

x 1= x 0

+ α 0 p 0 = (− 1/ 8,

и f (x 1 ) = (0, 1/ 2) T . Точность не

достигнута, прейдем к шагу 5.

Шаг 5. Условие k + 1 = n не выполняется (нет рестарта), перейдем к шагу 6.

Шаг 6. Найдем коэффициент β 0 = 1/ 4 и новое направление спуска

p 1 = − f (x 1 ) + β 0 p 0 = (− 1/ 4, − 1/ 2) T . Перейдем к следующей итерации.

Поскольку x 1 , f (x 1 ) иp 1

= − f (x 1 ) +β 0

уже вычислены на итерации 1, то

итерацию 2 начинаем с шага 3.

Итерация 2.

Шаг 3. Решим задачу одномерной минимизации

f (x 1 + α p 1 ) → min . Получим

α = 1/ 4 . Перейдем к шагу 4.

Шаг 4. Найдем x 2

X 1 +α 1

p 1 = (− 3 /16,− 1/ 8)T и f (x 2 )= (0, 0)T − задача решена

Назначение сервиса . Онлайн-калькулятор предназначен для нахождения минимума функции методом сопряженных градиентов (см. пример). Метод Флетчера-Ривза и метод сопряженных градиентов – это разные методы, хотя второй и является разновидностью первого. Флетчер и Ривз расширили предшествующий метод на случай произвольных функций. В применении к квадратичным функциям он становится равносильным методу сопряженных градиентов. Также реализован вариант Миля-Кентрелла .

f(x 1 ,x 2) =

Метод отыскания минимума функции Метод сопряженных градиентов Метод Флетчера–Ривза Метод Миля-Кентрелла Метод Поллака-Рибьера Метод Ньютона Метод наискорейшего спуска
Начиная из точки ( ; ) . Точность ξ = .
Количество итераций 1 2 3

Решение оформляется в формате Word .

Правила ввода функций :

Например, x 1 2 +x 1 x 2 , записываем как x1^2+x1*x2

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

Схема алгоритма метода сопряженных градиентов

Положить k=0.
Ш. 1 Пусть x 0 - начальная точка; ,
d 0 =-g 0 ; k=0.
Ш. 2 Определить x k +1 =x k +λ k d k , где
.
Затем d k+1 =-g k+1 +β k d k ,
,
β k находится из условия d k +1 Ad k =0 (сопряжены относительно матрицы A).
Ш. 3 Положить k=k+1 → Ш. 2.
Критерий останова одномерного поиска вдоль каждого из направлений d k записывается в виде: .
Значения выбираются таким образом, чтобы направление d k было A-сопряжено со всеми построенными ранее направлениями.

Метод Флетчера-Ривса

Стратегия метода Флетчера-Ривса состоит в построении последовательности точек {x k }, k=0, 1, 2, ... таких, что f(x k +1) < f(x k), k=0, 1, 2, ...
Точки последовательности {x k } вычисляются по правилу:
x k +1 =x k -t k d k , k = 0, 1, 2,…
d k = ▽f(x k) + b k -1 ▽f(x k -1)

Величина шага выбирается из условия минимума функции f(х) по t в направлении движения, т. е. в результате решения задачи одномерной минимизации:
f(x k -t k d k) → min (t k >0)
В случае квадратичной функции f(x)= (х, Нх) + (b, х) + а направления d k , d k -1 будут H-сопряженными, т.е. (d k , Hd k -1)=0
При этом в точках последовательности {x k } градиенты функции f(x) взаимно перпендикулярны, т.е. (▽f(x k +1),▽f(x k))=0, k =0, 1, 2…
При минимизации неквадратичных функций метод Флетчера-Ривса не является конечным. Для неквадратичных функций используется следующая модификация метод Флетчера-Ривса (метод Полака-Рибьера), когда величина b k -1 вычисляется следующим образом:

Здесь I- множество индексов: I = {0, n, 2n, 3n, ...}, т. е. метод Полака-Рибьера предусматривает использование итерации наискорейшего градиентного спуска через каждые n шагов с заменой x 0 на x n +1 .
Построение последовательности{x k } заканчивается в точке, для которой |▽f(x k)|<ε.
Геометрический смысл метода сопряженных градиентов состоит в следующем. Из заданной начальной точки x 0 осуществляется спуск в направлении d 0 = ▽f(x 0).В точке x 1 определяется вектор-градиент ▽f(x 1).Поскольку x 1 является точкой минимума функции в направлении d 0 , то▽f(x 1) ортогонален вектору d 0 . Затем отыскивается вектор d 1 , H-сопряженный к d 0 . Далее отыскивается минимум функции вдоль направления d 1 и т. д.

Алгоритм метода Флетчера-Ривса

Начальный этап.
Задать x 0 , ε > 0.
Найти градиент функции в произвольной точке
k=0.
Основной этап
Шаг 1. Вычислить ▽f(x k)
Шаг 2. Проверить выполнение критерия останова |▽f(x k)|< ε
а) если критерий выполнен, расчет окончен,x * =x k
б) если критерий не выполнен, то перейти к шагу 3, если k=0, иначе к шагу 4.
Шаг 3. Определить d 0 = ▽f(x 0)
Шаг 4. Определить или в случае неквадратичной функции
Шаг 5. Определить d k = ▽f(x k) + b k -1 ▽f(x k -1)
Шаг 6. Вычислить величину шага t k из условия f(x k - t k d k) → min (t k >0)
Шаг 7. Вычислить x k+1 =x k -t k d k
Шаг 8. Положить k= k +1 и перейти к шагу 1.

Сходимость метода

Теорема 1. Если квадратичная функция f(x) = (х, Нх) + (b, х) + а с неотрицательно определенной матрицей Н достигает своего минимального значения на R n , то метод Флетчера-Ривса обеспечивает отыскание точки минимума не более чем за n шагов.
Теорема 2. Пусть функция f(x) дифференцируема и ограничена снизу на R m , а ее градиент удовлетворяет условию Липшица . Тогда при произвольной начальной точке для метода Полака-Рибьера имеем
Теорема 2 гарантирует сходимость последовательности {x k } к стационарной точке x * , где ▽f(x *)=0. Поэтому найденная точка x * нуждается в дополнительном исследовании для ее классификации. Метод Полака-Рибьера гарантирует сходимость последовательности {x k } к точке минимума только для сильно выпуклых функций.
Оценка скорости сходимости получена только для сильно выпуклых функций , в этом случае последовательность {x k } сходится к точке минимума функции f(x) со скоростью: |x k+n – x*| ≤ C|x k – x*|, k = {0, n, 2, …}

Пример . Найти минимум функции методом сопряженных градиентов: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10 .
Решение. В качестве направления поиска выберем вектор градиент в текущей точке:

- t 0 - 0.1786

20 10

= + 0.0459 - t 1 - 0.4667 Так как матрица Гессе является положительно определенной, то функция f(X) строго выпукла и, следовательно, в стационарной точке достигает глобальный минимум .

Градиентные методы, базирующиеся только на вычислении градиента R (x ), являются методами первого порядка, так как на интервале шага они заменяют нелинейную функцию R (x ) линейной.

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

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядка с исключением их недостатков. На начальных этапах (вдали от оптимума) метод ведет себя как метод первого порядка, а в окрестностях оптимума приближается к методам второго порядка.

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

Алгоритм метода можно записать следующим образом (в векторной форме):

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

x i+1 = x i – h .

Величина α может быть приближенно найдена из выражения

Алгоритм работает следующим образом. Из начальной точки х 0 ищут minR (x ) в направлении градиента (методом наискорейшего спуска), затем, начиная с найденной точки и далее, направление поиска min определяется по второму выражению. Поиск минимума по направлению может осуществляться любым способом: можно использовать метод последовательного сканирования без коррекции шага сканирования при переходе минимума, поэтому точность достижения минимума по направлению зависит от величины шага h .

Для квадратичной функции R (x ) решение может быть найдено за п шагов (п – размерность задачи). Для других функций поиск будет медленнее, а в ряде случаев может вообще не достигнуть оптимума вследствие сильного влияния вычислительных ошибок.

Одна из возможных траекторий поиска минимума двумерной функции методом сопряженных градиентов приведена на рис. 1.

Алгоритм метода сопряжённых градиентов для поиска минимума.

Начальный этап. Выполнение градиентного метода.

Задаём начальное приближение x 1 0 , х 2 0 . Определяем значение критерия R (x 1 0 , х 2 0). Положить k = 0 и перейти к шагу 1 начального этапа.

Шаг 1. и
.

Шаг 2. Если модуль градиента

Шаг 3.

x k+1 = x k – h grad R (x k)).

Шаг 4. R (x 1 k +1 , х 2 k +1). Если R (x 1 k +1 , х 2 k +1) < R (x 1 k , х 2 k), то положить k = k+1 и перейти к шагу 3. Если R (x 1 k +1 , х 2 k +1) ≥ R (x 1 k , х 2 k), то перейти к основному этапу.

Основной этап.

Шаг 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. Определить значение критерия R (x 1 k +1 , х 2 k +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. Делаем рабочий шаг в соответствии с алгоритмом метода, получаем х 1 = 0,502, х 2 = 1,368. Далее все повторяется аналогично. Ниже, в табл. 6 приведены текущие координаты поиска следующих шагов.

Таблица 6

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

Описание алгоритма

Шаг 0 . Выбирается точка начального приближения , параметр длины шага , точность решения и вычисляется начальное направление поиска .

Шаг k . На k -м шаге находится минимум (максимум) целевой функции на прямой, проведенной из точки по направлению . Найденная точка минимума (максимума) определяет очередное k -е приближение , после чего определяется направление поиска

Формула (5.4) может быть переписана в эквивалентном виде

.

Алгоритм завершает свою работу, как только выполнится условие ; в качестве решения принимается значение последнего полученного приближения .

Метод Ньютона

Метод предназначен для решения задачи (5.1) и принадлежит классу методов второго порядка. В основе метода лежит разложение Тейлора целевой функции и то, что в точке экстремума градиент функции равен нулю, то есть .

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

. (5.5)

Формулу (5.5) перепишем в матричной форме, учитывая при этом, что :

где матрица Гессе целевой функции в точке .

Предположим, что матрица Гессе невырождена. Тогда она имеет обратную матрицу . Умножая обе части уравнения (5.6) на слева, получим , откуда

. (5.7)

Формула (5.7) определяет алгоритм метода Ньютона: пересчет приближений на k

Алгоритм заканчивает свою работу, как только выполнится условие

,

где заданная точность решения; в качестве решения принимается значение последнего полученного приближения .

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

Метод является методом первого порядка и предназначен для решения систем n нелинейных уравнений c n неизвестными:

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

Пусть точка есть решение системы (5.9), а точка расположена вблизи . Разлагая функцию в точке по формуле Тейлора, имеем

откуда (по условию ) вытекает

, (5.11)

где матрица Якоби вектор-функции . Предположим, что матрица Якоби невырождена. Тогда она имеет обратную матрицу . Умножая обе части уравнения (5.11) на слева, получим , откуда

. (5.12)

Формула (5.12) определяет алгоритм метода Ньютона-Рафсона: пересчет приближений на k -й итерации выполняется в соответствии с формулой

В случае одной переменной, когда система (5.9) вырождается в единственное уравнение , формула (5.13) принимает вид

, (5.14)

где значение производной функции в точке .

На рис. 5.2 показана схема реализации метода Ньютона-Рафсона при поиске решения уравнения .

Замечание 5.1. Сходимость численных методов, как правило, сильно зависит от начального приближения.

Замечание 5.2. Методы Ньютона и Ньютона-Рафсона требуют большого объема вычислений (надо на каждом шаге вычислять и обращать матрицы Гессе и Якоби).

Замечание 5.3. При использовании методов обязательно следует учитывать возможность наличия многих экстремумов у целевой функции (свойство мультимодальности ).

ЛИТЕРАТУРА

1. Афанасьев М.Ю. , Суворов Б.П. Исследование операций в экономике: Учебное пособие. – М.: Экономический факультет МГУ, ТЕИС, 2003 – 312 с.

2. Базара М, Шетти К. Нелинейное программирование. Теория и алгоритмы: Пер. с англ. – М.: Мир, 1982 – 583 с.

3. Берман Г .Н . Сборник задач по курсу математического анализа: Учебное пособие для вузов. – СПб: «Специальная Литература», 1998. – 446 с.

4. Вагнер Г. Основы исследования операций: В 3-х томах. Пер. с англ. – М.: Мир, 1972. – 336 с.

5. Вентцель Е. С. Исследование операций. Задачи, принципы, методология – М.: Наука, 1988. – 208 с.

6. Демидович Б.П. Сборник задач и упражнений по математическому анализу. – М.: Наука, 1977. – 528 с.

7. Дегтярев Ю.И. Исследование операций. – М.: Высш. шк., 1986. – 320 с.

8. Нуреев Р.М. Сборник задач по микроэкономике. – М.: НОРМА, 2006. – 432 с.

9. Солодовников А. С., Бабайцев В.А., Браилов А.В. Математика в экономике: Учебник: В 2-х ч. – М.:Финансы и статистика, 1999. – 224 с.

10. Таха Х. Введение в исследование операций, 6-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 912 с.

11. Химмельблау Д. Прикладное нелинейное программирование: Пер. с англ. – М.: Мир, 1975 – 534 с.

12. Шикин Е. В., Шикина Г.Е. Исследование операций: Учебник – М.: ТК Велби, Изд-во Проспект, 2006. – 280 с.

13. Исследование операций в экономике : Учебн. пособие для вузов/ Н.Ш.Кремер, Б.А.Путко, И.М.Тришин, М.Н.Фридман; Под ред. проф. Н.Ш.Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. – 407 с.

14. Матрицы и векторы : Учебн. пособие/ Рюмкин В.И. – Томск: ТГУ, 1999. – 40 с.

15. Системы линейных уравнений : Учебн. пособие / Рюмкин В.И. – Томск: ТГУ, 2000. – 45 с.

ВВЕДЕНИЕ……………………………………...................................
1. ОСНОВЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ………………...
1.1. Постановка задачи математического программирования...............................
1.2. Разновидности ЗМП…………….…………..........................................
1.3. Базовые понятия математического программирования................................
1.4. Производная по направлению. Градиент………….........................................
1.5. Касательные гиперплоскости и нормали…………..........................................
1.6. Разложение Тейлора……………………………...............................................
1.7. ЗНЛП и условия существования ее решения...................................................
1.8. Задачи ……………..……...................................................................................
2. РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БЕЗ ОГРАНИЧЕНИЙ................................................................................................................
2.1. Необходимые условия решения ЗНЛП без ограничений...............................
2.2. Достаточные условия решения ЗНЛП без ограничений.................................
2.3. Классический метод решения ЗНЛП без ограничений...................................
2.4. Задачи……………..............................................................................................
3. РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ОГРАНИЧЕНИЯХ-РАВЕНСТВАХ.................................................................................
3.1. Метод множителей Лагранжа…………………………...................................
3.1.1. Назначение и обоснование метода множителей Лагранжа……………
3.1.2. Схема реализации метода множителей Лагранжа……………………...
3.1.3. Интерпретация множителей Лагранжа…………………………………
3.2. Метод подстановки…………………………….................................................
3.3. Задачи…………………………..........................................................................
4. РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ОГРАНИЧЕНИЯХ-НЕРАВЕНСТВАХ………………………………………………..
4.1. Обобщенный метод множителей Лагранжа…………………………………
4.2. Условия Куна-Таккера…………………………..............................................
4.2.1. Необходимость условий Куна-Таккера…………………………………
4.2.2. Достаточность условий Куна-Таккера…………………………………..
4.2.3. Метод Куна-Таккера………………………...............................................
4.3. Задачи…………………………..........................................................................
5. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ …………………………...……………………………………
5.1. Понятие алгоритма…………………………....................................................
5.2. Классификация численных методов…………………………………………
5.3. Алгоритмы численных методов……………………………………………...
5.3.1. Метод наискорейшего спуска (подъема)…………………………………
5.3.2. Метод сопряженных градиентов………………………….........................
5.3.3. Метод Ньютона………………………….....................................................
5.3.4. Метод Ньютона-Рафсона………………………………………………...
ЛИТЕРАТУРА………………………………..............................................................

Определения линейной и нелинейной функций см. в разделе 1.2