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

Арифметико-геометрическое среднее

Арифметико-геометрическое среднее (АГС) величин a и b — предел последовательности <math>\{a_N\}</math>, <math>\{b_N\}</math>, где:

<math>a_0=a \quad \quad \quad \quad \quad \quad \quad \quad b_0=b</math>

<math>a_1=\frac{a_0+b_0}{2} \quad \quad \quad \quad b_1=\sqrt{a_0b_0}</math>

<math>a_2=\frac{a_1+b_1}{2} \quad \quad \quad \quad b_2=\sqrt{a_1b_1}</math>

…

<math>a_N=\frac{a_{N-1}+b_{N-1}}{2}\quad \quad b_N=\sqrt{a_{N-1}b_{N-1}}</math>

имеют при <math>N\to +\infty</math> один и тот же предел:

<math>\lim_{N\to\infty}a_N = \lim_{N\to\infty}b_N = M(a,b)</math>.

Модифицированное арифметико-геометрическое среднее

Модифицированное арифметико-геометрическое среднее двух величин x и y - (общий) предел (убывающей) последовательности <math>\{x_n\}_{n=1}^\infty</math> и (возрастающей) последовательности <math>\{y_n\}_{n=1}^\infty</math>, где <math>x_0 = x</math>, <math>y_0 = y</math> и <math>z_0 = 0</math>.

<math>x_{n+1} = \frac{x_n+y_n}{2}</math>

<math>y_{n+1} = z_n+\sqrt{(x_n-z_n)(y_n-z_n)}</math>

<math>z_{n+1} = z_n-\sqrt{(x_n-z_n)(y_n-z_n)}</math>

Приложения

Можно воспользоваться этим фактом, чтобы вычислить число <math>\pi</math>. Например, по формуле Гаусса-Сэлэмина:

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

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

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

<math>a_0 = 1, \quad \quad \quad b_0 = \cos\alpha ,</math>

то

<math>\lim_{N\to\infty}a_N = \frac{\pi}{2K(\sin\alpha)},</math>

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

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

Более лаконично, <math>\pi</math> вычисляется по формуле

<math>\pi = \frac{M(\sqrt{2})^2}{N(2) - 1},</math>

где <math>M(x)</math> - aрифметико-геометрическое среднее 1 и <math>x</math>, а <math>N(x)</math> - модифицированное арифметико-геометрическое среднее 1 и <math>x</math>, которое было введено Адлаем в статье 2012 года.

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

См. также

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

Отрывок, характеризующий АГС метод Гаусса

– Для этого я бы советовал вам… – начал было Борис, желая сказать ей колкость; но в ту же минуту ему пришла оскорбительная мысль, что он может уехать из Москвы, не достигнув своей цели и даром потеряв свои труды (чего с ним никогда ни в чем не бывало). Он остановился в середине речи, опустил глаза, чтоб не видать ее неприятно раздраженного и нерешительного лица и сказал: – Я совсем не с тем, чтобы ссориться с вами приехал сюда. Напротив… – Он взглянул на нее, чтобы увериться, можно ли продолжать. Всё раздражение ее вдруг исчезло, и беспокойные, просящие глаза были с жадным ожиданием устремлены на него. «Я всегда могу устроиться так, чтобы редко видеть ее», подумал Борис. «А дело начато и должно быть сделано!» Он вспыхнул румянцем, поднял на нее глаза и сказал ей: – «Вы знаете мои чувства к вам!» Говорить больше не нужно было: лицо Жюли сияло торжеством и самодовольством; но она заставила Бориса сказать ей всё, что говорится в таких случаях, сказать, что он любит ее, и никогда ни одну женщину не любил более ее. Она знала, что за пензенские имения и нижегородские леса она могла требовать этого и она получила то, что требовала.
Жених с невестой, не поминая более о деревьях, обсыпающих их мраком и меланхолией, делали планы о будущем устройстве блестящего дома в Петербурге, делали визиты и приготавливали всё для блестящей свадьбы.


Граф Илья Андреич в конце января с Наташей и Соней приехал в Москву. Графиня всё была нездорова, и не могла ехать, – а нельзя было ждать ее выздоровления: князя Андрея ждали в Москву каждый день; кроме того нужно было закупать приданое, нужно было продавать подмосковную и нужно было воспользоваться присутствием старого князя в Москве, чтобы представить ему его будущую невестку. Дом Ростовых в Москве был не топлен; кроме того они приехали на короткое время, графини не было с ними, а потому Илья Андреич решился остановиться в Москве у Марьи Дмитриевны Ахросимовой, давно предлагавшей графу свое гостеприимство.
Поздно вечером четыре возка Ростовых въехали во двор Марьи Дмитриевны в старой Конюшенной. Марья Дмитриевна жила одна. Дочь свою она уже выдала замуж. Сыновья ее все были на службе.
Она держалась всё так же прямо, говорила также прямо, громко и решительно всем свое мнение, и всем своим существом как будто упрекала других людей за всякие слабости, страсти и увлечения, которых возможности она не признавала. С раннего утра в куцавейке, она занималась домашним хозяйством, потом ездила: по праздникам к обедни и от обедни в остроги и тюрьмы, где у нее бывали дела, о которых она никому не говорила, а по будням, одевшись, дома принимала просителей разных сословий, которые каждый день приходили к ней, и потом обедала; за обедом сытным и вкусным всегда бывало человека три четыре гостей, после обеда делала партию в бостон; на ночь заставляла себе читать газеты и новые книги, а сама вязала. Редко она делала исключения для выездов, и ежели выезжала, то ездила только к самым важным лицам в городе.