192
7 Solving Nonlinear Algebraic Equations
Required Work in the Bisection Method
If the starting interval of the bisection method is bounded by a and b, and the
solution at step n is taken to be the middle value, the error is bounded as
|b − a|
2 n ,
(7.4)
because the initial interval has been halved n times. Therefore, to meet a
tolerance , we need n iterations such that the length of the current interval
equals
|b − a|
2 n = ⇒ n =
ln((b − a)//)
ln 2
.
This is a great advantage of the bisection method: we know beforehand how
many iterations n it takes to meet a certain accuracy in the solution.
7.5 Rate of Convergence
With the methods above, we noticed that the number of iterations or function calls
could differ quite substantially. The number of iterations needed to find a solution is
closely related to the rate of convergence, which dictates the speed of error reduction
as we approach the root. More precisely, we introduce the error in iteration n as
e n = |x − x n |, and define the convergence rate q as
e n+1 = Ce
q
n ,
(7.5)
where C is a constant. The exponent q measures how fast the error is reduced from
one iteration to the next. The larger q is, the faster the error goes to zero (when
e n < 1), and the fewer iterations we need to meet the stopping criterion |f (x)| < <.
Convergence Rate and Iterations
When we previously addressed numerical integration (Chap. 6), the approximation error E was related to the size h of the sub-intervals and the
convergence rate r as E = Kh r , K being some constant.
Observe that (7.5) gives a different definition of convergence rate. This
makes sense, since numerical integration is based on a partitioning of the
original integration interval into n sub-intervals, which is very different from
the iterative procedures used here for solving nonlinear algebraic equations.
7 Solving Nonlinear Algebraic Equations
Required Work in the Bisection Method
If the starting interval of the bisection method is bounded by a and b, and the
solution at step n is taken to be the middle value, the error is bounded as
|b − a|
2 n ,
(7.4)
because the initial interval has been halved n times. Therefore, to meet a
tolerance , we need n iterations such that the length of the current interval
equals
|b − a|
2 n = ⇒ n =
ln((b − a)//)
ln 2
.
This is a great advantage of the bisection method: we know beforehand how
many iterations n it takes to meet a certain accuracy in the solution.
7.5 Rate of Convergence
With the methods above, we noticed that the number of iterations or function calls
could differ quite substantially. The number of iterations needed to find a solution is
closely related to the rate of convergence, which dictates the speed of error reduction
as we approach the root. More precisely, we introduce the error in iteration n as
e n = |x − x n |, and define the convergence rate q as
e n+1 = Ce
q
n ,
(7.5)
where C is a constant. The exponent q measures how fast the error is reduced from
one iteration to the next. The larger q is, the faster the error goes to zero (when
e n < 1), and the fewer iterations we need to meet the stopping criterion |f (x)| < <.
Convergence Rate and Iterations
When we previously addressed numerical integration (Chap. 6), the approximation error E was related to the size h of the sub-intervals and the
convergence rate r as E = Kh r , K being some constant.
Observe that (7.5) gives a different definition of convergence rate. This
makes sense, since numerical integration is based on a partitioning of the
original integration interval into n sub-intervals, which is very different from
the iterative procedures used here for solving nonlinear algebraic equations.