・a[n+1]=a[n]+f(a[n])の数列の漸近挙動(2019/3/31)
数列 a[n+1]=a[n]+1/a[n] で定義される数列は a[n]≒sqrt(2n)な挙動をするということに以前出会いました。
http://searial.web.fc2.com/aerile_re/suretu.html
その直接的な証明はとても煩雑なものでした。
最近になって、もう1つ、b[n+1]=b[n]+1/exp(b[n]) で定義される数列は b[n]≒log(n)な挙動をするということに出会いました。
(下記1つ目のリンク)
今回、これらの挙動をより抽象的な視点から示す方法を実現することができたという経緯です。
・2019/03/31 mel***さんによる追加の指摘点を修正
[https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11205429386]
・2019/04/10,11 ts3***さんによる追加の指摘点を修正
[https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11205653871]
(丁寧に読んで修正点を指摘してくださりありがとうございました。)
次のように状況を設定する:
f(x)はx>0で定義されていて、f(x)は正で単調減少で0に収束、f'(x)は単調増加で0に収束するとする。
t>0で定義されて dx/dt = f(x(t)) を満たす関数x(t)があったとする。
このとき、数列 b[n+1]=b[n]+f(b[n]) について b[n]-x(n)は0に収束することを示すのが本題であり下記で実現する。
初項b[1]は正であれば何でも良い。特に
f(x)=1/x, x(t)=sqrt(2t) とおくと上記の数列
f(x)=1/e^x, x(t)=log(t) とおくとリンク先のもう1つの例となる。
-------
数列b[n]は単調増加であり、fが正だから、収束しない=∞に発散することに注意する。
[αに収束すると仮定するとα=α+f(α)が成り立つがこれはf≠0と矛盾]
従ってnが十分大きい時、f(b[n]), f'(b[n])は十分0に近いと考えることができる。
本題を示すのに、次の命題に帰着する。
<命題>
2つの数列 a[n+1]=a[n]+f(a[n])-w[n], b[n+1]=b[n]+f(b[n]) の漸近挙動を比較する。
d[n] = b[n]-a[n] とおく。
(0) 「n≧N ならば -1<f'(a[N])」を満たすNが存在する。
(1) 上記のNに対して d[N]≧0 ならば n>N では常に d[n]>0 である
(2) さらにw[n]は各項が非負で、Σ[n=1,∞]w[n]<∞を満たすとする。d[n]は0に収束する。
(3) しかし実は、d[N]≧0 という仮定がなくても、
w[n]は各項が非負で、Σ[n=1,∞]w[n]<∞を満たすならば、d[n]は0に収束する。
===============
<補題1>
a[n]は∞に発散する。
-------
・あるMに対して常にa[n]≦Mだと仮定する。
そうするとfの性質からf(a[n])≧ε>0 となるεが存在する。
これらの条件は、a[n+1]-a[n] = f(a[n])-w[n]、w[n]→0と矛盾する。
従ってa[n]はいくらでも大きくなる
・次に任意のMをとり、n≧Nならばa[n]≧Mを満たすNが存在することを示す。
Σw[n]は有限値なのでWとおける。
そこで先の議論より M+W よりも大きくなるようなa[n]が存在する。
漸化式により、これ以降のa[n]はMを下回ることが無い。
-------
<補題2>
Σf'(b[n]) は -∞に発散する。
-------
f(b[n+1])-f(b[n]) = f'(c)*(b[n+1]-b[n]) = f'(c)*f(b[n])
となるb[n]<c<b[n+1]が存在する。
f'(b[n]) < f'(c) < 0 が成り立つので
f'(b[n]) < {f(b[n+1])-f(b[n])}/f(b[n]) < 0 が言える
n≧Nならばf'(b[n])は-1より大きいと考えるのであった。
その範囲で両辺に log(1+x)を作用させることができる。
log( 1+f'(b[n]) ) < log ( 1 + {f(b[n+1])-f(b[n])}/f(b[n]) ) = log f(b[n+1]) - log f(b[n])
両辺のn=Nから∞までの和をとると右辺の和は「望遠鏡和」で-∞に発散する。
従って Σlog( 1+f'(b[n]) )も-∞に発散する
ここで log( 1+f'(b[n]) ) = f'(b[n]) + O(f'(b[n])^2)
なので Σlog( 1+f'(b[n]) ) = Σf'(b[n]) + ΣO(f'(b[n])^2)
先の結果より左辺は-∞に発散するから右辺もそうであり、
そのためには Σf'(b[n]) が-∞に発散しなければいけない
========
<命題の証明>
(0) f'(x)は0に収束することを仮定しているので、
x≧X ならば -1<f'(X)<0 となるようなXをとることができて
従って<補題1>よりn≧Nならばa[N]≧X となるようなNをとれる。
--
(1) f(b[n])-f(a[n]) = f'(c[n])*(b[n]-a[n]) を満たす c[n]がa[n]とb[n]の間に存在する。
d[n+1] = d[n]+f'(c[n])d[n]+w[n] ということになる。
すなわち d[n+1] = (1+f'(c[n]))d[n] + w[n] が成り立つ
数学的帰納法により d[N]≧0 ならば d[N+1]≧0 を示せば良い。
d[N]≧0という仮定より、a[N]≦c[N]≦b[N] の大小関係であり、
従って -1<f'(a[N])<f'(c[N])<0 だから w[N] ≦ d[N+1] ≦ d[N] + w[N] が言える
ここから特に、d[N+1]≧0 が従うので目的が達成される。
--
(2) 上記の議論から n>Nに対して常に w[n] ≦ d[n+1] ≦ d[n] + w[n] が成り立つ
d[n+1]-d[n] ≦ w[n] と変形すれば Σw[n]<∞ という条件よりd[n]は上に有界であることも言える。
d[n+1]-d[n] = f'(c[n])d[n]+w[n] の両辺の無限和を考える。
Σ(d[n+1]-d[n]) と Σw[n] は有界であるから Σf'(c[n])d[n]も有界であることが要求される。
もしあるMに対してn≧Mで常にd[n]≧αだと仮定すると<補題2>よりΣf'(c[n])d[n]は発散し矛盾する。
(f'(x)が負で単調増加であるから f'(c[n])≦f'(b[n])<0 であることを使った。)
従って、どんなMに対してもn>Mの範囲にd[n]<αとなるようなnが存在する。
任意の正の数βに対して:
Σ[n=M..∞] w[n] <β/2 となるようなMをとり、α=β/2に対して上記を適用する。
すなわちn>Mの範囲に d[n]<β/2 となるようなnが存在する。
これと d[n+1] < d[n] + w[n] により、この先すべてのd[n]がβより小さいことが言える。
すなわちd[n]は0に収束することが言えた。
--
(3) b[n]は無限に発散する数列なので、b[N+M]>a[N]となるMをとることができる。
そこでb'[n] = b[n+M] とおくと、b'[N]>a[N]が成り立つことになる。
ここで、b[n+1]の階差数列g(b[n])=b[n+1]-b[n] はfに関する条件より0に収束するので
これを有限回繰り返すことで、b[n]-b'[n]も0に収束する。
従って、b'[n]-a[n]→0 と b[n]-a[n]→0 は同値である。
ここで b'[n]-a[n]→0 のほうは(2)を使って示せるので、b[n]-a[n]→0も成り立つのである。
=======
<本題(再掲)>
fを冒頭に課せられた条件を満たす関数とする。
t>0で定義されて dx/dt = f(x(t)) を満たす関数x(t)があったとする。
b[n+1]=b[n]+f(b[n]) で定義される数列について b[n]-x(n)は0に収束する。
-------
x'(t)=f(x(t))は条件より正なので、x(t)は単調増加で、lim[t→∞]x(t)=∞である。
[αに収束すると仮定すると 0 = dx/dt[x=α] = f(α) で矛盾する]
またx(t)が単調増加なのでx'(t)=f(x(t))はtの関数としても単調減少である(後で使う)
x(n+1) = x(n)+f(x(n))-w[n]
b[n+1] = b[n]+f(b[n])
を満たすようなw[n]を定めて漸近挙動を比較する。
x(n)をa[n]の役割をさせて命題を適用することを考える。
すなわち、w[n]の各項が非負で、Σw[n]が有限値であることを示せば良い:
-w[n] = x(n+1)-x(n)-f(x(n))
= x'(u[n])-f(x(n)) を満たすような n≦u[n]≦n+1が存在する
= x'(u[n])-x'(n)
= x"(v[n])*(u[n]-n) を満たすような n≦v[n]≦u[n]≦n+1 が存在する
従って 0≦w[n]≦-x"(v[n])
ここで x"(t) = f'(x(t))*x'(t) は (負で単調増加)*(正で単調減少) より 負で単調増加なので
Σ[n=2..∞]w[n]
≦ Σ[n=2..∞](-x"(v[n]))
< Σ[n=2..∞](-x"(n))
< ∫[t=1..∞](-x"(t))dt
= x'(1)-x'(∞)
= x'(1) = f(x(1)) は有限値
従って<命題>を適用することができて、b[n]-x(n)→0 が言えた。
ノート一覧