Вычисление наибольшего (наименьшего) значения функции с заданной точностью на заданном интервале
Необходимость организации вложенного цикла возникает также и при решении задачи нахождения наибольшего (наименьшего) значения функции на заданном интервале с заданной точностью. Рассмотрим сначала задачу определения с заданной точностью аргумента, при котором функция достигает своего экстремального значения. Данная задача может быть сформулирована следующим образом. Задана некоторая функция f(x) и некоторый интервал [a,b]. Известно, что на заданном интервале функция имеет один экстремум, известен и вид экстремума (максимум или минимум). Требуется с заданной точностью ε найти значение аргумента, при котором достигается экстремум функции.
Решить поставленную задачу можно, используя прием программирования вычисление максимума или минимума. При этом шаг изменения аргумента следует задать равным требуемой точности ε. Однако такой подход может потребовать большого количества вычислений. Сократить количество выполняемых операций можно за счет использования следующего алгоритма. Сначала вычисляются значения функции при “грубом” значении шага изменения аргумента. При этом очередное значение функции сравнивается с ранее вычисленным максимальным значением (допустим, что определяется максимум функции) и если текущее значение превышает максимальное, т.е. f(xi)>fmax , то fmax := f(xi), и производится вычисление значения функции в следующей точке. Если же на очередном шаге выполнится условие f(xi)<fmax , то это будет означать, что максимум функции уже пройден, т.е. он находится на интервале (xi-2h, xi), где h – шаг изменения аргумента. В этом случае шаг изменения аргумента уменьшается (обычно в два раза) и на вновь полученном интервале вычисляются значения функции и ищется максимум при новом шаге изменения аргумента. Процесс продолжается до тех пор, пока h не станет меньше или равным ε.
Таким образом, во внутреннем цикле вычисляются значения функции и ищется максимум на заданном интервале изменения аргумента при заданном шаге изменения аргумента. Во внешнем цикле задается новый интервал поиска максимума и новый шаг изменения аргумента. Фрагмент программы вычисления максимума функции y=2x3 +10x2 +6x-20 в интервале [a,b] имеет вид:
//Вычисление максимума функции с использованием
//итерационного (вложенного) цикла
N2:=0; //Количество вычислений значения функции
ReadLn(A,B,Eps,H);
Xn:=A;
while H>Eps do
begin
I:=0;
//Установка начального значения для максимума
Ymax:=((2*Xn+10)*Xn+6)*Xn-20;
Xmax:=Xn;
//Цикл определения максимума функции
//на очередном интервале изменения аргумента
repeat
I:=I+1;
//Вычисление текущего значения аргумента
X:=Xn+(I-1)*H;
//Вычисление значения функции в очередной точке
Y:=((2*X+10)*X+6)*X-20;
N2:=N2+1;
//Определение нового максимума
//и соответствующего значения аргумента
if Y>Ymax then
begin
Ymax:=Y;
Xmax:=X;
end;
until (Y<Ymax);
//Определение левого конца нового интервала
//вычисления максимума
Xn:= Xmax-H;
//Уменьшение шага изменения аргумента в два раза
H:=H/2;
end;
Поиск минимума функции можно свести к поиску максимума, если функцию f(x) заменить функцией -f(x).
Рассматриваемую задачу можно обобщить на случай, когда функция может не иметь внутри заданного интервала экстремума, а изменяется внутри него монотонно, причем заранее характер поведения функции не известен. В этом случае следует говорить о нахождении наибольшего (наименьшего) значения функции на заданном интервале. Наибольшее (наименьшее) значение функции достигается либо в критической точке (где первая производная равна нулю), либо на конце интервала.
В этом случае в программу необходимо добавить проверку аргумента на принадлежность заданному интервалу. В случае отсутствия такой проверки аргумент может принимать значения, не принадлежащие заданному интервалу (если наибольшее значение достигается на левом конце интервала, то возможен выход аргумента за левую границу, если же оно достигается на правом конце интервала, то возможен выход аргумента за правый конец). В этом случае добавляется еще одно условие выхода из цикла и проверка нового значения для начального значения аргумента:
until (Y<Ymax)or(X>=B);
Xn:= Xmax-H;//Определение левой границы нового интервала
//вычисления наибольшего значения
if Xn<A then Xn:=A; //Проверка выхода нового значения аргумента
//за пределы заданного интервала
Если известны аналитические выражения для первой и второй производных, то можно найти значение аргумента, при котором первая производная обращается в ноль (решить уравнение, например, методом деления отрезка пополам) и определить знак второй производной в найденной точке. Знак второй производной позволит определить вид экстремума (максимум или минимум) или его отсутствие на заданном интервале. В случае отсутствия экстремума следует сделать запрос о нахождении наибольшего или наименьшего значения функции.
Пример программы вычисления наибольшего (наименьшего) значения функции приведен ниже. В программе реализованы три рассмотренных подхода к определению наибольшего (наименьшего) значения функции на заданном интервале. Программа позволяет также оценить трудоемкость последних двух способов на основе сравнения количества вычислений значений функции.
program Extremum;
{
Вычисление наибольшего(наименьшего) значения функции
y=2x3 +10x2 +6x-20 в интервале [a,b] с заданной точностью eps
с начальным шагом изменения аргумента h.
y’=6x2 +20x+6 - первая производная функции,
y’’=12x+20 - вторая производная
}
{$APPTYPE CONSOLE}
uses
SysUtils;
var
X,A,B,Aa,Bb,H,Y,Ymax,Ya,Yb,Ysr,Eps,Xmax,Dx,Xn,Xsr:Real;
I,N1,N2,K,Mon:Integer;
begin
WriteLn('Введите a,b,eps,h');
ReadLn(A,B,Eps,H);
Mon:=0; //Признак монотонности:0 – немонотонная;1-монотонная
//Определение точки на заданном интервале, в которой первая
//производная функции обращается в ноль (уточнение корня
//уравнения методом деления отрезка пополам)
Ya:= 6*A*A+20*A+6;
if Ya=0 then
Xmax:=A
else
begin
Yb:=6*B*B+20*B+6;
if Yb=0 then
Xmax:=B
else if Ya*Yb>0 then
begin
WriteLn ('Функция на заданном интервале изменяется'
+' монотонно');
WriteLn ('Для нахождения наибольшего значения введите 1,'
+' для наименьшего - -1');
ReadLn(K);
Mon:=1;
end
else
begin
Aa:=A;
Bb:=B;
Xsr:=(Aa+Bb)/2;
Ysr:= 6*Xsr*Xsr+20*Xsr+6;
while (Abs(Bb-Aa)>Eps)and(Ysr*Ya<>0) do
begin
if Ya*Ysr>0 then Aa:=Xsr else Bb:=Xsr;
Xsr:=(Aa+Bb)/2;
Ysr:= 6*Xsr*Xsr+20*Xsr+6;
end;
Xmax:=Xsr;
end;
end;
//Определение знака второй производной в критической точке
//с целью определения вида экстремума
//(вторая производная отрицательна – максимум,
//вторая производная положительна – минимум)
if Mon=0 then
begin
if 12*Xmax+20<0 then
K:=1
else
K:=-1;//Поиск минимума сводится к поиску максимума
//функции –f(x)
//Вычисление значения функции в критической точке
Ymax:=K*((2*Xmax+10)*Xmax+6)*Xmax-20;
case k of
1: WriteLn('ymax=',k*ymax:10:5,' xmax=',xmax:10:5);
-1: WriteLn('ymin=',k*ymax:10:5,' xmin=',xmax:10:5);
end;
ReadLn;
end;
//Поиск максимума функции с использованием табулирования
//значений функции при шаге изменения аргумента, равном
//требуемой точности
N1:=Trunc((B-A)/Eps)+1;
//Установка начального значения для максимума
Ymax:=((2*A+10)*A+6)*A-20;
Xmax:=A;
Dx:=Eps;
for I:=1 to N1-1 do
begin
X:=A+I*Dx;
Y:= K*(((2*X+10)*X+6)*X-20);
if Y>Ymax then
begin
Ymax:=Y;
Xmax:=X;
end;
end;
case k of
1: WriteLn('ymax=',k*ymax:10:5,' xmax=',xmax:10:5);
-1: WriteLn('ymin=',k*ymax:10:5,' xmin=',xmax:10:5);
end;
WriteLn('n1=',n1);
ReadLn;
//Вычисление наибольшего значения функции с использованием
//итерационного (вложенного) цикла
N2:=0; //Количество вычислений значения функции
Xn:=A;
while H>Eps do
begin
//Установка начального значения для наибольшего значения
Ymax:=K*((2*Xn+10)*Xn+6)*Xn-20;
Xmax:=Xn;
I:=0;
//Цикл определения наибольшего значения функции
//на очередном интервале изменения аргумента
repeat
I:=I+1;
X:=Xn+(I-1)*H; //Вычисление текущего значения аргумента
//Вычисление значения функции в очередной точке
Y:=K*(((2*X+10)*X+6)*X-20);
N2:=N2+1;
if Y>Ymax then
//Определение нового наибольшего значения и
//соответствующе го значения аргумента
begin
Ymax:=Y;
Xmax:=X;
end;
until (Y<Ymax)or(X>=B);
Xn:= Xmax-H; //Определение левой границы нового интервала
//вычисления наибольшего значения
//Проверка выхода аргумента за пределы интервала
if Xn<A then
Xn:=A;
H:=H/2; //Уменьшение шага изменения аргумента в два раза
end;
case k of
1: WriteLn('ymax=',k*ymax:10:5,' xmax=',xmax:10:5);
-1: WriteLn('ymin=',k*ymax:10:5,' xmin=',xmax:10:5);
end;
WriteLn('n1=',n1);
ReadLn;
end.