Newton Raphson And Secant Method

1. Core Concept Overview & Intuition

The study of numerical analysis is fundamentally concerned with obtaining approximate solutions to mathematical problems that may be difficult or impossible to solve exactly. Every approximation, however, carries an inherent error. The first step in mastering numerical methods is to understand, quantify, and control these errors. This section introduces the foundational concepts of error analysis, which are prerequisites for understanding the iterative methods that follow.

1.1 The Nature of Error

In numerical computation, we often deal with two types of numbers: the exact number, denoted by $x$, and its approximate representation, denoted by $x_r$. The discrepancy between these two is the error. This error can arise from several sources, including the finite memory of a computer, which cannot represent all real numbers exactly, and the truncation of infinite mathematical processes (like series expansions) to finite ones.

The primary goal is not to eliminate error entirely—which is often impossible—but to understand its magnitude and ensure it remains within acceptable bounds. This requires a systematic way to measure error, leading to the concepts of absolute, relative, and percentage errors.

1.2 The Iterative Solution of Nonlinear Equations

Many problems in science and engineering culminate in an equation of the form $f(x) = 0$, where $f$ is a nonlinear function. Finding the roots of such equations analytically is frequently not possible. Iterative techniques provide a powerful alternative. These methods start with an initial guess for the root and generate a sequence of successively better approximations.

The core idea is to refine an initial estimate $x_0$ to get $x_1$, then refine $x_1$ to get $x_2$, and so on, such that the sequence ${x_n}$ converges to the true root $\alpha$. The efficiency and reliability of an iterative method are judged by:
- Convergence: Does the sequence of approximations approach the true root?
- Rate of Convergence: How quickly does the sequence approach the root?
- Cost per Iteration: How much computation is required for each step?

This unit focuses on two of the most important iterative methods for solving nonlinear equations: the Newton-Raphson method and the Secant method. Both are powerful tools that build upon the foundational concepts of error analysis and function approximation.

2. Mathematical Formalization & Core Definitions

This section provides the formal mathematical definitions and procedures for error analysis and the iterative methods.

2.1 Definitions of Error

Let $x$ be an exact number and $x_r$ be an approximate value.

> Definition 2.1 (Absolute Error). The absolute error, denoted $e_{abs}$, is the absolute difference between the exact number $x$ and the approximate number $x_r$:

$$
e_{abs} = \lvert x - x_r \rvert
$$

> The absolute error gives the magnitude of the discrepancy but does not provide context regarding the size of the exact value. For instance, an absolute error of $1$ is significant when measuring a length of $10$ meters but negligible when measuring an astronomical distance.

> Definition 2.2 (Upper Bound on Absolute Error). Let $\Delta x$ be an upper bound such that

$$
e_{abs} = \lvert x - x_r \rvert \le \Delta x
$$

> This bound $\Delta x$ provides a guarantee on the maximum possible error.

> Definition 2.3 (Relative Error). The relative error, denoted $e_r$, is the ratio of the absolute error to the magnitude of the exact number:

$$
e_r = \frac{\lvert x - x_r \rvert}{\lvert x \rvert}
$$

> The relative error provides a measure of error that is scaled by the size of the quantity being measured, making it a more meaningful indicator of accuracy.

> Definition 2.4 (Percentage Error). The percentage error is the relative error expressed as a percentage:

$$
\text{Percentage Error} = e_r \times 100\%
$$

2.2 Computation of Errors from Significant Figures

A common scenario is that a number is given as correct to a certain number of decimal places or significant figures. The maximum absolute error can be determined from this information.

> Theorem 2.1 (Maximum Absolute Error from Decimal Places). If a number is correct to $n$ decimal places, then the maximum absolute error is bounded by:

$$
e_{abs} \le 0.5 \times 10^{-n}
$$

Example 2.1: If $x = 2.4$ is correct to one decimal place ($n=1$), then the exact value $x$ lies in the interval $(2.35, 2.45)$. The maximum absolute error is:

$$
e_{abs} \le 0.5 \times 10^{-1} = 0.05
$$

This can be verified by taking the worst-case scenario, where the exact value is at the boundary of the interval, for example, $x = 2.35$. Then $e_{abs} = \lvert 2.35 - 2.4 \rvert = 0.05$.

Example 2.2: If $x_r = -10.788$ is correct to three decimal places ($n=3$), the exact value lies in the interval $[-10.7885, -10.7875]$. The maximum absolute error is:

$$
e_{abs} \le 0.5 \times 10^{-3} = 0.0005
$$

2.3 Propagation of Errors in Arithmetic Operations

When arithmetic operations are performed on approximate numbers, the initial errors propagate and affect the final result. Let $x$ and $y$ be exact numbers, and let $x^$ and $y^$ be their approximations with initial errors $\varepsilon$ and $\eta$ respectively, such that $x = x^ + \varepsilon$ and $y = y^ + \eta$.

> Definition 2.5 (Propagated Error). The error in the result of an arithmetic operation arising due to initial errors in the numbers used in that operation is called the propagated error.

> Definition 2.6 (Accumulated Error). The total cumulative error at any step in a multi-step procedure is called the accumulated error.

The total error in an operation $x \circ y$ (where $\circ$ is an arithmetic operator) can be decomposed as:

$$
\text{Total Error} = (x \circ y - x^ \circ y^) + (x^ \circ y^ - x^ \circ y^)
$$

This expression separates the error into two components:
- The propagated error, which is the difference between the exact operation and the operation on the approximations: $(x \circ y - x^ \circ y^)$.
- The generated error, which is the new error introduced by performing the operation itself on the approximate values: $(x^ \circ y^ - x^ \circ y^)$.

2.4 The Newton-Raphson Method

The Newton-Raphson method is a powerful iterative technique for finding the roots of a nonlinear equation $f(x) = 0$. It uses the tangent line to the function at the current approximation to find the next, better approximation.

> Definition 2.7 (Newton-Raphson Iteration). Given a function $f(x)$ that is differentiable, and an initial guess $x_0$ that is sufficiently close to the true root, the Newton-Raphson method generates a sequence of approximations via the recurrence relation:

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

> where $f'(x_n)$ is the derivative of $f$ evaluated at $x_n$.

Geometric Interpretation: The method can be understood geometrically. At the point $(x_n, f(x_n))$, we construct the tangent line to the curve $y = f(x)$. The equation of this tangent line is $y - f(x_n) = f'(x_n)(x - x_n)$. The next approximation $x_{n+1}$ is the $x$-intercept of this tangent line, found by setting $y=0$:

$$
0 - f(x_n) = f'(x_n)(x_{n+1} - x_n)
$$

Solving for $x_{n+1}$ yields the Newton-Raphson formula. This process is repeated, with each new tangent line providing a better estimate of the root.

2.5 The Secant Method

The Secant method is a variation of the Newton-Raphson method that avoids the need to compute the derivative $f'(x)$. It approximates the derivative using a finite difference.

> Definition 2.8 (Secant Method Iteration). Given a function $f(x)$ and two initial approximations $x_0$ and $x_1$, the Secant method generates a sequence of approximations via the recurrence relation:

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

> for $n = 1, 2, 3, \dots$

Geometric Interpretation: Instead of using the tangent line at $x_n$, the Secant method uses the secant line that passes through the two most recent points, $(x_{n-1}, f(x_{n-1}))$ and $(x_n, f(x_n))$. The next approximation $x_{n+1}$ is the $x$-intercept of this secant line. This method requires two initial guesses but does not require the evaluation of the derivative, which can be advantageous when $f'(x)$ is difficult or expensive to compute.