Newton's Method
Description
Newton's Method (also known as Newton-Raphson method) is an iterative method for finding successively better approximations to the roots of a real-valued function. It uses the first derivative of a function to find better approximations to the roots.
How It Works
- Start with an initial guess x₀
- Calculate the function value f(x₀) and its derivative f'(x₀)
- Apply the formula: xₙ₊₁ = xₙ - f(xₙ)/f'(xₙ)
- Repeat until convergence or maximum iterations reached
The method is based on the idea that a continuous and differentiable function can be approximated by its tangent line, and where that tangent line crosses the x-axis might be a better approximation to the root than the original guess.
Visualization
Enter a function and initial guess to begin
Complexity Analysis
Time Complexity
-
Per Iteration: O(1)
- Function evaluation: O(1)
- Derivative evaluation: O(1)
-
Overall: O(log n)
- n is the desired precision (number of decimal places)
- Quadratic convergence when close to root
Space Complexity
-
Variables: O(1)
- Only stores current approximation
- Function and derivative evaluations
Advantages and Disadvantages
Advantages
- Quadratic convergence near roots
- Very efficient for well-behaved functions
- Simple implementation
- Works well with continuous functions
Disadvantages
- Requires derivative calculation
- May diverge with poor initial guess
- Can fail at stationary points
- Not guaranteed to find all roots
Implementation
def newton_method(f, df, x0, epsilon=1e-6, max_iter=100):
"""
Find root of f(x) = 0 using Newton's method.
Parameters:
f: function - The function to find roots for
df: function - The derivative of f
x0: float - Initial guess
epsilon: float - Error tolerance
max_iter: int - Maximum number of iterations
Returns:
float: Approximate root
int: Number of iterations
bool: Whether the method converged
"""
x = x0
for i in range(max_iter):
fx = f(x)
dfx = df(x)
# Check if derivative is too close to zero
if abs(dfx) < epsilon:
return x, i, False
# Newton's method formula
x_new = x - fx / dfx
# Check for convergence
if abs(x_new - x) < epsilon:
return x_new, i + 1, True
x = x_new
return x, max_iter, False
# Example usage
if __name__ == "__main__":
# Example 1: Find square root of 16
def f1(x): return x**2 - 16
def df1(x): return 2*x
root, iterations, converged = newton_method(f1, df1, x0=1.0)
print(f"√16 ≈ {root:.6f} (found in {iterations} iterations)")
# Example 2: Find cube root of 27
def f2(x): return x**3 - 27
def df2(x): return 3*x**2
root, iterations, converged = newton_method(f2, df2, x0=2.0)
print(f"∛27 ≈ {root:.6f} (found in {iterations} iterations)")
#include <iostream>
#include <cmath>
#include <functional>
#include <tuple>
class NewtonMethod {
private:
double epsilon;
int max_iterations;
public:
NewtonMethod(double eps = 1e-6, int max_iter = 100)
: epsilon(eps), max_iterations(max_iter) {}
std::tuple<double, int, bool> solve(
const std::function<double(double)>& f,
const std::function<double(double)>& df,
double x0
) {
double x = x0;
for (int i = 0; i < max_iterations; ++i) {
double fx = f(x);
double dfx = df(x);
// Check if derivative is too close to zero
if (std::abs(dfx) < epsilon) {
return std::make_tuple(x, i, false);
}
// Newton's method formula
double x_new = x - fx / dfx;
// Check for convergence
if (std::abs(x_new - x) < epsilon) {
return std::make_tuple(x_new, i + 1, true);
}
x = x_new;
}
return std::make_tuple(x, max_iterations, false);
}
};
int main() {
NewtonMethod newton;
// Example 1: Find square root of 16
auto f1 = [](double x) { return x*x - 16; };
auto df1 = [](double x) { return 2*x; };
auto [root1, iter1, conv1] = newton.solve(f1, df1, 1.0);
std::cout << "√16 ≈ " << root1 << " (found in " << iter1 << " iterations)\n";
// Example 2: Find cube root of 27
auto f2 = [](double x) { return x*x*x - 27; };
auto df2 = [](double x) { return 3*x*x; };
auto [root2, iter2, conv2] = newton.solve(f2, df2, 2.0);
std::cout << "∛27 ≈ " << root2 << " (found in " << iter2 << " iterations)\n";
return 0;
}
public class NewtonMethod
{
private readonly double epsilon;
private readonly int maxIterations;
public NewtonMethod(double epsilon = 1e-6, int maxIterations = 100)
{
this.epsilon = epsilon;
this.maxIterations = maxIterations;
}
public (double root, int iterations, bool converged) Solve(
Func<double, double> f,
Func<double, double> df,
double x0)
{
double x = x0;
for (int i = 0; i < maxIterations; i++)
{
double fx = f(x);
double dfx = df(x);
// Check if derivative is too close to zero
if (Math.Abs(dfx) < epsilon)
{
return (x, i, false);
}
// Newton's method formula
double xNew = x - fx / dfx;
// Check for convergence
if (Math.Abs(xNew - x) < epsilon)
{
return (xNew, i + 1, true);
}
x = xNew;
}
return (x, maxIterations, false);
}
public static void Main()
{
var newton = new NewtonMethod();
// Example 1: Find square root of 16
double F1(double x) => x * x - 16;
double DF1(double x) => 2 * x;
var (root1, iter1, conv1) = newton.Solve(F1, DF1, 1.0);
Console.WriteLine($"√16 ≈ {root1:F6} (found in {iter1} iterations)");
// Example 2: Find cube root of 27
double F2(double x) => x * x * x - 27;
double DF2(double x) => 3 * x * x;
var (root2, iter2, conv2) = newton.Solve(F2, DF2, 2.0);
Console.WriteLine($"∛27 ≈ {root2:F6} (found in {iter2} iterations)");
}
}