Способ вычисления квадратного корня.

[Rubik]

Предлагаю такой способ извлечения квадратного корня из числа $A$ (лучше всего целого):
1)выбираем первое приближение $B\approx\sqrt A$ (лучше всего $B=[\sqrt a]$);
2)вычисляем $\alpha=2B;\qquad\beta=A-B^2$;
3)строим рекуррентную последовательность: $I_n=\alpha I_{n-1}+\beta I_{n-2}$, первые члены лучше выбирать так: $I_0=0;\qquad I_1=1$;
4)$x_n=\frac{I_n}{I_{n-1}}-B;\qquad\sqrt A=\lim\limits_{n\to\infty}x_n$, что легко доказывается;
5)для оценки точности можно сравнить два соседних члена $x_n$, и если разница между ними меньше допустимой погрешности, значит нужная точность достигнута.
Преимущества:
1)Быстрая сходимость (как правило нужно сделать не более 10 шагов);
2)необходимость многократного применения только сложения и умножения, так как последовательность $I_n$ линейная рекуррентная, а в последовательности $x_n$ можно вычислять лишь отдельные члены для проверки точности (при вычислении методом Ньютона на каждом шаге необходимо производить деление, что приводит к дополнительной погрешности);
3)необходимость помнить лишь конечное количество чисел.
Недостатки:
1)При больших $A$ коэффициенты $\alpha,\beta$ также большие, поэтому при вычислении членов последовательности $I_n$ надо оперировать большими по модулю целыми числами;
2)При неудачном выборе $B$ последовательность $x_n$ сходится очень медленно.
Оцените, пожалуйста, данный алгоритм. Если потребуется, приведу все доказательства. Спасибо.

[Xaositect]

$x_n = \frac{I_n}{I_{n-1}} - B = \frac{\alpha I_{n-1} + \beta I_{n-2}}{I_{n-1}} - B = \alpha + \beta \frac{I_{n-2}}{I_{n-1}} - B = B + \beta\frac{1}{x_{n-1} + B} = B + \frac{A - B^2}{x_{n-1} + B} = B + (A - B^2) \frac{x_{n-1}^2 - B^2}{x_{n-1} - B}$
Вывод: предложенный метод есть не что иное, как метод хорд в приложении к нахождению квадратного корня.

[meduza]

Rubik в сообщении #331025 писал(а):

1)выбираем первое приближение $B\approx\sqrt A$ (лучше всего $B=[\sqrt a]$);

Не очень-то хорошо в качестве исходного данного для вычисления корня брать само значение корня, пусть даже приближённое.

Я попробовал Ваш метод, но в качестве начального значения $B$ брал $A/2$. Ньютон (с начальным приближением $1$) сходился быстрее при вычислении корней трёх пришедших в голову чисел (2, 49, 900). Может и вправду виновато неудачное начальное приближение.

(Результаты)

Сначала приведён результат 7-ми итераций Вашего метода, затем -- Ньютона:

Prelude> take 7 $ map (x 2) [1..]
[Infinity,1.0,1.5,1.4,1.4166666666666665,1.4137931034482758,1.4142857142857141]
Prelude> take 7 $ map (newt 2) [1..]
[1.0,1.5,1.4166666666666665,1.4142156862745097,1.4142135623746899,1.414213562373095,1.414213562373095]
Prelude> sqrt(2)
1.4142135623730951

Prelude> take 7 $ map (x 49) [1..]
[Infinity,24.5,13.25,9.897350993377486,8.474056603773583,7.782311708747585,7.424085332754316]
Prelude> take 7 $ map (newt 49) [1..]
[1.0,25.0,13.48,8.557507418397627,7.141736912383411,7.001406475243939,7.000000141269659]

Prelude> take 7 $ map (x 900) [1..]
[Infinity,450.0,226.0,151.7751479289941,114.99115044247787,93.18025186391833,78.85248624519875]
Prelude> take 7 $ map (newt 900) [1..]
[1.0,450.5,226.24889012208658,115.1134050942049,61.465891052400636,38.054079122333626,30.85231586212186]

[Rubik]

Ну вот, выводил-выводил а это оказывается всего-навсего метод хорд. Причем когда выводил думал не о нём, а о пределе отношения соседних членов линейной рекуррентности.

Цитата:

Не очень-то хорошо в качестве исходного данного для вычисления корня брать само значение корня, пусть даже приближённое

А почему? Определить целую часть корня можно поочерёдно отнимая от него последовательные нечётные числа.

Цитата:

Я попробовал Ваш метод, но в качестве начального значения $B$ брал $A/2$. Ньютон (с начальным приближением $1$) сходился быстрее при вычислении трх пришедших в голову чисел (2, 49, 900). Может и вправду виновато неудачное начальное приближение.

При 2 действительно сходится медленнее. Чтоб вычислить корень из 49 и 900 никакие особые методы не нужны . А проверьте, например на числе 905, но только взяв начальное приближение 30.

[meduza]

Rubik в сообщении #331045 писал(а):

А проверьте, например на числе 905, но только взяв начальное приближение 30.

ОК. Только, чтобы уравновесить условия, дадим такое же начальное приближение методу Ньютона.

(Результат)

Prelude> take 5 $ map (x 905) [2..]  -- Ваш метод
[30.0,30.083333333333336,30.083217753120664,30.08321791320406,30.08321791298234]
Prelude> take 5 $ map (newt 905) [1..]  -- метод Ньютона
[30.0,30.083333333333336,30.083217913204063,30.083217912982647,30.083217912982647]
Prelude> sqrt(905)
30.083217912982647

И опять Ньютон сошёлся быстрее. Я не говорю, что Ваш метод плохой, просто (пока) я не увидел приемущества над старым добрым $x_{n+1}=0{,}5(x_n+a/x_n)$.

[Rubik]

meduza в сообщении #331052 писал(а):

ОК. Только, чтобы уравновесить условия, дадим такое же начальное приближение методу Ньютона.

Хм... Сам даже никогда не задумывался над тем, что Ньютону можно давать начальное приближение. А ведь действительно, сошелся до десятого знака со второго шага. Недостатком его мне показалось то, что на каждом шаге делается деление, но поскольку итераций немного, то погрешности не успевают накапливаться, кроме того это можно предотвратить, если хранить рациональное число как числитель и знаменатель, а деление производить только при выдаче результата. И ещё: как в ньютоновском методе оценить точность?

[meduza]

Rubik в сообщении #331058 писал(а):

Сам даже никогда не задумывался над тем, что Ньютону можно давать начальное приближение.

$x_1$ в той формулке, что я писал выше.

Rubik в сообщении #331058 писал(а):

И ещё: как в ньютоновском методе оценить точность?

Этот метод -- частный случай метода касательных (Ньютона) нахождения численного решения уравнения $f(x)=x^2-a=0$. Этот метод подробно описан в любом учебнике по численным методам, оценки там тоже есть. Скажу лишь, что метод имеет квадратичную скорость сходимости, т. е., грубо говоря, каждая итерация удваивает число значащих цифр. А скорость сходимости метода хорд -- линейная.

[Rubik]

meduza в сообщении #331065 писал(а):

Этот метод -- частный случай метода касательных (Ньютона) нахождения численного решения уравнения $f(x)=x^2-a=0$. Этот метод подробно описан в любом учебнике по численным методам, оценки там тоже есть. Скажу лишь, что метод имеет квадратичную скорость сходимости, т. е., грубо говоря, каждая итерация удваивает число значащих цифр. А скорость сходимости метода хорд -- линейная.

Понятно, спасибо. Почитаю про метод касательных.