zero-finding problem:
Given a scalar function F(x) : R → R, find a point x∗ ∈ R s.t.
F(x∗) = 0.
Although not all our problems are immediately viewed in this form we can always rewrite them in this way.
Convergence criteria(标准)
Possible conditions to satisfy:
|xn+1 −x∗| < |xn −x∗|
ie. we are getting closer to the root at each step
|F(xn+1)| < |F(xn)|
ie. the function F(x) is reduced at each step
- These criteria are distinct
- one does not imply the other
- Different algorithms may satisfy one of these, rarely both, and often neither
Convergence rate
- converges linearly(线性收敛): Assume the sequence x0, x1, . . . , xn converges to x∗.
if there exists 0 < α < 1 and satisfied this formula, Here α is the rate of convergence.
i.e. the error is (eventually) reduced by a constant factor of α after each iteration
If α = 1 the sequence converges sublinearly*(亚线性).
- Sequence converges superlinearly(序列超线性收敛)
if for some q > 1 and α > 0
Sequence converges superlinearly
If q = 2, we say it converges quadratically(呈二次方收敛).
The Bisection Method
condition
1)the function F(x) is continuous
2)Assume we know two points xL and xR, such that
F(xL) F(xR) ≤ 0
called the bracket condition for the bracket [xL , xR ]-
3)the Intermediate Value Theorem: This implies that there is a solution x∗ ∈ [xL,xR], since the function changes sign over that interval
The Bisection Method Bisection Method is converges linearly and its converges rate is 1/2
Note: The convergence is not monotone(单调) in general.
i.e. it can happen that for some steps n we have |F(xn+1)| > |F(xn)|.The upper bound above guarantees that eventually lim n→∞ x Cn = x∗ so that limn→∞ F(xCn) = 0.
Pros and cons of bisection method
Performance:
Guaranteed to converge to x∗
Slow (linear convergence rate)
Other issues:
- We require an initial bracket (2 values), not just an initial guess (1 value)
- In practice we may have to search for a bracket given one point
- The initial bracket [xL , xR ] may contain more than one zero and it is not clear which it will compute
The difference of Bisection Method and Newton Method
- The Bisection Method is usually stopped when |b−a| < TOLx
for a bracket [a, b]. - Newton’s Method is usually stopped when
|F(x)| < TOLF
TOLx and TOLF are appropriately chosen tolerances
