Numerical Methods

Roots of Nonlinear Equations

Institution: PAMANTASAN NG LUNGSOD NG MAYNILA
Department: College of Engineering and Technology (CET)
Instructor: Engr. Reynaldo Ted L. Peñas II, MScEngg

Introduction to Roots of Nonlinear Equations

• The goal is to find the solutions of the equation $f(x) = 0$ where the function $f$ is defined.

• The solutions (values of $x$) are known as the roots of the equation $f(x) = 0$ or the zeroes of the function $f(x)$.

Nature of Roots

Types of Roots

• Roots or zeroes may be:

  • Real: Actual numerical values on the real number line.

  • Complex: Often computed in polynomials relating to applications such as damped vibrations (seldom significant in practical computations).

• The approximate locations of the roots can be effectively estimated by plotting the function.

Extraction of Roots

Key Points to Consider

• All methods of finding roots are iterative procedures that begin with a starting point (an initial estimate of the root).

• An initial estimate is crucial:

  • A poor choice may lead to failure to converge or converge to the “wrong” root.

Stopping Criteria for Iterative Methods

• Criteria for stopping iterations based on errors:

  • Identify actual error versus significant error:

  • $x_{ ext{present}}$ = estimated root in the current iteration

  • $x_{ ext{previous}}$ = estimated root in the last iteration

  • $n$ = number of significant figures

Methods for Finding Roots of Nonlinear Equations

• Various methods include:

  • Direct or Incremental Search Method

  • Interval-Halving Method

  • Method of False-Position

  • Newton-Raphson 1st Method

  • Newton-Raphson 2nd Method

  • Secant Method

  • Fixed-Point Iteration

  • Bairstow’s Method

Direct or Incremental Search Method

Description

• If $f(x<em>1)$ and $f(x</em>2)$ have opposite signs, then at least one root exists in the interval $[x<em>1, x</em>2]$.

• A small enough interval likely contains a single root.

• Zeroes can be detected by evaluating the function at various points and looking for a change in sign.

Algorithm

1. Estimate the initial interval $[x<em>i, x</em>{i+1}]$ bounding the root (where $f(x<em>i)$ and $f(x</em>{i+1})$ must be opposite signs).

2. Evaluate $f(x<em>i)$ and $f(x</em>{i+1})$.

3. Check the product of $f(x<em>i) imes f(x</em>{i+1})$:

   • If positive: Set $x<em>{i+1}$ as a new lower bound ($x</em>i$).

   • If negative: Estimate a smaller $ext{Δ}x$ and generate a new $x_{i+1}$.

4. Repeat steps 2 & 3 until stopping criteria satisfied.

Example

• Test Function: $f(x) = e^{-x} - ext{cos}(x)$

• Initial estimates: $x<em>i = 1$, $x</em>{i+1} = 1.5$, $ext{Δ}x = 0.5$

Simulation of Iterations

Bisection Method of Bolzano

Description

• The method is based on the principle that if there is a root in the interval $[x<em>1, x</em>2]$, then f(x1) f(x2) < 0.

• To halve the interval, compute $f(x<em>3)$, where $x</em>3 = rac{1}{2}(x<em>1 + x</em>2)$ is the midpoint.

• Depending on the sign of $f(x<em>2) f(x</em>3)$:

  • If negative, root lies in $[x<em>2, x</em>3]$, so replace $x<em>1$ with $x</em>3$.

  • If positive, root lies in $[x<em>1, x</em>3]$, so replace $x<em>2$ with $x</em>3$.

Algorithm

1. Estimate initial interval $[x<em>i, x</em>{i+1}]$ bounding the root (where $f(x<em>i)$ and $f(x</em>{i+1})$ must be opposite signs).

2. Compute $x<em>r$ (the midpoint): $x</em>r = rac{x<em>i+x</em>{i+1}}{2}$.

3. Evaluate $f(x<em>i)$, $f(x</em>{i+1})$, and $f(x_r)$.

4. Check the product of $f(x<em>i) imes f(x</em>r)$:

   • If positive: Define $x<em>r$ as the new lower bound ($x</em>i$).

   • If negative: Define $x<em>r$ as the new upper bound ($x</em>{i+1}$).

5. Repeat steps 3 & 4 until stopping criteria satisfied.

Example

• Test Function: $f(x) = e^{-x} - ext{cos}(x)$

• Initial estimates: $x<em>i = 1$, $x</em>{i+1} = 1.5$, $x_r = 1.25$

Simulation of Iterations

Method of False Position (Regula Falsi)

Description

• Similar to bisection, this method starts with an interval $[x<em>i, x</em>{i+1}]$ believed to contain the solution for $f(x) = 0$.

• It approximates the curve of $f(x)$ within the interval via a straight line connecting $f(x<em>i)$ and $f(x</em>{i+1})$. The intersection of this line with the x-axis gives a new approximation for the root.

Algorithm

1. Estimate the initial interval $[x<em>i, x</em>{i+1}]$ bounding the root.

2. Compute for new root $x<em>r$ where $x</em>r = x<em>{i+1} - rac{(f(x</em>{i+1})(x<em>i-x</em>{i+1}))}{(f(x<em>i)-f(x</em>{i+1}))}$.

3. Evaluate $f(x<em>i)$, $f(x</em>{i+1})$, and $f(x_r)$.

4. Check the product of $f(x<em>i) imes f(x</em>r)$:

   • If positive: Define $x<em>r$ as the new lower bound ($x</em>i$).

   • If negative: Define $x<em>r$ as the new upper bound ($x</em>{i+1}$).

5. Repeat steps 3 & 4 until stopping criteria satisfied.

Example

• Test Function: $f(x) = e^{-x} - ext{cos}(x)$

• Initial estimates: $x<em>i = 1$, $x</em>{i+1} = 1.5$, $x_r = 1.265416357$

Simulation of Iterations

Newton-Raphson 1st Method (Method of Tangents)

Description

• This is a notable method for finding roots due to its simplicity and speed.

• The method's drawback is that it requires the derivative $f'(x)$ of the function along with the function $f(x)$ itself.

• It is derived from the Taylor Series expansion.

/

Algorithm

1. Estimate the initial root approximation $x_i$.

2. Compute new root $x<em>{i+1}$ where: $x</em>{i+1} = x<em>i - rac{f(x</em>i)}{f'(x_i)}$.

3. Evaluate both $f(x<em>i)$ and $f(x</em>{i+1})$.

4. Repeat steps 2 & 3 until stopping criteria satisfied.

Example

• Test Function: $f(x) = e^{-x} - ext{cos}(x)$

• Initial estimate: $x_i = 1$

• Corresponding derivative: $f'(x) = -e^{-x} + ext{sin}(x)$

• First iteration gives: $x_{i+1} = 1.36407505$

Simulation of Iterations

Newton-Raphson 2nd Method

Description

• This method is calculus-based and derived from the first method, utilizing truncated Taylor’s series expansion.

• It employs both 1st and 2nd order derivatives to enhance the root approximation of $f(x) = 0$.

Algorithm

1. Estimate the initial root approximation $x_i$.

2. Compute new root $x<em>{i+1}$: $x</em>{i+1} = x<em>i - rac{f(x</em>i)}{f'(x<em>i)} - rac{f''(x</em>i)}{2 f'(x_i)}$.

3. Evaluate $f(x<em>i)$ and $f(x</em>{i+1})$.

4. Repeat steps 2 & 3 until stopping criteria satisfied.

Example

• Test Function: $f(x) = e^{-x} - ext{cos}(x)$

• Initial estimate: $x_i = 1$

• Derivatives: $f'(x) = -e^{-x} + ext{sin}(x)$, $f''(x) = e^{-x} + ext{cos}(x)$

• First iteration gives: $x_{i+1} = 1.320290083$

Simulation of Iterations

Secant Method

Description

• The Secant Method does not involve derivative calculations but converges rapidly, similar to Regula Falsi.

• It utilizes two initial points.

Algorithm

1. Estimate two initial points $x<em>i$ and $x</em>{i-1}$.

2. Evaluate $f(x<em>i)$ and $f(x</em>{i-1})$.

3. Compute new root $x<em>{i+1}$: $x</em>{i+1} = x<em>i - rac{f(x</em>i) (x<em>i - x</em>{i-1})}{f(x<em>i) - f(x</em>{i-1})}$.

4. The current $x<em>i$ will be transferred to the previous $x</em>{i-1}$ for the next iteration.

5. Repeat steps 2 & 3 until stopping criteria satisfied.

Example

• Test Function: $f(x) = e^{-x} - ext{cos}(x)$

• Initial estimates: $x<em>i = 1$, $x</em>{i-1} = 0.5$

• First iteration gives: $x_{i+1} = 1.874097878$

Simulation of Iterations

Fixed-Point Iteration

Description

• Also known as Picard iteration, this method attempts to establish an auxiliary function $g(x)$ from $f(x)$ to find the root $x<em>0$ such that $f(x</em>0) = 0$. The auxiliary form is: $x<em>0 = g(x</em>0)$.

• The method's convergence does not greatly depend on its initial estimate as long as the fixed point exists in the interval $[x<em>1, x</em>2]$.

Example

• Equation: $x = ext{√}(6 + 3 ext{√}(6 + x))$

• The equivalent representation: $x^3 - 6 = 3 ext{√}(6 + x)$

• Auxiliary function becomes: $g(x) = 3 ext{√}(x + 6)$.

Simulation of Iterations

Bairstow's Method

Description

• This method addresses special issues with polynomials that have complex roots, allowing the extraction of quadratic factors using only real arithmetic.

• When polynomials with real coefficients have complex roots, these occur in conjugate pairs corresponding to a quadratic factor of polynomial $P_n(x)$.

Algorithm

1. Initiate: Consider the general nth-degree polynomial $P<em>n(x) = a</em>n x^n + a<em>{n-1} x^{n-1} + … + a</em>0$.

2. Factor out the quadratic: $P(x) = (x^2 - rx - s)Q_{n-2}(x) + ext{Remainder}$.

3. Set up a system of equations and compute coefficients iteratively until convergence of factors $r$ and $s$ occurs.

4. Once the quadratic factor is determined, roots are extracted two at a time; the polynomial reduces by two degrees enabling repetition of the method.

Example

• Initial guesses for $r$ and $s$: $r<em>1 = 1.5$, $s</em>1 = -2.5$.

Iteration Steps to Find Coefficients

1. Begin with coefficients stored in arrays created by preceding values.

2. Conduct iterations to compute values $b<em>i$ and $c</em>i$ noting adjustments for $r$ and $s$.

Conclusion

• Document strategies and algorithms underpinning roots of nonlinear equations, with detailed simulations showcasing iterative methods and practical examples to illuminate their application in engineering and computational contexts.