Алгоритм 1.5 (Алгоритм метода средней точки)

Шаг 1. Ввести исходные данные: a, b, e.

Шаг 2. Определить x0 = .

Шаг 3. Вычислить f '(x0).

Шаг 4. Проверить критерий окончания вычислений. Если êf '(x0) ê£ e,,перейти к шагу 6, иначе – к шагу 5.

Шаг 5. Перейти к новому отрезку локализации [a, b]. Если f '(x0) > 0, то положить b = x0. Иначе положить a = x0. Перейти к шагу 2.

Шаг 6. Положить x*» x0. Вычислить f'(x*).

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

 

 

Задание функции, реализующей метод средней точки с заданной точностью:

 

 

В результате решения данной задачи был найден минимум x* = -1, значение функции f(x*) = 0, количество итераций n = 14.

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

 

Найти минимум функции методом Ньютона с заданной точностью.

Пусть f(x) – дважды непрерывно дифференцируемая функция, причем

f ''(x) > 0. Тогда, как уже указывалось в предыдущем разделе, решение задачи минимизации функции f (x) сводится к решению нелинейного уравнения f '(x) = 0.

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

Пусть корень x* Î [a, b], так, что f '(a)f '(b) < 0. Положим x0 = b. Проведем касательную к графику функции y = f '(x) в точке B0 = (x0, f '(x0))

 

Рис. 1.5

 

Уравнение касательной будет иметь вид:

 

y – f '(x0) = f"(x0)(x – x0). (1.16)

 

Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью OX, т. е. положив в (1.16) y = 0, x = x1:

 

x1 = x0 – . (1.17)

Аналогично поступим с точкой B1(x1, f '(x1)), затем с точкой B2(x2, f '(x2)), и т. д. в результате получим последовательность приближений x1, x2, …, xn, …, причем

 

xn +1 = xn – . (1.18)

 

Формула (1.18) является расчетной формулой метода Ньютона.

При заданной точности e > 0 вычисления по формуле (1.18) нужно вести до

тех пор, пока не будет выполнено неравенство| f '(xn)| £ e, после чего полагают x*» xn.

Алгоритм 1.6 (Алгоритм метода Ньютона).

Шаг 1. Ввести исходные данные: a, b, e. Положить n = 0, x0 = b.

Шаг 2. Вычислить f '(xn) и f "(xn).

Шаг 3. Вычислить xn +1 = xn – .

Шаг 4. Проверить критерий окончания вычислений. Если êf '(x n +1) ê£ e,, перейти к шагу 6, иначе – к шагу 5.

Шаг 5. Положить n = n +1. Перейти к шагу 2.

Шаг 6. Положить x*» xn +1. Вычислить f'(x*).

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

 

 

Задание функции, реализующей метод Ньютона с заданной точностью:

 

 

В результате решения данной задачи был найден минимум x* = -1, значение функции f(x*) = 0, количество итераций n = 13.

Вывод

 

Таблица 1 Результаты нахождения минимума функции разными численными методами поиска

Метод	Значение аргумента	Значение функции	Количество итераций	Точность
Метод перебора	-1			0.045
Метод поразрядного поиска	-0.98
Метод деления отрезка пополам	-1
Метод Фибоначчи	-1
Метод золотого сечения	-1
Метод средней точки	-1
Метод Ньютона	-1

 

Вывод. Для решения данной задачи самыми эффективными являются Метод Фибоначчи, Метод деления отрезка пополам и Метод Ньютона.

 

 

Литература

 

Основная

1. Краснов, М.Л. Вся высшая математика. Т. 6. Вариационное исчисление, линейное программирование, вычислительная математика, теория сплайнов / М.Л. Краснов, А.И. Киселев, Г.И. Макаренко. - М.: КД Либроком, 2014. - 256 c.

2. Пантина, И.В. Вычислительная математика: Учебник / И.В. Пантина, А.В. Синчуков. - М.: МФПУ Синергия, 2012. - 176 c.

Дополнительная

 

1. Бахвалов Н.С и др. Численные методы. - М.: Физматлит,2000.
2. Азаров А.И. и др. Сборник по методам вычислений - М.: Наука, 1994.
3. Бахвалов Н. С. и др. Численные методы в задачах и примерах. - М.: Высшая школа, 2000.
4. Самарский А.А., Гулин А.В. Численные методы. - М.: Наука, 1989.