Computational Techniques

Module 4: Nonlinear Algebraic Equations

Dr. Niket Kaisare

Department of Chemical Engineering
Indian Institute of Technology - Madras
A Simple Example
 To solve the following equation:
2.0  x  ln( x)  0

The solution is the

location where the curve
intersects the X
X-axis
axis

0.1586 3.1462 It is possible to have

multiple
l i l solutions
l i (fi
(finite)
i )
to the problem
2.0 - x + ln(x)
( )
General Setup
 Let x be a variable of interest. The objective is
to find the value of x which satisfies the
following nonlinear equation
f ( x)  0
 General Setup
 Let x be a variable of interest. The objective is
to find the value of x which satisfies the
following nonlinear equation
f ( x)  0

Example: Catalytic reaction in a CSTR with L-H Kinetics

cA0
C A0 C kC A
 A 0
  
1  KC A  2

 
f C A 
cA
Extension to Multi
Multi--Variables
 Let x1, x2, …, xn be n variables, which are
described by the following coupled equations:
f1  x1, x2 ,, xn   0
f 2  x1, x2 ,, xn   0

f n  x1, x2 ,, xn   0

 x1   f1 (x) 
x   f ( x) 
x   2 f x    2  f x   0
   
x   f (x)
 n  n 
 Example: Adiabatic CSTR
T0, CA0
C A0

CA
 k0e
E
RT  1.65
CA  0
 
f1 C A ,T 
T,, CA

T0 T  H   E RT  1.65 
  k0e CA 0
  c p  

f 2 C A ,T 
Outline of Non
Non--Linear Equation
 Bracketingg Methods
◦ Bisection method
◦ Regula
g Falsi
 Open Methods
◦ Secant method
◦ Fixed-point iteration
◦ Newton-Raphson
 Modifications and Extensions
 Root-Finding
R t Fi di
 Computational Techniques
Summary of Module 4

Dr. Niket Kaisare

Department of Chemical Engineering
Indian Institute of Technology - Madras
General Strategy of Solution

Start with initial guess(es)

Using a chosen strategy,

move in the
h direction
d off
the solution

Verify if stopping criterion

2.0 - x + ln(x) is satisfied

Yes
Solution!
 Summaryy (1
( of 2))
# initial x(i+1) = Order
Method
guesses Conv.
2; x (l )  x ( r ) 1
Bisection
f (l )  f ( r )  0 2
2; (l ) (l ) x (l )
 x (r ) 1 to 2
Regula Falsi x  f
f (l )  f ( r )  0 f (l )  f ( r )
Fixed Point
Iteration
1
 
g x (i )
1

2 (i ) (i ) x
(i )
 x (i 1) 1 to 2
Secant x f
f (i )  f (i 1)
Newton- 1 (i ) 
f x (i )  2
f x (i ) 
x 
Raphson
 Summaryy (2
( of 2))
Issues / Important Multi-
Method Stability
Considerations Variable
Guaranteed Single variable only. No
Bisection
f(x) change sign at x
Guaranteed – – do – – No
Regula Falsi

Fixed
Fi dP Point
i Not
N Limited
Li i d applicability
li bili Y
Yes
Iteration guaranteed due to stability. (easy)
Not Versatile and fast. Yes
Secant (moderate)
guaranteed
Not Most popular & fast. Yes
Newton-
N guaranteed x(1) be not far from x (moderate)
Raphson
 
f  x (i )  0
Multi--Variable Examples:
Multi
Fi d P
Fixed Point
i IIteration
i
 Extension is straightforward
For all j = 1 to n,

x (ji 1)  f j x1(i ) , x2(i ) , , xn(i ) 

 
x (i 1)  f x (i )

 Sufficient condition for convergence

f j f j f j
  1
x1 x2 xn
Multi--Variable Examples:
Multi
Newton--Raphson
Newton

 
x (i 1)  x (i )  J 1.f x (i )

 f1 f1 f
 x1 
 x1 x2 n
 f 2 f 2 f 2 
 x
J  f   x1 x2 n
     
 f n f n f n 
 x1 x2
 x  (i )
n x

Quadratic Rate of Convergence

Improvements developed for speed and performance

Newton--Raphson
Newton
Ralston’s modifications for multiple roots

If there are m roots:

(i 1) (i )  
f x (i )
f x (i ) 
x x m

Improved Newton
Newton-Raphson
Raphson
Roots of f(x) are the same as: h( x)  f  x 
f  x 

(i 1) (i )   
f x (i ) f  x (i )
f x (i )  f x (i )  f x (i )  f x (i ) 
x x 
Newton--Raphson
Newton
Modifications to improve stability
Line-Search :
“Line-Search”:
 
x (i 1)  x (i )  .J 1f x (i )

0    1 is like under-relaxation parameter

Levenberg-Marquardt modification
Motivation: Root of f ((x)) is a minimum of [f ((x))]2

x (i 1)
x (i )

 J J  I
T

1 T
 
J f x (i )
Root Finding
 Aim is to find all roots of a polynomial
p y

 e all solutions to f (x) = 0

ii.e.,
where f is a polynomial function

-1 1 2

x3  2 x 2  x  2
Root Finding
-1 1 2

 Bairstow’s method
2
a0  a1x  a2 x    an x n x3  2 x 2  x  2

b0 b1xb2x2 bn2 xn2 x2

 px  q   c1x  c0 
    
Pn  2 Q R

Pn  QPn  2  R Q is a factor of Pn if R = 0
Additional Reading
 Gupta S.K. (1995), Numerical Methods for Engineers, New
Age International

 Chapra S.C. and Canale R.P. (2006), Numerical Methods

for Engineers, 5th Ed., McGraw Hill

 Press W.H., Teukolskyy S.A., et al. ((2007),

)
Numerical Recipes:The Art of Scientific Computing,
Cambridge University Press, 3rd Edition.

 Online version at the Numerical Recipes website:

http://www.nr.com/