Северин В.П. Методы ОП

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

стимой погрешности.

А л г о р и т м м е т о д а Н ь ю т о н а - Р а ф с о н а .

4.7. Сравнение методов аппроксимации и интерполяции

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

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

ине использующие значений ее производных.

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

3.Метод второго порядка. Это один только метод Ньютона-

101

Рафсона, использующий значения первой и второй производных целевой функции.

Эти методы одномерного поиска можно сравнить по скорости сходимости. Методы одномерного поиска должны порождать последовательность точек {xk } , для которой

lim xk x .

k

Тогда по свойству предела

поэтому выполняется неравенство

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

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

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

Поведение последовательности точек {xk } в окрестности опти-

мальной точки x позволяет установить характер асимптотической сходимости. Если выполняется неравенство

102

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

Если выполняется неравенство

то говорят, что имеет место сверхлинейная сходимость. При этом, если существует такое 1 , что

то говорят, что имеет место сходимость порядка . В частности, если

то говорят, что имеет место квадратичная сходимость.

Метод квадратичной интерполяции нулевого порядка с тремя

рядка и f (x ) 0 , f (x ) 0 .

Метод секущих первого порядка с двумя точками имеет сверхли-

Метод кубической интерполяции первого порядка с двумя точками и метод Ньютона-Рафсона имеют квадратичную скорость сходимо-

сти, если f (x) дважды непрерывно дифференцируема и f (x ) 0 ,

103

f (x ) 0 .

Следовательно, в малой окрестности оптимальной точки метод кубической интерполяции с двумя точками и метод Ньютона-Рафсона при указанных предположениях относительно целевой функции f (x) сходятся быстрее остальных методов.

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

Лабораторная работа

Т е м а л а б о р а т о р н о й р а б о т ы .

Разработка подпрограммы для метода аппроксимации и интерполяции.

Ц е л ь л а б о р а т о р н о й р а б о т ы .

Разработать подпрограмму метода аппроксимации и интерполяции для минимизации унимодальной целевой функции.

П о р я д о к в ы п о л н е н и я л а б о р а т о р н о й р а б о т ы .

1.Получить у преподавателя задание на программирование одного из методов аппроксимации и интерполяции:

1) метод квадратичной интерполяции с тремя точками;

2) метод кубической интерполяции с четырьмя точками;

3) метод квадратичной интерполяции с двумя точками;

4) метод секущих;

5) метод кубической интерполяции с двумя точками;

6) метод Ньютона-Рафсона.

2.На основании алгоритма для заданного метода аппроксимации

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

1) входные параметры подпрограммы: f (x) – целевая функция,

104

5)после окончания процесса оптимизации на экране должна отображаться таблица, имеющая соответствующий заголовок и представляющая процесс минимизации функции;

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

3. Написать общую программу для выполнения вычислительного процесса минимизации целевой функции одной переменной и отображения на экране этого процесса в соответствии с требованиями:

1)за основу общей программы для минимизации функции взять общую программу из предыдущей лабораторной работы и модифицировать эту программу;

2)задать в программе значения x0 , x , h , , N ;

3)путем вызова подпрограммы метода Свенна с использованием подпрограммы вычисления функции f (x) и значений x0 , h , N вы-

полнить итерационный процесс поиска интервала неопределенности с построением таблицы процесса на экране и получением массивов значений переменной X и функции F , границ интервала неопределенности a и b , значений функции на концах интервала fa и fb , внут-

105

ренней точки интервала c и значения в ней функции fc ;

4) путем вызова разработанной подпрограммы метода аппроксимации и интерполяции реализовать итерационный процесс минимизации функции с построением таблицы процесса на экране и получением массивов значений переменной X и функции F , лучшей точки поиска x и значения в ней функции f x ;

5) с помощью подпрограммы графического отображения итерационного процесса по массивам X и F отобразить график процесса минимизации целевой функции одной переменной на экране компьютера.

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

5. Выполнить анализ полученных результатов:

1)на основании табличной и графической информации о работе методов одномерного поиска определить конечные точки метода Свенна и показать найденный этим методом интервал неопределенности;

2)на нескольких начальных итерациях по табличным данным и графикам сопоставить начало работы метода аппроксимации и интерполяции с его рабочими формулами;

3)оценить эффективность метода аппроксимации и интерполяции

исопоставить ее эффективностью метода уменьшения интервала неопределенности из предыдущей лабораторной работы.

6. Ответить на вопросы преподавателя по теме лабораторной работы.

7. Оформить и сдать отчет о проведенной лабораторной работе.

106

С о д е р ж а н и е о т ч е т а .

1)титульный лист установленного образца с указанием организации, названия учебной дисциплины, темы работы, номера варианта, исполнителя и принимающего, города, года;

2)постановка задачи минимизации целевой функции, включающая задание функции, начальную точку и точку минимума;

3)теоретическое описание метода аппроксимации и интерполя-

ции;

4)алгоритм метода;

5)распечатки используемых компьютерных программ;

6)табличное представление процесса минимизации и его итоги – количество вычислений значений целевой функции, минимальное значение функции и соответствующее ему значение точки минимума, достигнутую точность;

7)двумерный график траектории поиска со всеми точками;

8)анализ полученных результатов;

9)выводы о проделанной лабораторной работе.

Контрольные вопросы

1.Какое назначение метода квадратичной интерполяции с тремя точками?

2.Опишите метод квадратичной интерполяции с тремя точками.

3.Как начинается поиск минимума в методе квадратичной интерполяции с тремя точками?

4.Какого порядка метод квадратичной интерполяции с тремя точ-

ками?

5.Какие преимущества и недостатки метода квадратичной интерполяции с тремя точками?

6.Какое назначение метода кубической интерполяции с четырьмя точками?

7.Опишите метод кубической интерполяции с четырьмя точками.

8.Как начинается поиск минимума в методе кубической интерпо-

107

ляции с четырьмя точками?

9.Какого порядка метод кубической интерполяции с четырьмя точками?

10.Какие преимущества и недостатки метода кубической интерполяции с четырьмя точками?

11.Какое назначение метода квадратичной интерполяции с двумя точками?

12.Опишите метод квадратичной интерполяции с двумя точками.

13.Какие преимущества и недостатки метода квадратичной интерполяции с двумя точками?

14.Какое назначение метода секущих?

15.Опишите метод секущих.

16.Какого порядка метод секущих?

17.Какие преимущества и недостатки метода секущих?

18.Какое назначение метода кубической интерполяции с двумя точками?

19.Опишите метод кубической интерполяции с двумя точками.

20.Какие преимущества и недостатки метода кубической интерполяции с двумя точками?

21.Какое назначение метода Ньютона-Рафсона?

22.Выведите итерационную формулу метода Ньютона-Рафсона.

23.Опишите метод Ньютона-Рафсона.

24.Какого порядка метод Ньютона-Рафсона?

25.Какие преимущества и недостатки метода Ньютона-Рафсона?

26.На какие группы можно разделить методы аппроксимации и интерполяции?

27.Дайте определение глобальной сходимости метода одномерного поиска.

28.Дайте определение асимптотической сходимости метода одномерного поиска.

29.Как определяется линейная сходимость метода одномерного

поиска?

30.Приведите примеры методов одномерного поиска, обладаю-

108

щих свойством линейной сходимости?

31.Как определяется сверхлинейная сходимость метода одномерного поиска?

32.Приведите примеры методов одномерного поиска, обладающих свойством сверхлинейной сходимости?

33.Как определяется квадратичная сходимость метода одномерного поиска?

34.Приведите примеры методов одномерного поиска, обладающих свойством квадратичной сходимости?

35.Чем определяется выбор метода одномерного поиска для решения конкретной задачи оптимизации?

109