G - 方程式/Equations Editorial by MMNMM
この問題はニュートン法を用いても解くことができます。
ニュートン法を用いることで、適当な初期値 \(x=x_0\) から \(x\to x-\dfrac{f(x)}{f^\prime(x)}\) と更新することを繰り返して方程式 \(f(x)=0\) の解を近似することができます。
\(f(x)=ax^5+bx+c\) のとき、\(x-\dfrac{f(x)}{f^\prime(x)}=\dfrac{4ax^5-c}{5ax^4+b}\) です。この式に従って \(x\) を更新することを十分な回数繰り返すことで解を求めることができます。
反復回数の（だいたいの）評価
ここでは、必要な反復回数に関する厳密な評価を与えず、何回反復すれば十分そうかについての考察を行います。
\(f(x)=ax^5+bx+c=0\) の解の真の値を \(\widehat{x}\) とします。 \(x_n=\widehat{x}+\varepsilon\) に対して \(1\) 回反復を行った値 \(x_{n+1}=\dfrac{4ax_n^5-c}{5ax_n^4+b}\) と \(\widehat{x}\) との差を評価することを考えます（余談ですが、Wolfram に数値的に評価をさせたところ、\(\left|\dfrac{x_{n+1}-\widehat{x}}{x_n-\widehat{x}}\right|\leq0.6125\) という評価が得られました）。
\(x_{n+1}-\widehat{x}=\dfrac{(10\widehat{x}^3+20\widehat{x}^2\varepsilon+15\widehat{x}\varepsilon^2+4\varepsilon^3)a\varepsilon^2}{b+5ax_n^4}=\dfrac{10a\widehat{x}^3}{b+5a\widehat{x}^4}\varepsilon^2+O(\varepsilon^3)\)
これを見ると、\(\varepsilon\) がある程度小さいとき、\(\widehat{x},b\) は小さいほど、\(a\) は大きいほど \(x_{n+1}-\widehat{x}\) が大きくなりそう（すなわち、収束が遅そう）であることがわかります。
なので、そのような最悪ケース \((a,b,c)=(10^9-2,1,-10^9)\) で \(x_0=2\) からはじめて真の解 \(\widehat{x}=1.0000000002000000002800000004\ldots\) との差が \(10^{-9}\) 以下となるような反復回数を求めてみます。計算を行うと
\[\begin{aligned} x_0-\widehat{x}&=0.999999999799\ldots\\ x_1-\widehat{x}&=0.612499999804\ldots\\ x_2-\widehat{x}&=0.319582242975\ldots\\ x_3-\widehat{x}&=0.121626325549\ldots\\ x_4-\widehat{x}&=0.023669091728\ldots\\ x_5-\widehat{x}&=0.001069528281\ldots\\ x_6-\widehat{x}&=0.000002282896\ldots\\ x_7-\widehat{x}&=0.000000000010\ldots \end{aligned}\]
となり、\(7\) 回の反復で誤差が \(1.04\times10^{-11}\) ほどになりました。 実際に \(x_0=2\) から \(7\) 回反復を行うことで、この問題のテストケースについて AC を得ることができます。
実装は以下のようになります。実際の提出
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main(){
int a, b, c;
cin >> a >> b >> c;
long double x = 2;
for(int i = 0; i < 10; ++i)x = (4 * pow(x, 5) * a - c) / (5 * pow(x, 4) * a + b);
cout << fixed << setprecision(20) << x << endl;
return 0;
}
posted:
last update: