Файл: Численные методы и математическое моделирование.pdf

32
Оставшиеся ячейки второй строки заполняются формулами из первой и потом вторая строка копируется вниз по таблице, пока в столбце «
Ошибка
» не будет достигнута заданная точность реше- ния. Результат расчёта показан на рис. 34
Рис. 34. Расчётная таблица метода деления отрезка пополам.
Обычно процедура нахождения корня является промежуточ- ной и ходе решения задачи, поэтому иногда бывает полезно со- здать её, как функцию пользователя в среде VBA. Подробно об этом можно прочесть в [1].
К следующей группе задач можно отнести нахождение экстре- мумов функций.
Нахождение экстремумов функций
Основные понятия
Экстремумами уравнения являются его точки, в которых зна- чения функции принимают максимальные или минимальные зна- чения. Экстремумы могут быть локальными (их может быть не- сколько) и глобальным (их не более двух – один из них максимум, а другой – минимум). Они являются самыми большими среди максимумов или минимумов функции. Примеры экстремумов по- казаны на рис. 35. Здесь имеются два минимума (Х
э1
и Х
э3
), при-

33 чём первый из них локальный, а второй – глобальный. Если пред- положить, что дальше экстремумов больше не будет, Х
э2
является максимумом функции.
Для нахождения экстрему- мов существуют аналитические и приближенные методы. Пер- вые из них требуют знания про- изводной данного уравнения с последующим нахождением её корня – точки, в которой произ- водная превращается в нуль, яв- ляется экстремумом функции.
Исключениями могут быть функции с перегибами, но для них имеет место сохранение знака производной до и после точки с нулевым значением.
Численные методы позволяют находить экстремумы для лю- бых уравнений с заданной точностью, они не требуют вычисле- ния производных и позволяют находить экстремумы, которые ло- кализованы в определённом интервале, но они требуют большого объёма вычислений. Развитие вычислительной техники позво- лило в настоящее время широко использовать последние методы.
Уравнения могут содержать несколько экстремальных точек, которые должны быть локализованы интервалами поиска. Ясно, что в точке экстремума производная превращается в нуль, а слева и справа от неё производные имеют различные знаки. Пользуясь этими условиями, мы может локализовать все возможные экстре- мумы функции.
Как обычно реализуются численные методы поиска экстре- мума, рассмотрим на графике, показанном на рис. 36. Задаём ин- тервал поиска от Х
лев
до Х
пр
, содержащий искомую точку экстре- мума, и начинаем его уменьшать. Но нам надо знать, в каком из новых интервалов находится экстремум. Для этого мы вычисляем не одно, а два значения функции и принимаем, что нужный нам интервал находится вокруг большей из этих точек (см. точка Х
1
Y
X
0
X
э2
X
э1
X
э3
Рис. 35. Примеры экстремумов.

34 на рис. 36), т.е. он должен быть взят от границы (Х
лев
) через мак- симальную точку (Х
1
) до второй вычисленной точки (Х
2
). Ин- тервал от Х
2
до Х
пр
отбрасываем.
Данную процедуру по- вторяем до тех пор, пока расстояние между Х
пр
и Х
лев
не станет меньше заданной погрешности вычисления.
Ответом будет одна из двух средних точек, имею- щая максимальное значе- ние. Остаётся последний вопрос: как выбирать точки для вычисления но- вых значений?
Жела- тельно, чтобы на каждом следующем шаге необходимо было бы вычислять только одно значение функции. Для этого предлагаются два метода: метод зо- лотого сечения и метод чисел Фибоначчи.
Возникает вопрос можно ли совместить алгоритмы поиска максимума, как мы только что рассмотрели, с поиском минимума.
Если посмотреть на график (рис. 35.), то можем сделать заключе- ние, что любой минимум можно превратить в максимум функции умножением на –1. Следовательно, для реализации поиска макси- мума или минимума функции можем использовать одну про- грамму, но при вычислении функции необходимо умножать ре- зультат на соответствующий множитель: 1 – для поиска макси- мума и (–1) – для поиска минимума.
Реализация решений поиска экстремумов в Excel
Сначала рассмотрим конечно-разностный метод поиска экс- тремума, показанный на рис. 36. Как видим из рисунка для выбора интервала с экстремумом внутри надо задать две точки и их ме- стоположения будет определять эффективность метода решения.
Y
X
0
X
лев
X
пр
X
1
X
2
Рис. 36. Поиск экстремума методом золотого сечения

35
С одной стороны, мы можем обеспечить максимальную скорость сходимости решения, когда на каждом шаге будет отбрасываться максимальный интервал, который в лучшем случае может обес- печить размер в половину заданного интервала поиска, что имело место в реализации метода деления отрезка пополам. С другой можно экономит число вычислений функции, стараясь каждый раз сохранять одно из имеющихся значений. В этом случае мы приходим к одному из двух методов: «Метод золотого сечения» или «метод чисел Фибоначчи».
Метод золотого сечения
Рассмотрим первый из них, так как второй требует создания ряда Фибоначчи.
Понятие золотого сечения предполагает, что отрезок А отно- сится к его части В, как В относится к оставшейся части первона- чального отрезка С=А-В (рис. 37). Для простоты расчёта примем, что отношение для точки Х
1
равно 0,39 от А, а для точки Х
2
– 0.61.
Алгоритм решения данной задачи показа на рис. 38.
На первом шаге задаём функцию, экстремум которой надо найти, интервал поиска и точность решения задачи.
Затем вычисляем вспомогательные точки (Х
1
, Y
1
) и (Х
2
, Y
2
), по- сле этого проверяем наличие экстре- мума в заданном интервале. Предвари- тельно надо решить, что ищем макси- мум или минимум и отсюда прини- маем нужную формулу для проверки, например, для поиска максимума фор- мула имеет вид:
((Y
L
<Y
1
) and (Y
R
<Y
1
)) and ((Y
L
<Y
2
) and
(Y
R
<Y
2
)) хотя в случае очень близкого располо- жения экстремума к одной из границ интервала данное условие не сработает и проверять лучше через производные на границах интервала.
Рис. 37. Схема деления
X
1
X
л
X
2
X
пр
А
В
В
С
С

36
При наличии экстремума реализуем процедуру его поиска, так как приняли решение поиска максимума, то выбираем новый ин- тервал тот, где остаётся максимальное значение из двух промежу- точных точек, например, если Y
1
больше Y
2
то новый интервал бе- рётся от X
L
до X
2
и наоборот в случаем максимума в Y
2
, то интер- вал от X
1
до X
R
Рис. 38. Алгоритм метода золотого сечения
При смене интервала важен порядок переопределения пере- менных, например, если Y
1
>Y
2
то сначала переопределяем X
R
рав- ное X
2
, потом X
2
приравнивается X
1
и Y
2
=Y
1
и в конце вычисля- ются новые значения для X
1
и Y
1
, а иначе переопределение начи- нается с X
L
до вычисления новых значений X
2
и Y
2
После изменения границ интервала проверяется достижение

37 заданной точности, пока точность не достигнута процедура изме- нения интервала продолжается. По достижению заданной точно- сти определяется максимальное значение из двух имеющихся, ко- торое и является ответом.
Реализуем это решение на листе Excel. Для расчёта нам надо иметь четыре пары ячеек в столбцах (левая граница, первая точка, вторая точка и правая граница). Данная струк- тура подобна листу метода деления отрезка по- полам, поэтому копируем этот лист и встав- ляем два столбца, после точки «
Середина
». Для этого выделяем два столбца (рис. 39) и выпол- няем команду «
Главная
» – «
Вставить
». Выделяем четыре ячейки от заголовка «
Середина
» до «Y» на следующей строке и копируем на следую- щие два столбца. Потом исправляем заголовок листа на «
Метод зо- лотого сечения
» и заголовки столбцов «
Середина
» на «
Первая точка
» и
«
Вторая точка
». Получаем заготовку таблицы (рис. 40).
Рис. 40. Заготовка для решения методом золотого сечения
Переходим к заполнению самой таблицы. В качестве исследу- емой функции используем Y = 30 – 0,8*Х
2
+ 5*Ln(Х
3
). Вносим это уравнение во все столбцы «
Y
». «
Х
» для «
Первой точки
» вычисляем по формуле: =X
L
+0,39*(X
R
-X
L
), а для «
Второй точки
» по формуле:
=X
L
+0,39*(X
R
-X
L
). Исправляем формулы для вычисления «
Х
» во второй строке таблицы на границах интервала на следующие:
=Если(Y
1
>Y
2
;X
L
;X
1
) и =Если(Y
1
>Y
2
;X
2
;X
R
), соответственно для ле- вой и правой границ. Остаётся скопировать оставшиеся ячейки из первой строки и потом скопировать всю вторую строку вниз по листу, пока на будет достигнута необходимая точность решения.
Результат расчёта показан на рис. 41.
В данном случая порядок всех вычислений Excel выполнил сам, а если будет стоять задача создания отдельной программы,
Рис. 39. Вставка столбцов

38 то выполнение порядка расчёта переменных при смене интервала будет лежать на вас.
Рис. 41. Результаты расчёта методом золотого сечения
Воспользуемся созданной подпрограммой для вычисления производной в заданной точке и с её помощью найдём экстремум нашей функции. Для нахождения точки корня производной ис- пользуем команду Excel «Подбор параметра» на ленте «Данные» в разделе «Анализ что-если?».
На листе с результатами расчёта экс- тремума методом золотого сечения справа от основной таблицы создадим за- готовку для расчёта (рис. 42). В ячейки под заголовками столбцов внесём необходимые данные: в Х – начальное приближение для по- иска; Y=F(X) – функция, экстре- мум которой ищем, в данном слу- чае это
=My_Fun01(K3)
, dY – подпро- грамма для вычисления произ- водной от заданной функции
=Diff_Ur(K3;"My_Fun01")
Все готово для реализации ре- шения, встаём в ячейку с произ- водной и вызываем команду «
Под- бор параметра
» (рис. 43).
Рис. 42. Заготовка для решения
Рис. 43. Окно команды «Под- бор параметра»

39
В поле «
Значение
» указываем 0 и в поле «
Изменяя значение ячейки
» ставим ссылку на ячейку Х. Нажимаем кнопку «
Ok
» и получаем ответ, который совпадает с полученным ранее.
Однако чаще требуется найти экстремум многомерной функ- ции, сто требует использования других методов.
Поиск экстремумов многомерных функций
Все методы поиска экстремумов можно разделить на три группы:
- покоординатного поиска или подъёма;
- градиентного поиска;
- с использованием специальных функций и приёмов.
Рассмотрим их более подробно. В качестве исследуемой функ- ции используем 2-х параметрический полином, который задаём следующим набором коэф- фициентов (рис. 44). Его графический вид показан на рис. 45. Порядок по- строения данной диа- граммы показан в приложении 1.
Для удобства наблюдения за траекторией по- иска будем ис- пользовать поле изолиний (рис.
46) на которое наложим точеч- ный график с теми же коорди- натами по Х
1
и
Х
2
Рис. 44. Коэффициенты полинома
Рис. 45. Изометрия полиномиального уравнения

40
Прежде чем переходить к самим методам рассмотрим постро- ение такого графика. На основании тех же данных, по которым построена изометрия (рис. 45) строим график «
Поверхность
» – «
Про- волочная контурная
» и настраиваем подписи осей и их разметку, де- лаем график максимального размера на листе и с достаточным числом изолиний, которые задаются в формате вертикальной оси
(рис. 46)

41
Продолжаем движе- ние по Х
2
, снова дости- гаем максимального значения и проверяем его двумя шагами да- лее. Теперь меняем ко- ординату на X
1
и умень- шаем шаг в два раза.
Достигнув области экс- тремума получаем си- туацию, что каждый шаг приводит к умень- шению Y, поэтому идёт уменьшение шага до за- данной погрешности или некоторого смещения к экстремуму.
Для ускорения поиска можно воспользоваться уже созданной процедурой поиска экстремума однопараметрической функции, например, через производные (см. рис. 43).
Реализуем данный метод покоординатного спуска с поиском экстремума функции по одному из параметров. Для этого на листе создадим новую таблицу и заполним её необходимыми данными для начальной точки и поиска первого экстремума (рис. 48).
Таблица включает в себя па- раметры X
1
, X
2
, которые для первой точки вводим (что отме- чено цветом ячеек). Саму функцию Y=F(X
1
, X
2
), экстремум кото- рой мы ищем. В нашем случае это полином Y = A
0
+ A
1
*X
1
+ A
2
*X
2
+ A
11
*X
1
^2 + A
12
*X
1
*X
2
+ A
22
*X
2
^2 с коэффициентами, представ- ленными на рис. 44. Производные по каждому из параметров, находим простым дифференцированием этого уравнения по Х
1
и
Х
2
соответственно: dY(X
1
) = A
1
+ 2*A
11
*X
1
+ A
12
*X
2
и dY(X
2
) = A
2
+ A
12
*X
1
+ 2*A
22
*X
2
Рис. 47. Метод покоординатного спуска
Рис. 48. Заготовка таблицы

42
Вторую строку таблицы просто копируем с первой и используя команду подбора параметра ищем значение X
1
при котором произ- водная от данного параметра пре- вращается в нуль (рис. 49). Нажи- маем кнопку «
Ok
» и получаем от- вет, копируем вторую строку вниз и повторяем поиск нуля для вто- рой производной изменяя второй параметр Х
2
. Процедуру повто- ряем пока изменения входных па- раметров не станут малозначи- мыми. Результат поиска и его траектория показаны на рис. 50.
Рис. 50. Таблица поиска экстремума и его траектория.
Как видим решение становится более компактным, но требует вычисления частных производных для поиска локальных экстре- мумов вдоль выбранного сечения.
Если есть возможность вычислять производные, то можно вос- пользоваться методом градиентного поиска экстремума.
Рис. 49. Поиск корня произ- водной от Х1