UVa10428 The Roots 题解

· · 题解

题目大意

给出一个 n 次多项式，求它的所有 n 个根。

题目思路

这是牛顿迭代的一个标准的板子。

我们观测一下某个多项式 x^3-2x+1 的函数图像：

它现在的切线是这样的：

因而，我们可以把 A 点近似移动到切线与 x 轴相交的地方上，而后接着切线（在图中表明）：

可以看到它的切线再不断趋近于根，因此我们可以先把它的数学式写出来：设有一个函数 f(x)，而后，我们就可以先设一个起点 z，而后，我们可以先拿到点 (z,f(z)) 在 f(x) 上的切线的斜率 f'(z)，而后我们当然需要把方程列出（其中 r 为方程根）：

f'(z)=\frac{f(z)-f(r)}{z-r}

而后，我们可以先简单的化简一下：

(z-r)f'(z)=f(z) (z-r)=\frac{f(z)}{f'(z)} r=z-\frac{f(z)}{f'(z)}

我们当然不知道 r 的具体数值，但是我们当然可以用 z-\frac{f(z)}{f'(z)} 来逼近，而后接着逼近！

最后，我们找到了一个根 z，那么我们应该怎么找到下一个根呢？假若我们找到了某个根 r，而后假若我们的 x 取到 r，那么整个方程变成了 0，因此方程必然可以从 f(x) 拆成 (x-r)g(x)，随后对 g(x) 使用牛顿法。

这里多项式除法的具体细节略，但可以在代码中找到。代码如下。

#include <bits/stdc++.h>
using namespace std;
double EPS=1e-6;
int n;
double f[10],f_[10],g[10],g_[10],z[10];
double fc(double x){
    double ans=0;
    for(int i=n;i>=0;--i) ans=ans*x+f[i];
    return ans;
}
double f_c(double x){
    double ans=0;
    for(int i=n-1;i>=0;--i) ans=ans*x+f_[i];
    return ans;
}
double newton(double z){
    while(fabs(fc(z))>=EPS) z-=fc(z)/f_c(z);
    for(int i=n-1;i>=0;--i) g[i]=f[i+1]*z,f[i]+=f[i+1]*z;
    for(int i=0;i<=n-1;++i) f[i]=g[i];
    --n;
    for(int i=n-1;i>=0;--i) f_[i]=f[i+1]*double(i+1);
    return z;
}
int main(){
    int _=0;
    while(cin>>n&&n!=0){
        int m=n;
        for(int i=n;i>=0;--i) cin>>f[i];
        for(int i=n-1;i>=0;--i) f_[i]=f[i+1]*double(i+1);
        cout<<"Equation "<<(++_)<<": ";
        for(int i=1;i<=m;i++) z[i]=newton(0);
        sort(z+1,z+m+1);
        for(int i=1;i<=m;i++) cout<<fixed<<setprecision(4)<<z[i]<<(i==m?'\n':' ');
        cout<<flush;
    }
    return 0;
}

EOF