Unit III: Numerical Methods for Root Finding

Bisection Method

The bisection method is a bracketing method used to find the roots of a continuous function. It is based on the Intermediate Value Theorem.

Concept and Step-by-Step Explanation

If a function f(x) is real and continuous on the interval [a, b] and f(a) and f(b) have opposite signs (i.e., f(a) × f(b) < 0), then there exists at least one root between a and b.

1. Choose initial bounds a and b such that f(a) × f(b) < 0.
2. Calculate the midpoint x_r = (a + b) / 2.
3. Evaluate the function at the midpoint, f(x_r).
4. If f(x_r) = 0, then x_r is the exact root. Stop.
5. If f(a) × f(x_r) < 0, the root lies in the left subinterval. Set b = x_r and repeat.
6. If f(b) × f(x_r) < 0, the root lies in the right subinterval. Set a = x_r and repeat.

Formula: x_r = (a + b) / 2

Practical Example

Find a root of f(x) = x³ - x - 2 = 0. Let a = 1 and b = 2. Here, f(1) = 1 - 1 - 2 = -2 and f(2) = 8 - 2 - 2 = 4. Since f(1) × f(2) < 0, a root exists between 1 and 2.

Real-World Applications

Used in engineering design and physics simulations where a stable, guaranteed convergence is required within a known physical bracket.

Exam-Oriented Notes

Always verify the sign change condition before starting iterations. The error is halved at every step.

Common Mistakes

Selecting initial intervals where f(a) and f(b) have the same sign, which violates the Intermediate Value Theorem.

False Position Method

Also known as the Regula Falsi method, the false position method is a bracketing technique similar to the bisection method, but it uses linear interpolation instead of the midpoint.

Concept and Step-by-Step Explanation

Instead of dividing the interval in half, it draws a secant line between the endpoints (a, f(a)) and (b, f(b)) and finds the x-intercept of this line as the new approximation.

1. Choose initial bounds a and b such that f(a) × f(b) < 0.
2. Calculate the new approximation using the secant formula.
3. Evaluate f(x_r).
4. Update the interval based on the sign of f(x_r) similar to the bisection method.

Formula: x_r = [a × f(b) - b × f(a)] / [f(b) - f(a)]

Practical Example

Given f(x) = x³ - 2x - 5, use the endpoints a = 2 and b = 3 to find the first approximation using the Regula Falsi formula.

Real-World Applications

Used in financial calculations and root-finding algorithms where functions are monotonic and faster bracketing is preferred over bisection.

Exam-Oriented Notes

One of the interval endpoints may remain fixed for multiple iterations if the curve is heavily skewed, leading to slower convergence on one side.

Common Mistakes

Confusing the formula with the secant method formula. Remember that Regula Falsi strictly maintains the bracketing property.

Secant Method

The secant method is an open-bracket root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f(x).

Concept and Step-by-Step Explanation

Unlike the false position method, the secant method does not require the function to change signs across the interval, making it an open method. It requires two initial estimates.

1. Start with two distinct initial guesses x₀ and x₁.
2. Compute the next approximation x₂ using the secant line formula.
3. Update the values: set x₀ = x₁ and x₁ = x₂.
4. Repeat until convergence is achieved.

Formula: x_n+1 = x_n - [f(x_n) × (x_n - x_n-1)] / [f(x_n) - f(x_n-1)]

Practical Example

Given f(x) = x² - 4, start with x₀ = 1 and x₁ = 3 to find x₂.

Real-World Applications

Applied when derivative calculations are computationally expensive or impossible, serving as a derivative-free alternative to Newton-Raphson.

Exam-Oriented Notes

Does not require f(x₀) and f(x₁) to have opposite signs. Can diverge if the initial guesses are poor.

Common Mistakes

Division by zero when f(x_n) equals f(x_n-1).

Fixed Point Iteration Method

The fixed-point iteration method is an open method used to find roots by rearranging an equation into an equivalent form.

Concept and Step-by-Step Explanation

An equation f(x) = 0 is rewritten in the form x = g(x). Starting with an initial guess x₀, successive approximations are generated via x_n+1 = g(x_n).

1. Rewrite f(x) = 0 as x = g(x).
2. Choose an initial guess x₀.
3. Calculate x₁ = g(x₀).
4. Calculate x₂ = g(x₁), and so on.
5. Stop when |x_n+1 - x_n| < tolerance.

Formula: x_n+1 = g(x_n)

Practical Example

Solve x³ + x - 1 = 0 by rewriting it as x = g(x) = 1 / (1 + x²).

Real-World Applications

Used in solving systems of nonlinear equations and integral equations.

Exam-Oriented Notes

Convergence depends heavily on the choice of g(x). The method converges if |g'(x)| < 1 in the region of the root.

Common Mistakes

Choosing a rearrangement of g(x) where the derivative magnitude is greater than 1, leading to divergence.

Newton-Raphson Method

The Newton-Raphson method is a powerful open method that uses the tangent line of the function to rapidly find successively better approximations to the roots.

Concept and Step-by-Step Explanation

It uses the derivative of the function at the current guess to project down to the x-axis and find the next intercept.

1. Choose an initial guess x₀ close to the root.
2. Evaluate the function value f(x₀) and the derivative value f'(x₀).
3. Calculate the next approximation using the Newton-Raphson formula.
4. Repeat the process until the desired accuracy is met.

Formula: x_n+1 = x_n - [f(x_n) / f'(x_n)]

Practical Example

Find the root of f(x) = x² - 2 = 0 starting with x₀ = 1. Here f'(x) = 2x. Thus x₁ = 1 - (1 - 2) / 2 = 1.5.

Real-World Applications

Widely used in physics engines, optimization problems, and power flow analysis in electrical engineering due to its rapid convergence.

Exam-Oriented Notes

Requires the analytical derivative f'(x) to be known and non-zero at the approximations.

Common Mistakes

Selecting an initial guess where the derivative f'(x_n) is zero or close to zero, resulting in division by zero or massive overshooting.

Convergence of Methods and Related Problems

Convergence rate determines how quickly the error decreases with each successive iteration.

Related Problems and Analysis

Understanding convergence involves analyzing the error e_n = x_n - α where α is the exact root. For Newton-Raphson, e_n+1 ≈ C × (e_n)², which demonstrates quadratic convergence.

Exam-Oriented Notes

Expect theoretical questions asking to state the order of convergence for each method, or numerical problems requiring calculation up to a specified number of decimal places.

Common Mistakes

Assuming all open methods have quadratic convergence. Only Newton-Raphson guarantees quadratic convergence under standard conditions, while the secant method achieves superlinear convergence.