Тема «Многомерные методы оптимизации: метод покоординатного спуска. Многомерные методы оптимизации: метод наискорейшего спуска»

Наряду с методом половинного деления существует более сложные и более эффективные итерационные методы. Рассмотрим два метода, связанные с именем Ньютона: метод хорд и метод касательных.

Пусть дано уравнение f(x)=0, корень находится на отрезке [а;b]. Идея метода хорд состоит в том, что на достаточно малом промежутке [а;b] дуга кривой y=f(x) заменяется стягивающей её хордой. В качестве приближенного значения корня принимается точка пересечения хорды с осью Ох.

Рассмотрим случай, когда производные имеют одинаковые знаки

f ‘ (x)×f » (x)>0

Пусть дано уравнение y(x)=0, где f(x) – непрерывная функция, имеющая в интервале (а, b) производные первого и второго порядка.

Корень считается отделенным и находится на [а, b], то есть f(a)×f(b) <0

Рассмотрим случай, когда производные имеют разные знаки f ‘ (x)×f » (x) <0

Вычисления удобно производить в таблице:

Геометрический смысл метода Ньютона состоит в том, что дуга кривой y=f(x) заменяется касательной к этой кривой.

Если касательную провести в точке В, то она пересечет Ох в точке, не принадлежащей отрезку [а;b]. Поэтому проведём касательную к кривой y=f(x) в точке А.

y-f(a)=f ‘ (a)(x-a)

Получаем последовательность приближений х₁ х₂, …, х_n, каждый последующий член ближе к корню ξ.

Сравнивая формулы, получаем, что они отличаются только выбором начального приближения.

Правило: за исходную точку следует выбирать тот конец отрезка [а;b] в котором знак функции совпадает со знаком второй производной

1) f(b)- f »(х)>0, следовательно x₀=b

2) f(a)- f »(х)>0, следовательно х₀=а

Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто применяют в сочетании друг с другом, и уточнение корня происходит быстрее.

Если f ‘ (x) f » (х)>0, то метод хорд дает приближения корня с недостатком, а метод касательных- с избытком.

Если f ‘ (x)> f » (х)<0, то методом хорд получаем значение корня с избытком, а методом касательных — с недостатком.

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

Вычисления следует вести в таком порядке:

1) Если f ‘ (x)× f » (х)>0 то со стороны конца а лежат приближенные значения корня, полученные по методу хорд, а со стороны конца b — значения, полученные по методу касательных и тогда