2017年5月31日水曜日

微積分I演習(物理学類)(第6回)

[場所1E103(金曜日5限)]

HPに行く
manabaに行く

今回は
  • ロピタルの定理
  • マクローリン展開
についてやりました。
宿題は後でmanabaを通じて配布するとしていましたが、先日manabaにおきました
で受け取ってください。
Web掲示板にも告知がしてあると思います。


ロピタルの定理の使い方と、マクローリン展開のやり方は
お隣の数学類でのページに書いたのでそちらを参照してください。
2017年微積分I演習数学類(第6回)(リンク)
今回のやり方の説明は、このリンクと合わせてみていただければと思います。


また、このページを利用して、今回の授業中に
やっていた問題が途中になったので下の方でその計算を書きました。

マクローリン展開のやり方補足

また、説明のマクローリン展開の部分で、いきなり、
$\lim_{x\to 0}\frac{e^x-1}{x}$ の極限を考え出したことがよくわからなかった人がいたようです。

まず、$e^x$ のマクローリン展開、つまり、
$$e^x=a_0+a_1x+a_2x^2+...+a_nx^n+o(x^n)$$
を得たい時、上の極限を考えたのは、この展開の最初の項を求めるために考えた
のです。
実際、この計算はちょうど、$x=0$ での微分係数を求めることと一致します。

やってみるとこんな感じです。
まず、$a_0$ を求めたいとします。
そのためには、両辺に $x=0$ 代入してやればよいです。
代入した結果、$e^0=a_0$ となるので、$a_0=1$ がいえたことになります。

次に $a_1$ を求めます。
このとき、求めた $1$ を左辺に移項して、$e^x-1=a_1x+a_2x^2+...+a_nx^n+o(x^n)$ として、さらに、全体を $x$ で割ってやります。そうすると、
$\frac{e^x-1}{x}=a_1+a_2x+....+a_nx^{n-1}+o(x^{n-1})$ が得られます。

このとき、右辺に、$\frac{e^x-1}{x}$ なる式が現れていることに注意してください。
この両辺に $x=0$ を代入してやります。左辺は、$\lim_{x\to  0}$ をすることに対応します。

この極限は、ちょうど関数 $e^x$ の $x=0$ での微分係数を求めていることになります。

ゆえに、代入した結果、$1=a_1$ であることがわかります。

つまり、マクローリン展開の最初の2項は、
$$e^x=1+x+a_2x^2+a_3x^3+....+a_nx^n+o(x^n)$$
であるとわかるのです。

また、2番目以降も、係数がわかった部分を左辺に移項して、$x^2$ を全体で割り、
$x=0$ を代入してやることで求まります。

具体的な計算は、上のリンクに同じことを書きましたので省略します。

ロピタルの定理の計算例について
授業中に途中までになった計算を最後まで書いてみます。

$$\lim_{x\to 0}\frac{\sin x\tan x-x^2}{\sin^4x}$$
の計算です。まず、ロピタルの定理を当てはめて、

$$\lim_{x\to 0}\frac{\cos x\tan x+\sin x\frac{1}{\cos^2x}-2x}{4\sin^3x\cos x}$$
$$=\lim_{x\to 0}\frac{\cos^3 x\tan x+\sin x-2x\cos^2x}{4\sin^3x\cos^3 x}$$
$$=\lim_{x\to 0}\frac{\cos^2 x\sin x+\sin x-2x\cos^2x}{4\sin^3x\cos^3 x}\hspace{1cm}(1)$$

となります。
この極限が不定形なので、分母の $4\cos^3x$ などは除いてロピタルの定理を適用させると、
$$\lim_{x\to 0}\frac{-2\cos x\sin^2 x+\cos^3x+\cos x-2\cos^2x+4x\cos x\sin x}{3\sin^2x\cos x}$$
$$=\lim_{x\to 0}\frac{2\cos x(\cos^2 x-1)+\cos^3x+\cos x-2\cos^2x+4x\cos x\sin x}{3\sin^2x\cos x}$$
$$=\lim_{x\to 0}\frac{3\cos^2 x-2\cos x-1+4x\sin x}{3\sin^2x}\hspace{1cm}(2)$$
となります。(分母の一部を除いて考える理由は、上の数学類のblogのリンクを見てください。)

分母の $3$ を除いてさらにロピタルの定理を使うと、
$$\lim_{x\to 0}\frac{6\cos x(-\sin x)+2\sin x+4\sin x+4x\cos x}{2\sin x\cos x}$$
$$=\lim_{x\to 0}\frac{-3\cos x\sin x+3\sin x+2x\cos x}{\sin x\cos x}$$
$$=\lim_{x\to 0}\left(-3+\frac{3\sin x+2x\cos x}{\sin x\cos x}\right)\hspace{1cm}(3)$$

となり、和の後半部分を考えると、
$$\lim_{x\to 0}\frac{3\sin x+2x\cos x}{\sin x}\hspace{1cm}(4)$$
の部分にロピタルの定理を使って、
$$\lim_{x\to 0}\frac{3\cos x+2\cos x-2x\sin x}{\cos x}=5$$
となります。
ゆえに、(4) の極限がもとまって、
$$\lim_{x\to 0}\frac{3\sin x+2x\cos x}{\sin x\cos x}=5$$
であるから、(3)の極限が求められ、
$$\lim_{x\to 0}\left(-3+\frac{3\sin x+2x\cos x}{\sin x\cos x}\right)=2$$
となります。また、(2) の極限も求まり、
$$\lim_{x\to 0}\frac{3\cos^2 x-2\cos x-1+4x\sin x}{3\sin^2x}=\frac{2}{3}$$
となります。ゆえに、(1) の極限が求められたことになり、 
$$\lim_{x\to 0}\frac{\cos^2 x\sin x+\sin x-2x\cos^2x}{4\sin^3x\cos^3 x}=\frac{1}{6}$$
だということがわかります。

そしてさらに戻れば、最初の極限が
$$\lim_{x\to 0}\frac{\sin x\tan x-x^2}{\sin^4x}=\frac{1}{6}$$
だということがわかります。

微積分I演習(数学類)(第6回)

[場所1E103(水曜日4限)]

HPに行く
manabaに行く

今回は
  • ロピタルの定理
  • マクローリン展開
についてやりました。



ロピタルの定理
ロピタルの定理とは、不定形の極限の計算にとても有効です。
極限操作が不定形であるとは、$\lim_{x\to a}\frac{f(x)}{g(x)}$ の極限で
$x\to a$ となった時に、分母と分子が両方 $0$ に行くか、両方 $\pm \infty$
に行くかということです。

ロピタルの定理を使うと、多くの不定形の極限の計算が楽になります。
それ以前の不定形の極限の計算は、関数を約分をするとか、微分の定義を使うくらいしか
道具ありません。

例えば、
$\lim_{x\to 0}\frac{e^x-1}{x}$ の計算は、ちょうど $e^x$ の $x=0$ の定義になっているから、$e^x$ を微分して、$x=0$ を代入することで、$1$ と求まります。

また、高校の頃に出て来た不定形の極限では、$\lim_{x\to 0}\frac{\sin x}{x}=1$ が
ありますが、これも、$\sin x$ の $0$ での微分係数を求めていることになりますから、
$\cos 0=1$ であることからわかります。

ロピタルの定理を書いておきます。

定理(ロピタル)
$a$ を実数もしくは無限大とする。
$f(x),g(x)\to 0$ $(x\to a)$ もしくは、
$f(x),g(x)\to \pm\infty$ $(x\to a)$ が成り立つとする。
もし、$f,g$ が1回微分可能であり、$\lim_{x\to a}\frac{f'(x)}{g'(x)}$ が存在したとすると、
$$\lim_{x\to a}\frac{f(x)}{g(x)}=\lim_{x\to a}\frac{f'(x)}{g'(x)}$$
がなりたつ。


まず、分母と分子の導関数の比の極限が存在すれば、一致するという
ことです。ですので、存在しなければ求めることはできません。
また、分母と分子の導関数の比もまた不定形であれば、再びロピタルの定理を
適用させることができます。

そのようにして、何回かロピタルの定理を適用させることで、不定形の極限を求めることができます。しかし、可能性として、何回もロピタルの定理を適用させても
不定形しか出てこないこともあります。
そのような場合、ロピタルの定理では求めることはできません。

簡単な例だと、$\lim_{x\to \infty }\frac{e^{x}}{e^{2x}}$ があります。
この場合、$e^{x}$ を約分してやることで、$0$ に収束することがわかります。

例えば、
$\lim_{x\to 0}\frac{\tan x-x}{\sin^3 x}$ を求めるとします。
導関数の比の極限は、$\lim_{x\to 0}\frac{\frac{1}{\cos^2 x}-1}{3\sin^2x\cos x}$
となり、これも不定形となります。

一度、分母を払って変形をすると、
$$\lim_{x\to 0}\frac{1-\cos^2 x}{3\sin^2x\cos^3 x}=\lim_{x\to 0}\frac{\sin^2 x}{3\sin^2x\cos^3 x}=\lim_{x\to 0}\frac{1}{3\cos^3 x}=\frac{1}{3}$$
となります。

他にもやってみます。
$\lim_{x\to 0}\frac{x^2}{\cos^2 x-1}$ を計算します。
$$\lim_{x\to 0}\frac{2x}{2\cos x(-\sin x)}=\lim_{x\to 0}\frac{-1}{\cos x}\lim_{x\to 0}\frac{x}{\sin x}$$
なります。ここで、極限を分離した理由は、不定形でない部分をくくりだすためです。

後半部分は再度ロピタルの定理を当てはめればよいですが、この場合、
$\sin x/x$ の極限だから、ロピタルの定理は省略して、$1$ に収束するとして結論づけます。
よって、全体として、$\lim_{x\to 0}\frac{x^2}{\cos^2 x-1}=-1$ となります。


マクローリン展開

次にランダウの記号を用いたマクローリン展開をします。
まず、
$e^x$ の $x=0$ での微分の式
$\lim_{x\to 0}\frac{e^x-1}{x}=1$
を用います。

このとき、右辺を移項して、
$\lim_{x\to 0}\frac{e^x-1-x}{x}=0$ が成り立つので、
$e^x=1+x+o(x)$ が成り立ちます。
次に、この極限の式に $x$ で割って、
$\lim_{x\to 0}\frac{e^x-1-x}{x^2}$ を計算すると、ロピタルの定理から、
$\lim_{x\to 0}\frac{e^x-1}{2x}$ となり、この極限は、上の微分の定義式から、$\frac{1}{2}$
となります。
ゆえに、$\lim_{x\to 0}\frac{e^x-1-x-\frac{1}{2}x^2}{x^2}=0$ が言えます。
これは、
$e^x=1+x+\frac{1}{2}x^2+o(x^2)$
を意味しています。この流れで繰り返せば、次は、
$e^x=1+x+\frac{1}{2}x^2+\frac{1}{6}x^3+o(x^3)$
が成り立ち、続けていけば、帰納的に
$$e^x=1+x+\frac{1}{2!}x^2+\frac{1}{3!}x^3+\cdots +\frac{1}{n!}x^n+o(x^n)$$
が言えます。

この最後の帰納的にはの部分は、帰納法を用いて証明が本当はいります。
宿題ではその部分を示してください。

また、このように繰り返し作業でマクローリン展開を求める方法は
ランダウの記号やロピタルの定理の適用することで、納得するための
やり方です。

マクローリン展開の公式を習った後であれば、その公式を使って
計算した方が本当は早いです。

2017年5月29日月曜日

数学外書輪講I(第5回)

[場所1E501(月曜日5限)]

HPに行く
manabaに行く

来週(5/29)は休講ですので、今週(5/22)はレポートを出しました。

レポートは、数学の問題を解くということではなく、

MatousekのMiniature 5の要約を作ってくださいということです。


要約ということは...

外書輪講の授業中によく言っていますが、セミナー発表は英文和訳ではないということです。
つまり、ここは英語科でもなんでもなく、筆者の気持ちになって文脈を読み取るとか
言外の意味をしるとかそのようなことは想定されていません。

むしろ、論理的に筆者の数学のアイデアをわかりやすく説明をするという
科学的なアクティビティです。


Miniature 5の内容について

これは、簡単にいえば符号理論の話です。
符号理論(coding theory)とは、Wikipedia(符号理論)にあります。

何か情報を相手に送信し、それを受信をしたり、CDのように書き込まれた情報を
読み取ったりするときに、以下に書くように、一度符号(code)と呼ばれる
列に変換してから送ります。どうして、情報をそのままにして送らないのか?
は以下のような理由があります。

情報は電気信号、つまり電気のオンとオフの状態として送ります。
つまり、0と1からなる数字を電気信号として送るのです。
デジタル機器やパソコンなどにも0,1からなる数字とその電気信号が使われています。

しかし、このような信号を用いて大量の情報を送るとすると、経験上、
必ずバグなど間違った情報が入ったり、間違った情報が送られてしまうことがあります。

例えば、計算機で正しいプログラムを組んで計算を走らせても、
途中にバグが見つかりプログラムがストップしてしまったり、
CDの細かな傷のために、再生できないということにもなります。

毎回毎回プログラムが止まったり、買ったばかりのCDが聞けないということだと
話になりません。
そこで、たまたま間違っが情報がはいっても、それが自己修正能力を兼ね備えた
プログラムであれば、間違った信号を直しながら作業を続けることが
できるはずです。この自己修正のメカニズムが誤り訂正符号理論が必要となるのです。

そのアイデアとして、バグ修正のために、オリジナルのメッセージに
一旦冗長なメッセージ(少し長めのコード)を含ませておいて、
それを同時に送り、受信先でその冗長コードから
もとのオリジナルのメッセージを切り取って受信するという
方法がとられます。訂正のために付け加えた余分なコードの
ことをここでは訂正コード(訂正ディジット)ということにします。



日常的に我々が行っているバグ修正は、例えば言語です。
アルファベットやひらがななどで書かれた文章に誤植があったときに、
前後関係から、また、辞書に載っている単語の中でという縛りの元、
ほぼ一意に誤りを直すことができます。

また、例えば、滑舌の悪い人の話を聞くときにも、話の内容や状況、
そのニュアンスや単語の縛りなどから、聞き取りにくいところを
補完しながら聞くことができます。

仮に、アルファベットの並び全てのパターンに何らかの意味をもつ単語にしておいた
とすると、間違えたり、聞き取りにくい時に、復元することがかなり困難になる
のはずです。そのようなバグ修正ができる範囲の文字の総数として
アルファベットの26文字が選ばれているともいえます。

言語能力が高い人というのは、この修正能力が優れていると言っても
よいかもしれません。


誤り訂正コードの話に戻します。冗長なコードを使ってどのように訂正されているのか
を考えます。下のマーカスの本の中で説明しているコードの例を用います。

次のような、8マスに入る0と1からなる数列(とうか行列)を考えます。
ここでは、2個の元からなる2元体 ${\mathbb F}_2$ からなる数と考えても良いです。
つまり、$1+0=1$ かつ、$0+0=0$ かつ $1+1=0$ を満たす足し算からなる数体です。

011
110
10

今、オリジナルの情報(伝えたい情報)は左上の4つの $2\times 2$ 行列 $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ とします。ここで、誤り訂正のための成分は、
各行の3つめと各列の3つ目です。つまり、(1,3) 成分の1、(2,3)成分の 0、
(3,1)成分の 1、(3,2)成分の 0 です。この数は、各行を足し算してできた値を
置いています。例えば、(3,2)成分の 0 は、上の (1,2)成分と(2,2)成分の1 から
$1+1=0$ となります。これらの4つのディジットは本当はなくても、4つの
文字を読めばよいはずなので、冗長です。
つまり、それらは訂正ディジットということになります。

しかし、例えばコードが間違って伝わると、

101
100
10

のようなコードも伝わってしまったりします。このとき、各行と各列の関係から
間違いコードであることが判別できます。さらに、間違いを一つだけ
修正できることも分かります。

この場合だと、
間違っている行は、2行目で、
間違っている列は、1列目になります。

なので、間違っているのは、(2,1)成分だということになります。
つまり、(2,1)成分の1を0に直せばよいということになります。
また、間違っているのが1箇所だけであれば、訂正ディジットを直せばよいということになります。


訂正したら完全に正しいメッセージになるか?
ここで分かって欲しいことは、間違いを訂正したものは、確実に正しいメッセージ
とはかぎらないということです。おそらくそこに間違いがあるだろうと
推定されるだけです。

例えば、上の例において、正しいコードに、
オリジナルのメッセージの部分の1と0を全て入れ替えたコード
(訂正ディジット同じまま)は4つも誤りがあるくせに、
そもそも間違いかどうかさえわかりません。

また、行と列全てにおいて間違いが発見されるとすると、
2箇所以上の誤りを含んでおり訂正できません。

ハミングの方法

上の方法では、4つの文字のメッセージに4つの文字を付け加えてやると、1つの
文字の修正ならできるということになります。

しかし、ハミングはそれより効率の良い方法を考えたのです。

それが今回読んでもらう話です。
そのアイデアが

  • ハミング距離
  • 線形代数

です。

まず、コードとはアルファベットの全ての並び(もしくは0,1の全ての並び)ではなく
その部分集合を指定したものです。
つまり、コードから外れてしまったものから本当のコードに復元する操作が符号訂正理論ということになります。


 ハミング距離とは、コードとコードのうち、アルファベットの違う部分の
数を数えたものです。n こまで訂正できる(correct n errors) とは、
間違いがあった(コードから外れた)ときに、その間違いコードから
推定される正しいコードで n 個のアルファベットまで訂正したものが
たかだか一つ存在するということです。
(もしなければ、一番近いコードにするか、もう一度送ってもらって比べるか?など
になります。)

 今の場合、コードとなりうるのは、${\mathbb F}_2$ 上のベクトル空間の、
部分ベクトル空間です。
そのベクトル空間の基底を並べた行列のことを generator matrixとよび、
その部分ベクトル空間を定めている係数行列のことをParity check matrixといいます。

書いてある通りそのような部分ベクトル空間を作るには、オリジナルのメッセージが
4であるのに対して、3つの訂正ディジットを用意すればよいということが
分かります。

さっきの最初の例と比べてみると、1つだけ、文字数が減っています。
つまり、送る量として節約できたということになります。


なお、このハミングが開発したコードはその修正能力の高さから、
彼の同僚は、特許をとって大儲けしようとしたようです。しかし、純粋数学者であった
ハミングは全く興味がなかったようですね。Marcusの本にも
Hamming was keen to get the new codes into print. However, because he was working for a commercial company and the codes clearly had very significant commercial implications, Bell Labs were not so eager to go public. They wouldn’t let Hamming release the details until they had got the codes patented. But Hamming was rather sceptical about whether it was possible to patent pure maths: ‘I didn’t believe that you could patent a bunch of mathematical formulas. I said they couldn’t. They said, “Watch us.” They were right. Things that you shouldn’t be able to patent-it’s outrageous-you can patent.’
と書いています。これを訳した日本語(下記の参考文献)
ハミングは、ぜひこの新たなコードについての論文をまとめたいと思った。しかし所栓は民間企業に勤める身であり、しかもこのコードは莫大な利益を生む可能性があったので、ベル研究所はこの件を公にしたがらなかった。まず特許を取って、それから詳細を発表させればいい。一方ハミングは、純粋数学で特許が取れるはずがないと考えていた。「数式の束で特許が取れるとは、思っていなかった。無理だっていったんだがね。連中は『まあ見てろ』といった。そして連中のいうとおりになった。特許を与えるべきではないものにまで特許が与えられるんだから、まったくひどい話だ。」
としています。

この話はさらに有名な後日談があります。
この特許騒ぎで、そのハミングの理論が世にでるのが遅くなった
ため、その理論から広がる数学的に大変興味深い発見のための
数学的な研究に完全に出遅れてしまいます。(下の参考文献を参照)。
これらの発見はもしかしたらハミングがしていたかもしれません。

ゴレイは、ハミングと共同研究者のシャノンの論文に書いたことに着想を得て
独立に符号の理論に到達し、研究成果を発表しました。

彼は、符号の理論を発展させ、ハミングさえも見つけられなかった、
符号理論と、24次元細密充填問題、リーチ格子、有限単純群などの関係を発見するのです。
その時見つかった符号は今ではゴレイコード(Golay code)と言われています。
ゴレイにしてみれば、長年温めて来た研究に対して、他の論文から着想を得ただけで、
学問の自由さからして、これは正当なクレジットだと言わざるを得ません。
もちろんハミングが最初に符号理論をやり始めたということにも異論はありません。

数学のこのような熾烈な競争はよくあることで、目の付け所というか、
センスというか、同じことをやっていても、
「あ、その方向があったか。思いつかなかった。」
という悔しい思いをすることは少なくありません。諦めずに考え続けることと、
さらにもう一歩だけ進める力が必要となるのです。
「こんなに面白いんだから何かできるに違いない!」というその人にしか見えない
特別な思いに他なりません。

  1. Marcus du Sautoy, Symmetry: A Mathematical Journey,  Harper/HarperCollins
  2.  マーカス・デュ・ソートイ(冨永星訳) シンメトリーの地図帳 (新潮文庫)


2017年5月23日火曜日

微積分I演習(物理学類)(第5回)

[場所1E103(金曜日5限)]

HPに行く
manabaに行く

今回は
  • ランダウの記号
  • ライプニッツの公式
を行いました。

ランダウの記号
ランダウの記号はこのブログで多く書いてきました。

例えば今、お隣の数学類で今年度行っている授業のブログ
2017年微積分I演習数学類第4回(リンク)
2017年微積分I演習数学類第5回(リンク)

においてもあります。
上の数学類の第5回のブログにも書いたように、ランダウの記号の計算規則(1)-(5)
があり、下にもう一度書いておきます。
それは、今回の授業中においても説明しました。

まず、ランダウの記号 $o$ は以下のようにして定義されます。
関数 $f(x),g(x)$ に対して、
$$\lim_{x\to a}\frac{f(x)}{g(x)}=0$$
をみたすとき、$f(x)=o(g(x))$ とかく。


ここでは、$x\to a$ で $g(x)\to 0$ であると仮定します。
意味としては、関数 $f(x)$ は、$g(x)$ より速く
$0$ に収束するということです。

例えば、微分の定義を用いれば、$\frac{e^x-1-x}{x}\to 0$ $x\to 0$ であるから、
$e^x-1-x=o(x)$ と書かれます。つまり、関数 $e^x-1-x$ は、$x=0$ において
一次関数 $x$ より速く $0$ に収束するということになります。

よって、今の例を一般化することで、$f(x)$ が $x=a$ で微分可能であること
$$\lim_{x\to 0}\left(\frac{f(x)-f(a)}{x-a}-f'(a)\right)=0$$
を書き直せば、$f(x)-f(a)-f'(a)(x-a)=o(x-a)$ が成り立ちます。

また、式を一部移項すれば、
$$f(x)=f(a)+f'(a)(x-a)+o(x-a)$$
とも書き表されます。

$o(x-a)$ は、$x=a$ において $x-a$ より速く $0$ に小さくなる関数なので、
関数 $f(x)$ は、$x=a$ の近くにおいて接線 $f(a)+f'(a)(x-a)$
にかなり近いということがいえます。

実際、接線とは、$x=a$ において関数 $y=f(x)$ に最も近い一次式のことですので、
直感とも合います、接線の関数のことを関数の1次近似ともいいます。
そして2次近似は、今回提出してもらった宿題にもあったように、
$$f(x)=f(a)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2+o((x-a)^2)$$
に現れる2次式 $f(a)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2$ です。

ランダウの記号の計算規則

(1) $x^mo(x^n)=o(x^{n+m})$
(2) $\forall c\in {\mathbb R}, co(x^n)=o(x^n)$
(3) $x^{n+1}=o(x^n)$
(4) $o(x^n)+o(x^m)=o(x^n)\ \ \ (n\le m)$
(5) $o(x^n)o(x^m)=o(x^{n+m})$

証明も書いておきます。
(1) $f(x)=o(x^n)$ とすると、$\lim_{x\to 0}\frac{x^mf(x)}{x^{n+m}}=\lim_{x\to 0}\frac{f(x)}{x^n}=0$
(2) $c\in {\mathbb R}$ として、$f(x)=o(x^n)$ とすると、$\lim_{x\to 0}\frac{cf(x)}{x^n}=c\lim_{x\to 0}\frac{f(x)}{x^n}=0$
(3) $\lim_{x\to 0}\frac{x^{n+1}}{x^n}=\lim_{x\to 0}x=0$
(4) $f(x)=o(x^n)$ $g(x)=o(x^m)$ とすると、$\lim_{x\to 0}\frac{f(x)+g(x)}{x^n}=\lim_{x\to 0}\left(\frac{f(x)}{x^n}+x^{m-n}\frac{g(x)}{x^m}\right)=0$
(5) $f(x)=o(x^n), g(x)=o(x^m)$ とすると、$\lim_{x\to 0}\frac{f(x)g(x)}{x^{n+m}}=\lim_{x\to 0}\frac{f(x)}{x^n}\frac{g(x)}{x^m}=0$

今回の宿題はこれらを使って、近似多項式を作ってください。

ライプニッツの公式
ライプニッツの公式とは、関数の積の $n$ 回微分を計算する公式ですが、
これは、もう少し授業中に計算例をやっておけばよかったと思いました。

ライプニッツの公式とは、
$$(f(x)g(x))^{(n)}=\sum_{k=0}^n{}_nC_kf^{(k)}(x)g^{(n-k)}(x)$$
となります。

例えば、問題5-1(4) なら、公式から、
$((x^2+1)e^{-x})^{(n)}=\sum_{k=0}^n(x^2+1)^{(k)}(e^{-x})^{(n-k)}$
となります。$(x^2+1)^{(k)}$ は、

$k=0$ のときに、$x^2+1$
$k=1$ のときに、$2x$
$k=2$ のときに、$2$
$k\ge 3$ のとき、$0$
となります。

また、$(e^{-x})^{(n-k)}=(-1)^{n-k}e^{-x}$
なので、
$n\ge 2$ のとき、
$$((x^2+1)e^{-x})^{(n)}=(x^2+1)(-1)^ne^{-x}+n\cdot 2x(-1)^{n-1}e^{-x}+\frac{n(n-1)}{2}2(-1)^{n-2}e^{-x}$$
$$=(-1)^n((x^2+1)-2nx+n(n-1))e^{-x}=(-1)^n(x^2-2nx+n^2-n+1)e^{-x}$$
となります。

また、$n=1$ のとき、
$$-(x^2-2x+1)e^{-x}$$
となります。よって、どちらの場合でも統一して、

$$((x^2+1)e^{-x})^{(n)}=(-1)^n(x^2-2nx+n^2-n+1)e^{-x}$$
として書くことができます。


問題5-1の(5)(6)も同様にできると思います。

また、問題5-1の(2) は、$(e^{-x}\sin x)^{(n)}$
の計算で、少々めんどくさいですが、
$n=1$ のとき、 $e^{-x}(\cos x-\sin x)$
$n=2$ のとき、 $-2e^{-x}\cos x$
$n=3$ のとき、 $2e^{-x}(\cos x+\sin x)$
$n=4$ のとき、 $-4e^{-x}\sin x$
$n=5$ のとき、 $-4e^{-x}(\cos x-\sin x)$
$n=6$ のとき、 $8e^{-x}\cos x$
.....
となっていきます。

つまり、$(e^{-x}\sin x)^{(4)}=-4e^{-x}\sin x$ が帰納的に成り立ちます。
周期4で同じ関数のマイナス4倍になります。

なので、
$$(e^{-x}\sin x)^{(n)}=\begin{cases}(-4)^me^{-x}(\cos x-\sin x)&n=4m+1\\-2(-4)^me^{-x}\cos x&n=4m+2\\2(-4)^me^{-x}(\cos x+\sin x)&n=4m+3\\(-4)^me^{-x}\sin x&n=4m\end{cases}$$
とまとめられます。

また、有理式の微分も、
$$\frac{1}{x^2+x-2}=\frac{1}{3}\left(\frac{1}{x+2}-\frac{1}{x-1}\right)$$
のように、まずは分解しておいてから、
それぞれの成分の高次の微分係数を求めればよいということになります。

また、問題5-3、5-4についてはおまけの問題なので
だれか解く人がいれば、点数をあげます。

問題5-3
関数 $(1+1/x)^{x}$ は単調増加であることを示せ。

問題5-4
$0<a<b$ のとき、$\lim_{x\to \infty}\left(\frac{a^x+b^x}{2}\right)^{\frac{1}{x}}$ の極限を求めよ。

宿題の方は、誘導に乗っていけば自然と解けると思います。
宿題5-3はランダウの記号が分母に来たときの処理の仕方に関する問題ですが、
分母を払って考えれば自然と考えられると思います。

微積分I演習(数学類)(第5回)

[場所1E103(水曜日4限)]

HPに行く
manabaに行く

今回は

  • ランダウの記号の計算規則
  • ライプニッツの公式

をやりました。

ランダウの記号について
ランダウの記号のさらなる使い方について学びました。

もう一度書いておきます。ここでは特別に、$x\to 0$ とした場合を考えます。
そのほかの場合も対応する極限を考えます。

(1) $x^mo(x^n)=o(x^{n+m})$
(2) $\forall c\in {\mathbb R}, co(x^n)=o(x^n)$
(3) $x^{n+1}=o(x^n)$
(4) $o(x^n)+o(x^m)=o(x^n)\ \ \ (n\le m)$
(5) $o(x^n)o(x^m)=o(x^{n+m})$

証明も書いておきます。
(1) $f(x)=o(x^n)$ とすると、$\lim_{x\to 0}\frac{x^mf(x)}{x^{n+m}}=\lim_{x\to 0}\frac{f(x)}{x^n}=0$
(2) $c\in {\mathbb R}$ として、$f(x)=o(x^n)$ とすると、$\lim_{x\to 0}\frac{cf(x)}{x^n}=c\lim_{x\to 0}\frac{f(x)}{x^n}=0$
(3) $\lim_{x\to 0}\frac{x^{n+1}}{x^n}=\lim_{x\to 0}x=0$
(4) $f(x)=o(x^n)$ $g(x)=o(x^m)$ とすると、$\lim_{x\to 0}\frac{f(x)+g(x)}{x^n}=\lim_{x\to 0}\left(\frac{f(x)}{x^n}+x^{m-n}\frac{g(x)}{x^m}\right)=0$
(5) $f(x)=o(x^n), g(x)=o(x^m)$ とすると、$\lim_{x\to 0}\frac{f(x)g(x)}{x^{n+m}}=\lim_{x\to 0}\frac{f(x)}{x^n}\frac{g(x)}{x^m}=0$

となります。

2次近似

2回微分可能な関数 $f(x)$ は、
$$f(x)=f(a)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2+o((x-a)^2)$$
のような式が成り立ちます。この式は、関数 $f(x)$ が $x=a$ の近くで、
多項式関数 $y=f(a)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2$ が関数 $f(x)$
と近いことが分かります。

その差 $o((x-a)^2)$ は $x=a$ に近づくに従って、$(x-a)^2$ よりも小さい量で $0$
に近づくので、 $f(x)$ と $f(a)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2$ がそのような
量で近くということがわかります。

このような2次多項式関数 $f(a)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2$ は関数 $f(x)$ の2次(多項式)近似といいます。

ライプニッツの公式

積の微分の公式は $(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)$ として知られていますが、それを一般化した公式をライプニッツの公式といいます。

2回微分のときは、
$$(f(x)g(x))''=f''(x)g(x)+2f'(x)g'(x)+f(x)g''(x)$$
3回微分のときは
$$(f(x)g(x))'''=f'''(x)g(x)+3f''(x)g'(x)+3f(x)g''(x)+f(x)g'''(x)$$
となります。これらは積の微分を繰り返せば得られます。
一般に、$n$ 回微分のときは、
$$(f(x)g(x))^{(n)}=f^{(n)}(x)g(x)+nf^{(n-1)}(x)g'(x)+\cdots +f(x)g^{(n)}(x)$$
$$=\sum_{k=0}^n{}_nC_kf^{(k)}(x)g^{(n-k)}(x)$$

となります。これをライプニッツの公式といいます。

宿題について

宿題5-1  定義に戻って示してください。
宿題5-2  逆関数の微分法を2回用いる。
宿題5-3  宿題5-1を使って示しますが、必ず、近似多項式は2次多項式にして下さい。

2017年5月22日月曜日

数学外書輪講I(第4回)

[場所1E501(月曜日5限)]

HPに行く
manabaに行く

今回はlinear algebraの続きのところを読みました。

内容はさておき、予習の仕方、発表の仕方について少し書きます。

ノートを作ることについて
多くの人は自分のノートを作っておらず、その場で説明をしていたと思います。

この授業では、一回の分量は少しずつですが、セミナー形式を取っています。
なので、予習ノートを作っておくことをお勧めします。

ノートの作り方は、自分が黒板に書くであろう文章をノートに書いておく
というのが定番です。
じゃあどのような文章を黒板に書くか?ということですが、
伝えたいこと。例えば定義や定理のステートメント、証明など理路整然と
書かれていれば問題がありません。
思いついた順に放射状に用語を並べるというのは問題外です。
これまで受けてきた分かりやすいと思われる先生の板書の書き方を思い出し、
参考にするとよいと思います。

ちなみに、東大の河東先生のページ、阪大の落合先生のページに、筑波大の
竹山先生のページにセミナーの準備の仕方について書かれていますので参考にして見てください。
河東先生のページ(リンク)
落合先生のページ(リンク)
竹山先生のページ(リンク)


黒板の使い方について。
ノートは、黒板に書く内容を書いておけばよいと思いますが、
数学の場合、定義が出てこれば、その内容をちゃんと黒板に書いて欲しいです。

例えば、日本語で書く場合なら、


--------------------------------------
定義(線型独立linearly independent)

・・・・・・・・・・・をみたすものを線型独立という。
--------------------------------------



--------------------------------------
定理
・・・・を仮定する。
このとき、・・・・・が成り立つ。
--------------------------------------



などとなります。定理は必ず仮定と結論があります。
どのような仮定の元、どのような結論が導けるのか?
を明確にしてください。

また、大事な定義であれば、仮定などを口だけで説明せず、黒板に全て書いてください。
補足事項なども後で口で言うだけではなく、丁寧に書いておくとよいでしょう。


話し方について
どのような話し方をすればよいか?ですが、テレビのアナウンサーに育てるつもりは
ありませんので、ある程度聞き取れるように話してもらえば、十分です。
しかし、聞き手を混乱させないためには、

「・・・について考えます。」
「これから・・・を証明します。」
「これから・・・を定義します。」
「・・・のためには・・・を示せば十分となります。なので、・・・の部分を証明します。」
「次の話にうつります。」


など、話の方向性を指示することで、断然話し方がよくなります。
聞いている人を自分の話に誘導するようにして話してください。


などなど、予習の仕方から話し方まで、最低限のこれらのことを心がけただけでも、
かなりよいプレゼンテーションとなります。

あと、内容に自信を持って話すということも大事です。
そのためには完璧に内容を理解することが必要となります。

2017年5月15日月曜日

微積分I演習(物理学類)(第4回)

[場所1E103(金曜日5限)]

HPに行く
manabaに行く

今回は微分の話に入りました。

内容としては、

  • 小テスト
  • 第2回の宿題の解答
  • 微分法(特に逆関数の微分法と対数微分法)
でした。小テストでは、問題文に不備が見つかってしまいすいません。
また、授業後に言われたのですが、皆さんよく理解しているようで、
宿題3-1の数列は単調ではありませんでした。
そこで解けずに迷った方はすいませんでした。
それ以外の部分を採点します。

微分

関数 $f(x)$ が $x=a$ で微分可能とは、極限
$$\lim_{x\to a}\frac{f(x)-f(a)}{x-a}$$

が存在する(収束する)ことをいいます。その極限値を微分係数といいます。


逆関数の微分法


先週は三角関数の逆関数や双曲線関数の逆関数についてやりましたので、
その微分を求めるために、逆関数の微分法を復習しました。

ある関数 $f$ の逆関数 $f^{-1}$ を微分する公式は、
$$\frac{df^{-1}(x)}{dx}=\frac{1}{\frac{df}{dy}(f^{-1}(x))}$$
となります。公式にしてみると、なんだかわかりにくいです。
ここで、実際の計算をしてみれば、どういうことなのかよくわかります。

$y=\text{Arcsin}(x)$ とすると、$x=\sin y$ となり、
$$\frac{d(\text{Arcsin}(x))}{dx}=\frac{1}{\frac{d(\sin y)}{dy}}=\frac{1}{\cos y}=\frac{1}{\sqrt{1-\sin^2y}}=\frac{1}{\sqrt{1-x^2}}$$
となります。つまり、逆関数の微分がしにくければ、関数を逆に解いておいてから
微分してもかまわない。ただし、そのときは、微分係数が逆数になる。
という公式だということになります。

しかし、実はルートをとる段階で少々注意が必要です。
わり算をするときや、ルートを取る時、”普段"とは違う操作なので、少々の
エネルギーが必要です。そのようなときに、ちょっとした壁があるということを
いつも考えて置いてください。通常は場合分けをしたりすれば
大概のりこえられるものが多いですが。

具体的には、例えばゼロでないことを確認することや、ルートの中が負ではないことや
ルートを取った時に、解として複数現れることなどの確認などの作業です。

この場合、ルートの中身は負ではありませんが、通常、プラスマイナスがでてきます。
今の場合、$\text{Arcsin}$ の値域が $-\frac{\pi}{2}\le y\le \frac{\pi}{2}$ であるので、
$\cos y$ の値は、非負の数でないといけません。なので、マイナスの方がなくなって、
$\cos y=\sqrt{1-x^2}$ となります。


対数微分法

対数微分法は、あまり馴染みがない人も多いですが、便利なことも多いので、
この段階で教えています。公式は簡単で、

$(\log(f(x)))’=\frac{f’(x)}{f(x)}$ であることを使って分母を払えば、対数微分法とは、
$$f’(x)=f(x)(\log f(x))'$$
という公式になります。

例えば、次のような多項式の場合、一度展開してから微分をし、もう一度因数分解をしたり、積の微分法を用いる人が多いのですが、実は対数微分法を用いることができます。
$f(x)=(x^2+1)^2(x+2)^3$ などの関数を微分する場合、
$$f’(x)=(x^2+1)^2(x+2)^3(2(\log(x^2+1))’+3(\log(x+2))’)$$
$$=(x^2+1)^2(x+2)^3(\frac{4x}{x^2+1}+\frac{3}{x+2})$$
$$=(x^2+1)(x+2)^2(4x(x+2)+3(x^2+1))$$
$$=(x^2+1)(x+2)^2(7x^2+8x+3)$$
となります。

極限の問題

$$\lim_{n\to \infty}\frac{n}{\sqrt[n]{n!}}=e$$
である問題を授業中に出しましたが、すぐ解いてくれる人がいたようですので、
来週はそこから始めようと思います。

このことから、$\sqrt[n]{n!}$ は”大体”、$\frac{n}{e}$ の勢いで大きくなっていく(漸近していく)
ということがわかるかと思います。
とくにこの数列が発散します。

このようななんでもない数列ですが、この授業の後半の方(積分まで終わった段階で)
で少々意味付けを与えようと思います。(講義ではそこまで進まないかもしれませんが....)
意味が分かれば、瞬時に発散するということ($n/e$ に漸近するまではわかりませんが)
がわかります。

また、この「大体」、とか「漸近」とかの言葉は少し厳密に、
今後の授業で扱っていきます。

2017年5月11日木曜日

微積分I演習(数学類)(第4回)

[場所1E103(水曜日4限)]

HPに行く
manabaに行く

宿題の解答

宿題の一つはこちらの不備で答えがありませんでした。すいません。

2-1 について。

任意の整数 $n$ について $f(nx)=f(x)^n$ かつ $f(0)=1$ かつ $f(1)=e$
を満たす実数値連続関数は $f(x)=e^x$ だけという問題でした。

$F(x)=f(x)e^{-x}$ と定義して $F(x)=1$ であることを示します。

(1) 任意の有理数で証明する前に、任意の整数で成り立つかを考えます。

$\forall n\in {\mathbb Z}$ とすると、条件から、$F(n)=f(n)e^{-n}=f(1)^ne^{-n}=1$ が成り立ちます。

任意の有理数を $r=\frac{m}{n}$ とします。ただし $n,m$ は整数かつ
$n$ は奇数とします。このとき、
$F(\frac{m}{n})^n=(f(\frac{m}{n})e^{-\frac{m}{n}})^n=f(m)e^{-m}=1$

となり、$f(x)$ は実数関数であるから、$f(\frac{m}{n})=1$ となります。


$n$ が偶数の場合にも証明しなければなりません。(これは授業ではやりませんでした。)
どうしてかというと、$1=F(\frac{1}{2})^2$ を満たしますが、これだけでは、
$F(\frac{1}{2})=\pm1$ の両方が出てしまうからです。
そのために、$f(x)$ の連続性が必要です。

$r_t=\frac{mt}{nt-1}$ とおくと、$r_t\to \frac{m}{n}\ \ (t\to \infty)$ となります。
また、$r_t$ の分母は明らかに奇数です。

なので、分母が奇数の有理数列で、分母が偶数の有理数 $\frac{m}{n}$ に収束させることができることになります。

$F(x)$ の連続性から、$F(\frac{m}{n})=F(\lim_{t\to \infty}r_t)=\lim_{t\to \infty}F(r_t)=1$
となります。

よって、任意の有理数 $r$ で、$F(r)=1$ が成り立ちます。

(2) $\forall \alpha\in {\mathbb R}$ に対して、$\alpha$ に収束する有理数列 $r_n$ が存在することを示します。

有理数の稠密性を用いることで、
$$r_n\in (\alpha-\frac{1}{2^n},\alpha+\frac{1}{2^n})$$
となる $r_n\in {\mathbb Q}$ が存在します。
このとき、$0\le |r_n-\alpha|\le \frac{1}{2^n}$ となります。

ここで、$\frac{1}{2^n}\to 0$ ($n\to \infty$) となるので、挟み撃ちの原理から
$r_n\to \alpha$ となります。

(3) $\forall \alpha\in {\mathbb R}$ に対して $F(\alpha)=1$ であることを示します。
これは、上で偶数の場合に示したものと方針は同じです。

$$F(\alpha)=F(\lim_{n\to \infty}r_n)=\lim_{n\to \infty}F(r_n)=1$$

となります。

微分

講義の方ではすでに微分に入ったということで、演習も微分に入りました。
$x=a$ で微分ができるとは、極限

$$\lim_{x\to a}\frac{f(x)-f(a)}{x-a}$$

が存在することです。

逆関数の微分法を復習しながら、$\text{Arcsin}(x)$ の微分を実行しておきます。
$y=\text{Arcsin}(x)$ とおくと、$x=\sin y$ とします。

$$\frac{d}{dx}\text{Arcsin}(x)=\frac{1}{\frac{dx}{dy}}=\frac{1}{\cos y}=\frac{1}{\sqrt{1-\sin^2y}}$$
$$=\frac{1}{\sqrt{1-x^2}}$$

となります。

ランダウの記号

ランダウの記号の使い方を解説します。
ランダウの記号(スモールオー)に関しては、こちら(リンク)に書きました。

定義
$f(x)=o(g(x))\ \ x\to a$

であるとは、$\frac{f(x)}{g(x)}\to 0$ のこととして定義します。

使い方その1
$g(x)=(x-a)^n$ としたとき、

$f(x)=o((x-a)^n)$ であるとは、関数 $f(x)$ が $x=a$ において、$0$ に収束する”速度” が $(x-a)^n$ より速いということです。

例えば、$f(x)=(x-a)^{n+1}$ であるとすると、

$\frac{f(x)}{(x-a)^n}=x-a\to 0$ なので、$(x-a)^{n+1}$ は $(x-a)^n$ より $0$ になる速度が
速いということです。

また、$f(x)=(x-a)^n$ とすると、
$\frac{f(x)}{(x-a)^n}=1$ なので、これは、$(x-a)^n\neq o((x-a)^n)$ となります。

もちろん $r>0$ とすると $(x-a)^{n+r}=o((x-a)^n)$ となります。

使い方その2
また、$f(x)=f_1(x)-f_2(x)$ とすると、$f_1(x)-f_2(x)=o((x-a)^n)$ であり、
$$f_1(x)=f_2(x)+o((x-a)^n)$$

とすることができます。
この式では、$f_1(x)$ と $f_2(x)$ を比較することができます。

つまり、$f_1(x)$ と $f_2(x)$ の差がすごく小さいということは、$f_1(x)$ と $f_2(x)$
がとても近いということを意味しています。


簡単のため、$n=1,2$ とします。
このとき、

実は、1回微分可能関数は、微分可能であることから
$$f(x)=f(a)+f'(a)(x-a)+o(x-a)$$
と変形できます。
上で書いたことから、関数 $f(x)$ と $f(a)+f’(a)(x-a)$ が近いということがわかります。
実際、$f(x)$ の $x=a$ での接線のなす関数が $f(a)+f’(a)(x-a)$ ということになります。
接線はその関数に接しているので、確かに関数として近いことになります。

また、2回微分可能関数なら、

$$f(x)=f(a)+f'(a)(x-a)+\frac{f’’(a)}{2}(x-a)^2+o((x-a)^2)$$

が成り立ちます。
この2次関数はこの関数に接していますが、もちろん接線とは言いません。
単なる近似ということになりますが、接線の時にはわからなかった、
関数のその点の周りでの曲がり方を最も反映している近似となります。
この近似を2次近似といいます。

今回、微分の定義だけを用いて、この式の証明をするという宿題を出しておきました。

数学外書輪講I(第3回)

[場所1E501(月曜日5限)]

HPに行く
manabaに行く

今日は前回残った問題とLangのLinear algebra とMatousekの33-Miniaturesの
Miniature 1を読みました。

Linear algebra 

以下のような文章がありました。

It is possible to add several elements of a vector space. Suppose we wish to add four elements, say u, v, w, z. We first add any two of them, then a third, and finally a fourth. Using the rules VS1 and VS4, we see that it does not matter in which order we perform the additions. 
ベクトル空間のいくらかの元を付け加えることができます。4つの元を付け加えたいとします。たとえば、u, v, w, zとしましょう。まず、それらの任意の2つを足し、それから3つめを足し、最後に、4つ目を足します。規則VS1とVS4使えば、足し算をする順番には問題がないことがわかります。

このorderというのは規律だとか命令、注文などの他に数学では順番(順序)という
文脈でよく使われます。数学では他に、群の位数(群の集合としての数と一つの元
が持つ単位元になるまでの最小の正の数という場合もある)という意味で用いられることも
あります。

本文に戻ります。

ベクトル空間において足し算は、厳密には2つの和が定義されているだけなので、一気に例えば4つを足すという操作は定義されていません。なので、便宜的に、まず、u+v をし、さらにそれに w を足し、さらにそれに、z を足してとりあえず定義しなさいと言っています。つまり、
((u+v)+z)+w
ということです。

しかし、ベクトル空間のベクトル同士の足し算は結合律と、可換性があるので、足し合わせ方を便宜的に定めたが、実はどのような順番に足しても同じになります。

ちなみに
VS1 は、(u+v)+w=u+(v+w)
VS4 は、u+v=v+u
です。

この2つのルールだけを使えば、4つに限らず、どんなに多くの数の元を
足すことも、その順番によらないことが示されます。
これは厳密に証明がいります。


少し脱線して、例えば、4つのベクトルを足し算する方法がいくつあるのかを
数えてみます。
足し算の形式としては以下の2種類が考えられます。
ただし、可換性を使ってU+V=V+Uを仮定しておきます。

最初に2つを足し、そのあとに、その他の1つを足し、最後に残りの1つを足す
という方法(上の本文に書いてあった方法)と、
最初に2つを足し、残りの2つ同士も足し、できた2つの元どうしを足す
という方法です。

かっこのつけ方で言えば、
((*+*)+*)+*



(*+*)+(*+*)

です。

最初の形式では、((a+b)+*)+*
の a,b を選ぶ方法は、${}_4C_2=6$ 通り。
のこりを並べる方法は2通りなので、全部で12通り。

2番目の形式であれば、4つを2つのグループに分ける方法の数ですが、
まず、4つのうち2つを取る方法の数は ${}_4C_2=6$ 。
そのうち、4つの残りの2つをとる方法も同時に数えてしまっているので、
その分を割って $6/2=3$ 通りとなります。
(もしくは、どれか一つを固定して考える。それと一緒になる元をどれか選べば
2つのグループに分けることができるその相手の探しかたはのこりの3つの
どれかだから3通り)

よって、全部で $12+3=15$ 通りとなります。

Fibonacci Numbers, Quickly

の部分を読みました。内容としてはそれほど問題はなかったかと思います。
フィボナッチ数とは $F_0=0, F_1=1$, $F_{n+2}=F_{n+1}+F_n$ なる漸化式を満たす
数列 $F_n$ のことです。すぐわかることですが、全て自然数を値とする数列です。

この数列をいかに速く求めるか?という問題の内容です。普通に考えれば、
$F_n$ の値を求めるには、この漸化式を使って、$n$ 回くらい計算をすれば
求められるはずですが、実はもっと手早く計算する方法があるということです。


フィボナッチ数列の漸化式の行列表示

まず、フィボナッチ数列の漸化式を下のように、

$$\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}=M\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}$$
$$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$$

として、書き直しておけば、次のフィボナッチ数を求めるのに、足し算の漸化式
ではなく、行列 $M$ を掛け算をすることでも得られることがわかります。
これを繰り返せば、任意のフィボナッチ数は、

$$\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}=M^n\begin{pmatrix}F_{1}\\F_0\end{pmatrix}$$

のように得られることがわかります。


2進法とその応用
次に2進法を使います。

任意の自然数は、
$n=2^{k_1}+2^{k_2}+\cdots+2^{k_t}$  ($0\le k_1<k_2<\cdots<k_t$) のように
2進展開をすることができます。
2進展開を用いれば、上の行列の $n$ 乗は

$$M^n=M^{2^{k_1}}\cdots M^{2^{k_t}}$$

となります。

例えば、$M^{2^m}$ を求めるには、
$$M,\ M^2,\ (M^2)^2=M^4=M^{2^2},\ (M^{2^2})^2=M^{2^3},\cdots $$

から、$m$ 回計算をすれば済むことがわかります。
一般の自然数 $n$ において $F_n$ を求める計算にしても、

$$M^n=M^{2^{k_1}}\cdots M^{2^{k_t}}$$

ですが、2乗を繰り返す操作を $k_t$ 回繰り返せば、それまでに $M^{2^{k_i}}$ も同時に
求めていることになるので、それぞれの成分 $M^{2^{k_1}}$ は $k_t$ 回計算すれば全て得られます。さらにその成分同士を $t$ 回かける操作がありますので、
厳密には $t+k_t$ だけ計算すればよいことになります。
しかし、$t\le k_t$ であるので大体、$2k_t$ くらい計算すればよいということになります。

また、掛け算といっても、行列を求めるには、本当は行列の成分の4倍くらい
計算しなければなりませんが、それを数えたとしても $8k_t$ くらいです。


$M^n$ が計算できたとすれば、実はその  (2,1) 成分がちょうど $F_{n}$ ですので、
高々 $2k_t$ (計算の量を $8k_t$ と数えてもよい)くらいの計算量で求められるという
ことになります。
$$k_t\le \log_2n$$
なので、係数が2でも8でも高々、$n$ の $\log$ のオーダー(order)くらいの計算量で済むということになります。(このオーダーも上の使い方とも異なります。)

結論として、フィボナッチ数列を計算する計算量を $n$ から $\log n$ まで節約(手早く)できたというこになります。


2017年5月2日火曜日

微積分I演習(数学類)(第3回)

[場所1E103(水曜日4限)]

HPに行く
manabaに行く

今日は、関数について以下の項目
  • 宿題の解答
  • 上限の求め方
などについてやりました。

宿題の解説など
宿題は 
$\lim_{n\to \infty}(1+\frac{1}{n^2})^n$ の収束と、
$a_n=n!/n^n$ としたときの、$\lim_{n\to \infty}a_n/a_{n+1}$ の極限値でした。

前半の方は、
$\left(1+\frac{1}{n^2}\right)^n=\left(\left(1+\frac{1}{n^2}\right)^{n^2}\right)^{\frac{1}{n}}$ と式変形すれば、$\log$ をとって、
$\frac{1}{n}\log(1+\frac{1}{n^2})^{n^2}$ となるので、積の極限の公式から、
$\lim_{n\to \infty}\frac{1}{n}\lim_{n\to \infty}\log(1+\frac{1}{n^2})^{n^2}$ 
と等しくなり、それぞれ、$0$, $1$ に収束するので、
全体として $0$ に収束することがわかります。

よって、$\log$ が単調増加な連続関数なので、$\log$ を取り払った
$\left(1+\frac{1}{n^2}\right)^n$ は $1$ に収束することがわかります。

一般に、$a_n\to \alpha>0$ に収束するなら、$\sqrt[n]{a_n}\to 1$ になります。
議論は、今のように、$\log$ をとってから収束先を決定し、あとで $\log$ をとる
という方法です。

ただ、$a_n\to 0$ の場合は注意が必要です。ようするに、収束先として $0^0$ のような
数は存在しません。

一般に数列 $\sqrt[n]{a_n}$ は、このように考えることができます。

まず自明な例として、$a_n=a^{n}$ であるとすれば、
$\sqrt[n]{a_n}=a$ ですので、明らかに $\sqrt[n]{a_n}$ 収束がいえます。

また、$f(n)$ を多項式数列 $f(n)$ ( $f(n)>0, \forall n$ と仮定します) とします。
多項式数列とは、$f(x)$ がある多項式であるような多項式です。
多項式数列は、任意の指数増大関数 $a^n\ \ a>1$ と比べると小さいです。
つまり、十分 $n$ を大きくすると、
$$\frac{f(n)}{a^n}<1$$
となるということです。

つまり、$n$ を十分大きくしてやると、$f(n)$ は十分大きくなり、
$1<\sqrt[n]{f(n)}<a$ がいえます。$a$ を任意に $a>1$ となる実数を取って来たことを
考えると、いわゆる挟み撃ちの原理から、$\sqrt[n]{f(n)}\to 1$ であることがわかります。

また、これらを合わせた増大関数として、$b_n=a^n$ かつ、$c_n$ を多項式数列や
収束する数列などであるとし、$a_n=b_nc_n$ とするなら、
$\sqrt[n]{a_n}=\sqrt[n]{b_n}\sqrt[n]{c_n}$ なので、
積の極限操作から、$\sqrt[n]{b_nc_n}\to a$ であることがわかります。

つまり、一般に、$\sqrt[n]{a_n}$ という数列は 数列 $a_n$ の指数増大度(減少度)の部分を
取り出しているということができます。(もちろんこれだけでは証明にはなりませんが。。)

ここで、$\sim$ という記号を、$f(n)\sim g(n)\Leftrightarrow f(n)/g(n)\to 1\ \ (n\to\infty)$ 
として定義しておきます。この記号を使えば、数列が漸近的にどのような振る舞い
をするかがわかります。

上で書いたことは、次のように一般化できます。

$f(n)$ を 多項式数列として、$a_n\sim a^nf(n)$ であるなら、$\sqrt[n]{a_n}\sim  a$ が成り立つ。

特に、
$a_n\sim 1\Leftrightarrow a_n\to 1$ であるなら、$\sqrt[n]{a_n}\sim a$ となります。

$f(n)$ 有理数列 $f(n)=\frac{p(n)}{q(n)}$ であるときも同じで、
$\sqrt[n]{f(n)}\to 1$ となります。ここで、$p(n),q(n)$ が多項式数列。

また、$a_n=e^{e^n}$ として、$\sqrt[n]{a_n}$ を考えると、指数増大より大きすぎて
$\infty$ に発散してしまいます。つまり、この数列は、$\sqrt[n]{a_n}$ は指数増大
より真に大きいということがいえます。この場合、
$\sqrt[n]{a_n}\sim e^n$ にはならず、$\sqrt[n]{a_n}\sim e^{e^n/n}$ となるだけです。

今回の宿題でもあるように、
$a_n=\frac{1}{n}$ などとしてとると、$\frac{1}{n}$ は有理式として考えることが
できるので、$\sqrt[n]{a_n}$ は 1 に収束します。
もちろん宿題ではこのような解答はNGです。

$\sqrt[n]{n}$ の収束に関しては、前回のblog(リンク)に書きましたが、
よく考えたら、次のような解答もありえました。

$\sqrt[n]{n}$ の有界性と単調性を考えればよいですが、

$\sqrt[n+1]{n+1}<\sqrt[n]{n}$ であることは、
$n\ge 3$ のときに、$(n+1)^n>n^{n+1}$ となることとを証明すればよいのですが、
(前回の命題)

実際は、この式、$(n+1)^n<n^{n+1}$ を$n^n$ で割ってやると、
$(1+\frac{1}{n})^n<n$ を示せばよいことなります。

ここで、知識として、$(1+\frac{1}{n})^n$ が単調増加で $e$ に収束するという事実を
使いますと、明らかに、$(1+\frac{1}{n})^n<e$ となります。

よって、$(1+\frac{1}{n})^n<n$ が成り立つためには、やはり、$3\le n$ であれば十分ということになります。
なので、$n^{\frac{1}{n}}$ が 3 から単調減少であったわけは、$e=2.7....$ であることから
来ていたということがわかります。

次の宿題であったところは、

$${\mathbb Z}=5{\mathbb Z}+7{\mathbb Z}$$

の等式の証明でした。できていた人も多かったのですが、簡潔に、というか形式的に
${\mathbb Z}\subset 5{\mathbb Z}+7{\mathbb Z}$
$5{\mathbb Z}+7{\mathbb Z}\subset {\mathbb Z}$
だけ示していた人はいませんでした。

1が5,7から作られるという証明の本質を使っているということを指摘している人は多かったです。(ヒントでも書きましたし。)

このように証明(答え)は一瞬で終わります。

$\forall x\in {\mathbb Z}$ とするとき、
$x=5(3x)+7(-2x)$ と書け、$3x,-2x\in {\mathbb Z}$ なので、$x\in 5{\mathbb Z}+7{\mathbb Z}$ である。
また逆に $\forall x\in 5{\mathbb Z}+7{\mathbb Z}$ とするなら
$x=5p+7q$ とかける。($p,q\in {\mathbb Z}$ ) ${\mathbb Z}$ は掛け算、足し算で閉じているので、$x\in {\mathbb Z}$ である。

ゆえに、
$${\mathbb Z}=5{\mathbb Z}+7{\mathbb Z}$$
がいえる。

宿題1-3に関しては省略します。

上限・下限
上限や下限は、となりの授業(2017物理学類の微積分I演習)でもやりました(リンク)

$E$ を実数の部分集合とします。
このとき、$y\in {\mathbb R}$ が $\forall x\in E$ に対して、$x\le y$ となるとき、$y$ を $E$ の上界といいます。上界の集合を $S$ と書くとすると、
$$\sup(E)=\min S$$
とかいて、$\sup(E)$ は $E$ の上限と言います。

$s=\sup(E)$ であることは以下の条件と同値になります。

(1)    $\forall x\in E$ に対して、$x\le s$ を満たす。
(2)       $\forall s’<s$ に対して $\exists t\in E$ が $s’<t<s$ を満たすこと。

最後の条件(2)は、次と同値です。
(2)'     $\forall x\in S$ に対して、$s\le x$ 



これらの条件(1),(2)の意味は、
$s\in S$ であること。
$\forall s’<s$ に対して $s’\not\in S$ であること。

と同じです。

$y\in {\mathbb R}$ が $\forall x\in E$ に対して、$y\le x$ となるとき、$y$ を $E$ の下界といいます。下界の集合を $T$ と書くことにすれば、
$$\sup(E)=\max T$$
とかいて、$\inf(E)$ は $E$ の下限と言います。

$s=\inf(E)$ であるための必要十分条件は上と同じようにいうことができます。
ここでは省略。


(例) $E=\left\{\frac{1}{n}|n\in {\mathbb N}\right\}$ としたとき、$\inf(E)=0$ であることの証明。
宿題もこれに則ってやってください。

$0=\inf(E)$ であることを証明します。
$T$ を $E$ の下界の集合とします。
このとき、$\forall n\in {\mathbb N}$ に対して $0\le \frac{1}{n}$ であるので、$0$ は $E$ の下界の集合に含まれる。つまり、$0\in T$ である。(1) が満たされた。

また、$0<s’$ を任意にとると、アルキメデスの原理より、$\frac{1}{s’}<n$ となる自然数 $n$ が存在します。これを書き直すと、$0<\frac{1}{n}<s’$ が言えて、$\frac{1}{n}\in E$ となります。これは、(2) が満たされています。

よって、$0=\inf(E)$ となります。