Метод Ньютона

Метод Ньютона применим к решению очень широкого класса нелинейных уравнений. Значение его в том, что он позволяет привести решение нелинейного уравнения к решению последовательности линейных уравнений.

Рассмотрим уравнение . Пусть- точное решение;- приближенное решение. Очевидно погрешность решения, и как правило это малая величина.

,

, разложим левую часть по степеням .

,

решая это уравнение относительно , найдем приближенное значение погрешностии сможем улучшить значение:, относительно которого можно ожидать, что оно будет ближе к, чем:

Аналогично можно улучшить и т.д.

[24]

Чтобы последовательные приближения сходились, необходимо чтобы .

Геометрический смысл правила [24] весьма прост. Построим график функции . Точное решениеэто абсцисса точки пересечения графика с осью ОТ. Рассмотрим на этом графике произвольную точкуи проведем в ней касательную. Уравнение касательной есть

.

Касательная пересечет ось ОТ в точке (t_i+1,0), или из уравнения касательной . Откуда найдем, что совпадает с [23]. Таким образом, правило Ньютона геометрически означает, что следующее приближение находится, если функцию заменить прямой, касающейся графика в точке.

Пример. Решить уравнение Кеплера методом Ньютона.

выберем t₀=1.2, тогда

ПОИСК МИНИМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

Функция имеет локальный минимумна множестве, если для всех значенийверно.

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

Метод золотого сечения

Пусть кусочно-непрерывна на отрезкеи имеет на нем только один локальный минимум. Построим итерационный процесс, сходящийся к этому минимуму.

Вычислим функцию на концах отрезка и в двух внутренних точкахи. Сравним все 4 значения функциимежду собой и выберем среди них наименьшее. Пусть наименьшим оказалось. Очевидно, минимум расположен в одном из прилегающих к нему отрезков. Поэтому отрезокможно отбросить. Первый шаг процесса приближений сделан.

На отрезке снова надо выбрать две внутренние точки и вычислить в них и на концах отрезка значения функции, и сделать следующий шаг процесса. Но на предыдущем шаге вычислений мы уже нашлина концах нового отрезкаи в одной его внутренней точке. Поэтому достаточно выбрать внутриеще одну точку, определить в ней значение функции и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений на одном шаге процесса.

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

Иными словами, требуется разделить отрезок так, чтобы отношение между меньшей частью и большей частью было равно отношению между большей частью и целым отрезком.

,

или

,

. Сложим эти уравнения

,

, но , поэтому,

,

, D=5,

То есть, после очередного вычисления длина отрезка уменьшается на 0.618. После n вычислений функции длина отрезка поиска минимума составит 0.618^n-3 долю первоначальной величины (три первых вычисления в точках a, b и t₁ еще не сокращают его длины). При длина отрезка стремится к нулю как геометрическая прогрессия со знаменателем 0.618, то есть метод золотого сечения всегда сходится линейно.

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

Образуем последовательность чисел так, что каждое следующее число будет суммой двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Это последовательность Фибоначчи. Найдем отношения предыдущего слагаемого к последующему:

1/2 = 0.500, 8/13 = 0.615,

2/3 = 0.666, 13/21 = 0.619,

3/5 = 0.600, 21/34 = 0.618,

5/8 = 0.625, 34/55 = 0.618.

Чем больше номер члена последовательности, тем ближе отношение к золотому сечению.

Кроме того: 0.618+1=1.618

1.618*0.618=1

1-0.618=0.382

0.618*0.618=0.382

2.618-1.618=1

2.618*0.382=1

2.618*0.618=1.618

1.618*1.618=2.618.

Алгоритм метода золотого сечения поиска минимума функции.

Пусть для единообразия ,. На первом шаге выберем,. После сравнения может быть отброшена точка с любым номером, и далее точки будут перенумерованы беспорядочно. Пусть на данном шаге есть 4 точки, из которых какие-то две являются концами отрезка. Выберем ту точку, в которой функция принимает наименьшее значение; пусть это оказалась точка:.

Затем отбрасываем ту точку, которая более всего удалена от ; пусть этой точкой оказалась:

.

Минимум находится внутри оставшегося отрезка. Если его длина меньше заданной точности вычислений, то находим его середину и считаем ее искомым минимумом. Значение функции в этой точке указывает глубину минимума.

Метод золотого сечения напоминает метод дихотомии поиска корня уравнения. он применим и к недифференцируемым функциям и всегда сходится; сходимость его линейна. Если на отрезке [a, b] функция имеет несколько минимумов, то процесс сойдется к одному из них, но не обязательно к наименьшему.

Пример. Найти минимум функции на отрезкес точностью0.3.

Отбрасываем , рассматриваем отрезок

Отбрасываем , рассматриваем отрезок

Отбрасываем , рассматриваем отрезок

Отбрасываем , рассматриваем отрезок

Длина отрезка равна , то есть с точностью0.3 минимум функции соответствует точке и значение в минимуме0.5.