Нахождение квадратного корня
Итерационный алгоритм.
Этот алгоритм я открыл тоже в детстве, но наверное, чуть позже, лет в 14-15. Мне было интересно, как можно найти квадратный корень с помощью итерации, то есть, чтобы с каждой новой итерации точность увеличивалась.
Основное положение:
$$ x = \sqrt{y} \\ x^2 = y $$Во второй части я просто домножил обе части уравнения на квадрат, и получил слева квадрат "x", справа просто "y". Давайте теперь разделим обе части уравнения на "x":
$$ x = \frac{y}{x} $$Как мы понимаем, левая часть уравнения должна равняться правой, то есть, мы должны найти такой x, чтобы если "y" на него делился, в итоге получался "x".
Я долго думал над этой задачей. Я взял y=5, а x=1, и разделил, получил y=5; потом я разделил y/5 и получил 1. Значение x мечется туда-сюда, то принимает значение 5, то 1, и так далее. И тут меня озарило! А что, если брать такой x, который будет посередине от \(x\) и от \(\frac{y}{x}\)? Ведь нам нужно, в конце-концов, свести их вместе. И я сделал это формулой половинного деления отрезка:
$$ x_i = \frac{1}{2}(x_{i-1} + \frac{y}{x_{i-1}}) $$Здесь берется предыдущее значение от "x" и вычисляется середина отрезка между \(x\) и \(\frac{y}{x}\).
В итоге оказалось, что я просто открыл заново метод Ньютона, и что он довольно эффективен для итеративного расчета квадратного корня. Вот так вот...