Next: Linear Algebraic and Equations Up: Numerical Analysis for Chemical Previous: Modeling, Computers, and Error

Subsections

# Backeting Methods

## Graphical Methods

A simple method for obtaining an estimate of the root of the equation is to make a plot of the function and observe where it crosses the x axis.

## The Bisection Method

In general, if is real and continuous in the interval from to and and have opposite signs, that is

 (2.1)

then there is at least one real root between and .

## The False-Position Method

A shortcoming of the bisection method
• equally dividing the interval
• no account for for the magnitudes of and
An alternative method is to join and by a straight line and the intersection of this line with the x axis represents an improved estimate of the root. This mothod is called as method of false position, regula falsi, or linear interpolation method.

The false-position formula is

 (2.2)

See Figure 5.14 in textbook

# Open Methods

• 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.

## Simple Fixed-point Iteration

Open methods employ a formula to predict the root. Such a formula can be develped for simple fixed-point iteration by rearranging the function so that s is on the left-hand side of the equation:

 (2.3)

## The Newton-Raphson Method

If the initial guess at the root is , a tangent can be extended from the point . The point where this tangent crosses the x axis usaually represents an improved estimate of the root.

The Newton-Raphson formula is

 (2.4)

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

## The Secant Method

A potential problem in implementing the Newton-Raphson method is the evaluation of the derivative. In Secant method the derivative is approximated by a backward finite divided difference

 (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)

## Multiple Roots

Some difficulities in multiple roots problem
• 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)

## Systems of Nonlinear Equations

The Newton-Raphson method can be used to solve a set of nonlinear equations. The Newton-Raphson method employ the derivative of a function to estimate its intercept with the axis of the independent variable. This estimate was based on a first-order Taylor series expansion. For example, we consider two variable case,

 (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)

# Roots of Polynomials

The roots of polynomials have the following properties
• 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.

## Polynomials in Engineering and Science

Polynomial are used extensively in curve-fitting. However, another most important application is in characterizing dynamic system and, in particular, linear systems.

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

## Computing with Polynomials

For nth-order polynomial calculation, general approach requires multiplications and additions. However, if we use a nested format, multiplications and additions are required.
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.

## Conventional Methods

• Müller's method : projects a parabola through three points.
• Bairstow's method:
1. guess a value for the root
2. divide the polynomial by the factor
3. 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

# Engineering Applications: Roots of Equations

See the textbook

Next: Linear Algebraic and Equations Up: Numerical Analysis for Chemical Previous: Modeling, Computers, and Error
Taechul Lee
2001-11-29