АГС метод Гаусса

Гаусс заметил, что последовательности $\{a_N\}$, $\{b_N\}$ :

$a_0=a \quad \quad \quad \quad \quad \quad \quad \quad b_0=b$

$a_1=\frac{a_0+b_0}{2} \quad \quad \quad \quad b_1=\sqrt{a_0b_0}$

$a_2=\frac{a_1+b_1}{2} \quad \quad \quad \quad b_2=\sqrt{a_1b_1}$

…

$a_N=\frac{a_{N-1}+b_{N-1}}{2}\quad \quad b_N=\sqrt{a_{N-1}b_{N-1}}$

имеют при $N\to +\infty$ один и тот же предел:^[1][2]

$\lim_{N\to\infty}a_N = \lim_{N\to\infty}b_N = M(a,b)$

называемый арифметико-геометрическим средним величин a и b.

Приложения

Можно воспользоваться этим фактом, чтобы вычислить число $\pi$. Например, по формуле Гаусса-Сэлэмина:^[3]

$\pi = \frac{4\left(M(1;\frac{1}{\sqrt{2}})\right)^2}{1-\sum_{j=1}^{\infty}2^{j+1}c_j^2},$

где $c_j = \frac 12\left(a_{j-1}-b_{j-1}\right).$

В то же время, если взять

$a_0 = 1, \quad \quad \quad b_0 = \cos\alpha ,$

то

$\lim_{N\to\infty}a_N = \frac{\pi}{2K(\sin\alpha)},$

где $K(\alpha)$ есть полный эллиптический интеграл

$K(\alpha) = \int_{0}^{\frac{\pi}{2}}(1 - \alpha^2\sin^2\theta)^{-\frac 12}d\theta.$

Пользуясь этим свойством АГС, а также преобразованиями, восходящими к Ландену,^[4] Брент предложил^[5] первые АГС-алгоритмы для быстрого вычисления простейших трансцендентных функций ($e^x, \cos x, \sin x$). В дальнейшем исследование и использование АГС -алгоритмов было продолжено многими авторами — см., например, книгу Дж. и П. Борвайнов "Пи и АГС".^[6]

Ссылки

1. ↑ B. C. Carlson (1971). «Algorithms involving arithmetic and geometric means». Amer. Math. Monthly 78: 496–505. DOI:10.2307/2317754. MR0283246.
2. ↑ B. C. Carlson (1972). «An algorithm for computing logarithms and arctangents». Math.Comp. 26 (118): 543–549. DOI:10.2307/2005182. MR0307438.
3. ↑ E. Salamin (1976). «Computation of $\pi$ using arithmetic-geometric mean». Math. Comp. 30 (135): 565–570. DOI:10.2307/2005327. MR0404124.
4. ↑ J. Landen (1775). «An investigation of a general theorem for finding the length of any arc of any conic hyperbola, by means of two elliptic arcs, with some other new and useful theorems deduced therefrom». Philos. Trans. Royal Soc. London 65: 283–289.
5. ↑ R.P. Brent (1976). «Fast Multiple-Precision Evaluation of Elementary Functions». J. Assoc. Comput. Mach. 23 (2): 242–251. DOI:10.1145/321941.321944. MR0395314.
6. ↑ J.M. Borwein and P.B. Borwein Pi and the AGM. — Wiley, 1987. — ISBN MR08777280-471-83138-7

См. также

• Быстрые алгоритмы
• Сложность вычисления (битовая)
• Метод БВЕ