Метод ДФП

Начнем поиск из начальной точки , взяв H ₀ в виде Е.

1. На шаге i имеется точка и матрица H.
2. В качестве направления поиска взять направление
3. Чтобы найти λ _i , необходимо минимизировать вдоль прямой .
4. Положить
5. Положить
6. Найти и . Завершить процедуру, если или достаточно малы.
7. Положить
8. Обновить матрицу Н: , где ; .
9. Увеличить i+ 1 и вернуться на шаг 2.

Доказательства использования H_i отсутствуют.

Программа метода ДФП.

procedure DFP;

type tt=array[1..10] of real; var X, P, Q, R, D, G, U, V, Y, M: tt;

type mat=array[1..10, 1..10] of real; var H: mat;

var I, J, N: integer;

var FP, GI; GP; QX, HH, BB, FQ, GQ, ZZ, FR, GR, KK, DK, WK: integer;

begin GQ: =0;

for I: =1 to N do

begin

for J: =1 to N do H[I, J]: =0; H[I, I]: =1;

end;

TT: =0;

4: for I: =1 to N do

begin

P[I]: =x[I]; Y[I]: =x[I];

end;

FUNK;

FP: =Z; GRAD; GI: =G0;

for I: =1 to N do

begin

U[I]: =G[I]; D[I]: =0;

for J: =1 to N do D[I]: =D[I]-H[I, J]*G[J];

6: GP: =0;

for I: =1 to N do CP: =GP+G[I]*D[I];

if GP< 0 then goto 68;

QX: =abs(2*FP/GP);

if QX> 1 then QX: =1;

for I: =1 to N do

begin x[I]: =P[I]-Qx*D[I]; P[I]: =x[I];

end;

FUNK;

FP: =Z; GRAD; G1: =G0; goto 6;

68: QX: =abs(2*FP/GP);

if QX> 1 then Qx: =1;

HH: =QX; BB: =HH;

for I: =1 to N do

begin Q[I]: =P[I]+BB*D[I]; X[I]: =Q[I];

end;

FUNK; FQ: =Z; GRAD; GZ: =G0; GQ: =0;

7: BB: =HH;

for I: =1 to N do

begin Q[I]: =P[I]+BB*D[I]; X[I]: =Q[I];

end;

FUNK; FQ: =Z; GRAD; GZ: =G0; GQ: =0;

for I: =1 to N do GQ: =GQ+G[I]*D[I];

if ((GQ> 0)or(FQ> FP)) then goto 83;

HH: =2*HH; goto 7;

83: ZZ: =3*(FP-FQ)/HH; ZZ: =ZZ+GP+GQ; WW: =ZZ*ZZ-GP*GQ;

if WW< 0 then WW: =0; W: =sqr(WW);

DD: =HH*(1-(GQ+W-ZZ)/(GQ-GP+2*W));

for I: =1 to N do x[I]: =P[I]+DD*D[I]; FUNK; FR: =Z;

GRAD; G3: =G0; GR: =0;

for I: =1 to N do GR: =GR+G[I]*D[I];

if ((Z< =FP) and (Z< =FQ)) then goto 11;

if GR> 0 then goto 99;

HH: =HH-DD;

for I: =1 to N do P[I]: =x[I];

FP: =Z; GP: =GR; G1: =G0; goto 83;

99: HH: =DD;

for I: =1 to N do Q[I]: =x[I];

11: KK: =0; WK: =0; DK: =0;

for I: =1 to N do

begin U[I]: =G[I]-U[I]; V[I]: =x[I]-Y[I];

end;

for I: =1 to N do

begin

M[I]: =0;

for J: =1 to N do M[I]: =M[I]+H[I, J]*U[J];

KK: =KK+M[I]*U[I]; WK: =WK+V[I]+U[I];

DK: =DK+V[I]*V[I];

end;

if ((KK=0) or (WK=0)) then goto 126

Проиллюстрируем основную идею метода графически на рис.5.11 для функции

f (x)=(x ₁ –3)² +(x₂ –2)²-5.

Окружности – линии равного уровня для f(x).

Пунктиром показаны траектории поиска экстремума покоординатным методом.

Сплошная линия – траектория наискорейшего спуска.

Градиент функции определяется:

f(x)=grad f(x)=(2x₁-6, 2x₂-4).

Рис. 5.11

Если овраг направлен вдоль одной из осей, то проблем поиска экстремума не возникает, но процесс наискорейшего спуска перестает быть таковым (рис.5.12) (шарик катится на дно, переваливаясь с одного склона на другой)

А если овраги узки и извилисты, то рассмотренные методы могут зайти в тупик.

Рис. 5.12

Литература

1. Мак-Кракен Д., Дорн У. Численные методы и программирование на Фортране. -

М.: Мир, 1977.

2. Корн Г., Корн Т. Справочник по математике, глава 20-я, М.: Наука, 1978.

3. Калиткин Н.Н. Численные методы. – М.: Наука, 1978.

4. Турчак Л.И. Основы численных методов. – М.: Наука, 1987.

5. Банди Б. Методы оптимизации. – М.: Наука, 1987.

6. Волков Е.А. Численные методы. – М.: Наука, 1987.

7. Дьяконов В.П. Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ. – М.: Наука, 1989.

8. Мудров А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. – М.: Роско, 1991.

9.Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.: Физматгиз, 2001.

10. Метьюз Д. Численные методы.- М.: 2001.

11.Ануфриев И.Е., Смирнов А.Б, Смирнова Е.Н. Матлаб 7.0 в подлиннике.- С.-Пб., 2005.

12.Кетков Ю.Л., Кетков А.Ю., Шульц М.М. Матлаб 7: программирование, численные методы. – СПб.: БХВ-Петербург, 2005.

13. M.J.Box, D.Davies and W.H.Swann, Non-linear Optimisation Techniques, ICI ltd., Monograph No.5, Oliver and Boyd, 1969.

Оглавление стр.

Предисловие 2

Введение 2

Глава 1.

Погрешности результата численного решения 5

1.1. Источники ошибок при вычислениях на ЭВМ. 5

1.2. Практическое вычисление функций. 8

1.3. Схема Горнера и метод Ньютона 10

1.4. Метод Бэрстоу. 17

1.5. Метод простых итераций. 18

1.6. Метод деления отрезка пополам (метод дихотомии). 20

1.7. Метод хорд. 21

Глава 2

Решение систем линейных уравнений 26

2.1. Метод Гаусса. 27

2.2. Метод итераций (Гаусса-Зейделя). 31

2.3. Метод LU преобразования. 32

2.4. Стандартные операторы МATLAB для решения

систем линейных алгебраических уравнений. 33

2.5. Решение систем нелинейных уравнений. 35

Глава 3.

Методы интерполяции. 38

3.1. Метод интерполяции Лагранжа. 39

3.2. Интерполяционные полиномы Эрмита 40

3.3. Интерполяционная формула Ньютона 41

3.4. Итерационно – интерполяционный метод Эйткена. 43

3.5. Полиномы Чебышева. 44

3.6 Сплайны. 44

Глава 4

Решение обыкновенных дифференциальных уравнений 47

4.1. Метод Эйлера. 48

4.2. Метод Эйлера усовершенствованный. 51

4.3. Метод Эйлера модифицированный 51

4.4. Оценки порядка точности методов Эйлера (Э),

Эйлера модифицированного (ЭМ) и Эйлера усовершенствованного (ЭУ). 52

4.5. Метод Рунге-Кутта 3^гопорядка 54

4.6. Метод Рунге-Кутта 4^гопорядка 54

4.7. Оценки точности методов Рунге-Кутта в процессе вычислений 54

4.8. Приведение систем дифференциальных уравнений к форме Коши 55

4.9. Краткий обзор методов интегрирования систем ОДУ с помощью

MATLAB 58

Глава 5.

Численная оптимизация. 60

5.1. Поиск экстремума функции одного переменного 60

5.2. Метод золотого сечения. 60

5.3. Метод квадратичной интерполяции. 62

5.4. Методы поиска экстремума функции многих переменных 65

5.5. Метод Нелдера-Мида. 65

5.6. Метод Хука-Дживса (Метод конфигураций). 69

5.7. Методы покоординатного спуска. 73

5.7.1. Метод покоординатного спуска (Гаусса – Зейделя) 73

5.7.2. Метод спирального покоординатного спуска. 74

5.8. Градиентные методы. 75