Итерационный алгоритм.
Этот алгоритм я открыл тоже в детстве, но наверное, чуть позже, лет в 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} .
В итоге оказалось, что я просто открыл заново метод Ньютона, и что он довольно эффективен для итеративного расчета квадратного корня. Вот так вот...
Вот еще тут есть программа на ассемблере для этого другого способа вычислить квадратный корень.
4 апр, 2018
© 2007-2022 Ужас в том, что Алиса кусает имбирем