2011年度　連続系アルゴリズム期末試験略解

問題1A

列和ノルム
- 1ノルムはxの成分の符号を入れ替えても不変なので、xの各成分を非負としても一般性を失いません。
- また、講義ノートでも示されているようにxのノルムを1に制限しても一般性を失いません。
- すると求めるノルムは線形関数の最大値になるはずです。ゆえに最大を与えるxは定義域の境界にあることになるのであとは手の運動です。
行和ノルム
- xの各成分を全て等しくしても一般性を失わないことを示せば手の運動になります。

(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)で逐次積分するときの公式にガウス・ルジャンドル則をあてはめるだけです。