Introduction to Solving Systems of Nonlinear Equations
- Shift from linear algebra to harder problems
- Next topics: systems of nonlinear equations and optimization problems
- Brief review of linear algebra ideas: singular value decomposition (SVD), singular vectors, singular values
Condition Number
- Condition number is applicable to any matrix in terms of singular values
- Condition number is of most use when error magnification is at issue for solving linear systems
Nonlinear Systems Require Iterative Solutions
- Iterative algorithms iteratively improve initial approximations until convergence
- Main question: When should we terminate iterating?
Stopping Iterative Algorithms Criteria
- Stepnorm criterion: Terminate when successive iterations' difference is small enough
- Consider distance between next and current iteration
- If steps are small enough, accept solution
- This entails taking into account absolute as well as relative error
- Relative error is a difficulty when it converges to zero
- Require absolute tolerance for solutions that are converging to tiny numbers
- Require relative tolerance for solutions that are converging to huge numbers
- Function norm criterion (Residual): Terminate when the function at the current solution is sufficiently close to zero
- Verify how well the solution meets the initial equation
- Residual: f(x) (or Ax-b in linear systems)
- If the residual magnitude is small enough, accept the solution
- Neither criterion is universally preferred; usually use multiple criteria
- These criteria apply to all iterative processes
- Neither criterion guarantees the exact solution is found
- Both criteria can fail
- Function norm can fail with shallow slopes
- Stepnorm can fail if steps become small far from a root
- It is best to apply both criteria
Validating Numerical Solutions
- You cannot simply accept what the computer says
- Every calculation has numerical error
- How to know if the result is correct?
- Validation is immensely important, especially for complicated problems
- Methods for validation:
- Plugging the solution back into the equation (may not be sufficient if the equation is insensitive)
- Physical reasoning
- Comparing against analytical solutions in certain limits (asymptotic analysis)
- Comparing against experiments (experiments represent reality, the computer model is a fiction)
- Solving the problem multiple times or multiple ways
- Using different initial guesses for iterative methods
Systems of Nonlinear Equations: Definition and Examples
- Form: f(x) = 0, where x is a vector of unknowns and f is a vector-valued function (map from Rn to Rn)
- f can be a nonlinear function of the elements of x
- Solutions are referred to as roots of the vector-valued function
- Linear equations (Ax - b = 0) are a special case
- Examples in chemical engineering: equations of state (e.g., Van der Waals), energy balances, mass balances with nonlinear reactions
Van der Waals Equation of State Example
- May have several roots (molar volumes) for the same pressure and temperature
- Contrary to linear equations, the number of solutions is usually not determinable (except if transformable to a polynomial)
Vapor-liquid Coexistence Problem for a Van der Waals Fluid
This example involves:
- Satisfaction of thermal, mechanical, and chemical equilibrium
- Chemical equilibrium represented by Maxwell equal area construction (equal chemical potential)
- Solving three nonlinear equations for saturation pressure, gas molar volume, and liquid molar volume
- Equations include the equation of state for gas and liquid phases and the Maxwell construction
- Must be solved numerically
- Can be reduced to 2D by solving for pressure, which can then be graphically represented
- Solutions are the intersection of the curves defined by f1=0 and f2=0
Properties of Solutions: Local Uniqueness
The problem is to determine x* where f(x*) = 0. Solutions may be:
- No solution, one to infinite locally unique solutions, or infinite solutions
- Locally unique solution: A solution that can be singled out in a ball of points having no other solutions
- Numerical methods are more certain for determining locally unique solutions
Inverse Function Theorem: If f(x*) = 0 and the determinant of the Jacobian J(x*) is not zero, then x* is a locally unique solution.
- Jacobian (J) is the matrix of partial derivatives of f with respect to x
- J is the derivative of the vector-valued function with respect to change
- If det(J(x*)) = 0, the solution might or might not be unique locally
- Connection to linear algebra: In f(x)=Ax-b, the Jacobian is A; there is a unique solution if det(A) is nonzero (A is invertible)
- The Inverse Function Theorem is a generalization of invertibility principles from linear algebra
Linearization of Nonlinear Functions
Around a root of f(x)=0, the function is usually linearizable. This procedure is known as linearization.
- For multi-dimensional functions, the linearization around x is: f(x + delta x) ≈ f(x) + J(x) * delta x
- This works for small delta x
- The error in this approximation is usually order delta x²
- This is from the Taylor expansion of each component of f
- The approach is to linearize the function around a point and then solve the linearized equation to obtain a point nearer to the actual solution
Rate of Convergence
This measures the speed at which an iterative process converges towards the solution. Consider the ratio of successive absolute errors:
- Linear convergence: Q=1 and C<1 in the formula of ratio
- Absolute error decreases by a constant amount at every iteration
- Example: C=10-1 means one additional accurate digit per iteration
- Jacobi and Gauss-Seidel techniques are linearly convergent
- Superlinear convergence: Q>1
- Quadratic convergence: Q=2 and C is finite
- The number of accurate digits doubles with each iteration
- Quadratic convergence is very desirable from the viewpoint of speed
Newton-Raphson Method
Most reliable and fastest converging methodology for the solution of systems of nonlinear equations. It has quadratic convergence if beginning close enough to a locally unique solution.
- Based on linearizing the function at the current estimate
- 1D method: Begin at xi, linearize f(x), solve the linearization for the next estimate xi+1
- Equation: xi+1 = xi - f(xi) / f'(xi)
- The derivative provides the direction of the step, the ratio provides magnitude
- Multi-dimensional method:
-
- Linearize f(x) around x_i and equate the linearization to zero.
- Use the linearized equation: f(x_i) + J(x_i) * (x_i+1 - x_i) = 0.
- Define the step/displacement d_i = x_i+1 - x_i.
- Solve for the step: J(x_i) * d_i = -f(x_i).
- The next iteration is: x_i+1 = x_i + d_i.
Linearization of the system
Instead of solving for the Jacobian inverse explicitly, linearize the system J*d = -f.
- Jacobian inverse serves as 1/derivative in describing the direction.
Problems with Newton-Raphson
- Poor global convergence (may get stuck with a bad initial guess).
- Singular Jacobian at the current point (equivalent to derivative being zero in 1D).
- This occurs with non-locally unique solutions (where det(J)=0).
- Around such points, the linear system may be ill-conditioned, making the step hard to calculate reliably.
Example: Intersection of two circles
This can be expressed as solving a system of two nonlinear equations:
- f1(x1, x2)=0 and f2(x1, x2)=0.
- Involves calculating the Jacobian of the system.
Local convergence property
Convergence to a locally unique solution is assured if the start is within some neighborhood where det(J) is not zero.
Convergence map example
This illustrates how the number of iterations to converge changes based on the initial guess:
- Few iterations close to the roots or distant from the single line (where det(J)=0).
- Numerous iterations close to the line where det(J)=0.
Conclusion
In spite of issues, Newton-Raphson is robust because it has quadratic convergence. Future discussions will cover how to fix problems with the method.
