Может ли кто-нибудь объяснить мне этот рекурсивный псевдокод, который находит квадратный корень числа? Мне трудно понять, так как мне не известно, что означают входные данные n, p и e. Спасибо.
if abs(e^2 - n) < p
SR(n,p,e) = e
else
SR(n,p,e) = SR(n,p,(e+n/e)/2)
(e begins at n)
n — это число, из которого вы хотите получить квадратный корень, e — это оценка квадратного корня, а p — это желаемая точность, то есть ошибка, которую вы готовы допустить. Алгоритм говорит: если e «достаточно близко» к ответу, т. е. e^2 находится в пределах p от n, то e — это ответ, который вы ищете; в противном случае попробуйте более точную оценку (e+n/e)2. Почему это лучшая оценка? если e больше, чем sqrt(n), то n/e будет меньше, чем sqrt(n), поэтому sqrt(n) будет между e и n/e, поэтому попробуйте среднее значение e и n/e в качестве следующего оценивать. (И наоборот, если e меньше sqrt(n)).
Надеюсь это поможет,
Брюс
Алгоритм Ньютона — это нечто большее, чем просто переход от одной оценки к «лучшей оценке». Есть некоторая подробная математика, объясняющая, почему лучшая оценка — это то, что есть.
Идея состоит в том, чтобы найти решение ЛЮБОГО уравнения формы f(x) = 0 (кроме нескольких исключительных случаев), если у вас есть приближение к x, вы можете получить ЛУЧШЕЕ приближение, глядя на скорость изменения f(x), который часто пишется как f'(x), и используя его, чтобы выяснить, насколько вам нужно скорректировать свою оценку, чтобы получить гораздо лучшую оценку истинного решения.
В случае квадратного корня, то есть мы хотим найти x=sqrt(n), мы можем написать f(x)=x^2-n и f'(x)=2x, а затем использовать алгоритм Ньютона, чтобы найти правильное x, чтобы получить f(x)=0. Это означает, что если у нас есть оценка e, то для выработки следующей оценки мы смотрим на f(e)=e^2-n и спрашиваем, насколько нам нужно изменить e, чтобы избавиться от этой ошибки. Поскольку скорость изменения f равна f'(x), что равно 2e в точке (e,e^2-n), мы должны разделить e^2-n на 2e, чтобы определить, на сколько нам нужно скорректировать e, чтобы получить нашу следующую оценку.
То есть наша следующая оценка должна быть
e - (e^2-n) / 2e
= e - (e / 2) + (n / 2e)
= (e + n / e) / 2
Дополнительную информацию об алгоритме Ньютона можно найти по адресу http://tutorial.math.lamar.edu/Classes/CalcI/NewtonsMethod.aspx (где есть прекрасная диаграмма, объясняющая, как это работает) и на http://www.math.brown.edu/UTRA/linприблизительно.html, в котором рассматриваются некоторые технические детали.
