Контрольные вопросы
К каким одномерным функциям могут быть применены методы исключения интервала?
На какие этапы можно разбить процедуру поиска минимума функции методами исключения интервала?
Как влияет величина шага на результаты поиска границ интервала?
Каким образом осуществляется поиск граничных точек?
Опишите метод определения пробной точки по Свену.
Каким способом подбирается знак D величины шага?
От чего зависит эффективность поиска граничных точек? Как влияет
Что является исходными данными при решении задачи определения границ интервала поиска оптимума одномерной функции в среде MS EXCEL?
Какую логическую функцию используют в среде MS EXCEL для определения знака D при решении задачи определения границ интервала поиска оптимума одномерной функции?
Какая функция MS EXCEL может быть использована в качестве аргумента другой функции при решении задачи определения границ интервала поиска оптимума одномерной функции и как она называется?
Для чего используется индекс «х» в расчетном блоке при решении задачи определения границ интервала поиска оптимума одномерной функции в среде MS EXCEL?
Что является границами интервала поиска оптимума одномерной функции в среде MS EXCEL?
Практическое задание № 8. Определение оптимума одномерной функции. Методы исключения интервалов. Метод деления интервала пополам
Задание.
По варианту (табл. 8.1) найти минимум функции методом деления интервала пополам с заданной точностью λ.
Таблица 8.1
|
|
Сделать выводы.
Дополнительные необходимые исходные данные взять из табл. 7.1 (практическое задание № 7).
Решить задачу методом деления интервала пополам
Работа рассчитана на 2 аудиторных часа.
Элементы теории
Метод бисекции или метод деления отрезкапополам - простейшийчисленный методдля решениянелинейных уравненийвидаf(x) = 0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.
Дана некоторая функция f(x) от одной переменной x, надо определить такое значение x*, при котором функция f(x) принимает экстремальное значение6. В общем случае функция может иметь одну или несколько экстремальных точек. Нахождение этих точек с заданной точностью λ можно разбить на два этапа. Сначала по экстремальным точкам определяют отрезки, которые содержат по одной экстремальной точке, а затем уточняют до требуемой точности λ.
Отделение можно осуществить, как графически, так и табулированием. Все методы уточнения точек экстремумов можно рассматривать относительно уточнения минимума на заданном отрезке. Алгоритм основан на следующем следствии из теоремы Больцано-Коши:
пусть непрерывная функция f(x) Î С ([a, b]), тогда, если sign (f(a)) ≠ sign (f(b)), то C Î [a, b]: f(C) = 0.
Таким образом, если ищется ноль, то на концах отрезка функция должны быть противоположные знаки. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается.
Точность вычислений задаётся одним из двух способов:
λf(x) по оси y, что ближе к условию f(x) = 0 из описания алгоритма; или
λx, по оси x, что может оказаться удобным в некоторых случаях.
Процедуру следует продолжать до достижения заданной точности λ.
Задача заключается в нахождении корней нелинейного уравнения
f(x) = 0 (8.1)
Для начала итераций необходимо знать отрезок [x(L), x(R)] значений x, на концах которого функция принимает значения противоположных знаков.
Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения f(x(L)) и f(x(R)) путём сравнения результата с нулём:
f(x(L)) · f(x(R)) < 0. (8.2)
В действительных вычислениях такой способ проверки противоположности знаков при крутых функциях приводит к преждевременному переполнению.
Для устранения переполнения и уменьшения затрат времени, т.е. для увеличения быстродействия, на некоторых программно-компьютерных комплексах противоположность знаков значений функции на концах отрезка нужно определять по формуле:
sign (f(x(L))) ≠ sign f(x(R)), (8.3)
так как одна операция сравнения двух знаков двух чисел требует меньшего времени, чем две операции: умножение двух чисел (особенно с плавающей запятой и двойной длины) и сравнение результата с нулём. При данном сравнении, значения функции f(x) в точках x(L) и x(R) можно не вычислять, достаточно вычислить только знаки функции f(x) в этих точках, что требует меньшего машинного времени.
Из непрерывности функции f(x) и условия (8.3) следует, что на отрезке [x(L), x(R)] существует хотя бы один корень уравнения (в случае не монотонной функцииf(x) функция имеет несколько корней и метод приводит к нахождению одного из них).
Найдём значение х в середине отрезка:
x(M) = (x(L) + x(R))/2. (8.4)
В действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:
x(D) = x(R) - x(L), (8.5)
а в цикле вычисляют длину очередных новых отрезков по формуле:
x(D) = x(D) /2 (8.6)
и новую середину по формуле:
x(M) = (x(L) + x(D)). (8.7)
Вычислим значение функции f(x(M)) в середине отрезка x(M):
Если f(x(M)) = 0 или, в действительных вычислениях, ǀf(x(M))ǀ ≤ λf(x), где λf(x)— заданная точность по оси y, то корень найден.
Иначе f(x(M)) ≠ 0 или, в действительных вычислениях, ǀf(x(M))ǀ > λf(x), то разобьём отрезок [x(L), x(R)] на два равных отрезка: [x(L), x(M)] и [x(M), x(R)].
Теперь найдём новый отрезок, на котором функция меняет знак.
Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, f(x(L)) · f(x(M)) ˂ 0 или sign f(x(L)) ≠ sign f(x(M)), то, соответственно, корень находится внутри левого отрезка [x(L), x(M)]. Тогда возьмём левый отрезок присвоением x(R) = x(M), и повторим описанную процедуру до достижения требуемой точности λf(x)по оси y.
Если значения функции на концах отрезка имеют противоположные знаки на правом отрезке, f(x(M)) · f(x(R)) ˂ 0 или sign f(x(M)) ≠ sign f(x(R)), то, соответственно, корень находится внутри правого отрезка [x(M), x(R)]. Тогда возьмём правый отрезок присвоением x(L) = x(M), и повторим описанную процедуру до достижения требуемой точности λf(x) по оси y.
Итерации деления пополам осуществляется N раз, поэтому длина конечного отрезка в 2N раз меньше длины исходного отрезка.
Существует похожий метод, но с критерием остановки вычислений λ (х) по оси х. В этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси х: (x(R) - x(L)) > λ (х). В этом методе отрезок на оси x может достичь заданной величины λ (х), а значения функций f(x) (особенно крутых) на оси y могут очень далеко отстоять от нуля, при пологих же функциях f(x) этот метод приводит к большому числу лишних вычислений.
В дискретных функциях x(L), x(M) и x(R) - это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия остановка вычислений, разность (x(R) - x(L)) не может быть меньше λ (х) = 1.
Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.
После определения границ интервала можно приступать к уменьшению интервала поиска для получения уточненных оценок координат оптимума. Величина подынтервала, исключаемого на каждом шаге, зависит от расположения пробных точек х(1) и х(2) внутри интервала поиска. К методам исключения интервалов относятся метод деления интервала пополам и метод золотого сечения. Рассмотрим первый из них.
Метод деления интервала пополам позволяет исключить половину интервала на каждой итерации.
Основные шаги поисковой процедуры нахождения точки минимума в интервале (a, b):
Принимаем хm=(a + b)/2, L = b - a. Вычислить f(xm).
x1 = a + L/4; x2 = b - L/4. Вычислить f(x1) и f(x2).
Сравнить f(x1) и f(xm). Если f(x1) £ f(xm), исключить интервал (xm, b), положив b = xm. Средней точкой нового интервала поиска становится точка х1. xm = x1. Перейти к п.5. Если f(x1) ³ f(xm), перейти к п.4.
Сравнить f(x2) и f(xm). Если f(x2) £ f(xm), исключить интервал (a, xm), положив xm = a. x2 становится точкой xm. Средней точкой нового интервала становится точка x2. Перейти к п.5. Если f(x2) ³ f(xm), исключить интервалы (a, x1) и (х2, b), положив а = х1, b = x2. xm остается средней точкой нового интервала. Перейти к п.5.
Вычислить L = b - a. Если величина ½L½£ λ (λ – некоторое заданное значение точности), закончить поиск. В противном случае вернуться к п. 2.
Достоинства метода: простота и быстрое достижение результата.
Недостатки метода: необходимо заранее знать отрезок, на котором функция меняет знак. Это не совсем удобно.
Выполнение работы в среде MS EXCEL
Определив границы интервала поиска минимума функции, можно приступить собственно к определению минимума этой функции методами деления интервала пополам.
Исходными данными для определения минимума функции методом деления интервала пополам служат определенные интервалы поиска и заданное значение точности поиска λ.
Таблица расчетных данных должна содержать согласно алгоритму расчета графы расчета величин a, b, L, xm, x1, x2, f(xm), f(x1), f(x2). Для первой итерации формулы для расчета этих величин очевидны. На следующих итерациях трудность представляет только определение границ a и b, формулы для расчета остальных величин одни и те же для всех итераций. Во второй итерации необходимо внести такие формулы для расчета границ a и b, которые при копировании на все остальные итерации давали бы правильные значения границ в зависимости от значений функции в точках xm, x1, x2. Для этого также необходимо использовать логические функции. Расчет следует вести до тех пор, пока L не станет меньше λ.
Блок-схема алгоритма поиска корня уравнения f(x)=0 методом деления отрезка пополам
Пример выполнения представлен в табл. 8.2.
Таблица 8.2
f(x) = (100-x)2 λ = 0,1
|
Итерация |
a |
b |
L |
xm |
х(1) |
x(2) |
f(х(1)) |
f(x(m)) |
f(x(2)) |
|
1 |
65,000 |
185,000 |
120,000 |
125,000 |
95,000 |
155,000 |
25,000 |
625,000 |
3025,000 |
|
2 |
65,000 |
125,000 |
60,000 |
95,000 |
80,000 |
110,000 |
400,000 |
25,000 |
100,000 |
|
3 |
80,000 |
110,000 |
30,000 |
95,000 |
87,500 |
102,500 |
156,250 |
25,000 |
6,250 |
|
4 |
95,000 |
110,000 |
15,000 |
102,500 |
98,750 |
106,250 |
1,563 |
6,250 |
39,063 |
|
5 |
95,000 |
102,500 |
7,500 |
98,750 |
96,875 |
100,625 |
9,766 |
1,563 |
0,391 |
|
6 |
98,750 |
102,500 |
3,750 |
100,625 |
99,688 |
101,563 |
0,098 |
0,391 |
2,441 |
|
7 |
98,750 |
100,625 |
1,875 |
99,688 |
99,219 |
100,156 |
0,610 |
0,098 |
0,024 |
|
8 |
99,688 |
100,625 |
0,938 |
100,156 |
99,922 |
100,391 |
0,006 |
0,024 |
0,153 |
|
9 |
99,688 |
100,156 |
0,469 |
99,922 |
99,805 |
100,039 |
0,038 |
0,006 |
0,002 |
|
10 |
99,922 |
100,156 |
0,234 |
100,039 |
99,980 |
100,098 |
0,000 |
0,002 |
0,010 |
|
11 |
99,922 |
100,039 |
0,117 |
99,980 |
99,951 |
100,010 |
0,002 |
0,000 |
0,000 |
|
12 |
99,980 |
100,039 |
L<l |
|
|
|
|
|
|
Примеры программ, реализующих поиск корня уравнения
f(x) = 0 методом деления отрезка пополам (Basic, Pascal)
Basic
DECLARE FUNCTION F! (X!) REM ИСХОДНОЕ УРАВНЕНИЕ В ВИДЕ F(X)=0
CLS
INPUT "Введите границы интервала "; A, B
IF (F(A) * F(B)) > 0 THEN
SOUND 500, 5
PRINT "Ошибка! Функция не меняет знак на этом интервале!"
END
ELSE
INPUT "Задайте точность вычислений "; E
PRINT " X F(X) A F(A) B F(B)"
PRINT "------------------------------------------------"
DO WHILE (ABS(B - A) >= 2 * E)
X = (B + A) / 2
IF F(X) * F(A) > 0 THEN A = X ELSE B = X
PRINT USING "####.###"; X; F(X); A; F(A); B; F(B)
LOOP
END IF
PRINT "Корень уравнения ";
PRINT USING "####.###"; (B + A) / 2
END
FUNCTION F (X)
F = SIN(X) + COS(X) REM ИСХОДНОЕ УРАВНЕНИЕ В ВИДЕ F(X)=0
END FUNCTION
Pascal
Program Half;
Uses Crt;
Var
a,b,e,x: real;
Function f(x:real):real;
Begin
f:= sin(x)+cos(x);
End;
Begin
Clrscr;
Write('Введите границы интервала: ');
Readln(a,b);
if (f(a)*f(b)) > 0 then
Begin
Sound(220);
Delay(200);
NoSound;
Writeln('Ошибка! Функция не меняет знак на этом интервале!');
Writeln('Нажмите любую клавишу');
Readkey;
Halt;
End
else
Begin
Write('Задайте точность вычислений: ');
Readln(e);
Writeln;
Writeln(' X F(X) A F(A) B F(B)');
Writeln('------------------------------------------------');
While (Abs(b-a)>=2*e) do
Begin
x:=(b+a)/2;
if f(x)*f(a)>0 then a:=x else b:=x;
Writeln(x:8:3,f(x):8:3,a:8:3,f(a):8:3,b:8:3,f(b):8:3);
End;
End;
Writeln;
Writeln('Корень уравнения ',(B + A) / 2:4:2);
Writeln('Нажмите любую клавишу');
Readkey;
End.