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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (16431727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

Описание метода[править | править вики-текст]

Обоснование[править | править вики-текст]

Чтобы численно решить уравнение методом простой итерации, его необходимо привести к эквивалентному уравнению: , где  — сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:

С учётом этого функция определяется:

При некоторых условиях эта функция в окрестности корня осуществляет сжимающее отображение[1], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню уравнения .

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

Геометрическая интерпретация[править | править вики-текст]

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к графику исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Пусть 1) вещественнозначная функция  непрерывно дифференцируема на интервале  ;
2) существует искомая точка  :  ;
3) существуют и такие, что
для
и для  ;
4) точка такова, что .
Тогда формула итеративного приближения к может быть выведена из геометрического смысла касательной следующим образом:

где  — угол наклона касательной прямой к графику в точке .

Следовательно ( в уравнении касательной прямой полагаем ) искомое выражение для имеет вид :

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

Если , то имеет место «перелёт» (корень лежит рядом с границей ). В этом случае надо (воспользовавшись идеей метода половинного деления) заменять на до тех пор, пока точка «не вернётся» в область поиска .

Замечания. 1) Наличие непрерывной производной даёт возможность строить непрерывно меняющуюся касательную на всей области поиска решения .
2) Случаи граничного (в точке или в точке ) расположения искомого решения рассматриваются аналогичным образом.
3) С геометрической точки зрения равенство означает, что касательная прямая к графику в точке - параллельна оси и при не пересекается с ней в конечной части.
4) Чем больше константа и чем меньше константа из пункта 3 условий, тем для пересечение касательной к графику и оси ближе к точке , т.е. тем ближе значение к искомой .

Итерационный процесс начинается с некоторого начального приближения , причём между и искомой точкой не должно быть других нулей функции , т.е. «чем ближе к искомому корню , тем лучше». Если предположения о нахождении отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях.

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

Алгоритм[править | править вики-текст]

  1. Задается начальное приближение .
  2. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .

Пример[править | править вики-текст]

Иллюстрация применения метода Ньютона к функции с начальным приближением в точке .
График последовательных приближений.
График сходимости.
Согласно способу практического определения скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум.

Рассмотрим задачу о нахождении положительных , для которых . Эта задача может быть представлена как задача нахождения нуля функции . Имеем выражение для производной . Так как для всех и для , очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение , тогда:

Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.


Условия применения[править | править вики-текст]

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

Рассмотрим ряд примеров, указывающих на недостатки метода.

Контрпримеры[править | править вики-текст]

  • Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

Пусть

Тогда

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

График производной функции при приближении к нулю справа.

Рассмотрим функцию:

Тогда и всюду, кроме 0.

В окрестности корня производная меняет знак при приближении к нулю справа или слева. В то время, как для .

Таким образом не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, бесконечно дифференцируема везде, кроме как в корне, а её производная ограничена в окрестности корня.

Рассмотрим пример:

Тогда и за исключением , где она не определена.

На очередном шаге имеем :

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

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

Пусть

Тогда и следовательно . Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.

Ограничения[править | править вики-текст]

Пусть задано уравнение , где и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста Леонида Витальевича Канторовича (19121986).

Теорема Канторовича.

Если существуют такие константы , что:

  1. на , то есть существует и не равна нулю;
  2. на , то есть ограничена;
  3. на , и ;

Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:

  1. на существует корень уравнения ;
  2. если , то итерационная последовательность сходится к этому корню: ;
  3. погрешность может быть оценена по формуле .

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

Тогда ограничения на исходную функцию будут выглядеть так:

  1. функция должна быть ограничена;
  2. функция должна быть гладкой, дважды дифференцируемой;
  3. её первая производная равномерно отделена от нуля;
  4. её вторая производная должна быть равномерно ограничена.

Историческая справка[править | править вики-текст]

Метод был описан Исааком Ньютоном в рукописи «Об анализе уравнениями бесконечных рядов» (лат. «De analysi per aequationes numero terminorum infinitas»), адресованной в 1669 году Барроу, и в работе «Метод флюксий и бесконечные ряды» (лат. «De metodis fluxionum et serierum infinitarum») или «Аналитическая геометрия» (лат. «Geometria analytica») в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения , а последовательность полиномов и в результате получал приближённое решение .

Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе «Общий анализ уравнений» (лат. «Analysis aequationum universalis»). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

В 1879 году Артур Кэли в работе «Проблема комплексных чисел Ньютона — Фурье» (англ. «The Newton-Fourier imaginary problem») был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

Обобщения и модификации[править | править вики-текст]

Иллюстрация последовательных приближений метода одной касательной, применённого к функции с начальным приближением в точке .

Метод секущих[править | править вики-текст]

Родственный метод секущих является «приближённым» методом Ньютона и позволяет не вычислять производную. Значение производной в итерационной формуле заменяется её оценкой по двум предыдущим точкам итераций:

.

Таким образом, основная формула имеет вид

Этот метод схож с методом Ньютона, но имеет немного меньшую скорость сходимости. Порядок сходимости метода равен золотому сечению — 1,618...

Замечания. 1) Для начала итерационного процесса требуются два различных значения и .
2) В отличие от «настоящего метода Ньютона» (метода касательных), требующего хранить только (и в ходе вычислений - временно и ), для метода секущих требуется сохранение , , , .
3) Применяется, если вычисление затруднено (например, требует большого количества машинных ресурсов: времени и/или памяти).

Метод одной касательной[править | править вики-текст]

В целях уменьшения числа обращений к значениям производной функции применяют так называемый метод одной касательной.

Формула итераций этого метода имеет вид:

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

При таком выборе в точке выполнено равенство:

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

Этот метод является частным случаем метода простой итерации. Он имеет линейный порядок сходимости.

Многомерный случай[править | править вики-текст]

Обобщим полученный результат на многомерный случай.

Пусть необходимо найти решение системы:

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

где .

Применительно к задачам оптимизации[править | править вики-текст]

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

где  — гессиан функции .

В более удобном итеративном виде это выражение выглядит так:

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

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

Метод Ньютона — Рафсона[править | править вики-текст]

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

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

Применительно к задачам о наименьших квадратах[править | править вики-текст]

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

Эти задачи отличаются особым видом градиента и матрицы Гессе:

где  — матрица Якоби вектор-функции ,  — матрица Гессе для её компоненты .

Тогда очередное направление определяется из системы:

Метод Гаусса — Ньютона[править | править вики-текст]

Метод Гаусса — Ньютона строится на предположении о том, что слагаемое доминирует над . Это требование не соблюдается, если минимальные невязки велики, то есть если норма сравнима с максимальным собственным значением матрицы . В противном случае можно записать:

Таким образом, когда норма близка к нулю, а матрица имеет полный столбцевой ранг, направление мало отличается от ньютоновского (с учётом ), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.

Обобщение на комплексную плоскость[править | править вики-текст]

Бассейны Ньютона для полинома пятой степени . Разными цветами закрашены области притяжения для разных корней. Более тёмные области соответствуют большему числу итераций.

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

Особый интерес представляет выбор начального приближения . Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал Артура Кейли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры.

Ввиду того, что Ньютон применял свой метод исключительно к полиномам, фракталы, образованные в результате такого применения, обрели название фракталов Ньютона или бассейнов Ньютона.

Реализация[править | править вики-текст]

Scala[править | править вики-текст]

object NewtonMethod {

  val accuracy = 1e-6

  @tailrec
  def method(x0: Double, f: Double => Double, dfdx: Double => Double, e: Double): Double = {
    val x1 = x0 - f(x0) / dfdx(x0)
    if (abs(x1 - x0) < e) x1
    else method(x1, f, dfdx, e)
  }

  def g(C: Double) = (x: Double) => x*x - C

  def dgdx(x: Double) = 2*x

  def sqrt(x: Double) = x match {
    case 0 => 0
    case x if (x < 0) => Double.NaN
    case x if (x > 0) => method(x/2, g(x), dgdx, accuracy) 
  }
}

Python[править | править вики-текст]

def newtons_method(x0, f, f1, e):
    #f1 - производная
    while True:
        x1 = x0 - (f(x0) / f1(x0))
        if abs(x1 - x0) < e:
            return x1
        x0 = x1

PHP[править | править вики-текст]

<?php
// PHP 5.4
function newtons_method(
	$a = -1, $b = 1, 
	$f = function($x) {
	
		return pow($x, 4) - 1;
	
	},
	$derivative_f = function($x) {

		return 4 * pow($x, 3);
	
	}, $eps = 1E-3) {

        $xa = $a;
        $xb = $b;

        $iteration = 0;

        while (abs($xb) > $eps) {

            $p1 = $f($xa);
            $q1 = $derivative_f($xa);
            $xa -= $p1 / $q1;
            $xb = $p1;
            ++$iteration;

        }

        return $xa;

}

Octave[править | править вики-текст]

function res = nt()
eps = 1e-7;
x0_1 = [-0.5,0.5];
max_iter = 500;
xopt = new(@resh, eps, max_iter);   
xopt
endfunction
function a = new(f, eps, max_iter)
x=-1;
p0=1;
i=0;
 while (abs(p0)>=eps)
[p1,q1]=f(x);
 x=x-p1/q1;
p0=p1;
 i=i+1;
 end
 i
 a=x;
endfunction
function[p,q]= resh(x)   % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1;
   p=-25*x.^4+16*x.^3-36*x.^2+22*x-2;
   q=-100*x.^3+48*x.^2-72*x+22;
endfunction

С[править | править вики-текст]

#include <stdio.h>
#include <math.h>

#define eps 0.000001
double fx(double x) { return x*x-17;}
double dfx(double x) { return 2*x;}

typedef double(*function)(double x);

double solve(function fx, function dfx, double x0) {
  double x1  = x0 - fx(x0)/dfx(x0);
  while (fabs(x1-x0)>eps) {
    x0 = x1;
    x1 = x1 - fx(x1)/dfx(x1);
  }
  return x1;
}

int main () {
  printf("%f\n",solve(fx,dfx,4));
  return 0;
}

C++[править | править вики-текст]

typedef double (*function)(double x);

double TangentsMethod(function f, function df, double xn, double eps) {
   double x1  = xn - f(xn)/df(xn);
   double x0 = xn;
   while(abs(x0-x1) > eps) {
      x0 = x1;
      x1 = x1 - f(x1)/df(x1);
   }
   return x1;
}

//Выбор начального приближения
xn = MyFunction(A)*My2Derivative(A) > 0 ? B : A;

double MyFunction(double x) { return (pow(x, 5) - x - 0.2); } //Ваша функция
double MyDerivative(double x) { return (5*pow(x, 4) - 1); } //Первая производная
double My2Derivative(double x) { return (20*pow(x, 3)); } //Вторая производная

//Пример вызова функции
double x = TangentsMethod(MyFunction, MyDerivative, xn, 0.1)

Литература[править | править вики-текст]

  1. Акулич И. Л. Математическое программирование в примерах и задачах : Учеб. пособие для студентов эконом. спец. вузов. — М. : Высшая школа, 1986. — 319 с. : ил. — ББК 22.1 А44. — УДК 517.8(G).
  2. Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров : Учеб. пособие. — М. : Высшая школа, 1994. — 544 с. : ил. — ББК 32.97 А62. — УДК 683.1(G). — ISBN 5-06-000625-5.
  3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М. : Лаборатория Базовых Знаний, 2000.
  4. Вавилов С. И. Исаак Ньютон. — М. : Изд. АН СССР, 1945.
  5. Волков Е. А. Численные методы. — М. : Физматлит, 2003.
  6. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
  7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575-576.
  8. Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
  9. Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
  10. Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

Примечания[править | править вики-текст]

  1. Доказательство: Пусть дана функция вещественного переменного дважды непрерывно дифференцируемая в своей области определения, производная которой нигде не обращается в нуль:
    И необходимо доказать, что функция осуществляет сжимающее отображение вблизи корня уравнения . В силу непрерывной дифференцируемости функции и неравенства нулю её первой производной непрерывна. Производная равна:
    В условиях, наложенных на , она также непрерывна. Пусть  — искомый корень уравнения: , следовательно в его окрестности :
    Тогда согласно теореме Лагранжа:
    В силу того, что в этой же дельта окрестности выполняется:
    Таким образом полученная функция в окрестности корня осуществляет сжимающее отображение.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]