0

http://introcs.cs.princeton.edu/java/13flow/Sqrt.java.html :

public class Sqrt { 
    public static void main(String[] args) { 

        // read in the command-line argument
        double c = Double.parseDouble(args[0]);
        double epsilon = 1e-15;    // relative error tolerance
        double t = c;              // estimate of the square root of c

        // repeatedly apply Newton update step until desired precision is achieved
        while (Math.abs(t - c/t) > epsilon*t) {
            t = (c/t + t) / 2.0;
        }

        // print out the estimate of the square root of c
        System.out.println(t);
    }

}

事は..私はプログラム自体がどのように機能するかを完全によく理解しています。私が抱えている問題は、式 f(x) = x^2 - c と、それが上記のコードにどのように関係しているかです。同様に、なぜそれを x で割って x(x - c/x) になるのでしょうか? これらの例のいくつかに関しては、数学的な説明が欠けているようです。言い換えれば、コーディングではなく、単純な数学的な観点からの説明を探しています。

4

4 に答える 4

4

あなたは与えられc、あなたは解決したい

t = sqrt(c)

または同等に、

c = t^2

または、もう一度、

c - t^2 = 0.

上記の式を呼び出します(これは定数であるため、f(t) = 0言及しません)。cニュートン法は、 の試行値を反復しtます。これを とラベル付けしt_i, t_{i+1}, ...ます。

1次へのテイラー展開は次のとおりです。

f(t_i + dt_i) = f(t_i) + dt_i * f'(t_i) + ...

したがって、 がまったくない場合は、そのようなものf(t_i) = 0を追加しますdt_i

f(t_i + dt_i) nearly = 0 = f(t_i) + dt_i * f'(t_i) + ...

つまりdt_i = -f(t_i) / f'(t_i)、f(t_i + -f(t_i) / f'(t_i))は よりゼロに近いですf(t_i)。

の導関数を実行すると、コード内の方程式が上記の推定値を使用した単なる反復式でf(t) = c - t^2あることがわかります。t_{i+1} = (c / t_i + t_i) / 2t_{i+1} = t_i + dt_idt_i

これは反復法であるため、正確な解は得られません。停止するタイミングを決定する必要があります (十分な精度)。そうしないと、アルゴリズムが永遠に続くことになります。f(t_i) < thresholdそのため、 true の代わりにチェックしますf(t_i) = 0。彼らの場合、彼らはthreshold = epsilon * t^2;を選択しました。固定定数をしきい値として使用すると、数値精度の問題が発生する可能性があるため、乗算t^2が使用されたと思います（つまり、数兆で遊んでいる場合10^{-10}、浮動小数点の有限精度のために固定精度を得ることができませんでした）表現。）

于 2012-01-23T14:00:00.467 に答える
1

コードに基づいて、Javadocコメントで次のことがすでに説明されています。

 *  Computes the square root of a nonnegative number c using
 *  Newton's method:
 *     - initialize t = c
 *     - replace t with the average of c/t and t
 *     - repeat until desired accuracy reached
于 2012-01-23T12:52:32.060 に答える
1

わかりました、私はそれにbashを与えます（インラインコメントを参照してください）：

public class Sqrt { 
    public static void main(String[] args) { 

        // read in the command-line argument (i.e. this is the value that we want
        // square root from.)
        double c = Double.parseDouble(args[0]); 

        // Since the the square root of non-squares are irrational, we need some
        // error tolerance.  In other words, if the answer is less than epsilon wrong
        // we'll take it.  
        double epsilon = 1e-15;    // relative error tolerance

        // t is our first guess (c / 2.0 works well too - in fact it tends to be
        // better.)
        double t = c;              // estimate of the square root of c

        // repeatedly apply Newton update step until desired precision is achieved
        // The condition here is rather elegant and optimized... to see why it works,
        // simply break it up.  The absolute is there to cater for negative values, but
        // for c >= 0:
        //   | c - c/t | > epsilon * t
        //   t * ( t - c / t ) > epsilon
        //   tt - c = > epsilon)
        while (Math.abs(t - c/t) > epsilon*t) {
            // Improve the guess by applying Newton's genius :-)
            // Take the original number, divide by the guess add t and take the
            // average.
            t = ( c / t + t) / 2.0;
        }

    // print out the estimate of the square root of c
    System.out.println(t);
}

}
于 2012-01-23T13:02:14.397 に答える