Let us go for algorithms 1) 2) and 4)! I am going
to tempt to well structure the posting of the results because the web is not the
more convenient for the mathematical prooves!
let a and b two positive or nil reals. We define series (an) and (bn) by :
|Lemma 1 : (an) and (bn) are convergent and of the same limit. Furthermore, (an) is decreasing and (bn) is increasing. This limit is noted M(a,b) and called arithmetico-geometrical
mean of a and b.
I.a) Let us prove that for n>0 and a#b,
- In fact, if a=b, one immediately obtains for every integer n that an=a=bn
- If a=0 or b=0, one has (immediately again !) for every integer n bn=0 and an+1=an/2 that well proves (1) and (2)
- If a>0 and b>0, a#b
I.a).(1) A small recurrence for (1) to begin well !
n=1 : a#b so by developping, so b1<a1, and by redoing the same, b2<a2.
Moreover, a2=a1 /2+b1 /2<a1 /2+a1 /2=a1 so a2<a1 and b2>(b12)1/2=b1 so, finally, one has the result (1) at the rank 1
Let us suppose now that result (1) is true for k in [[1,n]]...
Since bn<an, one has again (anbn)1/2<(an+bn)/2 so bn+1<an+1 and an+1<2an/2=an and finally bn+1>(bn2)1/2=bn
This is realy the hypothesis at the following rank, so by the recurrence theorem,
the result (1) is correct for every integer n not nil...
I.a).(2) Pour tout n>0, on a :
That is well the result (2) !
I.b) Let us
show now that these series are convergent :
- If a=b one hase for every n an=bn ans so (difficult !) an=a=bn
- If b=0, a#0 one has fir every n>0 : bn=0 and an=an-1 /2=a0 /2n so an=bn=0
- If a=0, an=0 and so bn=0 for every n, that solves the problem of the limit !
- If a>0, b>0, a#b
_ According to I a) (1) (bn) is increasing,
and (an) is decreasing
_ Moreover, according to I a) (2) and by an immediate recurrence, an-bn<(a1-b1)/2n-1 so (an-bn)=0, hullo !
Would not it be adjacent series ? Of course yes ! So they converge toward a same
limit that we will note M(a,b)
II Properties of the arithmetico-geometrical
II.c) M(ßa,ßb)=ßM(a,b) for every integer n, ß>0, a>0, b>0
II.a) Given n0>0
(ano+k)k and (bno+k)k got same limit that (ak)k and (bk)k so, M(ano,bno)=M(a,b)
II.b) Given (a'n) and (b'n) the series defined by (an) and (bn), but with a'0=b and b'0=a
One has a'1=a1 and b'1=b1 so according to I. a) with n=1, one has M(a,b)=M(b,a)
II.c) Also, if one defines (a"n) and (b"n) by a"0=ßa0 and b"0=ßb0, one has immediately for every n : a"n=ßan and b"n=ßbn.
So, at the limit one has, M(ßa,ßb)=ßM(a,b)
III Function f(x)=M(1,x)
Here we are in the heart of the proof : for a=1 and b=x, the previous results (convergence...) allow us to build
a function f defined by :
For x positive or nil real,
The interesting results on this function are :
III.a) Lemma 2
continuous on [0,+[
In the case a0=a=1 and b0=b=x, we will show that the uniform convergence of the series (an) and (bn) on every compact of R+ toward the function f. To well differentiate this case of the previous study,
I will note respectively (Un) and (Vn) these series of functions...
III.a).1) Let us show that for every integer n, Un and Vn are continuous on R+
By recurrence, for example !
n=0 : U0(x)=1, V0(x)=x, no comment !
Let us suppose the result until a certain integer n,
Un+1=(Un+Vn)/2 and Vn+1=(UnVn)1/2 so Un+1 and Vn+1 are clearly continuous as composition of continuous functions...
The recurrence theorem is verified, Un and Vn are continuous for every n on R+.
III.a).2) Let us show the uniform convergence of Un and Vn toward f on every compact of R+ :
- According to I.a).1). one has n0, bnM(a,b)an so :
- xR+, Vn(x)f(x)Un(x) so :
0Un(x)-f(x)Un(x)-Vn(x)<(Un-1(x)-Vn-1(x))/2<|1-x|.2-n for every xR+
- Let us place on a compact [A,B] of R+
This upper bounding is uniform, so there is uniform
convergence of (Un) and (Vn) toward the function f on every compact of R+
So f is countinuous on [0,+[,
it's already a very important result !
III.b) Lemma 3
increasing on [0,+[
III.b).1) Let us show by a recurrence (again!) on nN that (Un) and (Vn) are increasing on [0,+[
U0=1 and V0=x so one has the result for n=0
Let us suppose that the result is true for a certain nN
Un and Vn being increasing, Un+Vn and also(UnVn)1/2 so Un+1 and Vn+1 are also increasing and this is the hypothesis at the following
The result is true for every nN.
III.b).2). Given x10, x20 with x1<x2
Since there is uniform convergence of (Un) towards f, one has f(x2)-f(x1)=(Un(x2)-Un(x1))
now nN*, Un(x2)-Un(x1)0 (growth of Un), so f(x2)-f(x1)0, that insure us of the growth of f on [0,+[,
and so, this is the end of the proof of lemma 3 !
III.c) Lemma 4 (Study at bounds...)
a vertical tangent in x=0
In 0, lim f =0
In +, lim f =+ , f(x)=o(x)
III.c).1) one has x1/2=V1(x)f(x) xR+*,
so x-1/2f(x)/x and finally :
so f admit a vertical tangent in x=0.
for n1 Un(x)=Un-1(x)/2=2-n, and Vn(x)=0 so f(0)=0
III.c).2) According to II.b) et II.c),
When x -> + lim f(1/x)=f(0)=0 because f is continuous in 0
so f(x)/x->0 and in +, f(x)=o(x)
Moreover xR+*, f(x)x1/2, so in +, lim
III.d) Theorem 5
|f is C class on ]0,+[
This result is very strong (almost too, since we will only need of the character C1!) is not simple to proove. It will even drive us to the theory of
elliptic integrals !
So, we will successively :
III.d).1) Express M(a,b) by an elliptic integral I(a,b)
III.d).2) Apply this result to function f
III.d).3) Use the character C of I(1,x) to deduct the one of f !
III.d).1) We will take an interest in the following integral,
Given a,b>0, let pose :
Given and m(0)=1/(ab), now m being of course continuous on R+, m is integrable on R+ and so I(a,b) is well defined...
III.d).1).ii) Change of variable
Let us pose
this is a increasing bijection so let us do a little change of variable... Let us
pose t=b.tan(y), one obtains :
III.d).1).iii) function g
One defines the function g by g(x)=I(1,x)
Let us show that it is C class on ]0,+[
Given h(x,y)= with (x,y)]0,+[*[0,/2]
Let us show by a recurrence on nN (allways !) that exists ans is continuous on ]0,+[*[0,/2]
In this way, let us show in the same time, allways by recurrence, that with the hypothesis
on parameters :
(x,y)= where x ->
this is the definition of h !
h is clearly continuous on ]0,+[*[0,/2] and admit a partial derivative in x
- n=1 :
This is truly the foretelled form for n=1 and this is perfectly continuous on ]0,+[*[0,/2]
- Let us suppose now the result for a certain nN
that is truly the waited result with Pn+1 of the wanted form... Pn+1 is a polynomial in x and a trigonometrical polynomial in y and is so therefore
continuous on ]0,+[*[0,/2] and derivable
As for the denominator, the hypothesis of recurrence is verified at rank n+1, that concludes
the recurrence !
h is C on ]0,+[*[0,/2]
Since we are on the segment [0,/2] for y,
the function g defined by :
is C on R+* and one
x -> I(1,x) is a C function on R+*
Now we have to express M(a,b) in function of I(a,b)
This is, of course, the main result of this study and it was obtained by Gauss (he did not go farer !).
III.d).1).iv) First of all let us show that :
In that way, let us pose j(t)= defied on R+* and that is clearly a bijection from R+* to R ( j'(t)=>0 ) so, in I(1,t) defined at 1), one poses s= and one obtains :
and on the other hand, ds=dt, so one obtain finally :
The last but one equality being obtained thank
to the parity of the term under the integral
III.d).1).v) So, let us show now that
One has clearly I(ßa,ßb)=I(a,b)/ß so :
now an=M(a,b) and one has an/bn=1.
Moreover, g is continuous on R+* according to iii) so :
that allow us to conclude :
III.d).2) by applying this result to the function f, one obtains
III.d).3) And the proof of the theorem 5 is finished, g being C on R+*, f also on the same interval
Small note : f is continuous in 0 but is not differentiable in 0 according to lemma 4...
III.e) Asymptotic attitude of f
We will search for equivalent of f at the bounds of R+ thank to equivalents of g
III.e).1) A new expression of g !
Let us pose haphazardly (!) s=x/t :
III.e).2) Let us find now an equivalent of
g in the neighbourhood of 0
t[0,x1/2], one has 11+t21+x, so
so according to III.d).2) one has :
the second equivalence being coarsly obtained thank to III.c).2) (f(x)=x.f(1/x))
IV Expression of Pi in function of f and f'
We will show that =
In that way, we restrain Un and Vn to ]0,1[ and we introducet Wn and kn, function defined on ]0,1[ by :
Wn= and kn=
These functions are obviously well defined and
positive because according to III a)2) 0<Vn(x)<Un(x) on ]0,1[
IV.a) Convergence of (kn)n
Let us pose a=Un+Vn=a0, b=Un-Vn=b0 as at I, one has
so according to the asymptotic study of III e), one obtains :
according to the previous property, that allow us to conlude :
IV.b) Convergence of (k'n)n
Let us be interested in the derivative series of functions (k'n)n.
In fact, f' appears in the final searched expression , so there is great chances
that we speack of derivatives series at a moment... so that is become clear :
IV.b).1) Existence et positivity
|nN, Un, Vn, Wn, kn are continuously derivable
Moreover, x]0,1[, nN*, U'n>0,
As for the continuity of Un and Vn, we do a recurrence on n to prove that. So let us be brief !
U1 and V1 obviously verify the property and if we suppose that the property
is true for a certain rank n, a small calculus according to the definition of Un and Vn gives us
that insure the existence, the continuity and the positivity at rank n+1... Hop,
this is finished, needless to waste time on such recurrences !
Wn and kn being composition of continuously derivable functions, they are
also for every n...
IV.b).2) Expression of (k'n)
according to IV a)1) so
now Vn2=Un2-Wn2 and if we derive, 2VnVn'=2UnUn'-2WnWn' so :
and one finally obtains :
|(k'n) uniformly converges on every compact of ]0,1[ towards : x->
Let us set on [a,b] compact of ]0,1[, 0<a<b<1
nN, x[a,b], one has :
by using III.a).2)...
This upper bounding involves the uniform convergence of (k'n)n towards
x -> on every compact of ]0,1[
IV.c) Expression of Pi
Here we are, finally !
|x -> is the derivative of x ->
- nN, kn is C1 class on ]0,1[ according to IV b)1)
- the series of function (kn)simply converges on ]0,1[ towards the function
x-> according to IV a)2)
- The series of functions (k'n) uniformly
converges on every compact of ]0,1[ towards x ->
So by applying the theorem of derivation of the
series of functions,
x-> is the derivative on ]0,1[ of x ->
IV.c).2) Différential equations
the differential equation :
Easy ! We simply have to derive x -> and to use the previous result a).
I do not do that, that is only calculus !
IV.c).3) Expression of Pi
The quest of the mathematical Holy Graal would go to his end ? Anyway, we touch here
the most important result of the proof !
Reference from the Encyclopedia of Integer
Sequences about M(1,sqrt(2)) : A003054
Easy again ! We just have to pose x= in the diiferential equation. As previously, that is only
calculus. I will not overload this page with useless expressions.
That is a great result !
And it will be the fundation of many very efficient algorithms with a quadratic convergence
Serious things now !
Many uses on this formula are possible :
V.a) Direct use of derivative series
The first thing of that we think is to use the derivative series (U'n) and (V'n) converge towards f' (the proof of this convergence is given at V.b) ). One
obtains replacing f and f' by Un and Vn of different ways the following algorithm :
Even if it seems more complicated than the algorithms
of Borwein or Brent/Salamin, I was amazed to not find it anywhere
! But in my concern of exhaustiveness, I could not miss to notice it.
V.b) Algorithm of J. and P. BORWEIN (1987)
This algorithm was published in Pi and the AGM. I will give the detailed proof
and by estimating the efficiencecy... It is given under the form :
We will set us during all the proof on a compact K of ]0,1[
With the notations of the previous parts, let us pose for n1 :
Let us show that :
|yn1, zn1, nN*
(yn) and (zn) uniformly converge towards 1 on K
* According to III.a).2). and the definition of yn and zn, UnVn, so yn1
* nN, x]0,1[
according to III.a).2). and Vn(x)>V0(x)=x.
one has x->1/x-1 is bounded (continuous on a compact) by a certain MR+*, so
by this way, (yn) uniformly converges towards 1 on K
* Let us show by a recurrence on nN* that zn1
n=1 : z1=x-1/2>1 on ]0,1[
Let us suppose the result for a certain nN*
that show us the relations of recurrence for (yn) and (zn) !
because zn1 by the hypothesis of recurrence and yn1 according to previously,
in consequence this ends the recurrence...
For n1, zn+1-yn+1 is of the sign of :
zn+1-yn1/2 is also af the sign of :
now yn1 so yn1/2yn and finally :
so 0<yn+1-1<zn+1-1<yn-1 and :
The uniform convergence of (yn) towards 1 on K insures, by this way, the uniform convergence of (zn) towards 1 on K...
V.b).2) Let us show now that (U'n) and (V'n) uniformly converge on K. This is certainly the hardiest to obtain, but it works
and it is the main thing !!
Given x]0,1[, nN*,
zn1, so U'nV'n and as U'n+1=(U'n+V'n)/2 one has U'n+1U'n
so (U'n) is increasing
V'n+1(x)-V'n(x)= so te sign of V'n+1(x)-V'n(x) is the one of :
By dividing by U'n(x)V'n(x)>0 one obtains :
now, according to a), yn1/2-1yn-1zn-1, and (zn) uniformly converge towards 1 on K so at a certain rank n0, for nn0,
xK, 0<zn(x)-1<1/2, so :
so for nn0 and xK, V'n+1(x)V'n(x) and finally :
This being, given ß>0
(zn) uniformly converges towards 1 on K, so it exists n1N such that :
nn1 => 0supK(zn(x)-1)<ß*Vno(x)-1
with nMax(n0,n1) and since (V'n) is decreasing according to above (eh yes!), one has for nMax(n0,n1) V'n(x)V'no(x), so :
x]0,1[, (U'n(x) and (V'n(x)) are adjacent series and converge towards the same limit that we
will note µ(x).
So one has :
For nMax(n0,n1) one has :
So the series (U'n) and (V'n) uniformly converge on K towards µ(x)
V.b).3) Let us build the series (fn)
(Un) uniformly converges (so simply) on K towards f and (U'n) uniformly converges on K so his limit is f' on ]0,1[
Let us pose
One has :
that concludes the proof. Ah ! what a beautiful result !