Algebraic Equations

3.3.1 Solving Algebraic Equations

3.3.2 Bisection Method

3.3.3.Secant Method

3.3.4 Newton's Method

 

The following are all algebraic equations.

x - 3 = 5 (1)

sin 3x = y cos x (2)


a x2 + b x + c = 0 (3)

Analytical Solution

Only equations which are linear in their unknown have a guaranteed analytical solution:

a x = b (4)

Or:

a x - b =0 (5)


\begin{displaymath}x = \frac{b}{a} \end{displaymath}

However, consider:

\begin{displaymath}\log x - 4 = 3 \end{displaymath} (6)


\begin{displaymath}\sin(3\pi y) + 4 - \cos \frac{3 \pi}{2} = 0 \end{displaymath} (7)

Solving a Single Algebraic Equation

Where is the solution ?






Here:

It clearly lies on the x-axis at the point where the function f(x) value is zero.

Given an equation

f(x) = 0

find the value of x such that the function f(x) is zero to within some specified tolerance.

Engineering Problems have Bounded Solutions

Intrinsic:

$ 0 \le mol \; fraction \le 1.0 $

Operational: cooling water temperature, vessel pressure, etc

3.3.2 Simplest Method: Bisection

First bisection gives a new, better x

Next discard redundant bound, here xmin

Replace it by xm which becomes `new' xmin

Repeat

Bisection Algorithm

1.
Specify bounds xmin and xmax
2.
Evaluate fl=f(xmin) and fu=f(xmax)
3.
Check that sign $f_l \neq $ sign fu. Abandon with error message if not so.
4.
Start iteration.
5.
Let xm = (xmin+xmax)/2
6.
Evaluate fm = f(xm)
7.
If sign fm = sign fl then make xmin = xm and fl=fm
8.
Else make xmax = xm and fu = fm
9.
If $ f_m \approx 0 $ then stop
10.
Repeat from step 4

Accuracy:

\begin{displaymath}r = \frac{1}{2^n} \end{displaymath}

3.3.3 Secant Method

Method 2 - Secant

Same algorithm as bisection, but a different way of choosing the new value.

Secant Update

If f(x) is nearly linear between xmin and xmax, then a straight line between the point (xmin , fl) and (xmax , fu) will cross the x-axis at xs , close to the true solution of f(x)=0.

From similar triangles A and B:

\begin{displaymath}\frac{x_{max}-x_s}{-f_u} = \frac{x_s-x_{min}}{f_l} \end{displaymath}

\begin{displaymath}x_s = \frac{f_u x_{min} - f_l x_{max}}{f_u - f_l}
\end{displaymath}

New step 4:
1.
Let xm= (fu xmin - fl xmax)/(fu - fl)

3.3.4 Newton's Method

Method 3 - Newton-Raphson

Bisection uses only sign,

Secant uses value,

Newton also uses slope.

Newton Update


\begin{displaymath}\frac{f(x_0)}{x_0 - x_1} = S = f'(x_0)
\end{displaymath}

Hence:

\begin{displaymath}x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}
\end{displaymath}

Possible problems:

Numerical Differentiation

By perturbing x by a small amount $\delta x$


\begin{displaymath}f'(x) = \frac{df}{dx} \approx \frac{f(x+\delta x) - f(x)}{\delta x}
\end{displaymath}

Then:

   \begin{displaymath}x_1 = x_0 - \frac{f(x_0) \delta x}{f(x+\delta x) - f(x)}
\end{displaymath}

<

NB, if we set:

x0 = xmin


\begin{displaymath}x_0+\delta x = x_{max}\end{displaymath}

\begin{displaymath}\delta x = x_{max} - x_{min}\end{displaymath}

...this gets back to the secant formula.

A Method which Usually Doesn't Work

Methods involving rearrangement of:
f(x)=0

to the form:
   \begin{displaymath}x = \phi(x)
\end{displaymath}

E.g. consider:

x3 +b x + c = 0

By alternative rearrangements:
\begin{displaymath}x = - ( b x + c) ^{\frac{1}{3}}
\end{displaymath}

\begin{displaymath}x=-\frac{(x^3 + c)}{b}
\end{displaymath}

Try with:
x3 - 0.01 x + 3 = 0

x3 -100 x - 1 =0

First equation can be solved by first rearrangement but not second. Second equation solves by second method but not first.

Sufficient condition for convergence is:

\begin{displaymath}\vert\frac{d\phi(x)}{dx}\vert \leq 1 \end{displaymath}

at the solution

In general this class of repeated substitution method cannot be guaranteed to work. An exception is a situation where the physics of the system ensures that the above condition is always met. One example of this is in solving process recycle problems.

A Chemical Process with Recycle


Consider the recycle of a reactant.

If c is the fractional conversion in the reactor and s the fractional recovery of the recycled reactant in the separator, then the classic procedure of `guessing a recycle stream' is equivalent to solving for x , the amount of reactant entering the reactor:

x = f + r

Here r=s(1-c)x) so:

x = f = s(1-c) x

Thus$\phi$ is the RHS expression, i.e.:

\begin{displaymath}\phi \equiv s(1-c) x \end{displaymath}

And:

\begin{displaymath}\frac{d\phi(x)}{dx} = c(1-c) \end{displaymath}

Since c and s are both fractions, this must be less than unity.

Repeated substitution methods should be avoided unless it is certain that this condition is fulfilled. Even when it is, other methods are usually better.


Back to 3.3 Iterative Solution of Single Algebraic Equations

Back to Section 3 index.