Newton's Method (The Newton-Raphson Method)

Face reality as it is, not as it was or as you wish it to be, Jack Welch.

The Derivative: Unlocking Instantaneous Change

The derivative of a function at a chosen input value, when it exists, is the slope of the tangent line to the graph of the function at that point. It is the instantaneous rate of change —the exact ratio of the instantaneous change in the dependent variable ($y$) to that of the independent variable ($x$).

Definition. A function $f(x)$ is differentiable at a point $a$ of its domain if its domain contains an open interval containing $a$, and the following limit exists: $\boxed{f'(a) = L = \lim_{h \to 0} \frac{f(a+h) - f(a)}{h}}$

Formal Definition: More rigorously, for every positive real number $\epsilon > 0$, there exists a positive real number $\delta > 0$, such that for every $h$ satisfying $0 < |h| < \delta$, the difference between the secant slopes at points sufficiently near a are guaranteed to be ε-close to the derivative: $\left| L - \frac{f(a+h) - f(a)}{h} \right| < \epsilon$

A critical point is a point in the domain of the function where the function is either not differentiable or the derivative is equal to zero ($f'(x) = 0$). The value of the function at a critical point (the $y$-value) is called a critical value.

The squeeze or sandwich theorem. If a function f lies between two functions g and h, and the limits of each of them at a particular point are both equal to L, then the limit of f at that particular point is also equal to L.

The Extreme Value Theorem. If f is a continuous function on an closed interval $[a, b]$, then f has both maximum and minimum values on $[a, b]$. It states that if a function is continuous on a closed bounded interval, then it is guaranteed to hit a highest point and a lowest point somewhere within that interval (either at a peak/valley or at the endpoints a or b).

Fermat’s Theorem. If a function $f(x)$ is defined on the interval $(a, b)$, has a local extremum (a relative maximum or minimum) at $x = c$, and $f'(c)$ exists, then $x = c$ is a critical point of $f(x)$ and $f'(c) = 0$.

Newton’s Method (The Newton-Raphson Method)

Newton’s method is a powerful root-finding algorithm. It is an iterative numerical technique that produces successively better approximations to the roots (zeroes) of a real-valued function $f(x)$.

It is widely used for solving nonlinear equations and finding roots of functions.

How the Formula is Derived

The core idea is to approximate the function’s curve with a straight line (the tangent line) and find where that line crosses the x-axis.

1. Start with an initial guess, $x_0$. Hopefully, it is a reasonable good guess, relatively close to the true root.

2. Then, we approximate the function by its tangent line, and calculate the x-intercept of this tangent line. This x-intercept is our new guess, say $x_1$, and it will typically be a better approximation to the original function's root than the first guess.
   This method is illustrated at the Figure 2.d.
   The point-slope formula for a line is $y - y_0 = m(x - x_0)$. Here, the slope $m$ is the derivative $f'(x_0)$. So, the tangent line is: $\boxed{y - f(x_0) = f'(x_0)(x - x_0)}$

3. Find the x-intercept of this tangent line. To find where the tangent line crosses the x-axis, set $y = 0$ and solve for $x$. We will call this new point $x_1$:
   $0 - f(x_0) = f'(x_0)(x_1 - x_0)$
   $-\frac{f(x_0)}{f'(x_0)} = x_1 - x_0$
   $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$

4. This $x_1$ is our new, refined guess. We repeat the process using $x_1$ to find $x_2$, and so on.
   $0-y_n=m(x_{n+1}-x_n) ⇒ x_{n+1} = x_n -\frac{y_n}{m} = x_n -\frac{f(x_n)}{f'(x_n)}$.
   This gives us the general recurrence formula: $\boxed{x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}}$

This method is particularly efficient and quite effective for approximating solutions to equations, especially when the original guess is reasonably close to the actual solution and the function is well-behaved. However, it may not converge or may converge to a local minimum or maximum if the initial guess is far from the actual root.

Additionally, Newton’s method requires the derivative of the function, which may not always be readily available or computationally expensive to compute. If the derivative $f′(x_n)$ is ever zero (a horizontal tangent), the formula fails because you cannot divide by zero.

Solved examples

• Use Newton’s method to approximate $\sqrt{2}$ starting with an initial guess of $x_0 = 1$.

We want to find the value of $x$ where $x = \sqrt{2}$. Squaring both sides gives $x^2 = 2$, which means we are looking for the root of the function: $f(x) = x^2 - 2$

The derivative is: $f'(x) = 2x$. Now we apply the iterative formula $\boxed{x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}}$:

1. Iteration 1: $x_1 = 1 - \frac{f(1)}{f'(1)} = 1 - \frac{1^2 - 2}{2(1)} = 1 - \frac{-1}{2} = 1 + 0.5 = 1.5$
2. Iteration 2: $x_2 = 1.5 - \frac{f(1.5)}{f'(1.5)} = 1.5 - \frac{1.5^2 - 2}{2(1.5)} = 1.5 - \frac{2.25 - 2}{3} = 1.5 - \frac{0.25}{3} \approx 1.41666$
3. Iteration 3: $x_3 = 1.41666 - \frac{f(1.41666)}{f'(1.41666)} = 1.41666 - \frac{1.41666^2 - 2}{2(1.41666)} \approx 1.41421$

After just three iterations, we have reached an approximation of $1.41421$, which is highly accurate to five decimal places.

• Approximating the root of $x^3 + x - 1 = 0$. Goal: Find a root near $x_0 = 1$.

Setup: Let $f(x) = x^3 + x - 1$. The derivative is $f'(x) = 3x^2 + 1$.

Using Newton’s method formula, $\boxed{x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}}$:

1. Iteration 1: $x_1 = 1 - \frac{1^3 + 1 - 1}{3(1)^2 + 1} = 1 - \frac{1}{4} = 0.75$
2. Iteration 2: $x_2 = 0.75 - \frac{0.75^3 + 0.75 - 1}{3(0.75)^2 + 1} = 0.75 - \frac{0.171875}{2.6875} \approx 0.6860$
3. Iteration 3: $x_3 = 0.6860 - \frac{0.6860^3 + 0.6860 - 1}{3(0.6860)^2 + 1} \approx 0.6823$

Check: Plugging this back in, $0.6823^3 + 0.6823 - 1 \approx 0.00002$. This is an extremely good approximation after just three steps.

• Finding a root for $x^5 - 5x + 3 = 0$. Goal: Locate and approximate a root for $f(x) = x^5 - 5x + 3$.

1. Existence of a Root. First, notice that $f(x)$ is continuous.
   Besides, $f(1) = 1^5 - 5(1) + 3 = -1$ (Negative) and $f(2) = 2^5 - 5(2) + 3 = 25$ (Positive).
   By the Intermediate Value Theorem, since the function changes sign, there must exist at least one root $a \in (1, 2)$.

2. Setup: Let’s use $x_0 = 2$ as our initial guess. The derivative is $f'(x) = 5x^4 - 5$.

3. Iteration 1: $x_1 = 2 - \frac{2^5 - 5(2) + 3}{5(2)^4 - 5} = 2 - \frac{25}{75} = \frac{5}{3} \approx 1.6667$

4. Iteration 2: $x_2 = 1.6667 - \frac{1.6667^5 - 5(1.6667) + 3}{5(1.6667)^4 - 5} \approx 1.4425$

5. Iteration 3: $x_3 = 1.4425 - \frac{1.4425^5 - 5(1.4425) + 3}{5(1.4425)^4 - 5} \approx 1.3204$

6. Iteration 4: $x_4 = 1.3204 - \frac{1.3204^5 - 5(1.3204) + 3}{5(1.3204)^4 - 5} \approx 1.2800$

7. Check: $f(1.2800) \approx 0.036$. While not perfectly zero, it is close enough for many purposes. Running one more iteration yields $x_5 \approx 1.2757$, where $f(1.2757) \approx 0.00015$, bringing us safely into the target precision for most use cases.

• Intersection of $y = x^2 - 4$ and $y = 2x - 3$.

1. Goal: Apply two iterations of Newton’s method to approximate the $x$-value where these two curves intersect, starting at $x_0 = 0$.
2. Setup: To find the intersection, set the equations equal to each other: $x^2 - 4 = 2x - 3$.
   Moving everything to one side gives our target function: $f(x) = x^2 - 2x - 1 = 0$.
   The derivative is $f'(x) = 2x - 2$.
3. Iteration 1: $x_1 = 0 - \frac{0^2 - 2(0) - 1}{2(0) - 2} = 0 - \frac{-1}{-2} = -0.5$
4. Iteration 2: $x_2 = -0.5 - \frac{(-0.5)^2 - 2(-0.5) - 1}{2(-0.5) - 2} = -0.5 - \frac{0.25}{-3} = -0.5 + \frac{1}{12} = -\frac{5}{12} \approx -0.4167$
5. Check: Let’s plug $x = -\frac{5}{12}$ back into both original equations to see if they yield the same $y$-value:
   $y_1 = \left(-\frac{5}{12}\right)^2 - 4 \approx -3.826$
   $y_2 = 2\left(-\frac{5}{12}\right) - 3 \approx -3.833$
   The outputs are nearly identical, proving that $x = -5/12$ is a fantastic approximation of the intersection point after only two iterations.

• Approximating $\sqrt[7]{1000}$

1. Goal: Approximate the 7th root of 1000.
2. Setup: This is mathematically identical to finding the root of $f(x) = x^7 - 1000 = 0$.
   The derivative is $f'(x) = 7x^6$.
   Since $3^7 = 2187$ (a bit high) and $2^7 = 128$ (too low), $x_0 = 3$ is a perfectly reasonable starting guess.
3. Iteration 1: $x_1 = 3 - \frac{3^7 - 1000}{7(3^6)} = 3 - \frac{1187}{5103} \approx 2.76739173$
4. Iteration 2: $x_2 = 2.76739173 - \frac{(2.76739173)^7 - 1000}{7(2.76739173)^6} \approx 2.69008741$
5. Iteration 3: $x_3 = 2.69008741 - \frac{(2.69008741)^7 - 1000}{7(2.69008741)^6} \approx 2.68275645$
6. Check: Standard search engines and calculators evaluate $\sqrt[7]{1000}$ as 2.682695…. This hand-calculated approximation matches perfectly up to the first three decimal places.

Bibliography

1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Calculus. Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn, and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. YouTube’s Andrew Misseldine: Calculus. College Algebra and Abstract Algebra.
8. MIT OpenCourseWare 18.01 Single Variable Calculus, Fall 2007 and 18.02 Multivariable Calculus, Fall 2007.
9. Calculus Early Transcendentals: Differential & Multi-Variable Calculus for Social Sciences.