Non-linear equations and systems

In the solution of linear equations and systems, f(x) = 0, we had the choice of using either direct methods or iterative processes. A direct method in that setting was simply the application of an exact formula involving only the four basic operations: addition, subtraction, multiplication, and division. The issues with this method arise when cancellation occurs, mainly whenever sums and subtractions are present. Iterative methods, rather than computing a solution in a finite number of operations, calculate closer and closer approximations to the said solution, improving the accuracy with each step.

In the case of nonlinear equations, direct methods are seldom a good idea. Even when a formula is available, the presence of nonbasic operations leads to uncomfortable rounding errors. Let's see this using a very basic example.

Consider the quadratic equation ax2 + bx + c = 0, with a = 10–10, b = –(1010 + 1)/1010, and c = 1. These are the coefficients of the expanded version of the polynomial p(x) = 10–10(x–1)(x–1010), with the obvious roots x = 1 and x = 1010. Notice the behavior of the quadratic formula in the following command:

In [1]: import numpy as np
In [2]: a, b, c = 1.0e-10, -(1.0e10 + 1.)/1.0e10, 1.
In [3]: (-b - np.sqrt(b**2 - 4*a*c))/(2*a)
Out[3]: 1.00000000082740371

A notable rounding error due to cancellation has spread. It is possible to fix the situation, in this case, by multiplying the numerator and denominator of this formula by the conjugate of its denominator, and using the resulting formula instead:

In [4]: 2*c / (-b + np.sqrt(b**2 - 4*a*c))
Out[4]: 1.0

Even the algebraic solvers coded in the sympy libraries share this defect, as the following example shows:

Tip

The sympy libraries have a set of algebraic solvers, and all of them are accessed from the common routine solve. Currently, this method solves univariate polynomials, transcendental equations, and a piecewise combination of them. It also solves systems of linear and polynomial equations.

For more information, refer to the official documentation for sympy at http://docs.sympy.org/dev/modules/solvers/solvers.html.

In [5]: from sympy import symbols, solve
In [6]: x = symbols('x', real=True)
In [7]: solve(a*x**2 + b*x + c)
Out[7]: [1.00000000000000, 9999999999.00000]

To avoid having to second-guess the accuracy of our solutions or fine-tune each possible formula that solves a nonlinear equation, we can always adopt iterative processes to achieve arbitrarily close approximations.

Iterative methods for univariate functions

Iterative processes for scalar functions can be divided in to three categories:

  • Bracketing methods, where the algorithms track the endpoints of an interval containing a root. We have the following algorithms:
    • Bisection Method
    • Regula falsi (false position method)
  • Secant methods, with the following algorithms:
    • The secant method
    • The Newton-Raphson method
    • The interpolation method
    • The inverse interpolation method
    • The fixed-point iteration method
  • Brent method, which is a combination of the bisection, secant, and inverse interpolation methods.

Now, let's explore the methods included in the SciPy stack.

Bracketing methods

The most basic algorithm is the method of bisection—given a continuous function f(x) in the interval [a, b] satisfying f(a)f(b) < 0. This method constructs a sequence of approximations by bisecting intervals and keeping the subinterval where the solution is present. It is a slow process (linear convergence), but it never fails to converge to a solution. In the module scipy.optimize, we have one implementation, the routine bisect.

Let's explore this method first with our running example. Since the signs of p(0) and p(2) are different, there must be a root in the interval [0, 2]:

In [8]: from scipy.optimize import bisect
In [9]: p = np.poly1d([a,b,c])
In [10]: bisect(p, 0, 2)
Out[10]: 1.0

Tip

Note that we chose to represent p(x) with a numpy.poly1d class. Whenever we need to work with polynomials, the optimal way to handle them in SciPy is by means of this class. This ensures evaluation of the polynomials using a Horner scheme, which provides faster computations than with any other lambda representation.

For polynomials with a very high degree, however, the Horner scheme might be inaccurate due to rounding errors from cancellation. Caution must be used in those cases.

One issue with the method of bisection is that it is very sensitive to the choice of initial endpoints, but in general, the quality of the computed solutions can be improved by requesting proper tolerances, as shown in the following example:

In [11]: bisect(p, -1, 2)
Out[11]: 1.0000000000002274
In [12]: bisect(p, -1, 2, xtol=1e-15)
Out[12]: 0.9999999999999996
In [13]: bisect(p, -1, 2, xtol=1e-15, rtol=1e-15)
Out[13]: 1.0000000000000009

More advanced sets of techniques are based upon regula falsi. Given an interval [a, b] that contains a root of the function f(x), compute the line that goes through the points (a, f(a)) and (b, f(b)). This line intersects the x axis inside [a, b]. We use this point for the next bracketing step. In the module scipy.optimize, we have the routine ridder (an improvement of regula falsi based on an algorithm developed by C. Ridders), which presents quadratic convergence.

To illustrate the difference in behavior between any solvers, we might use the optional output RootResult of each algorithm, as the following session shows:

In [14]: soln, info = bisect(p, -1, 2, full_output=True)
In [15]: print "Iterations: {0}".format(info.iterations)
Iterations: 42
In [16]: print "Function calls: {0}".format(info.function_calls)
Function calls: 44
In [17]: from scipy.optimize import ridder
In [18]: soln, info = ridder(p, -1, 2, full_output=True)
In [19]: print "Solution: {0}".format(info.root)
Solution: 1.0
In [20]: print "Iterations: {0}".format(info.iterations)
Iterations: 1
In [21]: print "Function calls: {0}".format(info.function_calls)
Function calls: 4

Secant methods

The next step of techniques is based on the secant method and its limit cases. The secant method is very similar to regula falsi computationally. Instead of bracketing the root, we start with any two initial guesses x0, x1, and compute the intersection x2 of the line through (x0, f(x0)) and (x1, f(x1)). The next step repeats the same operation on the guesses x1, x2 to compute a new approximation x3, and the process is repeated until a satisfactory approximation to the root is attained.

Improvements on this method can be obtained by employing smarter choices than the secant line to search for intersections with the x axis. The Newton-Raphson method uses a first derivative of f(x) to compute a better intersecting line. The Halley method employs both first and second derivatives of f(x) to compute the intersection of an arc of parabola with the x axis.

The secant method has an order of convergence of approximately 1.61803, while Newton-Raphson is quadratic and Halley is cubic.

For scalar functions, all three methods (secant, Newton, Halley) can be accessed with the common routine newton in the module scipy.optimize. The obligatory parameters for the routine are the function f(x), together with an initial guess x0.

Let's work on a more complex example involving the equation sin(x)/x = 0:

In [22]: from scipy.optimize import newton; 
   ....: from sympy import sin as Sin, pi, diff, lambdify
In [23]: def f(t): return np.sin(t)/t
In [24]: f0 = Sin(x)/x
In [25]: f1prime = lambdify(x, diff(f0, x), "numpy"); 
   ....: f2prime = lambdify(x, diff(f0, x, 2), "numpy")
In [26]: solve(f0, x)
Out[26]: [pi]
In [27]: newton(f, 1)                            # pure secant
Out[27]: 3.1415926535897931
In [28]: newton(f, 1, fprime=f1prime)            # Newton-Raphson
Out[28]: 3.1415926535897931
In [29]: newton(f, 1, fprime=f1prime, fprime2=f2prime)   # Halley
Out[29]: 3.1415926535897931

An issue with any of these three methods is that convergence is not always guaranteed. The routine newton has a mechanism that prevents the algorithm from going over a certain number of steps and, when this happens, it raises a runtime error that informs us of that situation. A classical example of bad behavior in the Newton-Raphson method and the Halley method occurs with the equation x20 = 1 (which has the obvious roots x = 1 and x = –1), if our initial guess happens to be x = 0.5:

In [30]: solve(x**20 - 1, x)
Out[30]:
[-1,
 1,
 -sqrt(-sqrt(5)/8 + 5/8) + I/4 + sqrt(5)*I/4,
 -sqrt(-sqrt(5)/8 + 5/8) - sqrt(5)*I/4 - I/4,
 sqrt(-sqrt(5)/8 + 5/8) + I/4 + sqrt(5)*I/4,
 sqrt(-sqrt(5)/8 + 5/8) - sqrt(5)*I/4 - I/4,
 -sqrt(sqrt(5)/8 + 5/8) - I/4 + sqrt(5)*I/4,
 -sqrt(sqrt(5)/8 + 5/8) - sqrt(5)*I/4 + I/4,
 sqrt(sqrt(5)/8 + 5/8) - I/4 + sqrt(5)*I/4,
 sqrt(sqrt(5)/8 + 5/8) - sqrt(5)*I/4 + I/4]
In [31]: coeffs = np.zeros(21); 
   ....: coeffs[0] = 1; 
   ....: coeffs[20] = -1; 
   ....: p = np.poly1d(coeffs); 
   ....: p1prime = p.deriv(m=1); 
   ....: p2prime = p.deriv(m=2)
In [32]: newton(p, 0.5, fprime=p1prime)
RuntimeError: Failed to converge after 50 iterations, value is 2123.26621974
In [33]: newton(p, 0.5, fprime=p1prime, fprime2=p2prime)
RuntimeError: Failed to converge after 50 iterations, value is 2.65963902147

There is yet another technique to approximate solutions to nonlinear scalar equations iteratively, via fixed point iterations. This is very convenient when our equations can be written in the form x = g(x), for example, since the solution to the equation will be a fixed point of the function g.

In general, for any given equation f(x) = 0, there is always a convenient way to rewrite it as a fixed point problem x = g(x). The standard way would be to write g(x) = x + f(x), of course, but this does not necessarily provide the best setting. There are many other possibilities out there.

To calculate iteration to a fixed point, we have the routine fixed_point in the module scipy.optimize. This implementation is based in an algorithm by Steffensen, using a smart convergence acceleration by Aitken:

In [34]: def g(t): return np.sin(t)/t + t
In [35]: from scipy.optimize import fixed_point
In [36]: fixed_point(g, 1)
Out[36]: 3.1415926535897913

Brent method

Developed by Brent, Dekker, and van Wijngaarten, an even more advanced (and faster) algorithm arises when combining the secant and bisection methods with inverse interpolation. In the module scipy.optimize, we have two variations of this algorithm: brentq (using inverse quadratic interpolation) and brenth (using inverse hyperbolic interpolation). They both start as a bracketing method and require, as input, an interval that contains a root of the function f(x).

Let's compare these two variations of the Brent method to the bracketing methods, with the equation sin(x)/x = 0:

In [37]: soln, info = bisect(f, 1, 5, full_output=True); 
   ....: list1 = ['bisect', info.root, info.iterations,
   ....:           info.function_calls]
In [38]: soln, info = ridder(f, 1, 5, full_output=True); 
   ....: list2 = ['ridder', info.root, info.iterations,
   ....:          info.function_calls]
In [39]: from scipy.optimize import brentq, brenth
In [40]: soln, info = brentq(f, 1, 5, full_output=True); 
   ....: list3 = ['brentq', info.root, info.iterations,
   ....:          info.function_calls]
In [41]: soln, info = brenth(f, 1, 5, full_output=True); 
   ....: list4 = ['brenth', info.root, info.iterations,
   ....:          info.function_calls]
In [42]: for item in [list1, list2, list3, list4]:
   ....:     print "{0}: x={1}. Iterations: {2}. Calls: {3}".format(*item)
   ....:
bisect: x=3.14159265359. Iterations: 42. Calls: 44
ridder: x=3.14159265359. Iterations: 5. Calls: 12
brentq: x=3.14159265359. Iterations: 10. Calls: 11
brenth: x=3.14159265359. Iterations: 10. Calls: 11

Systems of nonlinear equations

In this section, we aim to find solutions of systems of scalar or multivariate functions, F(X) = 0, where F represents a finite number N of functions, each of them accepting as a variable a vector X of dimension N.

In the case of systems of algebraic or transcendental equations, symbolic manipulation is a possibility. When the dimensions are too large, it is nonetheless very impractical. A few examples to illustrate this point should suffice.

Let's start with a very easy case that can be readily solved by elimination: the intersection of a circle (x2 + y2 = 16) with a parabola (x2 – 2y = 8):

In [1]: import numpy as np; 
   ...: from sympy import symbols, solve  
In [2]: x,y = symbols('x y', real=True)
In [3]: solutions = solve([x**2 + y**2 - 16, x**2 - 2*y -8])
In [4]: for item in solutions:
   ...:     print '({0}, {1})'.format(item[x], item[y])
   ...:
(0, -4)
(0, -4)
(-2*sqrt(3), 2)
(2*sqrt(3), 2)

Now, let's present a harder example. One of the equations is fractional and the other is polynomial: 1/x4 + 6/y4 = 6, 2y4 + 12x4 = 12x4y4:

In [5]: solve([1/x**4 + 6/y**4 - 6, 2*y**4 + 12*x**4 - 12*x**4*y**4])
Out[5]: []

No solutions? How about (1, (6/5))1/4?

In [5]: x0, y0 = 1., (6/5.)**(1/4.)
In [6]: np.isclose(1/x0**4 + 6/y0**4, 6)
Out[6]: True
In [7]: np.isclose(2*y0**4 + 12*x0**4, 12*x0**4*y0**4)
Out[7]: True

Only iterative methods can guarantee accurate and fast solutions without exhausting our computational resources. Let's explore some techniques in this direction.

Tip

Going from one to several variables brings many computational challenges. Some of the techniques that arise in this context are generalizations from the methods explained for scalar functions in the previous section, but there are many other strategies that exploit the richer structures of spaces with large dimensions. As in the case of solutions of linear equations employing iterative methods, the command of all these techniques involves learning about very advanced topics such as operators in Functional Analysis, Spectral Theory, Krylov subspaces, and so on. This is far beyond the scope of our book.

For a complete description and analysis of all methods, optimal choices of initial guesses, or the construction of successful preconditioners (when used), refer instead to the book Iterative solutions of nonlinear equations in several variables, by Ortega and Rheinboldt. It was published in 1970 as a Monograph Textbook for Computational Science and Applied Mathematics by Academic Press, and is still among the best available sources for this topic.

For our analysis of systems of nonlinear equations, we will run all our different methods on a particularly challenging example that tries to determine the values of x = [x[0], ..., x[8]], solving the following system of tridiagonal equations:

(3-2*x[0])*x[0]           -2*x[1]                   = -1
        -x(k-1) + (3-2*x[k])*x[k]         -2*x[k+1] = -1,  k=1,...,7
                            -x[7] + (3-2*x[8])*x[8] = -1

We can define such systems as both a purely NumPy function or as a SymPy matrix function (this will help us compute its Jacobian in the future):

In [8]: def f(x):
   ...:     output = [(3-2*x[0])*x[0] - 2*x[1] + 1]
   ...:     for k in range(1,8):
   ...:         output += [-x[k-1] + (3-2*x[k])*x[k] - 2*x[k+1] + 1]
   ...:     output += [-x[7] + (3-2*x[8])*x[8] + 1]
   ...:     return output
   ...:
In [9]: from sympy import Matrix, var
In [10]: var('x:9'); 
   ....: X = [x0, x1, x2, x3, x4, x5, x6, x7, x8]
In [11]: F  = Matrix(f(X)); 
   ....: F
Out[11]:
Matrix([
[      x0*(-2*x0 + 3) - 2*x1 + 1],
[-x0 + x1*(-2*x1 + 3) - 2*x2 + 1],
[-x1 + x2*(-2*x2 + 3) - 2*x3 + 1],
[-x2 + x3*(-2*x3 + 3) - 2*x4 + 1],
[-x3 + x4*(-2*x4 + 3) - 2*x5 + 1],
[-x4 + x5*(-2*x5 + 3) - 2*x6 + 1],
[-x5 + x6*(-2*x6 + 3) - 2*x7 + 1],
[-x6 + x7*(-2*x7 + 3) - 2*x8 + 1],
[       -x7 + x8*(-2*x8 + 3) + 1]])

All available iterative solvers could be called with the common routine root in the module scipy.optimize. The routine requires, as obligatory parameters, a left-hand side expression of the system F(x) = 0 and an initial guess. To access the different methods, we include the parameter method, which can be set to any of the following options:

  • linearmixing: For linear mixing, a very simple iterative inexact-Newton method that uses a scalar approximation to the Jacobian.
  • diagbroyden: For diagonal Broyden method, another simple iterative inexact-Newton method that uses a diagonal Broyden approximation to the Jacobian.
  • excitingmixing: For exciting mixing, one more simple inexact-Newton method, that uses a tuned diagonal approximation to the Jacobian.
  • broyden1: The good Broyden method is a powerful inexact-Newton method using Broyden's first Jacobian approximation.
  • hybr: Powell's hybrid method, the most versatile and robust solver available in the SciPy stack, although it is not efficient for systems with large dimensions.
  • broyden2: The bad Broyden method, similar to the good Broyden method, is another inexact-Newton method that uses Broyden's second Jacobian approximation. It is more apt for large-scale systems.
  • krylov: The Newton-Krylov method is another inexact-Newton method based on Krylov approximations to the inverse of the Jacobian. It is a top pick for systems with large dimensions.
  • anderson: This is an extended version of the Anderson mixing method. Together with Newton-Krylov and the bad Broyden method, this is the other weapon of choice for dealing with large scale systems of nonlinear equations.

The implementations are very clever. Except in the case of Powell's hybrid method, the rest uses the same code employing different expressions for the (approximations to the) Jacobian of f(x), Jacf(x). To this effect, there is a python class, Jacobian, stored in the module scipy.optimize.nonlin, with the following class attributes:

  • .solve(v): This returns, for a suitable left-hand-side vector v, the expression Jacf(x)^(-1)*v
  • .update(x, F): This updates the object to x, with residual F(x), to guarantee evaluation of the Jacobian at the right location on each step
  • .matvec(v): This returns, for a suitable vector v, the product Jacf(x)*v
  • .rmatvec(v): This returns, for a suitable vector v, the product Jacf(x).H*v
  • .rsolve(v): This returns, for a suitable vector v, the product (Jacf(x).H)^(-1)*v
  • .matmat(M): For a dense matrix M with the appropriate dimensions, this returns the matrix product Jacf(x).H*M
  • .todense(): This forms the dense Jacobian matrix, if ever needed

We seldom need to worry about creating objects in this class. The routine root accepts as Jacobians any ndarray, sparse matrix, LinearOperator, or even callables whose output is any of the previous. It transforms them internally to a Jacobian class with the method asjacobian. This method is also hosted in the submodule scipy.optimize.nonlin.

Simple iterative solvers

We have three very simple inexact-Newton solvers in the SciPy stack which, like the secant method for scalar equations, substitute the Jacobian of a multivariate function with a suitable approximation. These are the methods of linear and exciting mixing, and the diagonal Broyden method. They are fast, but not always reliable—use them at your own risk!

To analyze, in depth, the speed and behavior of these solvers, we will use a callback function to store the steps of convergence. First, the method of linear mixing:

In [12]: from scipy.optimize import root
In [13]: root(f, np.zeros(9), method='linearmixing')
Out[13]:
  status: 2
 success: False
     fun: array([  9.73976997e+00,  -1.66208587e+02,   7.98809260e+00,
        -1.66555288e+01,   6.09078392e+01,  -5.57689008e+03,
         5.72527250e+06,  -2.61478262e+13,   3.15410157e+06])
       x: array([  2.85055795e+00,  -8.21972867e+00,   2.28548187e+00,
        -1.17938653e+00,   4.52499108e+00,  -4.30522840e+01,
         8.68604963e+02,  -3.61578590e+06,   4.81211473e+02])
 message: 'The maximum number of iterations allowed has been reached.'
     nit: 1000

This is not too promising! If we so desire, we can play around with different tolerances, or the maximum number of iterations allowed. Another option that we could change for this algorithm is the method of searching for optimal lines in the approximation of the Jacobian. This helps determine the step size in the direction given by the said approximation. At this point, we only have three choices: armijo (the Armijo-Goldstein condition, the default), wolfe (using Philip Wolfe's inequalities), or None.

All options passed to any method must be done through a Python dictionary, via the parameter options:

In [14]: lm_options = {}; 
   ....: lm_options['line_search'] = 'wolfe'; 
   ....: lm_options['xtol'] = 1e-5; 
   ....: lm_options['maxiter'] = 2000
In [15]: root(f, np.zeros(9), method='linearmixing',
   ....:      options=lm_options)
OverflowError: (34, 'Result too large')

Now, let's try the method of exciting mixing, with the same initial condition:

In [16]: root(f, np.zeros(9), method='excitingmixing')
Out[16]:
  status: 2
 success: False
     fun: array([  1.01316841e+03,  -8.25613756e+05,   4.23367202e+02,
        -7.04594503e+02,   5.53687311e+03,  -2.85535494e+07,
         6.34642518e+06,  -3.11754414e+13,   2.87053285e+06])
       x: array([  1.24211360e+01,  -6.41737121e+02,   1.20299207e+01,
        -1.69891515e+01,   3.26672949e+01,  -3.77759320e+03,
         8.82115576e+02,  -3.94812801e+06,   7.34779049e+02])
 message: 'The maximum number of iterations allowed has been reached.'
     nit: 1000

A similar (lack of) success! The relevant options to fine-tune this method are line_search, the floating-point value alpha (to use -1/alpha as the initial approximation to the Jacobian), and the floating-point value alphamax (so the entries of the diagonal Jacobian are kept in the range [alpha,alphamax]).

Let's try the diagonal Broyden method with the same initial condition:

In [17]: root(f, np.zeros(9), method='diagbroyden')
Out[17]:
  status: 2
 success: False
     fun: array([-4.42907377, -0.87124314, -2.61646043,  0.59009568, -1.34073061,
       -2.06266247, -0.32076522,  0.25120731,  0.0731001 ])
       x: array([ 2.09429178,  1.46991649, -0.06730407,  0.96778603,  0.75367344,
        1.2489588 ,  1.46803463,  0.08282948, -0.24223748])
 message: 'The maximum number of iterations allowed has been reached.'
     nit: 1000

A poor performance from this method too! We could experiment with the options line_search and alpha to try to improve the convergence, if needed.

The Broyden method

The good Broyden method is another inexact Newton method that uses an actual Jacobian in the first iteration, but for subsequent iterations, it employs successive rank-one updates. Let's see if we have more luck with our running example:

In [18]: root(f, np.zeros(9), method='broyden1')
Out[18]:
  status: 2
 success: False
     fun: array([-111.83572901, -938.30236242, -197.71489446, -626.93927637,
       -737.43130888,  -19.87676004, -107.31583876,  -92.32200167,
       -252.26714229])
       x: array([  6.65222472,  22.1441079 ,   9.17971608,  17.78778014,
        19.65632798,   3.43502682,  -6.03665297,   6.94424738,  11.87312669])
 message: 'The maximum number of iterations allowed has been reached.'
     nit: 1000

To fine-tune this algorithm, besides line_search and alpha, we also have control over the method of enforcing rank constraints on successive iterations. We could plainly restrict the rank to be not higher than a given threshold, with the optional integer max_rank. But even better, we could impose a reduction method that depends on other factors. To do so, we employ the option reduce_method.

These are the options:

  • restart: This reduction method drops all matrix columns.
  • simple: Only the oldest matrix column is dropped.
  • svd: Together with the optional integer to_retain, this reduction method keeps only the most significant SVD components (up to the integer to_retain). If the integer max_rank was imposed, a good choice for to_retain is usually max_rank - 2:
    In [19]: b1_options = {}; 
   ....: b1_options['max_rank'] = 4; 
   ....: b1_options['reduce_method'] = 'svd'; 
   ....: b1_options['to_retain'] = 2
In [20]: root(f, np.zeros(9), method='broyden1', options=b1_options)
Out[20]:
  status: 2
 success: False
     fun: array([ -1.22226719e+00,  -6.72508500e-02,  -6.31642766e-03,
        -2.24588204e-04,  -1.70786962e-05,  -4.55208297e-05,
        -4.81332054e-06,   1.42432661e-05,  -1.64421441e-05])
       x: array([ 0.87691697,  1.65752568, -0.16593591, -0.60204322, -0.68244063,
       -0.688356  , -0.66512492, -0.59589812, -0.41638642])
 message: 'The maximum number of iterations allowed has been reached.'
     nit: 1000

Powell's hybrid solver

Among the most successful nonlinear system solvers, we have the hybrid algorithm of Powell, for which there are several Fortran routines named HYBRID** in the library MINPACK. These routines implement several modified versions of the original algorithm.

The scipy routine root, when called with method='hybr', acts as a wrapper to both HYBRID and HYBRIDJ. If an expression for the Jacobian is offered via the optional parameter jac, then root calls HYBRIDJ, otherwise, it calls HYBRID. Instead of an actual Jacobian, HYBRID uses an approximation to this operator constructed by forward differences at the starting point.

Tip

For a complete description and analysis of Powell's hybrid algorithm from his author, refer to the article A Hybrid Method for Nonlinear Equations, published in 1970 in the journal of Numerical Methods for Nonlinear Algebraic Equations.

For implementation details of the Fortran routines HYBRID and HYBRIDJ, refer to Chapter 4 of the MINPACK user guide at http://www.mcs.anl.gov/~more/ANL8074b.pdf.

Let's try again with our elusive example:

In [21]: solution = root(f, np.zeros(9), method='hybr')
In [22]: print solution.message
The solution converged.
In [23]: print "The root is approximately x = {0}".format(solution.x)
The root is approximately x = [-0.57065451 -0.68162834 -0.70173245 -0.70421294 -0.70136905 -0.69186564
 -0.66579201 -0.5960342  -0.41641206]
In [24]: print "At that point, it is f(x) = {0}".format(solution.fun)
At that point, it is f(x) = [ -5.10793630e-11   1.00466080e-10  -1.17738708e-10   1.36598954e-10
  -1.25279342e-10   1.10176535e-10  -2.81137336e-11  -2.43449705e-11
   3.32504024e-11]

It is refreshing to at least obtain a solution, but we can do better. Let's observe the behavior of method='hybr' when a precise Jacobian of f(x) is offered. In our case, this operator can be readily computed both symbolically and numerically, as follows:

In [25]: F.jacobian(X)
Powell's hybrid solver
In [26]: def Jacf(x):
   ....:     output = -2*np.eye(9, k=1) - np.eye(9, k=-1)
   ....:     np.fill_diagonal(output, 3-4*x)
   ....:     return output
   ....:
In [27]: root(f, np.zeros(9), jac=Jacf, method='hybr')
  status: 1
 success: True
     qtf: array([ -1.77182781e-09,   2.37713260e-09,   2.68847440e-09,
        -2.24539710e-09,   1.34460264e-09,   8.25783813e-10,
        -3.43525370e-09,   2.36025536e-09,   1.16245070e-09])
    nfev: 25
       r: array([-5.19829211,  2.91792319,  0.84419323, -0.48483853,  0.53965529,
       -0.10614628,  0.23741206, -0.03622988,  0.52590331, -4.93470836,
        2.81299775,  0.2137127 , -0.96934776,  1.03732374, -0.71440129,
        0.27461859,  0.5399114 ,  5.38440026, -1.62750656, -0.6939511 ,
        0.3319492 , -0.11487171,  1.11300907, -0.65871043,  5.3675704 ,
       -2.2941419 , -0.85326984,  1.56089518, -0.01734885,  0.12503146,
        5.42400229, -1.8356058, -0.64571006,  1.61337203, -0.18691851,
        5.25497284, -2.34515389,  0.34665604,  0.47453522,  4.57813558,
       -2.82915356,  0.98463742,  4.64513056, -1.59583822, -3.76195794])
     fun: array([ -5.10791409e-11,   1.00465636e-10,  -1.17738708e-10,
         1.36598732e-10,  -1.25278898e-10,   1.10176535e-10,
        -2.81135115e-11,  -2.43454146e-11,   3.32505135e-11])
       x: array([-0.57065451, -0.68162834, -0.70173245, -0.70421294, -0.70136905,
       -0.69186564, -0.66579201, -0.5960342 , -0.41641206])
 message: 'The solution converged.'
    fjac: array([[-0.96956077,  0.19053436,  0.06633131, -0.12548354,  0.00592579,
         0.0356269 ,  0.00473293, -0.0435999 ,  0.01657895],
       [-0.16124306, -0.95068272,  0.1340795 , -0.05374361, -0.08570706,
         0.18508814, -0.04624209, -0.05739585,  0.04797319],
       [ 0.08519719,  0.11476118,  0.97782789, -0.0281114 , -0.08494929,
        -0.05753056, -0.02702655,  0.09769926, -0.04280136],
       [-0.13529817, -0.0388138 ,  0.03067186,  0.97292228, -0.12168962,
        -0.10168782,  0.0762693 ,  0.0095415 ,  0.04015656],
       [-0.03172212, -0.09996098,  0.07982495,  0.10429531,  0.96154001,
        -0.12901939, -0.13390792,  0.10972049,  0.02401791],
       [ 0.05544828,  0.17833604,  0.03912402,  0.1374237 ,  0.09225721,
         0.93276861, -0.23865212, -0.00446867,  0.09571999],
       [ 0.03507942,  0.00518419,  0.07516435, -0.0317367 ,  0.17368453,
         0.20035625,  0.9245396 , -0.20296261,  0.16065313],
       [-0.05145929, -0.0488773 , -0.08274238, -0.02933344, -0.06240777,
         0.09193555,  0.21912852,  0.96156966, -0.04770545],
       [-0.02071235, -0.03178967, -0.01166247,  0.04865223,  0.05884561,
         0.12459889,  0.11668282, -0.08544005, -0.97783168]])
    njev: 2

Observe the clear improvement—we have arrived at the same root, but only in 25 iterations. It was necessary to evaluate the Jacobian only twice.

Large-scale solvers

For large scale systems, the hybrid method is very inefficient, since the strength of the method relies on the internal computation of the inverse of a dense Jacobian matrix. In this setting, we prefer to use more robust inexact-Newton methods.

One of these is the bad Broyden method (broyden2). Anderson mixing (anderson) is also a reliable possibility. However, the most successful is, without a doubt, the Newton-Krylov method (krylov):

In [28]: root(f, np.zeros(9), method='krylov')
Out[28]:
  status: 1
 success: True
     fun: array([ -8.48621595e-09,  -1.28607913e-08,  -9.39627043e-10,
        -6.71023681e-10,  -1.12563803e-09,  -3.46839557e-09,
        -7.64257968e-09,  -1.29112268e-08,  -1.26301001e-08])
       x: array([-0.57065452, -0.68162834, -0.70173245, -0.70421294, -0.70136905,
       -0.69186565, -0.66579202, -0.5960342 , -0.41641207])
 message: 'A solution was found at the specified tolerance.'
     nit: 29

We have accomplished a good approximation in only 29 iterations. Improvements are possible through a series of optional parameters. The two crucial options are:

  • The iterative solvers for linear equations from the module scipy.sparse.linalg used to compute the Krylov approximation to the Jacobian
  • A preconditioner for the inner Krylov iteration: a functional expression that approximates the inverse of the Jacobian

    Tip

    To illustrate the employment of preconditioners, there is a great example in the official documents of SciPy at http://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html.

    Further explaining the usage of these two options would require a textbook on its own! For the theory behind this technique, refer to the article Jacobian-free Newton-Krylov methods, published by D.A. Knoll and D.E. Keyes in the Journal of Computational Physics. 193, 357 (2003).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.129.26.22