Root-Finding: Bisection Method

• Numerical root-finding methods seek to implement algorithms for finding roots of equations. This is essential when analytical methods are unavailable, particularly with transcendental equations. The goal is to ensure the algorithm's convergence and obtain roots with acceptable accuracy.

Bisection Method

• It relies on the Intermediate Value Theorem that requires a continuous function f over an interval [a, b], where f(a) * f(b) < 0, indicating 0 lies within the function's values on [a, b]. According to the IVT, there exists a value a ≤ c ≤ b such that f(c) = 0.
• It guarantees convergence to a single root.
• It has slow linear convergence but is effective.
• Also known as the Bolzano Method.
• To find the midpoint c of the interval [a, b] is calculated and the value of f(c) is determined. Depending on the sign of f(c) * f(a) compared to f(c) * f(b), the process iterates on either [a, c] or [c, b] until convergence.
• The method always converges to a root if the initial interval is correctly bracketed. The search interval is halved with each iteration.
• The absolute error after n steps is given by: ε = |xn - xr| = (b - a) / 2^n. To achieve p decimal places of accuracy, the error must be less than 0.5 * 10^-p.

Root Bracket Finding

• Find root brackets for these functions:
• f(x) = x³ – 4x + 1.
• f(x) = 1 / (x-1)
• f(x) = e^x – 3x.

Bisection Method Example

• Using the Bisection Method, find a root of the function f(x) = x³ - x² - 1 with an accuracy of 3 decimal places. By iterative steps, the interval is refined until desired accuracy is achieved. For finding a root with the bisection method for f(x) = x³-x²-1 with three decimal places accuracy:
• Initial values are bracketed to satisfy f(a)f(b) < 0, such as f(0) = -1 and f(2) = 3, choosing the interval [1,2].
• Iterations continue until the error is less than 0.5 * 10^-3. During the first few iterations, the midpoint calculation and function evaluation results were, c=1.5, f(1.5) = 0.125 and epsilon = 0.5.
• After 11 iterations the bracket [1.46484375, 1.4658203125] and c ≈ 1.46533203125 is reached which satisfies the required precision of < 0.005.

Iteration Estimation

• Estimate the number of iterations required to find a root of f(x) = x^3 − x^2 − 1 with an accuracy of three decimal places.
• Considering the bracket [1, 2] already encloses the root, we need the error to be less than 0.5 * 10^-3. Set up inequality and compute the number of iterations: 2^n = 1/ є = 1/0.0005 = 2000 -> n = log2(2000) = 10.966
• Approximately 11 iterations are needed.

Secant Line-based Methods

• They are based on the bisection idea. Two include: Regula Falsi (False Position Method) and Secant Method.
• They start from two initial estimates, drawing a secant line to find intersections with the x-axis. They pros are that it does not require bracketing a root. Its con is that convergence is not always guaranteed.

Newton Method

• It uses the tangent line at a specific point instead of a secant line. The derivative is used directly instead of approximating it using divided differences like the secant method. No root bracket or only on start point is needed. Tangent slope is based on f'(x).
• To identify the tangent line of f(x) at a point (x0, f(x0)), the equation for the tangent line with slope f′(x0) is y = f′(x0)x + b. The offset b, calculated from the line passing through (x0, f(x0)), is b = f(x0) − f′(x0)x0.
• Setting y = 0 calculates the point where the tangent line intersects the x-axis: x1 = x0 - f(x0) / f'(x0)
• In the iterative algorithm: initialize x₁, calculate xn+1 using the formula and repeat until convergence is achieved.
• It converges quadratically to a root and is faster than the bisection, regula falsi, and secant methods. Convergence is NOT guaranteed and it fails when the derivative on an estimate is 0, and may get stuck in a loop or converge to a different root.
• Error after n steps is given by: ε = |xn - xn-1|.

Newton Method Example

• Find a root of f(x) = x^3 - x^2 - 1 with 3 decimal places accuracy. Starting with x₁ = 1, where f(x₁) = −1, we calculate derivative f′(x) = 3x² − 2x. The next estimate is computed via x₂ = x₁ - f(x₁) / f′(x₁) giving x2 = 2.
• With f(x3) = 0.650390625 and e = 0.375 The third iteration x4 = 1.4857859531772575
  • With f(x4) = 0.07240158956588028 and € = 0.13921404682274252 Iteration details, where ϵ represents the change in x value between iterations
• Iteration 4: x5=1.4659559197359893 and €= 0.019830033441268213
• Iteration 5: x6 = 1.4655713749070918 and € = 0.00038454482889749286 which is less than 0.005.

Extra Exercises

• Find roots with specified accuracy for several functions:
• f(x) = xe^x - 1.
• f(x) = e^x - 2 - x.
• f(x) = 2x² + ln(x) - 3.
• f(x) = ln(x) + 30e^-x - 3.
• f(x) = x³ + 4x² + 4x - 4.
• f(x) = x³ - x² + 0.1.
• f(x) = xe^x - 0.004x² + 0.2.