1

次のように、Cで合成除算アルゴリズムを実装しています。

int deflate( double r, double im, double* poly, int n ) {
    int retval;
    int i;
    if( im == 0 ) {
            if( n < 1 ) {
                    retval = 1;
            } else {
                    double* out = ( double* )malloc( ( n )*sizeof( double ) );
                    out[ n - 1 ] = poly[ n ];
                    for( i = n - 2; i >= 0; i-- ) {
                            out[ i ] = out[ i + 1 ]*r + poly[ i + 1 ];
                    }

                    for( i = 0; i < n; i++ ) {
                            poly[ i ] = out[ i ];
                    }
                    poly[ n ] = 0;
                    free( out );
                    retval = 0;
            }
    } else {
            if( n < 2 ) {
                    retval = 1;
            } else {
                    /*code to handle complex numbers here*/
                    retval = 0;
            }
    }
    return retval;
}

非ゼロの虚数成分に対してこれを実装する効率的な方法を考えようとしています。具体的には、複素係数多項式を使用せずに、両方の複素共役根を 1 回のパスで収縮させたいと考えています。誰でもこれを行う方法を考えることができますか?

4

1 に答える 1

0

私はこれを行う方法を見つけることができました。解決策は、共役対の収縮が 2 つの根を一度に収縮することであり、両方が演算の除数である 2 番目の多項式を形成することを理解するだけです。

double div1 = -2*r;
double div0 = r*r + im*im;

これらの 2 つの値を使用して、多項式と先行係数が 1 である 2 次の間で長い除算を行う場合と同じ方法で合成除算を行います (これは、実質的に実根の場合の合成除算と同じです。除数は 2 次かどうかにかかわらず線形です):

int i;
out[ n - 2 ] = poly[ n ];
out[ n - 3 ] = -out[ n - 2 ]*div1 + poly[ n - 1 ];
for( i = n - 4; i >= 0; i-- ) {
    out[ i ] = -out[ i + 2 ]*div0 + -out[ i + 1 ]*div1 + poly[ i + 2 ];
}
for( i = 0; i < n; i++ ) {
    poly[ i ] = out[ i ];
}
poly[ n - 1 ] = 0.0;
poly[ n ] = 0.0;
free( out );
retval = 0;

これにより、複素係数多項式を形成する必要が完全に回避され、両方の複素根が 1 回のパスで収縮されます。

于 2013-05-08T19:11:49.853 に答える