Algebraic Equations

The following are all algebraic equations.

x - 3 = 5

(1)

sin 3x = y cos x

(2)

a x² + b x + c = 0

(3)

(1) is linear in x
(2) is nonlinear in x because of its appearance in the trigonometric functions
(2) is however linear in y
(3) is nonlinear in x, but linear in a, b and c

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 x_min

Replace it by x_m which becomes `new' x_min

Repeat

Bisection Algorithm

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

Accuracy:

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

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 x_min and x_max, then a straight line between the point (x_min , f_l) and (x_max , f_u) will cross the x-axis at x_s , 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 x_m= (f_u x_min - f_l x_max)/(f_u - f_l)

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:

Not bounded
Needs reasonable starting guess
Must differentiate

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:

x₀ = x_min

$\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:

x³ +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:

x³ - 0.01 x + 3 = 0

x³ -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.

Algebraic Equations

3.3.2 Bisection Method

3.3.3.Secant Method

3.3.4 Newton's Method

x0 = xmin

x₀ = x_min