The Newton-Raphson method for solving equations

-----------------------------------------------
By Gilberto E. Urroz, Ph.D., P.E.
January 2010

1 - The Newton-Raphson for solving single equations:

---------------------------------------------------
The Newton-Raphson method used for solving an equation of the form

f x 0
requires the knowledge of the derivative f'(x). This can be easily
accomplished in SMath Studio using the "Derivative" option in the
"Functions" palette:
d
fp x f x
dx
Given an initial guess of the solution, x x , the solution can
0
be approximated by the iterative calculation:

f x
k
x x
k 1 k f' x
k
for k 0 ,1, ...

The iteration continues until either the solution converges, i.e.,

f x ε , or a certain large number of iterations are performed

k 1
without convergence, i.e., k n
max

2
Example: Solve the equation: x 2 x 5 0
--------

Solution: A graph of the function can help us find where the

--------- solutions may be located:

2
Define the function: f x x 2 x 5

Produce a graph of f(x):

y
24

16

0 x

-8

-4 -2 0 2 4 6
f x

-1-
 The graph shows solutions near x = -2 and x = 3. We can
implement the solution using the Newton-Raphson method
as follows:
d
fp x f x fp x 2 1 x
dx
6
Parameters of the solution are: ε 1.0 10 nmax 100
First solution:
Starting with a guess of xG 2.5
we find a solution by using the following iterative procedure:
k 0

while k nmax f xG ε
f xG
xGp1 xG
fp xG
k k 1
xG xGp1

xG 1.4495 This is the solution found

k 4 After this many iterations
11
f xG 2.1427 10 The function at the solution point

Second solution:
Starting with a guess of xG 4.2
we find a solution by using the following iterative procedure:
k 0

while k nmax f xG ε
f xG
xGp1 xG
fp xG
k k 1
xG xGp1

xG 3.4495 This is the solution found

k 4 After this many iterations
13
f xG 2.2529 10 The function at the solution point

2 - Solution to equations with function "solve":

-----------------------------------------------
Most equations can be solved using function "solve" in SMath
Studio. For the present case we'll have:

1.4495
solve f x 0, x
3.4495

Alternatively, you can use:

2 1.4495
solve x 2 x 5 0, x
3.4495

-2-
 3 - The Newton-Raphson method for a system of equations:
-------------------------------------------------------

A system of n equations in n unknowns can be represented as:

f1 x ,x .. x 0
1 2 n

f2 x ,x
.. x 0
12 n
...
fn x , x .. x 0
1 2 n

or simply, f x 0 , with

f1 x ,x .. x
1 2 n f1 x
f2 x ,x .. x f2 x
f x 1 2 n
. .
fn x ,x .. x fn x
1 2 n

The variable x is defined as the vector:

x
1
x
x 2
.
x
n

We can provide an initial guess for the solution, x , and

0
proceed with an iterative process defined by the formula:

1
x x J x f x
k 1 k k k

J x
for k 0 ,1,... In this formula, k , is the Jacobian
matrix of the function defined as [to be 100% correct the
derivatives in this matrix should be partial derivatives]:

dy dy dy
1 1 1
.
dx dx dx
1 2 n
dy dy dy
2 2 2
.
J x dx dx dx
k 1 2 n
. . . .
dy dy dy
n n n
.
dx dx dx
1 2 n

Example:
--------
How to calculate the Jacobian matrix of a system of three
equations. Given the system of three equations:

-3-
 x x x 6 This is obvious, but could
1 2 3
useful for larger functions:
x x x 6
f x 1 2 3 n length f x
2 2 3
x x x 14 n 3
1 2 3

The following nested "for" loops calculate the elements of

the jacobian matrix as the elements "jac[i,j]":

for i 1 .. n
for j 1 .. n
d
jac f x
ij dx i
j

The following definition creates the function "Jacobi" that

represents the Jacobian matrix of the function f(x) shown
earlier:
Jacobi x jac
1 1 1
x x x x x x
Jacobi x 2 3 1 3 1 2
2 x 2 x 2
1 2 3 x
3
-------------------------------------------------------------------
Note: This approach for calculating the Jacobian matrix of a vector
function was made available by Radovan Omorjan (omorr) in the SMath
Studio wiki page: http://smath.info/wiki/diff.ashx
------------------------------------------------------------------
Generalized Newton-Raphson method for solving a system of equations:
-------------------------------------------------------------------
20
The parameters of the solution are: nmax 100 ε 1 10

5
An initial guess is: xG 1
4
The iterative process for the solution is expressed as:

k 0

while k nmax max f xG ε

1
xGp1 xG Jacobi xG f xG
k k 1
xG xGp1

A solution is found after these many iterations:

k 15

Here's a solution: And the function at that point:

3 14
1.0161 10
xG 2
f xG 14
1 3.9933 10
14
2.1316 10

-4-
----------------------------------------------------------------
Note: The function representing the system of equations solved
above, namely,
x x x 6
1 2 3
x x x 6
f x 1 2 3
2 2 3
x x x 14
1 2 3

can be thought of representing the system of equations:

x y z 6 0 x y z 6
x y z 6 0 or x y z 6
2 2 2 2 2 2
x y z 14 0 x y z 14

with the variable substitution: x x, x y , and x z.

1 2 3
----------------------------------------------------------------

-5-