ＭＹＣＰＵ８０でＣＰ／Ｍを！
超巨大基板の８０８０互換ＨＣＭＯＳ・ＣＰＵでＣＰ／Ｍを走らせてしまおうという、なんとも狂気なプロジェクトです！


［第５３回］


●チェビシェフの逆展開式を求める（３）

前回の続きです。
前回はチェビシェフの逆展開式をＢｏｒｌａｎｄ　Ｃ＋＋を使ってプログラムで求めました。
そのプログラムは［第４５回］で作ったチェビシェフの多項式を求めるプログラムに追加する形で作りましたので、前半に多項式が出力され、後半にそれを元に計算して求めた逆展開式が出力されます。
そのようにして作成した逆展開式のうち、ｘ^９の式までは「数値計算」にも記載されていますので、それと比較して一致していることを確認しました。
またｘ^１１の式は手計算で求めた式（［第５１回］）と一致しました。
そのことからｘ^１０の式も正しいと考えてもよいと思われます。

しかしｘ^１２〜ｘ^２０の各式については本当に正しい式になっているかどうか一抹の不安が残ります。
逆展開式を求める計算では分数の計算を行なうため、最終的に求めた逆展開式の係数が計算誤差によって不正確な値になってしまうことが考えられるからです。
かといってｘ^１１の式と同様に手計算で検算するというのは大変ですし、それをやったのではプログラムを書いた意味がありません。
厄介なのは途中を飛ばしてｘ^２０の式だけを検算するわけにはいかないという点です。
チェビシェフの多項式もそうだったのですが、逆展開式も次数の低い式から順に求めていく必要があるからです。

なんとかして簡単に検算する方法がないものかと思って、プログラムによって出力されたｘ^０〜ｘ^２０の逆展開式を眺めていましたら、各係数値には法則があるらしいことが見えてきました。
前回お見せした出力結果のうち、後半の逆展開式の部分を下に再掲します。

1=T0 x=T1 x^2=1/2(T2+T0) x^3=1/4(T3+3T1) x^4=1/8(T4+4T2+3T0) x^5=1/16(T5+5T3+10T1) x^6=1/32(T6+6T4+15T2+10T0) x^7=1/64(T7+7T5+21T3+35T1) x^8=1/128(T8+8T6+28T4+56T2+35T0) x^9=1/256(T9+9T7+36T5+84T3+126T1) x^10=1/512(T10+10T8+45T6+120T4+210T2+126T0) x^11=1/1024(T11+11T9+55T7+165T5+330T3+462T1) x^12=1/2048(T12+12T10+66T8+220T6+495T4+792T2+462T0) x^13=1/4096(T13+13T11+78T9+286T7+715T5+1287T3+1716T1) x^14=1/8192(T14+14T12+91T10+364T8+1001T6+2002T4+3003T2+1716T0) x^15=1/16384(T15+15T13+105T11+455T9+1365T7+3003T5+5005T3+6435T1) x^16=1/32768(T16+16T14+120T12+560T10+1820T8+4368T6+8008T4+11440T2+6435T0) x^17=1/65536(T17+17T15+136T13+680T11+2380T9+6188T7+12376T5+19448T3+24310T1) x^18=1/131072(T18+18T16+153T14+816T12+3060T10+8568T8+18564T6+31824T4+43758T2+24310T0) x^19=1/262144(T19+19T17+171T15+969T13+3876T11+11628T9+27132T7+50388T5+75582T3+92378T1) x^20=1/524288(T20+20T18+190T16+1140T14+4845T12+15504T10+38760T8+77520T6+125970T4+167960T2+92378T0)

最初に（）でくくって外に出した分母の値は左辺をｘ^ｎとしたときに２^ｎ−１になっています。
ここはまずＯＫです。
次に（）の中の第１項の係数は１、第２項の係数は３、４、５…の順になっていますから、これもＯＫです。
第２項は最初に１の次が３に飛んでいますが、これについては後で考えます。
とにかくそこだけ無視すればあとは問題はありません。
第３項は、これも最初の３から１０に飛んでいるところだけを無視すれば、１０、１５、２１、２８、３６、…と差が５、６、７、８、と順に開いていっています。
ここもよさそうです。
第４項はどうでしょうか。
ここも最初の１０から３５に飛んでいるところだけ無視すれば、３５、５６、８４、１２０、１６５、…には法則があることがわかります。
その差は２１、２８、３６、４５、…ですが、さらにその差をとってみると、７、８、９、…と差が順に増加していっています。

どうやら逆展開式の係数にはそういう法則があるようですので、最初のところだけを無視すれば、それ以降は差をとって、またその差をとって、…と計算していくことで正しい値になっているかどうか検算ができそうだということがわかってきました。
が。
困ったことが出てきました。

高次の式になって後ろのほうの項になってくると、第１階の差は取れても第２階、第３階というように差を取りたくてもそうするだけの式がなくて、正しいかどうかの検証ができないという問題です。
それにそもそも最初のところだけ値が飛んでいて、そこのルールがわからないという問題もあります。
たとえばｘ^１８の式の最終項からはじまる２４３１０Ｔ０、９２３７８Ｔ１、１６７９６０Ｔ２はこれだけではデータ不足で上でみつけたルールでは検算できません。
そもそも９２３７８の出所が全く不明です。
こうなるとどうしてもまずは最初のところで飛んでいる値の根拠をなんとか知る必要が出てきます。
またもや腕を組んでそのあたりを睨んでいましたら。

おお。
見えました。
わかりました。

世の中、こういう瞬間がたまらないのですよねえ。
うんうんうなって考えていても、なかなか見えてこないのですけれど、そこであきらめないでさらにがんばって考えていますと、突然一気に霧が晴れてぱっと視界が広がる瞬間が必ず訪れます。
本当なのですよ。
百尺竿頭進一歩（や。これはちょっと、意味がちがうか）。
ま。悟りの境地ですな。

説明と式を見比べることができるように、下に逆展開式の、今度はｘ^１０までの式を再掲します。
それを見ながら説明することにいたします。

1=T0 x=T1 x^2=1/2(T2+T0) x^3=1/4(T3+3T1) x^4=1/8(T4+4T2+3T0) x^5=1/16(T5+5T3+10T1) x^6=1/32(T6+6T4+15T2+10T0) x^7=1/64(T7+7T5+21T3+35T1) x^8=1/128(T8+8T6+28T4+56T2+35T0) x^9=1/256(T9+9T7+36T5+84T3+126T1) x^10=1/512(T10+10T8+45T6+120T4+210T2+126T0)

それでは、よろしいですか。
まず、初項ではないＴ０の係数は、そのひとつ前（上）の式のＴ１の係数と同じです。
ここで、ぜひとも、おお！と感動してください。

そして問題のＴ１の係数は、初項ではないときは、ひとつ前（上）の式のＴ２の係数＋Ｔ０の係数×２です。
ここでも、ぜひとも、おおおー！と感動願います。

初項ではないＴ２の係数は、ひとつ前（上）の式のＴ３の係数＋Ｔ１の係数です。
そして初項ではないＴ３の係数は、ひとつ前（上）の式のＴ４の係数＋Ｔ２の係数です。
以下同様です。

そして、ｘ^２０の式の係数もそのルールに合っていることを確認していただいて、そこでぜひとも、おおおおおー！と盛大に感動願います。

x^11=1/1024(T11+11T9+55T7+165T5+330T3+462T1) x^12=1/2048(T12+12T10+66T8+220T6+495T4+792T2+462T0) x^13=1/4096(T13+13T11+78T9+286T7+715T5+1287T3+1716T1) x^14=1/8192(T14+14T12+91T10+364T8+1001T6+2002T4+3003T2+1716T0) x^15=1/16384(T15+15T13+105T11+455T9+1365T7+3003T5+5005T3+6435T1) x^16=1/32768(T16+16T14+120T12+560T10+1820T8+4368T6+8008T4+11440T2+6435T0) x^17=1/65536(T17+17T15+136T13+680T11+2380T9+6188T7+12376T5+19448T3+24310T1) x^18=1/131072(T18+18T16+153T14+816T12+3060T10+8568T8+18564T6+31824T4+43758T2+24310T0) x^19=1/262144(T19+19T17+171T15+969T13+3876T11+11628T9+27132T7+50388T5+75582T3+92378T1) x^20=1/524288(T20+20T18+190T16+1140T14+4845T12+15504T10+38760T8+77520T6+125970T4+167960T2+92378T0)

あ。
そうすると。
わざわざ分数の計算をしなくても、上のルールを使えば、簡単な整数の計算プログラムを書くだけで逆展開式が求まってしまいますね。
ここでもう一度。
おお！（感動）

ＭＹＣＰＵ８０でＣＰ／Ｍを！［第５３回］
２０１４．１０．１６ｕｐｌｏａｄ

前へ
次へ
ホームページトップへ戻る