[Next Section] [Previous Section] [Table of Contents]

Full Equations (FEQ) Model for the Solution of the Full, Dynamic Equations of Motion for One-Dimensional Unsteady Flow in Open Channels and Through Control Structures

# 9.1 Newton's Iteration Method for Solution of Nonlinear Equations

In general, even a single nonlinear equation cannot be solved without some numerical method to approximate the solution to the equation. The example of a single equation illustrates some of the problems that are considered in FEQ simulation. Thus, Newton's iteration method for solution of nonlinear equations is initially described and illustrated for the case of a single nonlinear equation. The discussion of Newton's method is then expanded to the simultaneous solution of many equations.

## 9.1.1 Application to a Single Equation

If a direct solution to the nonlinear equation is not possible, then some indirect approach must be applied. For a single nonlinear equation, this is done by approximating the residual function over an interval by another simpler function that can be solved directly and easily. The residual function is simply the equation describing the process of interest, organized such that the sum of the relevant factors equals zero. Thus, the residual function of the continuity equation is given by equation 68, and the residual function of the conservation of momentum equation is given by equation 77. If the approximation of the residual function is close, then the solution to the simpler equation will be a close approximation to the solution of the nonlinear equation. In Newton's method, the approximating function is the line tangent to the residual function, F, at some point,  , where  is close to the location of a root. Let  denote the derivative of the function FN at any point u. Expanding FN in a Taylor series about and discarding nonlinear terms yields

(123)

,

where is the value on the line tangent to FN , the point of tangency being . Solving equation 124 for u where = 0 yields the root for the tangent line,

(124)

,

where is the root of the tangent line, which becomes the next approximation to a root of the equation. This process can be repeated until the approximations to the root approach some limit or until the value of the function FN becomes acceptably small. Equation 124, rewritten to show this process, becomes

(125)

,

where i= 0, 1, 2, . . . Various applications of Newton's method are shown in figure 18.

Cases that can result in problems in the convergence of Newton's method are shown in figure 18b-d. In the first case, the root is near a point of inflection so that the iterations oscillate and convergence is impossible. In the second case no root is possible: Newton's method will not converge because there is no root to converge to. In the third, the derivative is zero at a root, so the method may not converge or will converge slowly. Hamming (1973, p. 70-72) and Dennis and Schnabel (1983, p. 21-23) discuss means for detecting these problems for a single equation.

## 9.1.2 Application to Simultaneous Equations

The single-equation Newton's method forms the basis for the method extended to simultaneous nonlinear equations. Instead of a curve with a tangent line, Newton's method for simultaneous equations is based on an ne -dimensional plane tangent to an ne -dimensional surface, where ne is the number of equations. At each iteration, instead of solving a single equation in a single unknown, a linear system of ne equations in ne unknowns must be solved. Let be the residual function of the k th equation in the system, where u is the vector of unknown values. For a stream system simulated with FEQ, the residual function for the continuity equation is given by equation 68, conservation of momentum equation is given by equation 77, and external boundary conditions are given by equations 91, 121, and 122. To keep the notation compact, let Fkj ' denote the partial derivative of Fk with respect to the jth variable in the vector of unknowns, u. The steps followed are analogous to those for a single variable. The equation for the approximation to the functions is determined about some initial point, and the root of the approximation as an estimate of the root of the equation is then determined.

As an example of the application of Newton's method, consider two equations and two unknowns. To distinguish the iteration number from the number used to denote the variable, let a superscript denote the iteration number, and not an exponent. If there are exponents, they must be set off with parentheses. For example, denotes the initial value for the first unknown in the vector u, denotes the second iteration as it affects the first unknown, and denotes the square of the value of the second unknown at the second iteration. Discarding all nonlinear terms from a Taylor series expansion about the point u 0 yields two equations:

(126)

and

(127)

.

Setting each of these equations to zero and solving for the unknowns gives the first-iteration results for the roots of F 1 and F 2 as for a single equation. Two linear equations in two unknowns result. However, the notation becomes unmanageable as the number of equations increases. FEQ simulation can involve several thousand equations and as many unknowns. Matrix notation makes for a more compact and more general display of the equations and the solution process. Equation 123 in matrix notation is

(128)

,

where u is the vector of values on the tangent planes, F(u) is the vector of values of the residual functions for the equations, and J( u) is the matrix of partial derivatives of the residual functions, called the Jacobian matrix. If ne = 2, then

(129)

,

(130)

,

and

(131)

.

In equation 128, the argument list following a vector or matrix symbol is applied to each element of the vector or matrix.

Letting and solving for the approximation to the root results in

(132)

,

as the final form of the iteration for a simultaneous system of nonlinear equations by means of Newton's method. In equation 132, J -1 denotes the inverse matrix for the Jacobian of the system of equations. Dennis and Schnabel (1983, p. 21-23) discuss the conditions for convergence of Newton's method for a system of nonlinear equations. The convergence is quadratic if the first derivatives are sufficiently smooth and the initial point is not too far from one of the roots of the equations.

Obviously, the solution of a system of nonlinear equations is much more complex than for a single equation. Similar convergence problems may result, but now no simple geometric visualization is possible. Furthermore, Dennis and Schnabel (1983, p. 9) point out that problems involving 50 or more equations are difficult to solve unless a good estimate is available before iteration. However, this is only true for systems in which the Jacobian matrix is filled, or nearly so, with nonzero elements. In one-dimensional, unsteady-flow analysis, the Jacobian has a special structure and contains many zeros. For large stream systems, less than 1 percent of the elements in the Jacobian will be nonzero; all other elements are known in advance to be zero. This structure is used in FEQ simulation to reduce the complexity and number of computations.

9.1.1 Application to a Single Equation
9.1.2 Application to Simultaneous Equations

[Next Section] [Previous Section] [Table of Contents]