2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Способ вычисления квадратного корня.
Сообщение14.06.2010, 10:47 
Аватара пользователя
Предлагаю такой способ извлечения квадратного корня из числа $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$ сходится очень медленно.
Оцените, пожалуйста, данный алгоритм. Если потребуется, приведу все доказательства. Спасибо.

 
 
 
 Re: Способ вычисления квадратного корня.
Сообщение14.06.2010, 10:58 
Аватара пользователя
$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}$
Вывод: предложенный метод есть не что иное, как метод хорд в приложении к нахождению квадратного корня.

 
 
 
 Re: Способ вычисления квадратного корня.
Сообщение14.06.2010, 11:21 
Аватара пользователя
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]

 
 
 
 Re: Способ вычисления квадратного корня.
Сообщение14.06.2010, 11:34 
Аватара пользователя
Ну вот, выводил-выводил а это оказывается всего-навсего метод хорд. Причем когда выводил думал не о нём, а о пределе отношения соседних членов линейной рекуррентности.
Цитата:
Не очень-то хорошо в качестве исходного данного для вычисления корня брать само значение корня, пусть даже приближённое

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

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

 
 
 
 Re: Способ вычисления квадратного корня.
Сообщение14.06.2010, 11:46 
Аватара пользователя
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)$.

 
 
 
 Re: Способ вычисления квадратного корня.
Сообщение14.06.2010, 12:06 
Аватара пользователя
meduza в сообщении #331052 писал(а):
ОК. Только, чтобы уравновесить условия, дадим такое же начальное приближение методу Ньютона.

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

 
 
 
 Re: Способ вычисления квадратного корня.
Сообщение14.06.2010, 12:19 
Аватара пользователя
Rubik в сообщении #331058 писал(а):
Сам даже никогда не задумывался над тем, что Ньютону можно давать начальное приближение.

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

Rubik в сообщении #331058 писал(а):
И ещё: как в ньютоновском методе оценить точность?

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

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

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group