Информатика / математика и код

Нахождение квадратного корня

Итерационный алгоритм.

Этот алгоритм я открыл тоже в детстве, но наверное, чуть позже, лет в 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}\).

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

Яндекс.Метрика