196
7 Solving Nonlinear Algebraic Equations
by the two first term in a Taylor series expansion around x i :
F (x i+1 ) ≈ F (x i ) + ∇F (x i )(x i+1 − x i ) .
The next terms in the expansions are omitted here and of size ||x i+1 − x i || 2 , which
are assumed to be small compared with the two terms above.
The expression ∇F is the matrix of all the partial derivatives of F . Component
(i, j ) in ∇F is
∂F i
∂x j
.
For example, in our 2 × 2 system (7.10) and (7.11) we can use SymPy to compute
the Jacobian:
In [1]: from sympy import *
In [2]: x0, x1 = symbols(’x0 x1’)
In [3]: F0 = x0**2 - x1 + x0*cos(pi*x0)
In [4]: F1 = x0*x1 + exp(-x1) - x0**(-1)
In [5]: diff(F0, x0)
Out[5]: -pi*x0*sin(pi*x0) + 2*x0 + cos(pi*x0)
In [6]: diff(F0, x1)
Out[6]: -1
In [7]: diff(F1, x0)
Out[7]: x1 + x0**(-2)
In [8]: diff(F1, x1)
Out[8]: x0 - exp(-x1)
We can then write
∇F =
∂F 0
∂x 0
∂F 0
∂x 1
∂F 1
∂x 0
∂F 1
∂x 1
=
2x 0 + cos(πx 0 ) − πx 0 sin(πx 0 ) −1
x 1 + x
−2
0
x 0 − e −x 1
The matrix ∇F is called the Jacobian of F and often denoted by J .
7.6.3 Newton’s Method
The idea of Newton’s method is that we have some approximation x i to the root and
seek a new (and hopefully better) approximation x i+1 by approximating F (x i+1 ) by
a linear function and solve the corresponding linear system of algebraic equations.
We approximate the nonlinear problem F (x i+1 ) = 0 by the linear problem
F (x i ) + J (x i )(x i+1 − x i ) = 0,
(7.12)