120
5. Solution of Linear Equation Systems
and we continue until the change in the root x k - x k - 1 is as small as desired.
The method is equivalent to approximating the curve representing the function by its tangent at x k . When the estimate is close enough to the root, this
method converges quadratically i.e. the error at iteration k+ 1 is proportional
to the square of the error at iteration k. This means that only a few iterations
are needed once the solution estimate is close to the root. For that reason, it
is employed whenever it is feasible to do so.
Newton's method is easily generalized to systems of equations. A generic
system of non-linear equations can be written:
This system can be linearized in exactly the same way as the single equation.
The only difference is that now we need to use multi-variable Taylor series:
for i = 1,2, . . . , n. When this is set to zero, we have a system of linear
algebraic equations that can be solved by Gauss elimination or some other
technique. The matrix of the system is the set of partial derivatives:
which is called the Jacobian of the system. The system of equations is:
For an estimate that is close to the correct root, Newton's method for
systems converges as rapidly as the method for a single equation. However,
for large systems, the rapid convergence is more than offset by its principal
disadvantage. For the method to be effective, the Jacobian has to be evaluated
at each iteration. This presents two difficulties. The first is that, in the general
case, there are n2 elements of the Jacobian and their evaluation becomes the
most expensive part of the method. The second is that a direct method
of evaluating the Jacobian may not exist; many systems are such that the
equations are implicit or they may be so complicated that differentiation is
all but impossible.
To the authors' knowledge, Newton's method has been used only few
times to solve the Navier-Stokes equations although it has been used to solve
simplifications of these equations many times. It was found that the cost of
generating the Jacobian and solving the system by Gauss elimination was so
5. Solution of Linear Equation Systems
and we continue until the change in the root x k - x k - 1 is as small as desired.
The method is equivalent to approximating the curve representing the function by its tangent at x k . When the estimate is close enough to the root, this
method converges quadratically i.e. the error at iteration k+ 1 is proportional
to the square of the error at iteration k. This means that only a few iterations
are needed once the solution estimate is close to the root. For that reason, it
is employed whenever it is feasible to do so.
Newton's method is easily generalized to systems of equations. A generic
system of non-linear equations can be written:
This system can be linearized in exactly the same way as the single equation.
The only difference is that now we need to use multi-variable Taylor series:
for i = 1,2, . . . , n. When this is set to zero, we have a system of linear
algebraic equations that can be solved by Gauss elimination or some other
technique. The matrix of the system is the set of partial derivatives:
which is called the Jacobian of the system. The system of equations is:
For an estimate that is close to the correct root, Newton's method for
systems converges as rapidly as the method for a single equation. However,
for large systems, the rapid convergence is more than offset by its principal
disadvantage. For the method to be effective, the Jacobian has to be evaluated
at each iteration. This presents two difficulties. The first is that, in the general
case, there are n2 elements of the Jacobian and their evaluation becomes the
most expensive part of the method. The second is that a direct method
of evaluating the Jacobian may not exist; many systems are such that the
equations are implicit or they may be so complicated that differentiation is
all but impossible.
To the authors' knowledge, Newton's method has been used only few
times to solve the Navier-Stokes equations although it has been used to solve
simplifications of these equations many times. It was found that the cost of
generating the Jacobian and solving the system by Gauss elimination was so