aのｋ乗根を求める

プログラミングの課題で、「ある数aのk乗根を求める」というものがありました。問題に「改善値」というものを求める漸化式が載っているのですが、改善値が何を意味するのか、またその漸化式も理解しがたいのです。問題をそのまま載せますので、漸化式の解法、改善値の意味を教えてください。

問題
一般にaのk乗根は、ｋ＝2ｍとしたときには、　
X<n+1>=(1/m)((m-1)X<n>+(2a/(X<n>^(2m-1)+a/X<n>))
によってその改善値を求めることができる。ｋ乗根（ｋ＝偶数）を求めるプログラムを作成しなさい。

プログラムのとこは無視して下さい。
大変見難い数式ですが、よろしくお願いします。

、、、、、1、、、、、、、、、、、、、2a、、、、、
Xn+1=～～ {(m-1)Xn +～～～～～～～～～｝
、、、、、m、、、、、、、、、、、Xn^(2m-1)+a/Xn

↑うまく表示できるか・・・

No.2 ベストアンサー 回答者： age_momo 回答日時： 2007/01/21 21:03

丁度、一つ前にニュートン・ラフソン法についての質問がありますが、質問者さんは

これをご存知でしょうか？　この問題はこれの応用だと思います。
まず、改善値とはある値を取って方程式の解(x[n])とした時に漸化式によって計算した
x[n+1]がより近い値をとるように計算することです。このようなニュートン法や
2分法で数値解析する時にはよく出てくる言葉です。

次にこの問題をニュートン(ラフソン)法で解くと

f(x)=x^2m-a

が0になるところを探しますので

f'(x)=2mx^(2m-1)　より
x[n+1]=x[n]-{x[n]^2m-a}/2mx[n]^(2m-1)=(2m-1)/2m{x[n]+a/x[n]^(2m-1)}

となります。これでも十分、解は求まりますが、今回はもっと早く収束させるために
より小さな傾きを作ろうとしているように思います。
(ここからは勝手な想像です。二回微分しているのかと思いましたがそれとも違いますので)

今、f(x)=x^2m-a=0となるx=αを考えると
f'(α)=2mα^(2m-1)=2ma/α　(∵a=α^2m)
これとf'(x[n])の平均をとると
{2mx[n]^(2m-1)+2ma/α}/2=m{x[n]^(2m-1)+a/α}
これを漸化式の傾きに代入するとαにはx[n]を代用して

x[n+1]=x[n]-(x[n]^2m-a)/m{x[n]^(2m-1)+a/x[n]}=1/m{(m-1)x[n]+2a/(x[n]^(2m-1)+a/x[n]}

となります。(計算間違いしていたらごめんなさい）
通常はこのような計算をしませんが、今、この方程式が2回微分してもx>0の域で正なので
成立するように思います。
いずれにせよこれが大事な漸化式ならその導出が書いてあると思いますし、
通常は普通にニュートン・ラフトン法で数値解析すればいいと思いますので、
この式は頭の片隅に残しておいて、とりあえず、漸化式で十分、真の解に近くなるまでの
プログラムを組むことに専念されるのがよいと思います。

と書いていたら#1さんが値がおかしくなると書かれていますが、私の方は20^(1/16)を
それぞれニュートンラフトンとこの漸化式で解くと
x[0]=20ならニュートンラフトン法　50回、この方法24回、
x[0]=20/16=1.25ならニュートンラフトン法　5回、この方法3回で
10^-12以下の誤差になりました。20^(1/16)=1.2059085510307
(EXCEL　Worksheetで計算)

この回答へのお礼

ものすごい途中式ですね！！
絶対自分には解けなかったと思います。
まずニュートン法なんて初めて聞きましたし！！
この導き出された式は
「元の式より早く収束するが誤差が出てしまう」という認識でよいのでしょうか？？
単純に4の平方根を計算しても1.587・・・となってしまうようですし・・

お礼日時：2007/01/22 00:59

No.3 回答者： age_momo 回答日時： 2007/01/22 07:41

>「元の式より早く収束するが誤差が出てしまう」という認識でよいのでしょうか？？

いえ、ちゃんと2に収束しますよ。おそらく式の入力ミスでしょう。
少しやってみます。以下、

セル番号　入力　　で書いておきます。そのまま、コピペしてください。
A1　4　(ここに元の数を入れます)
B1　2　(ここにk乗根のkを入れます)
A2　1　(出発する数字、今、仮に1)
A3　=1/(B$1/2)*((B$1/2-1)*A2+2*A$1/(A2^(B$1-1)+A$1/A2))
A4-A20　A3をコピーしてペースト

ついでにニュートンラフソン法も入れておきます。

C2　1　(同じく、1から出発)
C3　=C2-(C2^B$1-A$1)/B$1/C2^(B$1-1)
C4-C20　C3をコピーしてペースト

これでそれぞれが計算できます。平方根だとほとんど差がつきませんね。
ついでにA1に20、B1に16ぐらいを入れて比較してみてください。
同じ数字に収束しますが、左のほうがはるかに速いです。

この回答へのお礼

わざわざexcelの数式まで作っていただいてありがとうございます！
自分で作った数式間違えてました・・・
課題は間違ってなかったのですね　笑
どうもありがとうございました！！！

お礼日時：2007/01/22 10:47

No.1 回答者： inara 回答日時： 2007/01/21 18:40

漸化式が変です。

これはニュートン法を使った関数値の求め方を利用したものですが、f(x)=x^k-aとしたときに、f(x)=0の解xがaのk乗根になるわけです。

f(x)=0の解xの漸化式は一般に

x[n+1]=x[n]-f(x[n])/f'(x[n])

で表されます。この場合、

f(x[n])=x[n]^k-a
f'(x[n])=k*x[n]^(k-1)

ですから、漸化式は

x[n+1]=x[n]-(x[n]^k-a)/{k*x[n]^(k-1)}--- (1)

のはずです。

試しに、a=2,k=4(m=2)のとき、p-aimarさんの漸化式を使って、初期値x[0]=1で計算すると、15回目で1.798908に収束しましたが、これは解(2^(1/4)=1.189207..)ではありません。(1)の漸化式を使った場合、同じ条件では、4回目で1.189207に収束し、値も合っています。

漸化式とは、ある値x[n]と次の値x[n+1]の関係を表したもので、何かの数列を作るときの元となる式です。まず初期値をx[0]として、式のx[n]のところに代入して、その結果得られたx[n+1]をまたx[n]に代入していくことを次々とやれば、x[n+1]はa^(1/k)にどんどん近づいていきます。このx[n+1]を改善値と言います。

参考文献：田中敏幸著「数値計算法基礎」コロナ社、p.107-109.

この回答へのお礼

どうもありがとうございます。
excelでやってみたらその通りでした！！
課題が間違っているんじゃ解けませんね　笑
「漸化式　改善値」で検索しても1件も見つからなかったので途方にくれてました。
本当にありがとうございました！！！！

お礼日時：2007/01/21 23:25