9. Homotopy and Bifurcation by MIT OpenCourseWare

Summary by www.lecturesummary.com: 9. Homotopy and Bifurcation by MIT OpenCourseWare

• 1. Introduction and Course Review (0:00)

  • Review of linear algebra and solving systems of nonlinear equations.
  • From basics to the numerical methods practice.
  • Discussion on sophisticated methods for complicated problems.
  • No longer required to apply techniques such as Newton's method manually; will employ facilities such as those available in Matlab.
  • Understanding how these techniques operate, their limitations, and how to apply related facilities (e.g., function definitions, Jacobians, parameters such as tolerances and iteration counts) is necessary.
  • Today's lecture focuses on solving things reliably.

  2. Significance of Good Initial Guesses (3:30)

  • Solving nonlinear systems of equations requires good initial guesses.
  • Poor initial guesses can result in nonsensical answers.
  • Good initial guesses enable the Newton-Raphson method to converge very quickly, potentially doubling the number of correct digits per iteration (quadratic convergence).
  • Having good initial guesses is the optimal condition.

  3. Finding Multiple Roots and Newton-Raphson Limitations (4:00)

  • Responding to a problem of finding multiple roots using Newton-Raphson.
  • Discussion on roots with multiplicity, where the function touches the axis but does not cross (the derivative is zero at the root).
  • Newton-Raphson depends on the derivative.
  • Near the root, the derivative is not necessarily zero, so Newton steps can be taken.
  • Analysis reveals linear rather than quadratic convergence in this situation. There is a penalty, but it is still possible for the method to converge, albeit very slowly.
  • With more than one dimension, there can be more than one root that will appear as tangent curves in solution space.
  • At a multiple root, the determinant of the Jacobian can be zero.
  • In the vicinity, the Jacobian can be non-singular, and movements can proceed towards the root.
  • Convergence can slow down if movements are taken in a direction parallel to the null space of the Jacobian at the root.
  • Such situations do not arise very frequently but will be seen in the discussion of the lecture.

  4. Quasi-Newton Methods and Global Convergence (7:15)

  • Referring to how to correct Newton-Raphson when good initial guesses cannot be made, e.g., Quasi-Newton methods.
  • Damped Newton-Raphson adds a damping parameter to make steps shorter.
  • The goal is to minimize the absolute value of the function, which is an optimization problem.
  • This optimization problem is not solved exactly.
  • Backtracking line search is used to systematically change the damping parameter until a smaller function value is found.
  • This approach can provide global convergence.
  • But convergence worldwide is to minima, asymptotes, and roots, not necessarily to roots alone.
  • The algorithm will stop, and you have to verify if the answer is within reasonable closeness to a root. Otherwise, it could be a minimum or asymptote, and you need a fresh starting guess.
  • Matlab employs an advanced version, such as the dogleg method, which is founded on the same principles: maintaining suitable step size and direction.
  • Accurate initial guesses are essential for solving nonlinear equations and optimization problems.

  5. Multiple Roots and Introduction to Continuation/Homotopy (10:20)

  • Nonlinear equations and optimization problems might have multiple roots/minima.
  • Numerical methods may find different solutions depending on the initial guess.
  • There are methods to find all roots or minima.
  • Continuation and Homotopy are methods discussed for finding all roots.
  • Bifurcation is also discussed.
  • The homework assignment this week involves a ternary phase equilibrium problem (vapor-liquid).
    • Utilize a homotopy approach to compute all roots (existing compositions) simultaneously.

    6. Continuation Explained (12:45)

    • Concept related to root-finding and good initial guesses.
    • Illustration: A third-degree polynomial with three roots apparent graphically in 1D. Initial guesses can be taken from the graph.
    • Graphical methods are impossible or hard in higher dimensions.
    • Continuation is a technique to turn a difficult problem into an easy one.
    • Polynomial example `x^3 - 2x + 1 = 0` is converted by substituting 2 with `2 * lambda`: `x^3 - 2*lambda*x + 1 = 0`.
    • The objective is to look for the roots as lambda increases from 0 to 1.
    • When lambda = 0, the equation is `x^3 + 1 = 0`, which has one real root: x = -1 (simple problem with known solution).
    • If lambda is just slightly larger than zero, there will be a root near -1; -1 is a good initial approximation.
    • Taking the solution at lambda_i as an initial guess for lambda_(i+1) enables stepping lambda along from 0 to 1.
    • When lambda is 1, the root of the original problem is obtained.
    • This is going from one set of solutions to another by changing a parameter continuously.
    • Earlier solutions are used as initial guesses for the next value of the parameter.
    • Example code illustrates looping over lambda values, solving (fzero in Mat lab), and changing the initial guess.
    • From lambda=0, the root path converges to one of the roots (say, about -1.5) at lambda=1.
    • This re-formulates the problem, employing a path along the transformation to achieve quick convergence with better initial guesses.

    7. Continuation for Multiple Roots (17:45)

    • Alternative method: begin with a large lambda and trace back to lambda = 1.
    • At large lambda, approximations of the roots can be determined by equating leading terms: `x ~ 1/(2*lambda)` and `x ~ +/- sqrt(2*lambda)`.
    • Taking these as starting guesses at large lambda and back-tracking to lambda = 1 enables determining all three roots of the original equation.
    • This is one lambda pass (large to 1) but entails starting the process with several starting guesses (three here) to trace different paths.
    • The paths can be complex.
    • Beginning from lambda=0 to 1 only discovered a single solution. Beginning from large lambda down to 1 discovered three. It's not always known in advance how many will be discovered.
    • The method reduces hard problems to a chain of easier ones by using a chain of good starting guesses to achieve quick convergence.

    8. Natural Parameters in Physical Problems (21:10)

    • Very often, physical issues have natural parameters whose values can be changed in order to continue.
    • Examples:
    • Fluid mechanics: change of Reynolds number from low (close to linear equations) up to high.
    • Mass transfer: changing Peclét number.
    • Phase equilibria: changing temperature or pressure.
    • Reaction equilibria: changing reaction rates.
    • This enables transformation from simple-to-solve problems (e.g., low Reynolds number, ideal gas) to difficult-to-solve problems (e.g., turbulent flow, real fluid behavior) continuously.
    • The procedure isn't always simple.

    9. Homotopy Method Introduced (24:30)

    • An approach for problems for which there isn't a clear natural parameter.
    • Homotopy is the smooth deformation from one problem to another.
    • A typical construction: `h(x, lambda) = lambda * f(x) + (1 - lambda) * g(x)`.
    • Roots `x*` are found as a function of `lambda`.
    • f(x) = 0 is the problem you wish to solve.

    • g(x) = 0 is an auxiliary problem, usually selected as simple to solve.

      Lambda Values and Roots

      • When lambda = 0, `h = g`, thus the roots of h are the roots of g.
      • When lambda = 1, `h = f`, thus the roots of h are the roots of f.
      • Continuously varying lambda from 0 to 1 changes the roots of g to the roots of f.
      • If the smooth transformation from g to f happens, behavior can be good.
      • Incrementing lambda in small steps and taking the solution at lambda_i as an initial guess for lambda_(i+1) is the approach.
      • g is usually an arbitrarily selected auxiliary problem; f is the problem to be solved, commonly selected to have physical relevance.

      10. Homotopy Example: Van der Waals Equation

      • To find roots (molar volume) of the Van der Waals equation of state (f).
      • Selecting the Ideal Gas equation of state (g) as the auxiliary problem.
      • Construction: `h = lambda * f_vdw + (1 - lambda) * f_ideal_gas`.
      • The ideal gas equation is simple to solve (one root).
      • The Van der Waals equation has three roots (liquid-like, vapor-like, unstable).
      • Changing lambda from 0 to 1 begins with the ideal gas root and changes to one of the VdW roots.

      11. Finding Cusps/Turning Points and Determining Multiple Roots

      • Proceeding with the homotopy procedure past lambda=1 may uncover more.
      • At some lambda value, the molar volume may jump to another solution branch.
      • The discontinuity or cusp (or turning point) shows that there is another branch of solutions.
      • Reversing the direction of change in lambda along the new branch can be used to find a different root.
      • By looking for root changes and reversing direction at cusps, all roots can be potentially located.
      • Such cusps are termed turning points.
      • At a turning point, the determinant of the Jacobian of the homotopy function (h) equals zero. The Jacobian is singular.
      • These features can be implemented by monitoring the Jacobian determinant.
      • At turning points, there is no clearly defined direction to go along the curve.

      12. Arclength Continuation (Systematic Approach)

      • Systematic means of tracing out the solution path in the lambda vs root plane.
      • The curve is parameterized by arc length (s).
      • Lambda and x are s functions.
      • There is an arclength constraint equation involving derivatives of lambda with respect to s and x with respect to s.
      • This yields a differential-algebraic equation.
      • Solving for this equation enables tracing the whole curve to determine all the roots associated with the path by determining where the curve crosses lambda=1.

      Turning Points and Multiplicity

      • Should there be a turning point at a root, it means multiplicity.
      • Such as curves being tangent in the solution plane, is all linked to multiplicity.

      13. Bifurcation Explained

      • It happens when a path of one root divides, hence more than one root.
      • Example: `x^3 - rx = 0`.
      • For r < 0, one real root (x=0).
      • At r = 0, one real root with multiplicity three.
      • For r > 0, three real roots.
      • As parameter r changes, the solution bifurcates from one root to three at r=0.
      • In a homotopy problem, striking a bifurcation point is essentially desiring to pursue all resulting paths.
      • Bifurcation points are identified where the Jacobian of the Homotopy is singular (determinant is zero).
      • The homework problem entails bifurcation: splitting from single component to two-component (azeotrope) and subsequently three-component azeotrope solution. 

        14. Physical Significance of Bifurcations

        Bifurcations tend to be locations of significant physical interest.

        For the Van der Waals equation, the bifurcation point is the critical point (critical pressure and temperature) where phase separation takes place.

        15. Definition of the Singular Jacobian

        Jacobian singular means the Jacobian of the homotopy function (h) with respect to the unknowns (x) computed at the root where the bifurcation or turning point happens.

        If x is of dimension n, this is the n x n matrix of partial derivatives of h with respect to the n components of x. Its determinant at these points is zero.

        16. Graphical Representation of Bifurcation (2D)

        • In 2D (x1, x2), roots are intersections of curves h1=0 and h2=0.
        • As lambda varies, the curves alter shape.
        • At the bifurcation point, the curves are tangent to one another. This tangency is the same as the Jacobian being singular.
        • After the bifurcation point, the curves intersect more than once, creating multiple roots.

        17. Practical Branch Detection

        • It is difficult to strike the bifurcation point numerically exactly.
        • A pragmatic approach is to follow the sign of the Jacobian determinant. A sign change signifies passing a bifurcation point.
        • Upon detection of a sign change, it signifies that there could be other solution branches.
        • To locate these other branches, move in directions in the null space of the Jacobian.
        • Forcing away from known solutions in parallel directions with the tangency of the curves assists in discovering initial guesses of the other branches.
        • This task is difficult but feasible.

        18. Finding Bifurcation Points Exactly (Augmented System)

        • To determine the exact location (x and lambda values) of a bifurcation point, solve an augmented system of equations.
        • The system is the original homotopy equation `h(x, lambda) = 0` and the requirement that the determinant of the Jacobian of h with respect to x is zero: `det(Jh(x, lambda)) = 0`.
        • If h has dimension n (x is n-dimensional), this is a system of n + 1 equations.
        • These equations are to be solved for n + 1 unknowns: the n components of x and the bifurcation parameter lambda.
        • This extended system is a nonlinear equation which can be solved by Newton-Raphson iteration.
        • This involves calculating the augmented Jacobian of the system.
        • It is advisable to use finite difference to calculate this augmented Jacobian instead of symbolic differentiation.

        19. Simple Example: Touching Circles

        • Simple example function with two unknowns (x1, x2) and one parameter (r).
        • `f1(x1, x2, r) = (x1+3)^2 + (x2+1)^2 - r^2 = 0` (Circle 1).
        • `f2(x1, x2, r) = (x1-2)^2 + (x2-2)^2 - r^2 = 0` (Circle 2).
        • To find the radius r at which the two circles are just touching is to find a bifurcation point.
        • If r is too big, two intersections (two solutions). If r is too small, no intersection (no solution).
        • To calculate the bifurcation point (the touching radius and position), solve the system of augmented equations: `f1=0`, `f2=0`, and `det(Jf(x1, x2)) = 0`.
        • This is a system of 3 nonlinear equations for 3 variables (x1, x2, r).
        • This can be solved with Newton-Raphson. The Jacobian of this 3x3 system must be calculated (finite difference recommended).

        20. Summary and Conclusion

        • Homotopy and bifurcation offer methods for obtaining good initial guesses by gradually deforming the problem.
        • This results in a sequence of problems that converge more rapidly.
        • It gives convergence to one of the roots in a reliable way.
        • By recovering solution branches at bifurcation points or cusps, several solutions can be obtained.
        • Strong methods for the computation of multiple roots or minima are available.
        • There is practice on the homework assignment.

          Branch Following and the Null Space (Revisited)

          Duration: 1:05:50

          Key Concepts

          • Under a bifurcation point, initial conditions are required for each of the new branches.
          • Such initial guesses need to be perturbed in directions in the null space of the Jacobian.
          • Such directions are parallel to the tangency of the curves at the bifurcation point. Finding the vectors enables tracing out the other roots.