题解 UVA10428 【The Roots】
Hexarhy
2021-03-31 20:21:02
### Preface
牛顿迭代法模板题。但是被 UVA 这个屑 OJ 搞得体验非常不好/tuu。
**前置知识：导数入门。**
### Translation
给定一个 $n(n\le 5)$ 次多项式 $f(x)$，当 $n=0$ 时输入终止（样例没有但事实确实如此）。求出 $f(x)=0$ 所有根，升序输出。
保证存在 $n$ 个实根，且所有实根的绝对值 $\le 25$。有 $T(T\le 5000)$ 组询问。
### Solution
我们来推一下牛顿迭代法。
假设已经得到了一个近似解 $x$，而答案为 $x_0$。这两点所在直线可以近似认为是过 $x_0$ 的切线。那么就得到：
$$f'(x)=\frac{f(x)-f(x_0)}{x-x_0}$$
$f(x_0)=0$，并将上式化简得到：
$$x_0=x-\frac{f(x)}{f'(x)}$$
然后就可以递推做了。一般写法是根据 $f(x)$ 是否小于 $\epsilon$ 来继续迭代的。
> 牛顿迭代法的收敛率是平方级别的，这意味着每次迭代后近似解的精确数位会翻倍。 —— [OI Wiki](https://oi-wiki.org/math/newton/)
时间复杂度上通常认为是常数级别（就像并查集复杂度中的 $\alpha(n)$），并且 `<cmath>` 里的 `std::pow()` 是使用了牛顿迭代法的。
-----
这题的第二步便是如何把 $n$ 个根都求出来。
刚开始很 sb 地想到用韦达定理折腾一下，结果发现直接把原多项式除以一个根的因式即可。
至于求除后的多项式，待定系数法手推一下也能出结果。这里直接给出结果：
$$b_i=a_{i+1}+b_{i+1}\cdot x_0$$
$b_i$ 为除后的多项式系数，$x_0$ 是上一个求出的根。
### Notice
- 在本题如果写 $\epsilon$ 精度太高 TLE，精度太低 WA，可以考虑固定迭代次数，比如设置迭代 $t=150$ 次。
- 再次提醒 UVA 提交注意事项：
- 行末不可以有多余空格。
- 结尾必须有且仅有一个空行。
- 题面虽然说精度要求 $10^{-10}$ ，但是必须要输出 $4$ 位小数。
### Code
```cpp
inline double f(cdb& x)
{
double res=0;
for(int i=0;i<=n;i++) res+=a[i]*pow(x,i);
return res;
}
inline double ff(cdb& x)
{
double res=0;
for(int i=1;i<=n;i++) res+=i*a[i]*pow(x,i-1);
return res;
}
inline void div(double* a,cdb& x)
{
double t[MAXN];memset(t,0,sizeof(t));
for(int i=n;i>=0;i--) t[i]=a[i+1]+t[i+1]*x;
for(int i=0;i<=n;i++) a[i]=t[i];
}
inline double solve(double x0)
{
for(int i=1;i<=150;i++) x0-=f(x0)/ff(x0);
return x0;
}
int main()
{
for(int i=1,N=0;cin>>N;i++)
{
n=N;memset(a,0,sizeof(a));
for(int i=N;i>=0;i--) cin>>a[i];
if(N==0) continue;
vector<double> ans;
for(;n>=1;n--)
{
cdb x=solve(-30.0);
ans.emplace_back(x);
div(a,x);
}
sort(ans.begin(),ans.end());
printf("Equation %d: ",i);
for(unsigned i=0;i<N-1;i++) printf("%.4f ",ans[i]);
printf("%.4f\n",ans[N-1]);
}
return 0;
}
```