偽レギュラ

数学において、レギュラ・ファルシ（偽位置法）とは、単一の未知数を求めるために線形方程式や滑らかな非線形方程式を解くアルゴリズム群である。楔形文字や象形文字に見られる最も古い例では、この方法は単純な試行錯誤を、初期推定値の比例補正に置き換えている。現代では、この方法は2つの異なる推定値に基づく線形補間を利用する。

2つの歴史的類型

歴史的に、偽位置法には単純偽位置法と二重偽位置法の2つの基本的なタイプを区別することができる。

単純な偽位置法は、直接比例を含む問題を解決することを目的としており、除算の初期のアルゴリズムと考えることができます。このような問題は、代数的に次の形式で記述できます。x を決定して $、$

ax=b,

$a$ と $b$ が既知の場合。この方法は、テスト入力値 $x'$ を使用し、対応する出力値 $b'を$ 乗算によって求めることから始まります。ax $' = b'$ 。次に、比例調整によって正しい答えが求められます $。x = ⁠ b / b' ⁠ x'$ 。

例として、リンド・パピルスの問題 26 を考えてみましょう。これは、(現代の記法で) 方程式 $x + ⁠ x / 4 ⁠ = 15$ の解を求める問題です。これは偽位置法で解かれます。^{[ 1 ]}まず、 $x = 4$ と仮定して、左辺で4 + ⁠ 4 / 4 ⁠ = 5を得ます。この仮定は整数値が得られるので良い選択です。しかし、4 は元の方程式の解ではありません。3 分の 1 しか得られない値になるからです。これを補正するために、 $x (現在 4 に設定) に 3 を掛けて再度代入し、$ 12 + ⁠ 12 / 4 ⁠ = 15を得て、解が $x = 12$ であることを確認します。

ダブルフォールスポジションは、代数的に $次$ の形式で記述できるより難しい問題を解決することを目的としています。

f(x)=ax+c=0,

もしそれが分かっているならば

{\begin{aligned}f(x_{1})&=b_{1};\\f(x_{2})&=b_{2}.\end{aligned}}

二重偽位置は、数学的には線形補間と同等です。テスト入力のペアとそれに対応する出力のペアを使用することで、このアルゴリズムの結果は、 ^[²^]で与えられます。

x={\frac {b_{1}x_{2}-b_{2}x_{1}}{b_{1}-b_{2}}},

暗記して丸暗記で実行することになるでしょう。実際、ロバート・レコードが著書『 Ground of Artes』（1542年頃）で述べた規則は次のとおりです。 ^{[ 2 ]}

この仕事は偶然に導かれるままに進め。偶然によって真実へと進むことができる。そしてまず、たとえそこに真実がなくても、質問によって仕事を進めよ。そのような偽りは良い土台となるので、それによってすぐに真実が見つかるだろう。多くのものからさらに多くのものへ、少なすぎるものから少なすぎるものへ。多すぎるものを再び少なすぎるものへ、少なすぎるものに多くの平野を加えよ。反対のものを交差させて増やし、すべての真実を偽りによって見つけ出せ。

アフィン線形関数の場合、

f(x)=ax+c,

二重偽位置法は正確な解を提供するが、非線形関数 $f$ の場合は反復によって逐次的に改善できる近似値を提供する。

歴史

単純な偽位置法は、古代バビロニアの数学の楔形文字粘土板や、古代エジプトの数学のパピルスに見られる。^[³^]^[¹^]

二重偽位置法は、古代末期に純粋に算術的なアルゴリズムとして出現しました。紀元前200年から紀元後100年にかけて書かれた古代中国の数学書『九章算術』^{[ 4 ]}では、第7章の大部分がこのアルゴリズムに割かれていました。そこでは、具体的な算術的議論によって手順が正当化され、円錐曲線上の割線と呼ばれるものを含む、さまざまな物語問題に創造的に適用されました。より典型的な例は、「過剰と不足」条件を含むこの「共同購入」問題です。^[⁵^]

今度は商品を共同で購入します。全員が8コインずつ出し、余剰は3コインです。全員が7コインずつ出し、不足は4コインです。人数、商品の価格、一人当たりの金額を答えてください。答え：7人、商品の価格53。^{[ 6 ]}

9 世紀から 10 世紀にかけて、エジプトの数学者アブカミルは、二重偽位置法の使用に関する、現在では失われてしまった論文「二つの誤りの書」（Kitāb al-khaṭāʾayn ）を著しました。中東で現存する二重偽位置法に関する最古の著作は、レバノンのバールベク出身のアラブの数学者クスタイブンルカ（10 世紀）によるものです。彼は、形式的なユークリッド幾何学の証明によってこの手法を正当化しました。中世イスラム数学の伝統では、二重偽位置法はhisāb al-khaṭāʾayn （「二つの誤りによる計算」）として知られていました。これは、商業や法律上の問題（コーランの相続規則に従った財産の分割）などの実際的な問題や、純粋に娯楽的な問題を解決するために何世紀にもわたって使用されました。このアルゴリズムは、イブン・アル＝ヤサミンに帰せられる詩や、アル＝ハッサールとイブン・アル＝バンナによって説明された天秤の図など、記憶術の助けを借りて暗記されることが多かった。この3人はいずれもモロッコ出身の数学者である。^[⁷^]

ピサのレオナルド（フィボナッチ）は、著書『算盤の書』（西暦1202年）の第13章を、二重偽位置法の使用法の説明と実証に充て、アラビア語の文献から学んだアル・ハタイン法にちなんで、この方法をレグリス・エル・ハタインと名付けた。^[⁷^] 1494年、パチョーリは著書『算術大全』でエル・カタイムという用語を使用したが、おそらくこの用語はフィボナッチから借用したものと思われる。他のヨーロッパの著述家はパチョーリに倣い、時にはラテン語や俗語に翻訳した。例えば、タルタリアは1556年にパチョーリの用語のラテン語版を俗語の「偽位置」に翻訳した。^[⁸^]パチョーリの用語は16世紀のヨーロッパの著作ではほとんど見られなくなり、この技法は「偽の規則」、「位置の規則」、「偽位置の規則」など様々な名前で呼ばれた。Regula Falsi は、早くも 1690 年頃には Rule of False のラテン語版として登場しています。^[²^]

16世紀のヨーロッパの著述家の中には、真実を探求する科学における方法の名前について謝罪する必要性を感じた者もいた。例えば、1568年にハンフリー・ベイカーは次のように述べている。^{[ 2 ]}

虚偽の法則は、欺瞞や虚偽を教えるからそのように名付けられているのではなく、あらゆる冒険で取られた偽りの数によって、要求された真の数を見つけ出すことを教えるものであり、実践されているすべての俗法則の中で^最も優れている。

数値解析

偽位置法は線形関数に対して厳密解を与えるが、より直接的な代数的手法がこれらの関数に対しては代わりに用いられるようになった。しかし、数値解析においては、二重偽位置法は反復数値近似法における根探索アルゴリズムとして用いられるようになった。

多くの方程式、特に複雑な方程式のほとんどは、反復的な数値近似によってのみ解くことができます。これは試行錯誤から成り、未知量のさまざまな値を試行します。この試行錯誤は、手順の各ステップで解の新しい推定値を計算することによって導かれます。計算による推定値を得る方法は数多くあり、regula falsi はそのうちの 1 つを提供します。

方程式が与えられたとき、そのすべての項を片側に移動して、 $f (x) = 0 の$ 形にします。ここで、 $f$ は未知変数 $x$ の何らかの関数です。この方程式を満たす値 $c 、つまり$ $f (c) = 0$ は、関数 $fの$ 根または零点と呼ばれ、元の方程式の解です。f $が$ 連続関数であり、 $f$ $($ $a$ $0$ $)$ と $f$ $($ $b$ $0$ $)$ が反対の符号を持つ 2 つの点 $a$ $0$ と $b$ $0$ が存在する場合、中間値の定理により、関数 $f$ は区間 $($ $a$ $0$ $,$ $b$ $0$ $)$ に根を持ちます。

このような根の近似値を得るために使用できる根探索アルゴリズムは多数あります。最も一般的なものの1つはニュートン法ですが、特定の状況下では根を見つけられない場合があり、関数の導関数を計算する必要があるため、計算コストが高くなる可能性があります。他の方法が必要であり、一般的な方法の1つに2点ブラケット法があります。これらの方法は、 $k$ 番目のステップで、 $($ $a$ $k$ $,$ $b$ $k$ $)が$ $f$ の根を含むような、縮小する区間 $[a k, b k]$ のシーケンスを生成することによって進みます。

2点ブラケット法

これらの方法は、試行錯誤によって最初に見つかった、 $f$ $($ $x$ $)の符号が反対になる 2 つの$ $x値から始まります。連続性の仮定の下では、$ $f$ の根は必ずこれら 2 つの値の間に存在し、つまり、これらの値が根を「挟む」ことになります。次に、これら 2 つの値のちょうど中間の点が選択され、根を挟むより小さな区間を作成するために使用されます。選択された点が $cの場合、より小さな区間は$ $cから、$ $f$ $($ $x$ $)の符号が$ $f$ $($ $c$ $)$ の符号と反対になる終点までになります。f $($ $c$ $) = 0$ という可能性の低いケースでは、根が見つかったことになり、アルゴリズムは停止します。それ以外の場合は、根の近似値を必要な精度で得るために、この手順が何度でも繰り返されます $。$

任意の区間内で選択された点は、解の推定値と考えることができる。この方法の様々なバリエーションは、この解の推定値を計算する方法の違いに基づいている。

括弧を維持し、解の推定値が括弧区間の内部にあることを保証することで、解の推定値が解に収束することが保証されます。これは、ニュートン法や割線法などの他の根探索方法では得られない保証です。

最も単純なバリエーションである二分法では、括弧区間の中点として解の推定値を計算します。つまり、ステップ $k$ において現在の括弧区間が $[a k, b k]$ である場合、新しい解の推定値 $c k$ は次のように得られます。

c_{k}={\frac {a_{k}+b_{k}}{2}}.

$これにより、 c k$ $がa k$ と $b k$ の間にあることが保証され、解への収束が保証されます。

区間の長さは各ステップで半分になるため、二分法の誤差は平均して反復ごとに半分になります。したがって、3回の反復ごとに、この方法は精度を約2/3倍、つまり小数点以下約1桁向上させます^。これは一般的に1次収束と呼ばれ、精度の桁数が反復回数に比例することを意味します。

regula falsi (偽の位置) メソッド

二分法の収束速度は、異なる解推定値を用いることで改善できる可能性がある。

regula falsi法は、現在の区間における関数の両端を結ぶ線分の $x$ 切片として新しい解の推定値を計算します。本質的に、実際の関数を区間内の線分に置き換え、その線分に対して古典的な二重偽位置公式を使用することで、根が近似されます。^[⁹^]

より正確には、 $k$ 番目の反復において、区間が $(a k, b k)であると仮定します。図に示すように、点$ $(a k, f (a k))$ と $(b k, f (b k))$ を通る直線を構築します。この直線は、関数 $f$ のグラフの割線または弦です。点傾斜形式では、その方程式は次のようになります。

yf(b_{k})={\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(x-b_{k}).

$ここで、 c k を$ $この直線のx$ 切片、つまり $y$ $= 0となる$ $x$ の値として選び、これらの値を代入して、

f(b_{k})+{\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(c_{k}-b_{k})=0.

この方程式をc _kについて解くと次のようになります。

c_{k}=b_{k}-f(b_{k}){\frac {b_{k}-a_{k}}{f(b_{k})-f(a_{k})}}={\frac {a_{k}f(b_{k})-b_{k}f(a_{k})}{f(b_{k})-f(a_{k})}}.

この最後の対称形式は、浮動小数点演算を使用する際に計算上の利点があります。解に近づくにつれて、 $a k$ と $b k は$ 非常に近くなり、ほぼ常に同じ符号になります。このような減算では、相殺によって精度が失われる可能性があります。f $($ $b$ $k$ $)$ と $f$ $($ $a$ $k$ $)は常に反対の符号であるため$ $、$ 改良された式の分子の「減算」は実質的に加算になります (分母の減算も同様です)。

反復回数 $k$ において、上記のように $c k$ を計算し、 $f (a k)$ と $f (c k)$ の符号が同じであれば、 $a k + 1 = c k$ および $b k + 1 = b k$ と設定し、そうでなければ $a k + 1 = a k$ および $b k + 1 = c k$ と設定します。このプロセスは、根が十分に近似されるまで繰り返されます。上記の式は、割線法でも使用されます。

非線形関数では、探索区間が十分に縮小して、その区間全体で2階微分が一定の符号を持つようになると、探索の一方の端点が固定され、もう一方の端点は根に収束します。したがって、解の最良推定値は、最後に計算された値です。 $c_{k}$ しかし、区間の縮小が止まるため、偽レギュラ法は二分法の精度保証には及ばない。場合によっては、収束速度が二分法を下回ることもある。これらの欠点を最小限のコストで修正できるため、一般的には偽レギュラ法の改良版が好まれる。

分析

初期端点 $a 0$ と $b 0は$ $f (a 0)$ と $f (b 0)$ が反対の符号になるように選択されているため、各ステップで、いずれかの端点が $fの根に近づきます。区間内で$ $f$ の 2 階微分が一定の符号である場合(つまり変曲点がない場合)、収束する端点が更新される一方で、一方の端点 ( $f$ も同じ符号を持つ端点) は以降のすべての反復で固定されたままになります。結果として、二分法とは異なり、括弧の幅はゼロに近づきません (ゼロが $sign(f) = -sign(f ")$ となる変曲点にある場合を除く)。結果として、偽の位置を選択するために使用される $f$ $($ $x$ $)$ の線形近似は、可能な限り迅速に改善されません。

この現象の一例は関数である。

f(x)=2x^{3}-4x^{2}+3x

初期括弧 [ − 1,1] 上で。左端− 1 は決して置き換えられません (最初は変化せず、最初の 3 回反復後、区間内で $f "$ は負になります)。したがって、括弧の幅は 1 を下回ることはありません。したがって、右端点は線形速度で 0 に近づきます (正確な桁数は線形に増加し、収束速度は 2/3 です)。

不連続関数の場合、この方法では関数の符号が変化する点（例えば、 $1/$ $x$ や符号関数の $x = 0$ ）しか見つけることができません。符号の変化に加えて、関数がその点で未定義（または別の値を持つ）であっても、関数の極限がゼロになる点に収束する可能性もあります（例えば、区間 [-0.5, 3.0] $から始まる$ $f$ $($ $x$ $) = abs($ $x$ $) -$ $x²$ で与えられる関数の $x$ $= 0の場合、$ $x$ $\neq 0$ の場合、 $f$ $(0) = 5$ の場合）。不連続関数では、この方法がゼロ極限または符号変化に収束しないことが数学的に起こり得ますが、実際には問題になりません。なぜなら、両端点が符号が変化しない不連続点（例えば、 $x$ $= \pm1$ の場合）に収束し続けるには、無限に連続する一致が必要になるからです。

f(x)={\frac {1}{(x-1)^{2}}}+{\frac {1}{(x+1)^{2}}}.

二分法を用いることで、この仮説上の収束問題を回避できる。

regula falsiの改善

偽レギュラ法は常に収束し、通常は二分法よりもかなり速く収束しますが、収束を遅らせる状況も存在し、場合によっては収束が著しく遅くなることもあります。この問題は偽レギュラ法に限ったことではなく、二分法以外のすべての数値方程式解法は、特定の条件下で収束が遅い、あるいは収束しないという問題を抱える可能性があります。ニュートン法や割線法は、収束する代わりに発散することがあり、多くの場合、偽レギュラ法の収束を遅らせるのと同じ条件下で発生します。

しかし、regula falsiは最良の方法の 1 つであり、改良されていない元のバージョンでも最良の選択肢となる場合が多い。たとえば、導関数の評価に非常に時間がかかるためニュートン法が使用できない場合や、ニュートン法と逐次代入法が収束しない場合などである。

偽レギュラの不具合は容易に検出できます。同じ終点が2回連続して保持されてしまうのです。この問題は、比較的まれな不利な状況による処理速度の低下を回避するために、修正された偽の位置を選択することで簡単に解決できます。偽レギュラに対するこのような改良は数多く提案されており、そのうちの2つ、イリノイアルゴリズムとアンダーソン・ビョークアルゴリズムについては以下で説明します。

イリノイアルゴリズム

イリノイアルゴリズムでは、新しいy値（つまり $f$ $($ $c$ $k$ $)）が前のy値（$ $f$ $($ $c$ $k$ $- 1$ )）と同じ符号を持つ場合、次の推定計算で保持された終点の $y$ 値を半分にします。これは、前のステップの終点が保持されることを意味します。したがって、次のようになります。

c_{k}={\frac {{\frac {1}{2}}f(b_{k})a_{k}-f(a_{k})b_{k}}{{\frac {1}{2}}f(b_{k})-f(a_{k})}}

または

c_{k}={\frac {f(b_{k})a_{k}-{\frac {1}{2}}f(a_{k})b_{k}}{f(b_{k})-{\frac {1}{2}}f(a_{k})}},

端点値の 1 つを重み付けを下げることで、次の $c k が$ 関数のその側で発生するように強制します。^{[ 10 ]}上記の係数⁠ 1 / 2 ⁠は任意に見えるかもしれませんが、超線形収束を保証します (漸近的に、アルゴリズムは任意の修正ステップの後に 2 つの通常のステップを実行し、収束次数は 1.442 です)。再スケーリングを選択する他の方法もあり、それによってさらに優れた超線形収束率が得られます。^[¹¹^]

上記のレギュラ・ファルシへの調整は、一部の学者によってイリノイアルゴリズムと呼ばれています。 ^{[ 10 ]}^{[ 12 ]}フォード（1995）は、この方法と、偽位置法の他の類似した超線形変種を要約し、分析しています。^{[ 11 ]}

アンダーソン・ビョルクアルゴリズム

$k$ 番目の反復において、区間が $[a k, b k]$ であり、新たに計算された推定値 $c k$ $の関数値がf (b k)$ と同じ符号を持つと仮定します。この場合、新しい区間 $[a k + 1, b k + 1] = [a k, c k]$ となり、左端点が保持されます。（ここまでは、通常の Regula Falsi およびイリノイアルゴリズムと同じです。）

しかし、イリノイアルゴリズムでは $f (a k)$ に1 / 2を掛けるのに対し、アンダーソン-ビョルクアルゴリズムでは $m$ を掛けます。ここで $m は$ 次の 2 つの値のいずれかをとります。^[¹³^]

${\begin{aligned}m'&=1-{\frac {f(c_{k})}{f(b_{k})}},\\m&={\begin{cases}m'&{\text{if }}m'>0,\\{\frac {1}{2}}&{\text{otherwise.}}\end{cases}}\end{aligned}}$

単純な根の場合、アンダーソン・ビョルク法は実際には非常に優れた性能を発揮します。^{[ 14 ]}

ITP法

与えられた $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$ 、 $n_{1/2}\equiv \lceil (b_{0}-a_{0})/2\epsilon \rceil$ そして $n_{0}\in [0,\infty )$ どこ $\phi$ 黄金比とは ${\tfrac {1}{2}}(1+{\sqrt {5}})$ 各反復において $j=0,1,2...$ ITP法はポイントを計算します $x_{\text{ITP}}$ 以下の3つのステップに従ってください。

【補間ステップ】二等分点と正則点を計算します。 $x_{1/2}\equiv {\frac {a+b}{2}}$ そして $x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}$ ;
【切り捨てステップ】推定量を中央方向に摂動させる： $x_{t}\equiv x_{f}+\sigma \delta$ どこ $\sigma \equiv {\text{sign}}(x_{1/2}-x_{f})$ そして $\delta \equiv \min\{\kappa _{1}|ba|^{\kappa _{2}},|x_{1/2}-x_{f}|\}$ ;
【射影ステップ】推定値をminmax区間に射影します。 $x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}$ どこ $\rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {ba}{2}},|x_{t}-x_{1/2}|\right\}$ 。

関数の値 $f(x_{\text{ITP}})$ この点について質問が行われ、その後、両端で反対の符号の関数値を持つ部分区間を保持することで、区間が縮小され、根を挟むようになります。この 3 段階の手順により、推定値は二分法の minmax 特性と割線法の超線形収束の両方を享受することが保証されます。また、滑らかな関数と滑らかでない関数の両方において、二分法と補間法の両方の手法よりも優れていることが観察されています。^{[ 15 ]}

実務上の考慮事項

コンピュータを使って1つまたは数個の方程式を解く場合、二分法は適切な選択肢です。二分法は他の方法ほど高速ではありませんが（他の方法が最良の状態で問題なく動作する場合）、それでも実用的な速度で収束することが保証されており、反復ごとに誤差がほぼ半減し、3回の反復ごとに小数点以下約1桁の精度が向上します。

電卓を使った手動計算では、より高速な方法を使いたくなる傾向があり、通常は二分法よりも速く収束するが、常にそうとは限らない。しかし、コンピュータは二分法を用いても、必要な精度で方程式を非常に迅速に解くことができるため、信頼性の低い方法を使って時間を節約しようとする必要はない。そして、どの方法も二分法より信頼性が低い。

例外として、コンピュータプログラムが実行中に方程式を非常に何度も解かなければならない場合は、より高速な方法によって節約できる時間が大幅に増える可能性があります。

次に、プログラムはニュートン法から開始し、ニュートン法が収束しない場合は、イリノイ版やアンダーソン・ビョルク版などの改良版であるレギュラ・ファルシに切り替えることができます。あるいは、それでも二分法ほど収束しない場合は、二分法に切り替えることができます。二分法は常に、目覚ましいとは言えないまでも、実用的な速度で収束します。

$y$ の変化が非常に小さくなり、 $x$ の変化も非常に小さい場合、ニュートン法はほとんどの場合問題なく収束します。したがって、このような好ましい条件下では、誤差を非常に小さく抑え、かつ収束を非常に速くしたい場合、ニュートン法に切り替えることができます。

例：ガマの成長

『九章』第7章では、根を求める問題を現代語に翻訳すると次のようになる。

過剰と不足の問題その11：
ガマは初日に3 単位成長した。毎日、その植物は前日の成長量の1/2だけ成長していることが観察された。
クラブラッシュは初日に1単位成長した。その後、毎日、前日の成長量の2倍の成長を遂げた。
イグサがガマと同じ高さになるまでの時間（日数）を求めなさい。
答え： $\left(2+{\frac {6}{13}}\right)$ 日;高さは $\left(4+{\frac {8}{10}}+{\frac {6}{130}}\right)$ 単位。
説明：
仮に2日目だとします。イグサはガマよりも1.5 単位短い。
仮に3日目だとします。イグサはガマよりも1.75 単位高いです。∎

$これを理解するため、 n$ 日目（ $n$ = 1, 2, 3...）の植物の高さを等比数列でモデル化します。

B(n)=\sum _{i=1}^{n}3\cdot {\frac {1}{2^{i-1}}}\quad

ガマ

C(n)=\sum _{i=1}^{n}1\cdot 2^{i-1}\quad

クラブラッシュ

表記をより分かりやすくするために、 $\ k=i-1~.$ 植物の高さの系列を書き直す $\ B(n),\ C(n)\$ $k$ を用いて、等比級数の公式を呼び出します。

\ B(n)=\sum _{k=0}^{n-1}3\cdot {\frac {1}{2^{k}}}=3\left({\frac {1-({\tfrac {1}{2}})^{n-1+1}}{1-{\tfrac {1}{2}}}}\right)=6\left(1-{\frac {1}{2^{n}}}\right)

\ C(n)=\sum _{k=0}^{n-1}2^{k}={\frac {~~1-2^{n}}{\ 1-2\ }}=2^{n}-1\

次に、regula falsiを使用して、 $\ (C(n)-B(n))\$

\ F(n):=C(n)-B(n)={\frac {6}{2^{n}}}+2^{n}-7\

セット $\ x_{1}=2\$ 計算 $\ F(x_{1})=F(2)\$ これは $-1.5$ （「赤字」）に等しい。
セット $\ x_{2}=3\$ 計算 $\ F(x_{2})=F(3)\$ これは $1.75$ （「超過分」）に等しい。

推定根（1回目の反復）：

\ {\hat {x}}~=~{\frac {~x_{1}F(x_{2})-x_{2}F(x_{1})~}{F(x_{2})-F(x_{1})}}~=~{\frac {~2\times 1.75+3\times 1.5~}{1.75+1.5}}~=~{\frac {32}{13}}~\approx ~2.4615\

正確な根を求めるには、 $y=2^{n}$ そのため、私たちは解決しようと努めます $6/y+y-7~=~0$ を掛ける $y$ 二次方程式を得る $y^{2}-7y+6=0$ 根源を持つ $y=0$ （ここでは偽物である）そして $y=6$ （我々が求める根）。したがって $n~=~\log _{2}(6)~\approx ~2.5849625$ そして、私たちの推定値には4.78%の誤差があります。

サンプルコード

C言語で書かれたこのサンプルプログラムは、イリノイアルゴリズムの例です。cos $($ $x$ $) =$ $x³$ となる正の数 $x$ $を$ 見つけるために、方程式は根を求める形式 $f$ $($ $x$ $) = cos($ $x$ $) -$ $x³$ $= 0$ $に$ 変換されます。

#include <stdio.h> #include <math.h>double f ( double x ) { return cos ( x ) - x * x * x ; } /* a,b: 探索する区間の端点 e: 相対誤差の上限の半分 m: 最大反復回数*/ double falsi_method ( double ( * f )( double ), double a , double b , double e , int m ) { double c , fc ; int n , side = 0 ; /* 区間の端点の開始値 */ double fa = f ( a ); double fb = f ( b );for ( n = 0 ; n < m ; n ++ ) { c = ( fa * b - fb * a ) / ( fa - fb ); if ( fabs ( b - a ) < e * fabs ( b + a )) break ; fc = f ( c );if ( fc * fb > 0 ) { /* fc と fb の符号が同じなので、c を b にコピーします */ b = c ; fb = fc ; if ( side == -1 ) fa /= 2 ; side = -1 ; } else if ( fa * fc > 0 ) { /* fc と fa の符号が同じなので、c を a にコピーします */ a = c ; fa = fc ; if ( side == + 1 ) fb /= 2 ; side = + 1 ; } else { /* fc * f_ が非常に小さい (ゼロのように見える) */ break ; } } return c ; }int main ( void ) { printf ( "%0.15f \n " , falsi_method ( & f , 0 , 1 , 5E-15 , 100 )); return 0 ; }

このコードを実行すると、最終的な答えは約0.865474033101614になります。

参考文献

1 2カッツ、ビクター・J. (1998)、『数学史』（第2版）、アディソン・ウェズリー・ロングマン、 15 ページ、ISBN 978-0-321-01618-8
1 2 3 4 Smith, DE (1958) [1925], History of Mathematics , vol. II, Dover, pp. 437–441 , ISBN 978-0-486-20430-7{{citation}}ISBN /日付の不一致（ヘルプ）
↑シャベール、ジャン＝リュック編 (2012) [1999]. 「3. 偽位置法」 .アルゴリズムの歴史：小石からマイクロチップまで. Springer. pp. 86–91 . ISBN 978-3-642-18192-4。
↑ニーダム、ジョセフ（1959）。『数学と天地の科学』『中国の科学と文明』第3巻。ケンブリッジ大学出版局。147頁以降。ISBN 978-0-521-05801-8。{{cite book}}ISBN /日付の不一致（ヘルプ）
↑ 「9つの章」。www -groups.dcs.st- and.ac.uk。2019年2月16日取得。
↑ Shen, Kangshen; Crossley, John N.; Lun, Anthony Wah-Cheung (1999). The Nine Chapters on the Mathematical Art: Companion and Commentary . Oxford University Press. p. 358. ISBN 978-7-03-006101-0。
1 2 Schwartz, RK (2004). Hisab al-Khata'ayn (二重偽位置による計算) の起源と発展における諸問題. 第 8 回北アフリカアラブ数学史会議。チュニジア、ラデス。オンラインで入手可能: http://facstaff.uindy.edu/~oaks/Biblio/COMHISMA8paper.doc 2011年9月15日にWayback Machineにアーカイブされ、「アーカイブされたコピー」(PDF)も利用可能です。2014年5月16日にオリジナル(PDF)からアーカイブされました。2012年6月8日に取得されました。{{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)
↑ジェネラル・トラッタート、vol. I、ヴェネツィア、1556 年、p.フォロー。 238、v、Regola Helcataym (ボキャブラ・アラボ) che in nostra lingua vuol dire delle false Positioni
↑コンテ、SD;ブール、カール・デ (1965)。初等数値解析: アルゴリズム的アプローチ(第 2版)。マグロウヒル。 p. 40. OCLC 1088854304。
1 2 Dahlquist, ゲルムント;ビョルク、オーケ (2003) [1974]。数値的手法。ドーバー。ページ231–232。ISBN 978-0486428079。
1 2 Ford, JA (1995). "非線形方程式の数値解法のためのイリノイ型アルゴリズムの改良" . ACM Transactions on Mathematical Software . 30 : 64–85 . 2025年7月1日取得。
↑ Dowell, M.; Jarratt, P. (1971). "方程式の根を計算するための修正されたregula falsi法". BIT . 11 (2): 168– 174. doi : 10.1007/BF01934364 . S2CID 50473598 .
↑ King, Richard F. (1983 年 10 月). "Anderson-Bjorck for Linear Sequences". Mathematics of Computation . 41 (164): 591–596 . doi : 10.2307/2007695 . JSTOR 2007695 .
↑ Galdino, Sérgio (2011). "A family of regula falsi root-finding methods" . Proceedings of 2011 World Congress on Engineering and Technology . 1. 2016年9月9日取得。
↑ Oliveira, IFD; Takahashi, RHC (2020-12-06). "An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality" . ACM Transactions on Mathematical Software . 47 (1): 5:1–5:24. doi : 10.1145/3423597 . ISSN 0098-3500 . S2CID 230586635 .

さらに読む

バーデン、リチャード・L.、フェアーズ、J・ダグラス（2000）。数値解析（第7 版）。ブルックス/コール。ISBN 0-534-38216-9。
シグラー、LE（2002）。フィボナッチの算盤、レオナルド・ピサーノの計算書。シュプリンガー・フェルラーク。ISBN 0-387-40737-5。
Roberts, AM (2020). 「コロンビア大学所蔵のアラビア語写本における二重偽位置論に関する論文における数学文献学」 . Philological Encounters . 5 ( 3–4 ): 3–4 . doi : 10.1163/24519197-BJA10007 . S2CID 229538951 . （中世アラビア語写本に収められた、これまで未発表だった二重偽陣形に関する論文について。）

[Katz-1] 1 2カッツ、ビクター・J. (1998)、『数学史』（第2版）、アディソン・ウェズリー・ロングマン、 15 ページ、ISBN 978-0-321-01618-8

[Smith-2] 1 2 3 4 Smith, DE (1958) [1925], History of Mathematics , vol. II, Dover, pp. 437–441 , ISBN 978-0-486-20430-7{{citation}}ISBN /日付の不一致（ヘルプ）

[3] シャベール、ジャン＝リュック編 (2012) [1999]. 「3. 偽位置法」 .アルゴリズムの歴史：小石からマイクロチップまで. Springer. pp. 86–91 . ISBN 978-3-642-18192-4。

[Needham1959-4] ニーダム、ジョセフ（1959）。『数学と天地の科学』『中国の科学と文明』第3巻。ケンブリッジ大学出版局。147頁以降。ISBN 978-0-521-05801-8。{{cite book}}ISBN /日付の不一致（ヘルプ）

[5] 「9つの章」。www -groups.dcs.st- and.ac.uk。2019年2月16日取得。

[6] Shen, Kangshen; Crossley, John N.; Lun, Anthony Wah-Cheung (1999). The Nine Chapters on the Mathematical Art: Companion and Commentary . Oxford University Press. p. 358. ISBN 978-7-03-006101-0。

[Schwartz-7] 1 2 Schwartz, RK (2004). Hisab al-Khata'ayn (二重偽位置による計算) の起源と発展における諸問題. 第 8 回北アフリカアラブ数学史会議。チュニジア、ラデス。オンラインで入手可能: http://facstaff.uindy.edu/~oaks/Biblio/COMHISMA8paper.doc 2011年9月15日にWayback Machineにアーカイブされ、「アーカイブされたコピー」(PDF)も利用可能です。2014年5月16日にオリジナル(PDF)からアーカイブされました。2012年6月8日に取得されました。{{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)

[8] ジェネラル・トラッタート、vol. I、ヴェネツィア、1556 年、p.フォロー。 238、v、Regola Helcataym (ボキャブラ・アラボ) che in nostra lingua vuol dire delle false Positioni

[9] コンテ、SD;ブール、カール・デ (1965)。初等数値解析: アルゴリズム的アプローチ(第 2版)。マグロウヒル。 p. 40. OCLC 1088854304。

[Dahlquist-10] 1 2 Dahlquist, ゲルムント;ビョルク、オーケ (2003) [1974]。数値的手法。ドーバー。ページ231–232。ISBN 978-0486428079。

[Ford-11] 1 2 Ford, JA (1995). "非線形方程式の数値解法のためのイリノイ型アルゴリズムの改良" . ACM Transactions on Mathematical Software . 30 : 64–85 . 2025年7月1日取得。

[12] Dowell, M.; Jarratt, P. (1971). "方程式の根を計算するための修正されたregula falsi法". BIT . 11 (2): 168– 174. doi : 10.1007/BF01934364 . S2CID 50473598 .

[13] King, Richard F. (1983 年 10 月). "Anderson-Bjorck for Linear Sequences". Mathematics of Computation . 41 (164): 591–596 . doi : 10.2307/2007695 . JSTOR 2007695 .

[14] Galdino, Sérgio (2011). "A family of regula falsi root-finding methods" . Proceedings of 2011 World Congress on Engineering and Technology . 1. 2016年9月9日取得。

[15] Oliveira, IFD; Takahashi, RHC (2020-12-06). "An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality" . ACM Transactions on Mathematical Software . 47 (1): 5:1–5:24. doi : 10.1145/3423597 . ISSN 0098-3500 . S2CID 230586635 .

[ 1 ]

[

[

[ 4 ]

[

[ 6 ]

[

[

[

[ 10 ]

[

[ 12 ]

[

[ 14 ]

[ 15 ]