基本情報技術者 2009年秋期午後問08

次のアルゴリズムの説明及びプログラムを読んで、設問に答えよ。

　方程式の解の一つを求めるアルゴリズムである。任意に定めた解の予測値から始めて、計算を繰り返しながらその値を真の値に近づけていく。この方法は、ニュートン法と呼ばれる。　〔アルゴリズム1の説明〕　3次方程式

a_{3} x^{3} + a_{2} x^{2} + a_{1} x + a_{0} = 0

の解の一つを、次の手順で求める。

(1) 解の予測値

x

, 係数

a_{3}

a_{2}

a_{1}

a_{0}

を読み込む。 (2)

3 \times a_{3}

の値を

b_{2}

に、

2 \times a_{2}

の値を

b_{1}

に、

1 \times a_{1}

の値を

b_{0}

に、それぞれ求める。 (3) 次の①〜④の処理を一定の回数繰り返す。　①

a_{3} x^{3}

a_{2} x^{2}

a_{1} x

a_{0}

の値を求め、これを

f

とする。　②

b_{2} x^{2}

b_{1} x

b_{0}

の値を求め、これを

d

とする。　③

x

f

d

の値を印字する。　④

x - \frac{f}{d}

の値（解の一つにより近い値となる）を求め、これを新たな

x

とする。　プログラム1は、このアルゴリズム1を実装したものである。　〔アルゴリズム2の説明〕　アルゴリズム1を一般化して、

n

次方程式

a_{n} x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{1} x + a_{0} = 0

の解の一つを、次の手順で求める。　なお、方程式によっては解が求められない場合がある。

(1) 次数

n

, 解の予測値

x

, 係数

a_{n}, a_{n - 1}, \dots, a_{1}, a_{0}

を読み込む。 (2)

n \times a_{n}

の値を

b_{n - 1}

に、

(n - 1) \times a_{n - 1}

の値を

b_{n - 2}

に、…、

2 \times a_{2}

の値を

b_{1}

に、

1 \times a_{1}

の値を

b_{0}

に、それぞれ求める。 (3) 次の①〜④の処理を一定の回数繰り返す。　①　

a_{n} x^{n}

a_{n - 1} x^{n - 1}

+…+

a_{1} x

a_{0}

の値を求め、これを

f

とする。　②　

b_{n - 1} x^{n - 1}

b_{n - 2} x^{n - 2}

+…+

b_{1} x

b_{0}

の値を求め、これを

d

とする。　③　

x

f

d

の値を印字する。　④　

x - \frac{f}{d}

の値（解の一つにより近い値となる）を求め、これを新たな

x

とする。　プログラム2は、このアルゴリズム2を実装したものである。

設問1：

問題文を見る

　次の記述中のに入れる正しい答えを、解答群の中から選べ。

(1) 解の予測値x = 2.5, 係数

a_{3} = 1

a_{2} = - 3

a_{1} = - 1

a_{0} = 3

を与えて、3次方程式

x^{3} - 3 x^{2} - x + 3 = 0

の解の一つを求める（解は3, 1, −1）。プログラム1をある処理系で実行した結果、図1に示すとおり解の一つである

x = 3

が近似的に得られた。

　この印字結果の行番号6, 7の

x

の値（網掛けの部分）はいずれも3.000000である。行番号6, 7を印字した時点で変数

x

に保持されていた実際の値をそれぞれ

x_{6}

x_{7}

で表すと、a。　なお、この処理系では、実数型は2進数の浮動小数点形式であって、有効けた数は10進数で十数けた程度であることが分かっている。

(2) プログラム2では、係数

a_{k}

(k: n, n−1, …, 1, 0)の値を配列aの要素a[k]に、

b_{k}

(k: n−1, n−2, …, 1, 0)の値を配列bの要素b[k]に、それぞれ図2のように格納している。

　プログラム2の行番号9〜11は、アルゴリズム2の手順(2)の処理である。この部分のプログラムは、次のようになる。

　また、行番号13〜18は、アルゴリズム2の手順(3)の①と②の処理である。プログラム1では、例えばfの値

a_{3} x^{3} + a_{2} x^{2} + a_{1} x + a_{0}

を求める式を

　　f ← ((a3 × x + a2) × x + a1) × x + a0

　と変形して、演算回数を減らす工夫をしている。この部分にも同様の工夫をすると、プログラムは次のようになる。

(3) 次数

n = 4

, 係数

a_{4} = 1

a_{3} = - 8

a_{2} = 24

a_{1} = - 32

a_{0} = 16

として、4次方程式

x^{4} - 8 x^{3} + 24 x^{2} - 32 x + 16 = 0

の解を求める（4個の解がすべて2）。解の予測値をx = 2.00001として、ある処理系でプログラム2を実行したところ、図3に示すとおりの印字結果となった。

　この印字結果の行番号2では、xの値（網掛けの部分）が解である2から遠ざかってしまっている。その原因を調べるため、fを求める式に実際の数値を当てはめて、

　として、(A)の部分の中間結果を印字するプログラムを作り、同じ処理系で実行した。印字結果は−16.00000であり、正確な値−15.99999999999999999999と有効数字7けたで一致した。しかし、行番号1で印字されたfの値は、正確な値である

1 0^{- 20}

（印字の表記では1.000000(−20)）とは異なっている。　これらのことから判断して、(A)の部分では演算の過程でeが徐々に累積し、(A)の計算結果に16.0を加算するときに、けた落ちが発生したと考えられる。　 aに関する解答群　ア：

x_{6} = x_{7}

である　イ：

x_{6} \neq = x_{7}

である　ウ：

x_{6} = x_{7}

とも

x_{6} \neq = x_{7}

ともいえない　 bに関する解答群　ア：b[k-1] ← (k-1) × a[k] 　イ：b[k-1] ← k × a[k] 　ウ：b[k] ← k × a[k+1] 　エ：b[k] ← (k+1) × a[k+1] 　 c, dに関する解答群　ア：b[k-1] 　イ：b[k] 　ウ：b[k+1] 　エ：b[n-1] 　オ：b[n-1] × x 　カ：b[n-1] × x + b[n-2] 　 eに関する解答群　ア：けたあふれ　イ：けた落ち　ウ：指数下位けたあふれ　エ：丸め誤差

模範解答

a：イ、b：イ、c：エ、d：イ、e：エ

解説

解答の導き方

(1) $x_{6}$ と $x_{7}$ が等しいか

プログラム1は、各回で現在の

x

、

f

、

d

を印字してから、次の

x

を計算します。つまり、行番号6に印字された

x

が

x_{6}

で、その後に更新され、行番号7に印字された

x

が

x_{7}

です。

図1では、どちらの

x

も表示上は3.000000です。しかし、表示は有効数字7けたなので、内部に保持されている値が同じとは限りません。

ここで、行番号6の

f

は7.527369(−9)で、行番号7の

f

は0.000000と表示されています。同じ

x

と同じ係数から計算すれば、

f

も同じ値になるはずです。したがって、行番号6と行番号7の内部の

x

は異なります。よって、

x_{6} \neq = x_{7}

であり、選ぶのはイです。

(2) 配列 $b$ の格納と、 $f$ ・ $d$ の計算

まず、

b_{k}

は、多項式の微分で使う係数です。項

a_{k} x^{k}

を微分すると、

k a_{k} x^{k - 1}

になります。つまり、指数が

k - 1

の項の係数は

k a_{k}

です。

そのため、繰返しで

k

を

n

から1まで動かすとき、格納する場所は添字が

k - 1

の要素になります。

b [k - 1] \leftarrow k \times a [k]

これに一致するのはイです。たとえば、

k = n

のときは

b [n - 1]

に

n \times a [n]

を格納します。

次に、

f

と

d

を計算する部分を考えます。多項式を掛け算と足し算の入れ子にして計算すると、各項の累乗を個別に計算せずに済みます。この計算方法をホーナー法といいます。

f

は、最初に高い次数の2項を使って、

f \leftarrow a [n] \times x + a [n - 1]

とします。その後、

k

を

n - 2

から0まで動かし、

f \leftarrow f \times x + a [k]

と順に計算すれば、残りの項も加えられます。

d

は微分した多項式の値です。最初は最高次の項の係数である

b [n - 1]

を置きます。したがって、14行目の空欄cはエです。

その後、

k

を

n - 2

から0まで動かすたびに、次の項の係数

b [k]

を加えます。したがって、17行目の空欄dはイです。

(3) 演算の途中で起きていること

4次方程式は、

x^{4} - 8 x^{3} + 24 x^{2} - 32 x + 16 = (x - 2)^{4}

と表せます。したがって、

x = 2.00001

のとき、正確な

f

の値は

1 0^{- 20}

です。また、微分した式の値

d

は、正確には

4 \times 1 0^{- 15}

です。

この正確な値でニュートン法の更新を行うと、

f \div d

は

2.5 \times 1 0^{- 6}

となり、次の

x

は2.0000075になります。つまり、本来は解の2に近づくはずです。

ところが図3では、行番号1の

f

が-3.552714(−15)と印字されています。これは、正確な値

1 0^{- 20}

とは大きく異なります。そのため、

f \div d

の値も正しく計算できず、行番号2の

x

が2.888899になっています。

問題文の(A)の計算では、途中の値が-16付近になります。実数を有限の桁数で表す浮動小数点形式では、計算のたびに、表現できる近い値に丸めることがあります。このとき生じる誤差を丸め誤差といい、演算の過程で積み重なったと考えられます。よって、空欄eはエです。

さらに、表示上-16.00000となる(A)の値に16.0を加えると、ほぼ等しい大きさの数が打ち消し合い、正確な結果に含まれる小さな値を正しく得にくくなります。この現象がけた落ちです。丸め誤差が計算途中で積み重なることと、最後の加算でけた落ちが起きることは、別の現象です。

誤りやすいポイント

表示された $x$ が同じなら、内部の値も同じだと思う
表示桁数には限りがあります。図1のように同じ3.000000と表示されても、内部の値が異なる場合があります。
$b [k - 1]$ と $b [k]$ を取り違える
$a [k] x^{k}$ を微分すると、指数が1つ下がって $x^{k - 1}$ になります。そのため、係数 $k \times a [k]$ は $b [k - 1]$ に格納します。
丸め誤差とけた落ちを同じものだと考える
丸め誤差は、計算途中で数を近似して表すことで生じます。けた落ちは、近い大きさの数どうしを足し引きしたときに、有効な桁が失われる現象です。この問題では、前者が(A)の計算で積み重なり、後者が16.0を加算するときに起きています。

FAQ

Q: ニュートン法を使えば、必ず正しい解に近づきますか？
A: 必ずとは限りません。問題文にもあるとおり、方程式によっては解が求められない場合があります。また、この問題のように計算誤差が大きくなると、解から遠ざかることもあります。

Q: ホーナー法を使うのはなぜですか？
A: 多項式を入れ子の形で計算することで、累乗を別々に計算する手間を減らせるからです。プログラム1の

f

の式も、その形に変形されています。

Q: 行番号1で $f$ が正確な値と大きく異なるのはなぜですか？
A: 正確な

f

が非常に小さい一方、計算途中では-16付近の値を扱っています。途中の丸め誤差が小さな結果に対して大きく影響し、

f

の計算結果が正確な値からずれたためです。

関連キーワード: ニュートン法、ホーナー法、浮動小数点数、丸め誤差、けた落ち

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

基本情報技術者 2009年 秋期 午後 問08

次のアルゴリズムの説明及びプログラムを読んで、設問に答えよ。

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

基本情報技術者 2009年秋期午後問08

設問1：