- Backeting Methods

- Open Methods
- Simple Fixed-point Iteration
- The Newton-Raphson Method
- The Secant Method
- Multiple Roots
- Systems of Nonlinear Equations

- Roots of Polynomials
- Polynomials in Engineering and Science
- Computing with Polynomials
- Conventional Methods
- Root Location with Libraries and Packages

- Engineering Applications: Roots of Equations

(2.1) |

then there is at least one real root between and .

- equally dividing the interval
- no account for for the magnitudes of and

The false-position formula is

(2.2) |

See Figure 5.14 in textbook

- bracketing method : the root is located within an interval prescribed by a lower and an upper bound.
- open method : require only a single starting value of x or two starting point that do not necessarily bracket the root.

(2.3) |

The Newton-Raphson formula is

(2.4) |

Pitfalls of the Newton-Raphson Method are shown in Figure 6.6

(2.5) |

The Secant formula is

(2.6) |

The difference between the secant method and the false-position method is how one of the initial values is replaced by the new estimate.

Rather than using two arbitrary values to estimate the derivative, an alternative approach involves a fractional perturbation of the independent variable to estimate ,

(2.7) |

where is a small perturbation fraction. This approximation gives the following iterative equation:

(2.8) |

- no change in sign at even multiple roots
- and go to zero at the root
- the Newton-Raphson method and secant method show linear, rather than quadratic, convergence for multiple roots.

Another alternative is to define a new function ,

(2.9) |

An alternative form of the Newton-Raphson method:

(2.10) |

where is

(2.11) |

And finally

(2.12) |

(2.13) | ||

(2.14) |

A first-order Taylor series expasion can be written as

(2.15) | |

(2.16) |

The above equation can be rearranged to give

(2.17) | ||

(2.18) |

Finally

(2.19) | ||

(2.20) |

- For an nth-order equation, there are n real and complex roots.
- If n is odd, there is at least one real root.
- If complex roots exist, they exist in conjugate pairs.

For example, we consider the following simple second-order ordinary differential equation:

(2.21) |

where is the forcing function. And the above ODE can be expressed as a system of 2 first-order ODEs by defining a new variable z,

(2.22) |

This reduces the problem to solving

(2.23) | ||

(2.24) |

In a simliar fashion, nth-order linear ODE can always be expressed as a system of n first-order ODEs.

The general solution of ODE equation deals with the case when the forcing function is set to zero.

(2.25) |

This equation gives something very fundamental about the system being simulated-that is, how the system reponds in the absence of external stimuli. The general solution to all unforced linear system is of the form .

(2.26) |

or cancelling the exponential terms,

(2.27) |

This polynomial is called as characteristic equation and these r's are referred to as eigenvalues.

(2.28) |

- overdamped case : all real roots
- critically damped case : only one root
- underdamped case : all complex roots

DO j=n, 0 p = p * x + a(j) END DO

If you want to find all roots of a polynomial, you have to remove the found root before another processing. This removal process is referred to as polynomial deflation.

- Müller's method : projects a parabola through three points.
- Bairstow's method:
- guess a value for the root
- divide the polynomial by the factor
- determine whether there is a reminder. If not, the guess is was perfect and the root is equal to. If there is a reminder, the guess can be systematically adjusted and the procedure repeated until the reminder disappears.

- Matlab:
- roots
- poly
- polyval
- residue
- conv
- deconv

- IMSL:
- ZREAL

2001-11-29