Материал: 5544

X 1 . В точке X 1 1,2; 0,533 значения функций

F X 1 1,2 0,533 2 1,2 3 0,533 4 0,640, G X 1 1,22 0,533 5 1,2 6 0,768 ,

а значения производных

Здесь Dx , Dy и D найдены по указанным выше общим формулам. При при-

менении пакета Excel достаточно использовать ссылки на нужные значения

На 4-м шаге x 0,001 0,01 и y 0,003 0,01 , вычисления законче-

ны. Действительно, добавив эти величины к прежним значениям x, y , получаем x 1, y 1 , для которых F 0 и G 0 , а именно это нам и требуется. Попытка пересчитать x, y приводит к тем же самым значениям.

Ответ: с точностью 0,001 решение системы – x 1, y 1 .

Замечание 1. Из схемы следует, что для сходимости метода Ньютона нужно, чтобы ни на каком шаге решения определитель матрицы частных производных не обратился в 0.

Если определитель не обращается тождественно в 0 в каждой точке (тогда задачу вообще решить невозможно), то определить по первоначальному приближению, выполнено ли условие сходимости, весьма сложно, и этот вопрос выходит за рамки пособия. При решении в пакете Excel достаточно поменять начальное приближение.

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

Замечание 3. При решении упрощённым методом Ньютона можно не пересчитывать частные производные и использовать те, что получены на 1-м шаге (тогда матрица соответствующей системы относительно i не изменяется). Схо-

димость при этом может существенно замедлиться.

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

Известно, что функция, непрерывная на отрезке, достигает на нём наименьшего и наибольшего значения либо на концах отрезка, либо в критических точ-

47

ках, где производная равна 0 или не существует. Отсюда следует простая схема поиска наименьшего и наибольшего значения функции f(x) на отрезке:

1) найти производную f x ;

2) найти с её помощью критические точки; 3) найти значения функции на концах отрезка и в критических точках, вхо-

дящих в отрезок; 4) выбрать самое большое и самое малое значения.

В этой схеме наиболее сложен 2-й пункт. По общей схеме можно найти корни только у простейших производных. В других случаях поиск критических точек возможен лишь приближённо, и точное решение всей задачи теряет смысл.

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

Поиск экстремума приближёнными методами похож на решение уравнения методом деления отрезка.

Пусть необходимо найти точку глобального минимума функции f(x) и известно, что она находится на отрезке [a, d]. Разделим отрезок на 3 части точками b, c так, чтобы a b c d и найдём значения f a , f b .

Пусть f b f c . Если функция не слишком «необычна», можно ожидать, что при движении слева к точке c функция возрастает. Тогда маловероятно, что точка минимума находится правее точки c, т.е. на участке [c, d], поэтому участок [c, d] можно исключить из рассмотрения. Скорее всего, точка минимума находится на промежутке [a, c], и именно на нём будем её искать дальше.

Наоборот, если f b f c , то, независимо от значений на концах отрезка, точка минимума должна быть на [b, d], но не на [a, b], и из рассмотрения можно исключить участок [a, b]. Скорее всего, на нём функция или всё время убывает, или возрастает до максимума и потом убывает.

В любом случае отсекая ненужный участок, получаем уменьшенный отрезок – либо [a, c], либо [b, d]. Переобозначив его как [a, d], снова делим на 3 части точками b, c и повторяем рассуждения.

Действуя так много раз, получим малый отрезок, длина которого будет меньше допустимой погрешности. Тогда любая точка такого отрезка может считаться точкой минимума (обычно берут середину отрезка).

Если же на отрезке [a, d] нет локального минимума, то произойдёт движение к концу отрезка, в котором значение функции меньше: к точке a, если

48

f a f d , или к точке b, если f a f d . Будет получено наименьшее значение, не являющееся локальным минимумом (глобальный минимум).

Общая схема метода

Даны отрезок [a, d] и f x . Надо найти точку глобального минимума xmin

сточностью .

1)Найдём b a d a / 3 и c a 2 d a / 3 .

dd .

4)Переходим к п.1.

Здесь равенства подразумеваются как операторы присваивания.

Если поменять всюду знаки неравенств, то в процессе вычислений придём к точке максимума xmax . В случае f b f c можно оставить любую часть – или

[a, c], или [b, d]. Для компьютера числа с плавающей запятой типа REAL никогда не равны, и результат выбора будет случаен.

Метод прост, но сходится очень медленно – ещё медленнее, чем метод деле-

где d a – длина начального отрезка.

Пример. Найдём с точностью 0,1 точку глобального минимума функции f x x2 x на отрезке 0; 1 . Вычисления проведём с одной запасной цифрой.

1-й шаг. Длина отрезка 0; 1 равна 1, треть длины равна 1/3. Отрезок делится на три части точками a 0, b 0,33, c 0,67, d 1 .

Находим f 0,33 0,332 0,33 0,22 и f 0,67 0,672 0,67 0,22 .

Поскольку f 0,33 f 0,67 , можно взять как 0; 0,67 , так и 0,33; 1 .

2-й шаг. Возьмём отрезок 0; 0,67 . Треть его длины равна 0,22, поэтому те-

Поскольку f 0,22 f 0,44 , оставляем участок 0,22; 0,67 как новый отрезок.

Поскольку f 0,47 f 0,57 , считаем, что xmin 0,47 0,5 . Ответ: xmin 0,5 с точностью 0,1.

Легко видеть, что точка x = 0,5 – точное решение задачи как вершина параболы y x 2 x . Поэтому при выборе xmin 0,47 или xmin 0,57 результат был бы только хуже.

Схема неудобна тем, что каждый раз приходится искать 2 новые точки и 2 новых значения функции. Оказывается, если делить отрезок не на равные части, а в отношении 0,382 : 0,236 : 0,382, то при удалении участка [c, d] бывшая точка b на следующем шаге всегда будет становиться точкой c.

Наоборот, бывшая точка c станет точкой b, если удалить участок [a, b]. Тогда достаточно найти точку на расстоянии 0,382(d–a) от a или от d соответственно и найти значение функции в этой точке, а потом сравнить со значением, уже известным из предыдущего шага.

Указанное свойство объясняется тем, что точка b делит отрезок [a, c] в той же пропорции, что точка c – отрезок [a, d], а именно в отношении 0,5 5 1 0,618 . Такая пропорция называется "золотым сечением". Таким образом можно примерно в 2 раза ускорить вычисления, хотя число шагов почти не уменьшается. Уменьшается же число действий на каждом шаге. Для достижения точности

Общая схема метода золотого сечения

Даны отрезок [a, d] и f x . По-прежнему ищем точку глобального минимума xmin с точностью .

50