newton(f, df, x0, tol, max_iter): x = x0 for i = 1..max_iter: fx = f(x) if |fx| < tol: return x x = x - fx / df(x) return xsimpson(f, a, b, n): h = (b - a) / n sum = f(a) + f(b) for i = 1..n-1: if i % 2 == 1: sum += 4 * f(a + i * h) else: sum += 2 * f(a + i * h) return sum * h / 3
구현
// Newton method: sqrt(2) via x^2 - 2 = 0// Simpson: integral of sin(x) from 0 to PI = 2#include <bits/stdc++.h>using namespace std;double f_sqrt(double x) { return x * x - 2; }double df_sqrt(double x) { return 2 * x; }double newton(double (*f)(double), double (*df)(double), double x0, double tol = 1e-12, int max_iter = 100) { double x = x0; for (int i = 0; i < max_iter; i++) { double fx = f(x); if (fabs(fx) < tol) return x; x -= fx / df(x); } return x;}double g(double x) { return sin(x); }double simpson(double a, double b, int n) { if (n & 1) n++; double h = (b - a) / n; double s = g(a) + g(b); for (int i = 1; i < n; i++) s += (i & 1 ? 4 : 2) * g(a + i * h); return s * h / 3;}int main() { cout << fixed << setprecision(12); cout << "sqrt(2) via Newton: " << newton(f_sqrt, df_sqrt, 1.0) << "\n"; cout << "expected: " << sqrt(2) << "\n"; cout << "Simpson integral: " << simpson(0, M_PI, 100) << "\n"; cout << "expected: 2.000000000000\n";}
# Newton method + Simpson ruleimport mathdef newton(f, df, x0, tol=1e-12, max_iter=100): x = x0 for _ in range(max_iter): fx = f(x) if abs(fx) < tol: return x x -= fx / df(x) return xdef f_sqrt(x): return x * x - 2def df_sqrt(x): return 2 * xdef simpson(f, a, b, n): if n & 1: n += 1 h = (b - a) / n s = f(a) + f(b) for i in range(1, n): s += (4 if i & 1 else 2) * f(a + i * h) return s * h / 3x = newton(f_sqrt, df_sqrt, 1.0)print(f"sqrt(2) via Newton: {x:.12f}")print(f"expected: {math.sqrt(2):.12f}")print(f"Simpson integral: {simpson(math.sin, 0, math.pi, 100):.12f}")print(f"expected: 2.000000000000")
// Newton-Raphson + Simpson ruleimport java.util.*;import java.io.*;public class Main { interface Func { double apply(double x); } static double newton(Func f, Func df, double x0) { double x = x0, tol = 1e-12; for (int i = 0; i < 100; i++) { double fx = f.apply(x); if (Math.abs(fx) < tol) return x; x -= fx / df.apply(x); } return x; } static double simpson(Func f, double a, double b, int n) { if ((n & 1) == 1) n++; double h = (b - a) / n; double s = f.apply(a) + f.apply(b); for (int i = 1; i < n; i++) { double x = a + i * h; s += (i % 2 == 1 ? 4 : 2) * f.apply(x); } return s * h / 3; } public static void main(String[] args) { Func f_sqrt = x -> x * x - 2; Func df_sqrt = x -> 2 * x; Func g = Math::sin; System.out.printf("sqrt(2) via Newton: %.12f%n", newton(f_sqrt, df_sqrt, 1.0)); System.out.printf("expected: %.12f%n", Math.sqrt(2)); System.out.printf("Simpson integral: %.12f%n", simpson(g, 0, Math.PI, 100)); System.out.println("expected: 2.000000000000"); }}
결과
sqrt(2) via Newton: 1.414213562373expected: 1.414213562373Simpson integral: 2.000000000000expected: 2.000000000000
복잡도
항목
값
Newton (2차 수렴)
O(log log 1/ε) 반복, 각 O(1) 도함수 평가
Bisection (1차 수렴)
O(log((b-a)/ε)) 반복
Simpson 1/3
O(N) 시간, O(1) 공간, 오차 O(1/N⁴)
Trapezoidal
O(N) 시간, O(1) 공간, 오차 O(1/N²)
변형 / 활용
변형
설명
Secant method
도함수 없이 이전 점 2개로 기울기 근사. 수렴 차수 1.618
Bisection + Newton hybrid
Bisection 으로 안정적 범위 수축 후 Newton 으로 급속 수렴
Modified Newton (다중근)
x -= m * f(x) / f’(x), m = 중복도
Newton for systems
Jacobian 으로 다변수 확장 (다변수 Newton)
Romberg integration
Richardson 외삽으로 trapezoidal 적분 개선
Gaussian quadrature
Legendre 다항식 + 가중치로 최적 정밀도
함정
1. 초기값
Newton 은 초기값이 해에서 멀면 발산. 특히 f’(x) 가 0 근처이면 overshoot. Bisection 으로 먼저 대략 위치 파악.
2. 도함수 비용
도함수 계산이 비싸면 Secant 또는 finite difference 로 대체. 단, 수렴 속도 감소.
3. 다중근
f’(α) = 0 이면 Newton 의 2차 수렴이 1차로 저하. Modified Newton 필요.
4. 특이 적분
적분 구간 내 특이점이 있으면 Simpson rule 이 큰 오차. 구간 분할 후 improper integral 처리.
5. 수렴 판정
|x_{k+1} - x_k| < ε 만 보면 부적절. |f(x_k)| < ε 병행. 발산 대비 max_iter 설정.
💬 댓글