2011年度 連続系アルゴリズム期末試験略解
問題1A
- 実際に逆行列をBとおいて単位行列と成分比較。三角行列に逆行列が存在する⇔対角成分は0でないという事実に注意。
問題1B
- 列和ノルム
- 1ノルムはxの成分の符号を入れ替えても不変なので、xの各成分を非負としても一般性を失いません。
- また、講義ノートでも示されているようにxのノルムを1に制限しても一般性を失いません。
- すると求めるノルムは線形関数の最大値になるはずです。ゆえに最大を与えるxは定義域の境界にあることになるのであとは手の運動です。
- 行和ノルム
- xの各成分を全て等しくしても一般性を失わないことを示せば手の運動になります。
問題2A
- ノートや講義資料を見れば詰まるところはないはずです。
絶対安定領域は |1/(1-x)|<1 になりました。
問題2B
- (1) n-1個の標本点で任意の2n-1次以下の多項式が積分できると困ることを背理法で示します。
- 標本点を a_i (i = 1, ..., n-1)
- 多項式 p(x) = (x - a_1) * (x - a_2) * ... * (x - a_(n-1))
- 重み関数 w(x) = 1, 積分区間 [0, 1] で定まる内積に対する直交多項式系を R_n(x) (R_nはn次多項式) とそれぞれおきます。
- すると、背理法の仮定からn以下の自然数mに対して R_m(x) * p(x) という多項式を積分公式で積分すると0になることがわかります。
ゆえにm<=n-2の場合を考えると直交多項式の性質とp(x)がn-1次であることから p(x) = R_(n-1) であることがわかります。
- ところがm=n-1の場合を考えると内積(R_(n-1), R_(n-1))が0となることからR_(n-1)=0となり矛盾します。
- (2) 多項式は実数全体で連続なので重積分の際には逐次積分が使えます。
- 逐次積分を積分公式で計算してやるとn^2個の標本点が必要なことが分かります。
- （この方針ではもっと少なくても十分である可能性は排除できていません）
- (3) (2)で逐次積分するときの公式にガウス・ルジャンドル則をあてはめるだけです。
問題3A
- これもノートを参照してください。
問題3B
if(abs(x) < abs(y)) swap(x, y); r = x * sqrt(1 + (y/x) * (y/x));