9
3.1.0 Introduction (2)
This is a consequence of the Intermediate-Value
Theorem (中值定理).
The bisection method exploits this idea in the
following way:

4
3.0 Introduction(2)
Examples of nonlinear equations can be found in
many applications.
In the theory of diffraction of light, we need the
roots of the equation
and if f (a) f (b) < 0, then f must have a zero in (a, b).
Since f (a) f (b) < 0, the function f changes sign
on the interval [a, b] and, therefore, it has at least one zero in the interval.

Next, e is the computation of the error bound that is established in the theorem to follow.
19
3.1.1Bisection Algorithm(3)
Notice the stopping criteria are present in the
21
3.1.2Error Analysis(1)
To analyze the bisection method, let us denote
the successive intervals that arise the process by [a0, b0], [a1,b1], and so on.
15
3.1.0 Introduction (8)
k 1 2 3 4 13 14 15 16 c 3.5000 3.2500 3.1250 3.1875 3.1829 3.1830 3.1831 3.1831 f c 0.321 0.694 10 1 0.605 10 1 0.625 10 1 0 .122 10 3 0 .193 10 4 0.124 1 0 4 0.345 10 5
14
3.1.0 Introduction (7)

When the bisection algorithm was run on a machine similar to the Marc-32.

The following output was produced, starting with the interval [-4,-3]

20
Topics of Today
3.0 Introduction 3.1 Bisection( Interval Halving) Method

3.1.0 Introduction 3.1.1 Bisection Algorithm 3.1.2 Error Analysis
3.2 Newton’s Method 3.3 Secant Method
16
Topics of Today
3.0 Introduction 3.1 Bisection( Interval Halving) Method

3.1.0 Introduction 3.1.1 Bisection Algorithm 3.1.2 Error Analysis
3.2 Newton’s Method 3.3 Secant Method
Here are some observations about the numbers:
a0 a1 a2 ... b0 b0 b1 b2 ... a0 1 bn 1 an 1 bn an 2
n 0
(1)
22
3.1.2Error Analysis(2)
algorithm.

First, M gives the maximum number of steps that the user permits. Next, the calculation can be stopped when either the error is small enough or the value of f (c) is small enough.

If f (a) f (b) < 0, then we compute c = ½(a+b) and test whether f (a) f (c) < 0.
10
3.1.0 Introduction (3)

If this is true, then f has a zero in [a, c]. So we rename c as b and start again with the new interval [a, b], which is half as large as the original interval. If f (a) f (c) < 0, then f (c) f (b) < 0, and in this case we rename c as a. In either case, a new interval containing a zero of f has been produced, and the process can be repeated.
Also, we discuss special methods for computing
the zeros of polynomials.
7
Topics of Today
3.0 Introduction 3.1 Bisection( Interval Halving) Method
Chapter 3 Solution of Nonlinear Equations
Lecturer: GUO Tongtong Time: 15th December, 2010 The 11th Lecture
1
Topics of Today
3.0 Introduction 3.1 Bisection( Interval Halving) Method 3.2 Newton’s Method

in numerical calculations it is best to compute a quantity by adding a small correction term to a previous approximation.
18
3.1.1Bisection Algorithm(2)
x tan x 0
5
3.0 Introduction(3)
In the calculation of planetary orbits, we need the
roots of Kepler’s equation
x a sin x b
for various values of a and b.

Second, it is better to determine whether the function changes sign over the interval using sign (w) ≠ sign (u) rather than wv < 0,

since the latter requires an unnecessary multiplication and could cause an underflow or overflow.
The objective of this chapter is :

To solve the roots of equations (or zeros of functions). To solve a system of nonlinear equations: to find x such that f (x) = 0 or finding X = (x1,x2,…,x n) T so that F (X) = 0.
6
3.0 Introduction(4)
In this chapter, we begin with three simple
methods that are quite useful:

The bisection method, Newton’s method, and the secant method.
3.3 Secant Method
2
Topics of Today
3.0 Inon( Interval Halving) Method 3.2 Newton’s Method
3.3 Secant Method
3
3.0 Introduction(1)
|f (c)| < 10 - 5.
The bisection method is also known as the
method of interval halving (区间减半法).
13
3.1.0 Introduction (6)
EXAMPLE 1

Use the bisection method to find the root of the equation ex = sin x closest to 0.