数理解析研究所講究録 1295 巻 2002 年 197-202

197

区間演算によるハイブリッド有理関数近似と安定化理論について
村上 裕美 (Yumi MURAKAMI) ’ 甲斐 博 (Hiroshi KAI) \dag er
愛媛大学 工学部
愛媛大学理工学研究科NODA)\ddagger

野田 松大郎 (Matu-Tarow

愛媛大学 工学部

1

はじめに有理関数補間を用いて関数近似を行った場合、補間区間内に不必要な極が現れる場合があるという問題が知られている
この不必要な極は、補間を行う有理関数の分子分母の多項式が、 補間区間内に非常に近$[3]_{\text{。}}$

い値の零点を持つために現れる。 これまでの研究では、 このことを利用して分子分母の多項式の近似 GCDを求めて、 この零点を近似的な共通因子として取り除く方法 $[1, 2]$ が提案されている。本研究では、 有理関数補間を行うときに現れる不必要な極のふるまいについて、 有効桁数を変化させた場合と補間を行う多項式の次数を変化させた場合についての再検討を行うと共に、 安定化理論 [4] を用いた有理関数補間についての検討を行う。

2

有理関数補間について

関数 $f(x)\in C[a, b]$ に対する有理関数補間は次のように計算される。 有限個の離散点 $a=x\mathit{0}<x_{1}<$$\ldots<x_{m+n}=b$ を与え、 対応する関数値 $f(x_{k})=f_{k},$ $k=0,1,$ $\cdots,m+n$ を求める。 ここで与えられた $m,n$ に対して、$r(xk)= \frac{p(x_{k})}{q(x_{k})}=f_{k}$$k=0,1,$$\cdots$$+n$,。

を満たすような$r_{m,n}(x)= \frac{p_{m}(x)}{q_{n}(x)}=\frac{\sum_{1=0}^{m}a_{\dot{l}}x^{\dot{l}}}{\sum_{j=0}^{n}b_{j}x^{j}}$を求める。 この有理関数を $(m,n)$ 有理関数と呼び、便宜上 $b_{0}=1$ と規格化する。多項式の係数 $a:,$

般に浮動小数であり、 線形方程式を解くことによって求められる。

.umi@hpc.cs.ehime-u.ac.jp$\mathrm{r}_{\mathrm{C}}$fkai@hpc.cs.ehime-u.ac.jp\ddagger noda@hpc cs.ehime-u.ac jp
XXIX-I$b_{j}$

は一1983

不必要な極のふるまいについて前節で述べたような有理関数補間を行うと、 元の関数 $f(x)$ が連続であるのに対して結果として得られた有理関数が不必要な極を持ち、不連続になってしまうことがある。 これは、不必要な極に対応する有理関数の分子 $p_{m}(x)$ の零点が分母 $q_{n}(x)$ の零点に非常に近い値をとっていることが原因となっている [2]。
ここでは、 有効桁数は補間多項式の次数を変化させたときの不必要な極のふるまいについて再検討を行う。 $\log(x+2)$ を補間区間 $[1, 2]$ で有理関数近似を行った場合の不必要な極の位置を表 1 に示す。 この結果

から、有効桁数を増加させるほど不必要な極が出やすく、 また補間を行う多項式の次数が大きくなるほど不必要な極が出やすくなることがわかる。

4Gauss 消去法の計算過程について補間を行う多項式の係数は、線形方程式を Gauss 消去法を用いて解くことによって決定される。 この解の値は、有効桁数が少ないときには全く異なる値となっているが、有効桁数を増加させるにしたがって一定の値に収束していく。 そこで、 不必要な極と Gauss 消去法を行う行列の性質との関係についての検証を行う。

4.1

行列の条件数線形方程式の係数行列$A$の条件数は、cond $A=||A||||A^{-1}||$で計算される。表 1 で使用したものと同じ関数 $\log(x+2)$ で同じ補間区間 $[1, 2]$ とした場合の行列の条件数は、 表 2 のようになる。

このように有理関数補間に使用される行列は、非常に悪条件となっている。 また、行列の条件数は有効桁数の少ない場合には有効桁ごとに全く異なっているが、有効桁数を多くするにしたがって一定の値に収束してくることがわかる。

条件数の変化からも明らかだが、 分子分母に 5 次のような低次の多項式を持つような有理関数補間においても、有効桁数が少ない場合には各係数の値は不安定となり、 当然得られる有理関数も不安定になる。
方、 このような場合にも有効桁数を 20 桁以上にすると、各係数の値も得られる有理関数の値も安定してく–ることがわかる。 このような安定な有理関数補間が得られるのは、表 2 から $(10, 10)$ 有理関数では有効桁数

40 桁、 $(15, 15)$ 有理関数では 60 桁等となることがわかる。
XXIX-2

199

ここで、少ない有効桁数では得られる解の値が不安定であっても、結果として得られた有理関数で近似を行うと図 1 に示されるように不必要な極を除けば正しく関数近似を行うことができる。 現在の実験結果からは、 Gauss 消去法で得られる解の値が不安定な場合に補間区間内に不必要な極が現れやすくなっている。

(b) 補間区間 $[1, 2]$ を拡大(a) 概形

図 1: 有効桁数 5 桁で得られた係数による有理関数近似

4.2

残差

有効桁数が少ないときには得られる解が不安定であるが、 不必要な極を除けば正しい有理関数近似が得られることを前節で示した。 そこで、有効桁数が少ない場合に得られる解の正当性を検証するために、残差の値を求めた。残差の値は、$||Ax$

一$b||$で計算される。 ここでのノルムは、 ユークリッドノルムを使用した。

XXIX-3200
表 3 の結果から、 解の値が不安定となっている有効桁数の少ない部分でも、 不必要な極を除けば残差の値を見ると十分な精度で正しく解けていると判断することができる。

なお、解力坏安定となる原因としては、入力時の浮動小数近似による丸め誤差の影響にょって、 Gauss 消去法の計算過程で行われるピボット選択の選択場所が異なっていることなどが考えられる。

5安定化理論を用いた有理関数補間
Gauss 消去法に安定化理論を適用して、 補間を行う有理関数の係数を得ることを考える。

5.1

人力と計算過程の有効桁を揃えた安定化

入力に用いる行列 $A$ の各成分の値を$a_{ij}$、入力の有効桁数を$p$桁とすると、 入力行列の各成分を$[a_{\dot{\iota}j}-0.5\mathrm{x}10^{-p},a_{\dot{\iota}j}+0.5\mathrm{x}10^{-p}]$から生成される区間数として、 安定化を施した Gauss 消去法を行う。
ここで、 正しい解が得られなかった場合は、 入力の有効桁数 を増加させていく方法で安定化を行う。
$p$511

結果

安定化を施した Gauss 消去法で、 有理関数補間の分子分母の多項式の次数と解が得られる有効桁数の関係は、表 4 のようになる。

安定化手法では、解が得られなかったり、誤った解が得られた場合には有効桁数を増加させて再度計算を行っていく。 この操作を繰り返し行うと、 いつかは必ず正しい解に到達するということを理論的に保証されている [4].

今回安定化を適用した Gauss 消去法では、 表 4 に示されている解が得られる有効桁数より少ない有効桁数では、消去法の計算過程で行列の階数が低下するために、解が求まらない。 そこで、安定化手法での手順
XXIX-4

201にしたがって有効桁数を増加させて再度計算を行っていく。 この過程で、初めて解が得られたとき、 その有効桁数は行列の条件数の値が完全に安定したときの有効桁数とほぼ一致する。
すなわち、 安定化を施した Gauss 消去法では、 計算に使用する有効桁数が条件数が安定する有効桁数を超えるまで解を導出しないため、有効桁数を増加させながら再計算することが要求される。結果、得られた解の値は必ず 4 節で述べたような 「安定した解」 の値を含むような区間数となっている。 したがって、 安定化を施した場合の有理関数補間によって得られる近似は、 必ず不必要な極を持たない滑らかな近似として得られる。 ただし、 多項式の次数が増加するほど、 解を得るのに必要な有効桁数も増加する。

52

人力の有効桁を固定し、計算過程の有効桁を変化させる安定化

前節のような安定化手法では、必要な有効桁数が非常に増大することが考えられる。 そこで、安定化を利用した Gauss 消去法の他の一つの可能性として、 入力の有効桁数を固定し、 その精度での厳密解に近い値を安定化手法によって得ることを考える。

入力に用いる行列の各成分の値を$a_{\dot{t}j}$、入力の有効桁数を$p$

桁とは別に、計算過程の有効桁数を$k$桁とし、入力行列の各成分を$[a_{1j}.-0.5\mathrm{x}10^{-p},a_{ij}+0.5\mathrm{x}10^{-p}]$から生成される区間数として、 Gauss 消去法を行う。
ここで、 入力の有効桁数 $p$ は固定し、 解が得られるまで計算過程の有効桁$k$のみを増加させていく方法

で安定化を行う。

521

結果解が得られる有効桁数は、 それぞれ表 5 のような結果となる。

このとき、 安定化を施した Gauss 消去法で解が得られたときは、 その解は、 入力の各或分を有理数として計算を行った場合の解を含むような区間として得られる。 したがって、入カデータの桁数が不足した場合は、安定化理論に基づく計算結果は、少ない有効桁数での「真の解」に収束する。 このため、 この解を用いて有理関数近似を行った場合には、 補間区間内に不必要な極が現れることがある。

6

まとめ
有理関数補間を単純に近似多項式の比として数値的にその係数を求めようとすると、 得られる有理関数には不必要な極が現れる。 この点を再検討し、不必要な極が近似多項式の次数や有効桁の変化によって大きXXIX-5202く変動することがわかった。 また、 このことは有理関数補間で使用される行列が、 非常に悪条件なものとなっていることに起因していることがわかった。有限桁の浮動小数計算では、有効桁数が少ないと解が不安定な値となる。 しかし、解の値が不安定であるにもかかわらず、残差の値からみると連立一次方程式の解としては正しく解けてていることがいえる。 このような解を用いて有理関数近似を行うと、 補間区間内に不必要な極は持つが、 それ以外の点では高い精度で元の関数を近似することができる。
一方、安定化理論た有理関数補間では、 入力と計算過程の有効桁数を同じにして計算を行えば、確実に安定した解の値のみを得ることができる。 したがって、安定化理論を適用したアルゴリズムで得られる有理関数の各係数は常に安定した解の値となっており、補間区間内に不必要な極が現れにくいものであると信頼できる。解が得られるまでにはある程度大きな有効桁数が必要となるが、得られる解を必ず信頼できることが利点であるといえる。
もちろん、有理関数補間そのものを得るには Pade’ 近似を始めとする有力な方法が多く研究されている。
しかし、 ここに示した単純な有理関数補間の議論は、 有効桁数と不必要な極の関係や悪条件行列の数値解であるにもかかわらず不必要な極以外では高い精度で有理関数補間が成立していること等、 多くの理論的に興味ある問題を提起しているといえる。

参考文献[1] 甲斐博: ハイブリッド有理関数近似の誤差評価, 情報処理学会論文誌,$\mathrm{V}\mathrm{o}\mathrm{l}.40$, No 4, PP.1754-1759,$\mathrm{A}\mathrm{p}\mathrm{r}.1999$[2] M.T.Noda and H.Kai: Hybrid rational function approximation and its accuracy analysis, Reliable
Computing$6,\mathrm{p}\mathrm{p}.429-438,2000$[3] M.T.Noda, E.Miyahiro and H.Kai: Hybrid rational function approximation and its use in the hy.
brid integration, in “Advances in Computer Methods for Partial Differential Equations VII” ,Vichnevetsky, D.Knight and G.Richter, IMACS, pp.565-571,1992$\mathrm{e}\mathrm{d}\mathrm{s}.\mathrm{R}$[4] K.Shirayanagi and M.Sweedler: ATheory of Stabilizing Algebraic Algorithms, Technical Report95-28, Cornell University, 1995, pp.1-92.

XXIX-6