Перейти к содержимому
Topos Uranos
Русский

Метод Ньютона-Рафсона

Краткое содержание

Теорема Больцано утверждает, что непрерывная функция, меняющая знак, имеет корень, а метод деления пополам находит его, получая по одному двоичному знаку при каждом делении. В этом уроке изучается способ, гораздо более быстрый, когда он работает: метод Ньютона-Рафсона, который заменяет график его касательной и берёт в качестве нового приближения точку, в которой касательная пересекает ось. Полученные так приближения определяются одно за другим для целых n≥0n \geq 0, а их предел понимается через определение предела при стремлении переменной к бесконечности, без теории последовательностей. Урок доказывает с помощью выпуклости вниз, что если производная не обращается в нуль и функция выпукла вниз или выпукла вверх, то итерации, начинающиеся с подходящей стороны, приближаются к корню, не перескакивая через него, и сходятся к нему; а с помощью теоремы о среднем, что значение функции, которое вычисляется, оценивает расстояние до корня, которое неизвестно. Затем на числовых примерах показывается, что число верных знаков на каждой итерации удваивается, и разбираются случаи, когда метод терпит неудачу: нулевая производная, зацикливание, расходимость. Задачи вычисляют кубические корни и обратные величины без деления, преодолевают зацикливание, исследуют двукратный корень и находят точную границу между сходимостью и расходимостью для арктангенса.

Цели обучения

  1. Вычислять итерации Ньютона-Рафсона для дифференцируемой функции и узнавать в них точку пересечения касательной с осью.
  2. Доказывать монотонную сходимость итераций, когда производная не обращается в нуль и функция выпукла вниз или выпукла вверх, и выбирать начальное приближение с подходящей стороны.
  3. Оценивать расстояние от приближения до корня через значение функции и оценку её производной снизу.
  4. Распознавать случаи неудачи метода и сравнивать его с методом деления пополам по скорости и надёжности.

Итерация

Пусть ff есть дифференцируемая функция, корень rr которой ищется, и пусть x0x_0 есть первое приближение. Вблизи x0x_0 график ff похож на свою касательную, y=f(x0)+f′(x0)(x−x0)y = f(x_0) + f'(x_0)(x - x_0), согласно определению касательной из урока о производной как пределе; на языке дифференциала из урока о производных высших порядков и дифференциале приращение f(x0+Δx)−f(x0)f(x_0 + \Delta x) - f(x_0) близко к f′(x0)Δxf'(x_0) \Delta x. Касательная пересекает ось в единственной точке, если f′(x0)≠0f'(x_0) \neq 0, и естественно взять эту точку в качестве нового приближения: она находится приравниванием к нулю уравнения касательной. Повторение этой процедуры из полученной точки и есть метод Ньютона-Рафсона.

ОпределениеИтерации Ньютона-Рафсона

Пусть ff есть функция, дифференцируемая на промежутке II, и x0x_0 есть точка из II. Итерациями Ньютона-Рафсона, начинающимися с x0x_0, называются числа, определяемые одно за другим формулой

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

пока xnx_n лежит в II и f′(xn)≠0f'(x_n) \neq 0. Если эти условия выполняются для всякого целого n≥0n \geq 0, итерации образуют функцию n↦xnn \mapsto x_n, определённую на множестве неотрицательных целых чисел, которое не ограничено сверху, и к ней применимо определение предела при стремлении переменной к бесконечности из урока о пределах при стремлении переменной к бесконечности. Говорят, что итерации сходятся к rr, если lim⁡n→∞xn=r\lim_{n \to \infty} x_n = r, то есть если

(∀ε>0)(∃M)(∀n≥0)(n>M→∣xn−r∣<ε)(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

Каждая итерация есть точка пересечения с осью касательной в (xn,f(xn))(x_n, f(x_n)): если положить y=0y = 0 и x=xn+1x = x_{n+1} в уравнении y=f(xn)+f′(xn)(x−xn)y = f(x_n) + f'(x_n)(x - x_n) и выразить неизвестное, получится формула из определения. Метод не требует, чтобы функция меняла знак на заданном промежутке, как метод деления пополам, а требует, чтобы она была дифференцируемой и чтобы её производная не обращалась в нуль в точках, через которые он проходит; взамен ничто не гарантирует заранее, что итерации приблизятся к корню. Ниже даны условия, которые это гарантируют.

ПримерКвадратный корень из 2

Применить метод Ньютона-Рафсона к f(x)=x2−2f(x) = x^2 - 2, начиная с x0=2x_0 = 2. Шаги показывают первые три касательные и точки их пересечения с осью.

Доказательство

  1. xn+1=xn−xn2−22xn=12(xn+2xn),x1=32x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}

    Производная равна f′(x)=2xf'(x) = 2x и не обращается в нуль при x>0x > 0. Итерация принимает следующий вид: каждое приближение есть полусумма предыдущего и числа 22, делённого на него. Из x0=2x_0 = 2 касательная y=2+4(x−2)y = 2 + 4(x - 2) пересекает ось в точке 32\frac{3}{2}.

  2. x2=12(32+43)=1712≈1,416667x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1{,}416667

    Касательная в точке (32,14)\left(\frac{3}{2}, \frac{1}{4}\right) пересекает ось гораздо ближе к корню.

  3. x3=12(1712+2417)=577408≈1,4142157,2≈1,4142136x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1{,}4142157, \qquad \sqrt{2} \approx 1{,}4142136

    Третья итерация имеет уже пять верных десятичных знаков. Погрешности, xn−2x_n - \sqrt{2}, составляют около 0,590{,}59, 0,0860{,}086, 0,00250{,}0025 и 0,00000210{,}0000021: каждая имеет порядок квадрата предыдущей.

Погрешность в этом примере возводится в квадрат точно. Из формулы итерации для всякого xn>0x_n > 0 получается следующее тождество:

xn+1−2=xn2−22 xn+22xn=(xn−2)22xnx_{n+1} - \sqrt{2} = \frac{x_n^2 - 2\sqrt{2}\,x_n + 2}{2x_n} = \frac{\left(x_n - \sqrt{2}\right)^2}{2x_n}

Следовательно, все итерации, начиная с первой, больше или равны 2\sqrt{2}, и если xn≥1x_n \geq 1, то следующая погрешность не превосходит половины квадрата текущей: четвёртая итерация, x4=665 857470 832x_4 = \frac{665\,857}{470\,832}, имеет одиннадцать верных десятичных знаков. Если заменить 22 любым положительным числом, та же процедура вычисляет квадратные корни; она встречается уже в Метрике Герона Александрийского, в I веке, и поэтому её называют также методом Герона.

Исаак Ньютон описал свой метод для полиномиальных уравнений в 1669 году в сочинении, которое распространялось в рукописи и было опубликовано в 1711 году; Джозеф Рафсон опубликовал в 1690 году более простое изложение, а Томас Симпсон представил его в 1740 году как итерационный метод для уравнений общего вида.