ニュートン法

コード例

def newton_sqrt(s, eps=1e-9):
    if s < 0:
        raise ValueError("負の数の平方根は計算できません")
    if s == 0:
        return 0

    def f(x):
        return x ** 2 - s # x^2 == sの変形

    def f_prime(x):
        return 2 * x # f'(x) = 2x

    x = s / 2.0

    while abs(f(x)) > eps:
        x = x - f(x) / f_prime(x)

    return x

print(newton_sqrt(2))

ニュートン法の基本的な考え方

ニュートン法は「接線」を利用して、より速く解に近づいていく方法。微分（関数のその点での傾き）の考え方を使う。

アルゴリズムは以下のステップを繰り返す。

1. まず、解に近そうな適当な点 x₀ からスタートする。
2. グラフ上の点 (x₀, f(x₀)) で接線（グラフにちょうど触れる直線）を引く。
3. その接線が x軸と交わる点を見つける。この点が、次のより良い近似解 x₁ となる。
4. 今度は点 x₁ から同じように接線を引き、次の近似解 x₂ を見つける。
5. これを繰り返すと、点は驚くほどの速さで真の解に収束していく。

更新の公式（漸化式）

$$x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}$$

• $x_{n}$ : 現在の近似解
• $x_{n+1}$ : 次の、より改善された近似解
• $f(x_{n})$ : 現在の点での関数の値
• $f'(x_{n})$ : 現在の点での微分係数（接線の傾き）

「傾き = 高さ ÷ 水平距離」を変形すると「水平距離 = 高さ ÷ 傾き」になり、これが漸化式の計算になる。