差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン 前のリビジョン 次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
kaz:km-iter [2014/01/09 15:36] – [定義と契約] kaz | kaz:km-iter [2014/05/16 22:26] – [参考文献] kaz | ||
---|---|---|---|
行 1: | 行 1: | ||
+ | ====== Racket(Scheme) によるKrasnosel' | ||
+ | [[.:|Go back]] | ||
+ | |||
+ | ===== はじめに ===== | ||
+ | 契約を用いたRacket(Scheme)プログラミングと,それらを使用した数値実験手法の入門的解説を行います. | ||
+ | ここでは例として,非拡大写像$T$ の不動点$u\in{}F(T) \left(=\left\{x: | ||
+ | アルゴリズムとしては,次に示すKrasnosel' | ||
+ | <WRAP box> | ||
+ | // | ||
+ | |||
+ | $H: | ||
+ | $\left\{\alpha_i\right\}\subset[0, | ||
+ | $x_1\in{}C$. | ||
+ | $$ x_{i+1}=\alpha_ix_i+\left(1-\alpha_i\right)Tx_i\quad\left(i=1, | ||
+ | </ | ||
+ | |||
+ | 実装には,Racket((PLT Design Inc.: **[[http:// | ||
+ | また,行列表現に用いるデータ構造,およびそれらに対する各種演算には,Math Library[(N. Toronto, J. A. Søgaard: **[[http:// | ||
+ | 読者は,R< | ||
+ | ===== Racket(Scheme) の文法 ===== | ||
+ | 今回は,より数学表現に則した形でプログラムを実装したいと思います. | ||
+ | そのために必要となるいくつかの文法,特にScheme 標準からRacket により独自拡張された文法に関して解説します. | ||
+ | |||
+ | ==== 定義と契約 ==== | ||
+ | 契約とは,定義する値に対してある一定の制約(保証)を与えるものです. | ||
+ | 例えば,ある変数$x$が**実数値であることを保証**することや,ある関数$f$が**$n$次元ベクトル$\mathbb{R}^n$から$m$次元ベクトル$\mathbb{R}^m$への写像であることを保証**することができます. | ||
+ | |||
+ | Racketにおける契約の表現形態は種々存在します. | ||
+ | 例えば,述語は契約として使用することができます. | ||
+ | 述語とは,任意の1つの値を受け取り,真偽値を返す関数です. | ||
+ | 例えば,関数'' | ||
+ | この関数'' | ||
+ | |||
+ | **契約付き変数定義**は,契約としてその変数が取りうる値の制約を与えて,変数を定義します. | ||
+ | 以下に,契約付き変数定義の記述形式を載せます. | ||
+ | <code scheme> | ||
+ | (define/ | ||
+ | </ | ||
+ | ''< | ||
+ | ''< | ||
+ | ''< | ||
+ | |||
+ | 例として,契約付き変数定義を用いて,初期値$3$を取る変数$x\in\mathbb{N}$を定義してみましょう. | ||
+ | ''< | ||
+ | ここで,変数$x$は自然数です. | ||
+ | Racketにおいては,自然数かどうかを判定する述語'' | ||
+ | (ここでは「自然数」を,「正確な正整数」と考えます.$\mathbb{N}: | ||
+ | 述語は契約として使用することができるので,ここでは次の記述, | ||
+ | <code scheme> | ||
+ | (define/ | ||
+ | </ | ||
+ | により,初期値$3$を取る変数$x\in\mathbb{N}$を定義することができます. | ||
+ | |||
+ | 契約付き変数定義により変数定義を行うと, | ||
+ | これにより定義した変数に対して契約に反する操作を行った際に,**エラーとして検出する**ことができます. | ||
+ | 例えば,先の例における変数$x$に自然数$5$を代入することは, | ||
+ | <code scheme> | ||
+ | (set! x 5) | ||
+ | </ | ||
+ | により行うことができます. | ||
+ | しかし,自然数ではない値$0$を代入するような次のコード, | ||
+ | <code scheme> | ||
+ | (set! x 0) | ||
+ | </ | ||
+ | を実行すると,エラーとなります. | ||
+ | |||
+ | **契約付き関数定義**は,契約として定義域および値域を与えて(引数と戻り値に対して契約を与えて),関数を定義します. | ||
+ | 以下に,契約付き関数定義の記述形式を載せます. | ||
+ | <code scheme> | ||
+ | (define/ | ||
+ | (-> < | ||
+ | < | ||
+ | </ | ||
+ | この形式は,名前が''< | ||
+ | これにより定義される関数は,''< | ||
+ | 契約は,受け取る各引数,およびそれらによって計算される戻り値に対して,制約をかけることができます. | ||
+ | 各引数に対する契約は,定義した引数の個数分だけ順に,''< | ||
+ | 戻り値に対する契約は,一連の契約を表すリストの最後の項''< | ||
+ | |||
+ | 例として,実数$x, | ||
+ | $$ d(x, | ||
+ | を,契約付き関数定義により定義してみましょう. | ||
+ | <code scheme> | ||
+ | (define/ | ||
+ | (-> real? real? (not/c negative?)) | ||
+ | (abs (- x y))) | ||
+ | </ | ||
+ | '' | ||
+ | ここで,関数$d$は,2つの実数$x$,$y$を受け取り,非負実数を返す関数です. | ||
+ | したがって,否定の契約を求める関数'' | ||
+ | なお,関数'' | ||
+ | |||
+ | 契約付き関数定義により定義された関数も,契約付き変数定義同様に, | ||
+ | これにより定義した関数に対して契約に反する操作を行った際,または契約に反する結果が得られた際に,**エラーとして検出する**ことができます. | ||
+ | 具体的には,関数呼び出し時に与えられた引数に関して,契約に反する操作を検出することができます. | ||
+ | また,計算結果としての関数の戻り値に関して,契約に反する結果を検出することができます. | ||
+ | 例えば,先に定義した関数$d$について,その引数に複素数を指定して呼び出すような式, | ||
+ | <code scheme> | ||
+ | (d 3+2i 5) | ||
+ | </ | ||
+ | を実行すると,エラーとなります. | ||
+ | |||
+ | ==== 行列表現とその演算 ==== | ||
+ | Racketで行列およびその演算を表現する方法はいくつか考えられますが,ここでは線形代数関数群である'' | ||
+ | '' | ||
+ | <code scheme> | ||
+ | (require math/ | ||
+ | </ | ||
+ | |||
+ | 今回は,行列のなかでも,特にn行1列行列,いわゆる列ベクトルが使用できればよいです. | ||
+ | 一般の行列を生成する命令以外に,'' | ||
+ | 例えば,列ベクトル$\left(1, | ||
+ | <code scheme> | ||
+ | (col-matrix (1 2 3)) | ||
+ | </ | ||
+ | 命令'' | ||
+ | |||
+ | 行列に対しては,いくつかの演算が関数として定義されています. | ||
+ | 代表的なものとしては,和'' | ||
+ | これらは,2つの行列を引数に取り,その(線形代数学で定義される一般的な)計算結果となる行列を返します. | ||
+ | また,2つの行列に対する内積は関数'' | ||
+ | |||
+ | 例えば,2つの$n$次元列ベクトル$x, | ||
+ | <code scheme> | ||
+ | (define/ | ||
+ | (-> col-matrix? col-matrix? (not/c negative?)) | ||
+ | (matrix-norm (matrix- x y))) | ||
+ | </ | ||
+ | により定義することができます. | ||
+ | ここでは,列ベクトルかどうかを判定する述語としては'' | ||
+ | (ちなみに,一般の行列かどうかを判定する述語としては'' | ||
+ | |||
+ | ==== 遅延評価と無限列 ==== | ||
+ | |||
+ | ===== Racket(Scheme) による実装 ===== | ||
+ | |||
+ | (書きかけ.) | ||
+ | |||
+ | <code scheme> | ||
+ | #lang racket | ||
+ | |||
+ | (require math/matrix racket/ | ||
+ | |||
+ | (define/ | ||
+ | (-> (-> col-matrix? col-matrix? | ||
+ | |||
+ | (define/ | ||
+ | (-> (and/c (>=/c 0) (</c 1)) col-matrix? col-matrix? | ||
+ | #:freevar t (-> col-matrix? col-matrix? | ||
+ | (matrix+ (matrix-scale x a) | ||
+ | | ||
+ | |||
+ | (let lp ((a-seq a-seq) (x x0)) | ||
+ | (stream-cons x (lp (stream-rest a-seq) (iter (stream-first a-seq) x))))) | ||
+ | |||
+ | |||
+ | (define/ | ||
+ | |||
+ | (define/ | ||
+ | (-> col-matrix? col-matrix? | ||
+ | (matrix* (matrix ((0 -1) (1 0))) x)) | ||
+ | |||
+ | |||
+ | (let ((x-seq (km-seq rotate90 alpha (col-matrix (100 50))))) | ||
+ | (plot | ||
+ | (lines | ||
+ | (for/list ((x (in-stream x-seq)) | ||
+ | (i (in-range 30))) | ||
+ | (vector i (matrix-norm (matrix- (rotate90 x) x))))) | ||
+ | #:x-label " | ||
+ | </ | ||
+ | |||