SME
Numerical Methods for Engineers · Problem type
Bisection: halve the bracket
Use this for “Bisect x³ − x − 3 = 0 on [1, 2] once, then say how many halvings reach a tolerance of 0.0001.”
Chart
Bisection: m₁ = 1.5 (f < 0)
The root stays in [1.5, 2], the bracket with a sign change
This is an example. Type your own values to start a new problem.
c₃
Cube coefficient
example
c₂
Square coefficient
example
c₁
Linear coefficient
example
c₀
Constant term
example
a
Left end
example
b
Right end
example
tol
Tolerance
example
f(a)
Function value at a
worked out (not typed)
f(b)
Function value at b
worked out (not typed)
m
Midpoint
calculated
f(m)
Function value at m
worked out (not typed)
a₁
New left end
worked out (not typed)
b₁
New right end
worked out (not typed)
n
Halvings for the tolerance
worked out (not typed)
Formulas
f
(
a
)
=
c₃
×
a
3
+
c₂
×
a
2
+
c₁
×
a
+
c₀
−3
=
1
×
1
3
+
0
×
1
2
+
(−1)
×
1
+
(−3)
f
(
b
)
=
c₃
×
b
3
+
c₂
×
b
2
+
c₁
×
b
+
c₀
3
=
1
×
2
3
+
0
×
2
2
+
(−1)
×
2
+
(−3)
m
=
a
+
b
2
1.5
=
1 + 2
2
f
(
m
)
=
c₃
×
m
3
+
c₂
×
m
2
+
c₁
×
m
+
c₀
−1.125
=
1
×
1.5
3
+
0
×
1.5
2
+
(−1)
×
1.5
+
(−3)
a₁
=
m
1.5 = 1.5
b₁
=
b
2 = 2
n
=
⌈log₂(
b
−
a
tol
)⌉
14
=
⌈log₂(
2 − 1
0.0001
)⌉
Assumptions
•
f(x) = c₃x³ + c₂x² + c₁x + c₀ is continuous and changes sign on [a, b], so a root lies between.
•
Each step keeps the half whose ends still differ in sign.
•
After n halvings the bracket is (b − a) ÷ 2ⁿ wide: n = ⌈log₂((b − a) ÷ tol)⌉.
Step-by-step
WE KNOW
c₃ = 1, c₂ = 0, c₁ = −1, c₀ = −3, a = 1, b = 2, tol = 0.0001
FIND
function value at a (f(a)), function value at b (f(b)), midpoint (m), function value at m (f(m)), new left end (a₁), new right end (b₁), halvings for the tolerance (n)
Step 1 · Find function value at a (f(a))
Use f(a) = c₃ × a³ + c₂ × a² + c₁ × a + c₀
Put the left end into f: its sign is the one to compare with.
f
(
a
)
=
1
×
1
3
+
0
×
1
2
+
(−1)
×
1
+
(−3)
f
(
a
)
=
1
×
1
+
0
×
1
−
1
×
1
−
3
f
(
a
)
=
1
−
1
−
3
f
(
a
)
=
−3
Step 2 · Find function value at b (f(b))
Use f(b) = c₃ × b³ + c₂ × b² + c₁ × b + c₀
Put the right end into f: it must have the other sign.
f
(
b
)
=
1
×
2
3
+
0
×
2
2
+
(−1)
×
2
+
(−3)
f
(
b
)
=
1
×
8
+
0
×
4
−
1
×
2
−
3
f
(
b
)
=
8
−
2
−
3
f
(
b
)
=
3
Step 3 · Find midpoint (m)
Use m = (a + b) ÷ 2
The midpoint of the bracket.
m
=
1 + 2
2
m
=
3
2
m
=
1.5
Step 4 · Find function value at m (f(m))
Use f(m) = c₃ × m³ + c₂ × m² + c₁ × m + c₀
Put the midpoint into f: its sign says which half keeps the root.
f
(
m
)
=
1
×
1.5
3
+
0
×
1.5
2
+
(−1)
×
1.5
+
(−3)
f
(
m
)
=
1
×
3.375
+
0
×
2.25
−
1
×
1.5
−
3
f
(
m
)
=
3.375
−
1.5
−
3
f
(
m
)
=
−1.125
Step 5 · Find new left end (a₁)
Use a₁ = m
f
(
m
)
has
the
sign
of
f
(
a
),
so
the
sign
change
is
past
m
:
the
root
is
in
[
m
,
b
].
−3
×
(−1.125)
>
0:
the
left
end
moves
to
m
a₁
=
1.5
Step 6 · Find new right end (b₁)
Use b₁ = b
f
(
m
)
has
the
sign
of
f
(
a
),
so
the
sign
change
is
past
m
:
the
root
is
in
[
m
,
b
].
−3 × (−1.125) > 0: the right end stays
b₁
=
2
Step 7 · Find halvings for the tolerance (n)
Use n = ⌈log₂((b − a) ÷ tol)⌉
Each
halving
halves
the
width;
halve
until
b
−
a
2ⁿ
is
at
most
tol.
log₂
x
=
ln x
ln 2
,
rounded
up.
n
=
⌈ln
(
b
−
a
) ÷ tol
ln(2)
⌉
n
=
⌈ln
(2 − 1) ÷ 0.0001
ln(2)
⌉
n
=
⌈
ln(10,000)
ln(2)
⌉
=
⌈13.2877⌉
n
=
14
Check
Put the numbers back in. Both sides should match.
−3
=
1
×
1
3
+
0
×
1
2
+
(−1)
×
1
+
(−3)
✓
3
=
1
×
2
3
+
0
×
2
2
+
(−1)
×
2
+
(−3)
✓
1.5
=
1 + 2
2
✓
−1.125
=
1
×
1.5
3
+
0
×
1.5
2
+
(−1)
×
1.5
+
(−3)
✓
1.5 = 1.5 ✓
2 = 2 ✓
14
=
⌈log₂(
2 − 1
0.0001
)⌉
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.