Solving Non-linear Equations: Methods, Errors & Applications

TAKEAWAYS:

• Non-linear equations cannot be solved algebraically in many cases, requiring numerical methods like bisection, secant, or Newton-Raphson.
• Error analysis (true error, relative error) measures how close an approximation is to the exact solution.
• Convergence depends on initial guesses, method choice, and the function’s behavior (e.g., continuity, differentiability).
• Iterative methods (Jacobi, Gauss-Seidel) solve systems of non-linear equations by successive approximation.
• Real-world applications include financial modeling (loan interest rates), traffic optimization (route planning), and engineering design (structural stability).
• Exam focus: Derive methods, apply them step-by-step, and compare advantages/disadvantages of each technique.

1. Introduction to Non-linear Equations

Non-linear equations are equations where the variable appears in a non-linear form (e.g., $x^2$, $\sin (x)$, $e^x$). Examples include:

• $f(x)=x^3-2x-5=0$ (polynomial)
• $f(x)=e^x-3x=0$ (transcendental)
• $f(x)=\sin (x)-x/2=0$ (trigonometric)

These cannot always be solved analytically, so numerical methods are used to approximate roots.

Key Concepts

• Root: A value $x=r$ such that $f(r)=0$.
• Initial guess: Starting point for iterative methods (e.g., $x_0=1$).
• Iteration: Repeated application of a formula to refine the guess.

2. Error Analysis

To measure how close an approximation $x_n$ is to the exact root $r$, we define:

1. True Error (Absolute Error): $$e_n=|x_n-r|$$ Problem: We don’t know $r$ in practice, so we estimate it.

2. Relative Error: $$e_n^{\text{rel}}=\left|\frac{x_n-r}{r}\right|$$ Use case: Comparing errors across different scales (e.g., $x=0.001$ vs. $x=1000$).

3. Approximate Error: Since $r$ is unknown, we use: $$e_n\approx |x_{n+1}-x_n|$$ Example: If $x_5=1.56$ and $x_6=1.561$, the approximate error is $0.001$.

3. Methods for Solving Non-linear Equations

We focus on iterative methods, which refine guesses until convergence.

A. Bisection Method

How it works:

1. Find two points $a$ and $b$ such that $f(a)$ and $f(b)$ have opposite signs (Intermediate Value Theorem guarantees a root in $[a,b]$).
2. Compute the midpoint $c=(a+b)/2$.
3. Check $f(c)$:
   • If $f(c)=0$, $c$ is the root.
   • If $f(a)f(c)<0$, the root lies in $[a,c]$. Set $b=c$.
   • Else, the root lies in $[c,b]$. Set $a=c$.
4. Repeat until $|b-a|<\text{tolerance}$.

Advantages:

• Guaranteed to converge if $f$ is continuous.
• Easy to implement.

Disadvantages:

• Slow convergence (linear rate: $e_{n+1}\approx e_n/2$).

Example 1: Solve $f(x)=2x^3-2x-5=0$ with $x_0=1$, $x_1=2$ (tolerance $=10^{-3}$) Final approximation: $x\approx 1.521$ (after 10 iterations).

Real-world tie-in:

• Loan interest calculation: Banks use root-finding to determine monthly payments where the net present value of payments equals the loan amount. The bisection method ensures stability in financial models.

B. Secant Method

How it works:

• Uses two initial guesses $x_0$ and $x_1$ to approximate the root.
• Formula: $$x_{n+1}=x_n-f(x_n)\cdot \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$$ (A secant line replaces the tangent line in Newton-Raphson.)

Advantages:

• Faster convergence than bisection (superlinear rate).
• No need for derivatives.

Disadvantages:

• May diverge if initial guesses are poor.

Example 2: Solve $f(x)=x^2-4x-10=0$ with $x_0=4$, $x_1=2$

Iteration | \(x_n\) | \(f(x_n)\) | \(x_{n+1}\)
--- | --- | --- | ---
0 | 4 | 2 | -
1 | 2 | -10 | \(x_2 = 2 - (-10)(4-2)/(2-(-10)) = 2.571\)
2 | 2.571 | -1.64 | \(x_3 = 2.571 - (-1.64)(2.571-2)/(-1.64-2) = 3.449\)
3 | 3.449 | 1.34 | \(x_4 = 3.449 - (1.34)(3.449-2.571)/(1.34-(-1.64)) = 3.245\)
... (converges to \(x \approx 5.0\))

Real-world tie-in:

• Traffic route optimization: Pathao uses root-finding to estimate optimal delivery routes where the cost function (time + fuel) is non-linear. The secant method balances speed and accuracy in real-time adjustments.

C. Newton-Raphson Method

How it works:

• Uses the tangent line at $x_n$ to approximate the root: $$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$
• Requires $f$ to be differentiable.

Advantages:

• Fast convergence (quadratic rate: $e_{n+1}\approx e_n^2$).

Disadvantages:

• May diverge if $f^{\prime }(x_n)=0$ or initial guess is poor.

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

Iteration | \(x_n\) | \(f(x_n)\) | \(f'(x_n)\) | \(x_{n+1}\)
--- | --- | --- | --- | ---
0 | 2 | -1 | 8 | \(2 - (-1)/8 = 2.125\)
1 | 2.125 | 0.023 | 9.023 | \(2.125 - 0.023/9.023 = 2.102\)
2 | 2.102 | 0.000 | 8.412 | \(2.102 - 0.000/8.412 = 2.102\)

Real-world tie-in:

• Stock price modeling (NEPSE): Analysts use Newton-Raphson to fit non-linear models to stock trends. For example, predicting the root of a profit function where $f(x)=\text{revenue}(x)-\text{cost}(x)=0$ helps determine break-even points.

D. Fixed-Point Iteration

How it works: Rewrite $f(x)=0$ as $x=g(x)$. Iterate: $$x_{n+1}=g(x_n)$$ Convergence condition: $|g^{\prime }(x)|<1$ near the root.

Example 4: Solve $x=\cos (x)$ Rewrite as $x=1-\frac{x^2}{2}+\frac{x^4}{24}$ (Taylor series). Start with $x_0=0.5$:

Iteration | \(x_n\)
--- | ---
0 | 0.5
1 | 0.875
2 | 0.645
3 | 0.782
4 | 0.718
... (converges to \(x \approx 0.739\))

Real-world tie-in:

• Khalti transaction fees: The effective fee $x$ after discounts can be modeled as $x=g(x)$, where $g$ accounts for dynamic pricing. Fixed-point iteration helps stabilize fee calculations.

4. Comparison of Methods

5. Systems of Non-linear Equations: Jacobi and Gauss-Seidel Methods

For systems like: $$\{\begin{array}{l}{f}_1(x,y,z)=0\\ f_2(x,y,z)=0\\ f_3(x,y,z)=0\end{array}$$ we rearrange to: $$x=g_1(x,y,z),y=g_2(x,y,z),z=g_3(x,y,z)$$

A. Jacobi Method

Update all variables simultaneously: $$x^{(k+1)}=g_1(x^{(k)},y^{(k)},z^{(k)})$$ $$y^{(k+1)}=g_2(x^{(k)},y^{(k)},z^{(k)})$$ $$z^{(k+1)}=g_3(x^{(k)},y^{(k)},z^{(k)})$$

B. Gauss-Seidel Method

Update variables sequentially (using latest values): $$x^{(k+1)}=g_1(x^{(k)},y^{(k)},z^{(k)})$$ $$y^{(k+1)}=g_2(x^{(k+1)},y^{(k)},z^{(k)})$$ $$z^{(k+1)}=g_3(x^{(k+1)},y^{(k+1)},z^{(k)})$$

Example 5: Solve the system $$\{\begin{array}{l}x+2y+3z=5\\ 2x+8y+22z=6\\ 3x+22y+82z=-10\end{array}$$ Rearrange: $$x=5-2y-3z,y=\frac{6-2x-22z}{8},z=\frac{-10-3x-22y}{82}$$ Initial guess: $x_0=y_0=z_0=0$.

Jacobi Iteration 1: $$x_1=5-0-0=5,y_1=\frac{6-0-0}{8}=0.75,z_1=\frac{-10-0-0}{82}\approx -0.122$$

Gauss-Seidel Iteration 1: $$x_1=5-0-0=5$$ $$y_1=\frac{6-2(5)-0}{8}=-0.5$$ $$z_1=\frac{-10-3(5)-22(-0.5)}{82}\approx -0.0366$$

Convergence: Gauss-Seidel typically converges faster because it uses updated values.

flowchart TD
    A["System of Equations"] --> B["Rearrange to \(x = g_1\), \(y = g_2\), \(z = g_3\)"]
    B --> C["Jacobi: Update all variables simultaneously"]
    B --> D["Gauss-Seidel: Update sequentially"]
    C --> E["Slower convergence"]
    D --> F["Faster convergence"]

Real-world tie-in:

• Daraz order processing: When a user places multiple items in a cart, the system solves a non-linear equation to balance inventory, shipping costs, and delivery times. Jacobi/Gauss-Seidel methods help optimize order fulfillment queues in real time.

6. Convergence Criteria

For a method to converge:

1. Fixed-point iteration: $|g^{\prime }(x)|<1$ near the root.
2. Newton-Raphson: $f^{\prime }(x)\ne 0$ and initial guess close to root.
3. Bisection/Secant: Function must be continuous and bracket the root.

Stopping criteria:

• $|x_{n+1}-x_n|<\text{tolerance}$ (e.g., $10^{-6}$).
• Maximum iterations reached.

7. In the Real World

1. eSewa (Nepal):

   • Application: Calculating dynamic electricity bills where the cost function is non-linear (e.g., $\text{Bill}=a\cdot {\text{Usage}}^b+c$).
   • Method: Newton-Raphson is used to solve for the exact usage when the bill amount is known but the usage is non-linear.

2. Ncell Network Optimization:

   • Application: Adjusting signal towers to maximize coverage while minimizing interference. The signal strength $S$ depends on non-linear factors like distance $d$ and obstacles: $$S(d)=\frac{P_t}{d^{\alpha }}\cdot e^{-\beta \cdot \text{obstacles}}$$
   • Method: Secant method approximates optimal tower placements where $S(d)=\text{threshold}$.

3. NEPSE Stock Analysis:

   • Application: Predicting the break-even point for a stock where the profit function is: $$\Pi (p)=p\cdot Q(p)-C=0$$ Here, $Q(p)$ is demand (non-linear) and $C$ is cost.
   • Method: Bisection method ensures stable convergence even with volatile data.

8. Exam Tip

1. Derivations are key:

   • For bisection, secant, or Newton-Raphson, show every step of the formula derivation. Examiners check if you understand the underlying logic.
   • Example: For Newton-Raphson, start from $f(x)=0$ and use the tangent line approximation.

2. Iteration tables:

   • Always present iterations in a clear table with columns for $x_n$, $f(x_n)$, and $x_{n+1}$. Partial credit is lost if steps are messy.

3. Error analysis:

   • Questions often ask for true error or relative error. Practice calculating these after each iteration.

4. Method comparison:

   • Be ready to contrast Jacobi and Gauss-Seidel in terms of speed, memory, and convergence. Use the table above as a reference.

5. Real-world connections:

   • Link numerical methods to Nepali contexts (e.g., Khalti fees, Daraz logistics, NTC billing). Examiners appreciate practical ties.

6. Graphs:

   • Always sketch the function and highlight the root-finding process (e.g., bisection intervals, secant lines). Visuals add marks.

9. Worked Exam-Style Questions

Question 1: Bisection Method

Solve $f(x)=x^3-x-2=0$ with $x_0=1$, $x_1=2$ (tolerance $=0.01$).

Solution:

1. Check signs: $f(1)=-2$, $f(2)=4$ → root in $[1,2]$.
2. Iterations:

   Iter | a | b | c = (a+b)/2 | f(c)
   --- | --- | --- | --- | ---
   1 | 1 | 2 | 1.5 | -0.875
   2 | 1.5 | 2 | 1.75 | 1.703
   3 | 1.5 | 1.75 | 1.625 | 0.406
   4 | 1.5 | 1.625 | 1.5625 | -0.230
   5 | 1.5625 | 1.625 | 1.59375 | 0.091
   6 | 1.5625 | 1.59375 | 1.578125 | -0.069
   

3. Final approximation: $x\approx 1.58$ (since $|1.59375-1.5625|=0.03125>0.01$, continue to $x\approx 1.582$).

Question 2: Newton-Raphson

Solve $f(x)=e^x-3x=0$ with $x_0=1$.

Solution:

1. Derivative: $f^{\prime }(x)=e^x-3$.
2. Iterations:

   Iter | \(x_n\) | \(f(x_n)\) | \(f'(x_n)\) | \(x_{n+1}\)
   --- | --- | --- | --- | ---
   0 | 1 | -1.718 | -2 | 1.859
   1 | 1.859 | 0.002 | -1.145 | 1.859
   

3. Root: $x\approx 1.859$.

Question 3: Jacobi vs. Gauss-Seidel

Solve: $$\{\begin{array}{l}10x+y+z=12\\ 2x+10y+z=13\\ 2x+2y+10z=14\end{array}$$ using both methods (3 iterations).

Solution: Rearrange: $$x=1.2-0.1y-0.1z,y=1.3-0.2x-0.1z,z=1.4-0.2x-0.2y$$

Jacobi Iterations:

Iter | x | y | z
--- | --- | --- | ---
0 | 0 | 0 | 0
1 | 1.2 | 1.3 | 1.4
2 | 0.89 | 0.98 | 0.94
3 | 0.953 | 0.976 | 0.982

Gauss-Seidel Iterations:

Iter | x | y | z
--- | --- | --- | ---
0 | 0 | 0 | 0
1 | 1.2 | 1.06 | 0.972
2 | 0.9828 | 0.9856 | 0.9914
3 | 0.995 | 0.997 | 0.998

Observation: Gauss-Seidel converges faster.

flowchart LR
    A["Initial Guess (0,0,0)"] --> B["Jacobi: Update all at once"]
    A --> C["Gauss-Seidel: Update sequentially"]
    B --> D["Slower convergence"]
    C --> E["Faster convergence"]