The Newton-Raphson method is a numerical analysis technique used to solve equations of the form \(f(x) = 0\) . This method starts with an initial guess and iteratively uses the derivative of the function to approximate the root.
Derivation
Basic Concept
Suppose we have a function \(f(x)=0\), and we want to find \(x\) such that \(f(x) = 0\). We start with an initial guess \(x_0\) and iteratively refine this guess to approximate the actual root of the equation.
Taylor Expansion
For a function \(f(x)\) near the point \(x = x_n\), we can perform a first-order Taylor expansion:
$$f(x) \approx f(x_n) + f{’}(x_n)(x - x_n)$$
where \(f’(x_n)\) is the first derivative of \(f(x)\) at \(x = x_n\).
Root Approximation
We aim to find \(x\) such that \(f(x) = 0\). Based on the Taylor expansion, we can write:
$$0 \approx f(x_n) + f{’}(x_n)(x_{n+1} - x_n)$$
Solving this equation gives us the next approximation \(x_{n+1}\):
$$x_{n+1} = x_n - \frac{f(x_n)}{f{’}(x_n)}$$
This is the iterative formula of the Newton-Raphson method.
Using the Newton-Raphson Method to Find Square Roots
Iterative Formula
In the square root problem, we want to find \(x\) such that \(x^2 = k\), i.e., \(f(x) = x^2 - k\).
Therefore, our equation becomes:
\(f(x) = x^2 - k\)
with the derivative: \(f’(x) = 2x\)
Substituting these into the Newton-Raphson formula: $$x_{n+1} = x_n - \frac{f(x_n)}{f{’}(x_n)} = x_n - \frac{x_n^2 - k}{2x_n}$$
Simplifying: $$x_{n+1} = \frac{1}{2} \left( x_n + \frac{k}{x_n} \right)$$
This can be intuitively understood as: the new guess \(x_{n+1}\) is the average of the previous guess \(x_n\) and \(\frac{k}{x_n}\) .
Code Implementation
Implementing in Racket
1#lang racket2
3; average: calculate the average of two numbers4(define (average x y)5 (/ (+ x y) 2))6
7; improve: improve the guess by averaging it with x/guess8(define (improve guess x)9 (average guess (/ x guess)))10
11; square: calculate the square of x12(define (square x) (* x x))13
14; good-enough?: determine if the current guess is close enough to the square root of x15(define (good-enough? guess x)16 collapsed lines
16 (< (abs (- (square guess) x)) 0.001))17
18; sqrt-iter: recursively improve the guess until it is close enough to the square root of x19(define (sqrt-iter guess x)20 (if (good-enough? guess x)21 guess22 (sqrt-iter (improve guess x) x)))23
24; sqrt: define the square root function, start the iteration process with an initial guess of 1.025(define (sqrt x)26 (sqrt-iter 1.0 x))27
28; Test: find the square root of 2429(define k 24.0)30(define result (sqrt k))31(displayln (string-append "Square root of " (number->string k) " is about " (number->string result)))Implementing in JavaScript
1// average: calculates the average of two numbers2function average(x, y) {3 return (x + y) / 2;4}5
6// improve: improves the guess by calculating the average of the current guess and x/guess7function improve(guess, x) {8 return average(guess, x / guess);9}10
11// is_good_enough: determines if the square of the current guess is close enough to x, within a predetermined tolerance (here 0.001)12function is_good_enough(guess, x) {13 return Math.abs(square(guess) - x) < 0.001;14}15
19 collapsed lines
16// square: calculates the square of x17function square(x) {18 return x * x;19}20
21// sqrt_iter: recursively improves the guess until it is close enough to the square root of x22function sqrt_iter(guess, x) {23 return is_good_enough(guess, x) ? guess : sqrt_iter(improve(guess, x), x);24}25
26// sqrt: defines the square root function, starts the iteration process with an initial guess of 1.027function sqrt(x) {28 return sqrt_iter(1, x);29}30
31// Test: find the square root of 2432let k = 24.0;33let result = sqrt(k);34console.log(`Square root of ${k} is about ${result}`);