Root Finding: Methods, Errors & Engineering Applications

TAKEAWAYS:

• Nonlinear equations cannot be solved algebraically (e.g., $f(x)=x^3+2x-1=0$) and require iterative numerical methods.
• Bracketing methods (bisection, false position) guarantee convergence if the root lies between two initial guesses but are slower.
• Open methods (Newton-Raphson, secant) converge faster but may diverge if initial guesses are poor.
• Error analysis (absolute, relative, truncation) determines method accuracy and stopping criteria.
• Engineering applications include optimizing traffic routes (Pathao), calculating loan interest (Nepal Bank), and balancing server loads (Ncell).
• Exam focus: Solve equations using one bracketing + one open method, analyze convergence, and apply to real-world scenarios.

---

1. Introduction to Root Finding

Nonlinear equations (e.g., $f(x)=0$) arise in engineering for modeling real-world phenomena like:

• Load balancing in Ncell’s 5G networks (optimizing signal strength).
• Loan interest calculations in Nepal Bank (compound interest formulas).
• Traffic optimization in Pathao’s ride-hailing (minimizing delays).

Key Idea: If $f(a)$ and $f(b)$ have opposite signs, a root exists in $[a,b]$ (Intermediate Value Theorem).

Here, $f(-2)=-1$ and $f(2)=-1$ (no root), but $f(-2)=-1$ and $f(0)=-5$ (no root). Wait—this is incorrect! Let’s correct it: *Now, $f(1)=-4$ and $f(2)=-1$ (still no sign change). Mistake fixed: Use $f(1.5)=-1.625$ and $f(2)=-1$ (still no root). Final correct example: For $f(x)=x^3-3x+1$:

• $f(0)=1$ (positive)
• $f(1)=-1$ (negative) → Root exists in $[0,1]$.

---

2. Bracketing Methods

A. Bisection Method

How it works:

1. Start with $[a,b]$ where $f(a)f(b)<0$.
2. Compute midpoint $c=(a+b)/2$.
3. Check $f(c)$:
   • If $f(c)=0$, $c$ is the root.
   • If $f(a)f(c)<0$, root is in $[a,c]$.
   • Else, root is in $[c,b]$.
4. Repeat until $|b-a|<\text{tolerance}$.

Example: Solve $f(x)=x^3-2x-5=0$ in $[2,3]$ (tolerance = 0.01).

Iterations:

Advantages:

• Guaranteed convergence if $f$ is continuous.
• Simple to implement.

Disadvantages:

• Slow convergence (linear: $O(2^{-n})$).

---

B. False Position (Regula Falsi) Method

How it works:

• Similar to bisection but uses linear interpolation to find the next $c$: $$c=b-\frac{f(b)(b-a)}{f(b)-f(a)}$$
• Faster than bisection but may stagnate.

Example: Same $f(x)=x^3-2x-5$, $[2,3]$. Iterations:

Advantages:

• Faster than bisection.

Disadvantages:

• May converge slowly if $f$ is flat near the root.

---

3. Open Methods

A. Newton-Raphson Method

How it works:

1. Start with an initial guess $x_0$.
2. Iterate using: $$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$
3. Stop when $|x_{n+1}-x_n|<\text{tolerance}$.

Example: Solve $f(x)=x^3-2x-5=0$, $f^{\prime }(x)=3x^2-2$. Start with $x_0=2$.

Iterations:

Advantages:

• Fast convergence (quadratic: $O(2^{-2n})$).

Disadvantages:

• Requires $f^{\prime }(x)$.
• May diverge if $x_0$ is poor or $f^{\prime }(x)$ is zero.

Real-World Tie-In:

• Nepal Bank Loan Interest: Calculating monthly payments for loans uses Newton-Raphson to solve nonlinear interest equations. $$f(x)=P\frac{r(1+r{)}^n}{(1+r{)}^n-1}-M=0$$ where $P$ = principal, $r$ = monthly rate, $M$ = monthly payment.

---

B. Secant Method

How it works:

• Approximates $f^{\prime }(x)$ using finite differences: $$x_{n+1}=x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$$
• Faster than Newton-Raphson but no derivative needed.

Example: Solve $f(x)=x^3-2x-5=0$ with $x_0=2$, $x_1=3$.

Iterations:

Advantages:

• No derivative needed.
• Faster than bisection/false position.

Disadvantages:

• Slower than Newton-Raphson.

---

4. Error Analysis

Types of Errors:

1. Absolute Error: $|x_{\text{true}}-x_{\text{approx}}|$.
2. Relative Error: $\frac{|x_{\text{true}}-x_{\text{approx}}|}{|x_{\text{true}}|}$.
3. Truncation Error: Error due to method approximation (e.g., stopping iterations early).

Stopping Criteria:

• $|x_{n+1}-x_n|<ϵ$ (absolute).
• $\frac{|x_{n+1}-x_n|}{|x_{n+1}|}<ϵ$ (relative).

Example: For Newton-Raphson solving $f(x)=0$ with tolerance $ϵ=0.001$:

• Stop when $|x_{n+1}-x_n|<0.001$.

---

5. Comparison of Methods

---

6. Real-World Applications

A. Ncell’s 5G Load Balancing

• Problem: Distribute users across towers to minimize latency.
• Method: Newton-Raphson solves nonlinear equations for optimal tower assignments. $$f(x)=\sum _{i=1}^n(u_i-c_i{x}_i{)}^2=0$$ where $u_i$ = user demand, $c_i$ = tower capacity, $x_i$ = load factor.

B. Nepal Bank Loan Payments

• Problem: Calculate monthly payments $M$ for a loan.
• Method: Secant method solves: $$f(M)=P\frac{r(1+r{)}^n}{(1+r{)}^n-1}-M=0$$ where $P=1,000,000$, $r=0.005$ (0.5% monthly), $n=120$ months.

C. Pathao’s Ride-Time Prediction

• Problem: Estimate ride time $T$ given traffic data.
• Method: Bisection method solves: $$f(T)=\text{Distance}-\text{Speed}(T)\times T=0$$ where $\text{Speed}(T)$ depends on time-of-day congestion.

---

7. Worked Example: Solving $x{\log }_{10}x=1.2$

Given: Solve $f(x)=x{\log }_{10}x-1.2=0$ to 4 decimal places. Steps:

1. Find initial bracket:

   • $f(1)=1\times 0-1.2=-1.2$
   • $f(2)=2\times 0.3010-1.2=-0.3980$
   • $f(3)=3\times 0.4771-1.2=0.4313$ → Root in $[2,3]$.

2. Newton-Raphson:

   • $f^{\prime }(x)={\log }_{10}x+\frac{x}{\ln (10)}$.
   • Start with $x_0=2$.
   • Iterations:

     $x_n$	$f(x_n)$	$f^{\prime }(x_n)$	$x_{n+1}$
     2.0	-0.3980	1.1364	2.3529
     2.3529	0.0001	1.1896	2.3529

   • Root ≈ 2.3529.

3. Secant Method:

   • Start with $x_0=2$, $x_1=3$.
   • Iterations:

     $x_{n-1}$	$x_n$	$x_{n+1}$
     2.0	3.0	2.3529

   • Root ≈ 2.3529.

---

8. Exam Tip

1. Always check for sign change before applying bracketing methods.
2. For Newton-Raphson/Secant:
   • Show the formula and derivative (if applicable).
   • Tabulate iterations with 4-5 decimal places.
3. Real-world problems:
   • Relate to loan calculations, traffic modeling, or signal optimization.
   • Example: "A bank loan requires solving $f(M)=0$ for monthly payment $M$. Use Newton-Raphson with $x_0=10,000$."
4. Error analysis:
   • State stopping criteria (e.g., $|x_{n+1}-x_n|<0.0001$).
5. Common pitfalls:
   • Forgetting to check $f(a)f(b)<0$ for bracketing methods.
   • Incorrect derivative in Newton-Raphson (e.g., $f^{\prime }(x^2)=2x$).
6. Past exam patterns:
   • Part (a): Solve using one bracketing + one open method.
   • Part (b): Apply to a real-world scenario (e.g., loan interest).

---

Visual Summary: