Interval bisection and linear interpolation

Interval bisection and linear interpolation

Spec 3.1 · Edexcel International A Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • If ff is continuous and f(a)f(a), f(b)f(b) have opposite signs, there is a root in [a,b][a,b].
  • Interval bisection halves the interval each time; after nn steps the width is b−a2n\frac{b-a}{2^n}.
  • Linear interpolation joins (a,f(a))(a,f(a)) to (b,f(b))(b,f(b)) and uses where the chord meets the xx-axis.
  • Always show the values of ff and the new interval at each step.
  • To check a root to nn d.p., show a sign change half a unit either side.

Locating a root

If ff is continuous on [a,b][a,b] and f(a)f(a) and f(b)f(b) have opposite signs, then f(x)=0f(x)=0 has at least one root in [a,b][a,b].

To solve f(x)=0f(x)=0 numerically, first show a root exists in an interval. For f(x)=x3+2x−7f(x)=x^3+2x-7: f(1)=−4f(1)=-4 and f(2)=5f(2)=5, so there is a root in [1,2][1,2].

In an answer, state both values, the sign change and that ff is continuous.

0.511.522.53−5510152025xy(1, −4)(2, 5)y = x³ + 2x − 7
f(x) = x³ + 2x − 7 is continuous and changes sign between x = 1 and x = 2, so it crosses the x-axis there.

Not continuous

  • f(x)=1x−2f(x)=\frac1{x-2} on [1,3][1,3] changes sign
  • but never equals zero

Repeated root

  • (x−2)2(x-2)^2 touches the axis
  • no sign change, so the root is missed

f(1)=−4f(1)=-4 and f(2)=5f(2)=5 for a continuous ff. What can you conclude?

Interval bisection

Interval bisection repeatedly halves an interval that contains a root, keeping the half where the sign changes.

Find the midpoint m=a+b2m=\frac{a+b}{2} and evaluate f(m)f(m). If f(m)f(m) has the same sign as f(a)f(a), the root is in [m,b][m,b]; otherwise it is in [a,m][a,m].

After nn bisections the interval has width b−a2n\frac{b-a}{2^n}. The method is reliable but slow: roughly three or four steps for each extra decimal place.

  1. 1

    Find the midpoint

    m=a+b2m=\frac{a+b}{2}, and evaluate f(m)f(m)

  2. 2

    Compare signs

    If f(m)f(m) has the same sign as f(a)f(a), the root is in [m,b][m,b]; otherwise in [a,m][a,m]

  3. 3

    Repeat

    with the new, half-width interval

One bisection step

Worked example

f(x)=x3+2x−7f(x)=x^3+2x-7 has a root in [1,2][1,2]. Bisect twice.

A root is in [2,3][2,3]. After 3 bisections, what is the width of the interval?

Linear interpolation

Linear interpolation replaces the curve with the chord between the end points and takes where it meets the xx-axis as the next estimate.

Linear interpolation uses the straight line through (a,f(a))(a,f(a)) and (b,f(b))(b,f(b)). By similar triangles, with f(a)<0<f(b)f(a)<0<f(b):

x−a∣f(a)∣=b−x∣f(b)∣⇒x=a+∣f(a)∣∣f(a)∣+∣f(b)∣(b−a).\frac{x-a}{|f(a)|}=\frac{b-x}{|f(b)|}\quad\Rightarrow\quad x=a+\frac{|f(a)|}{|f(a)|+|f(b)|}(b-a).

Use the sign of ff at the new estimate to choose the next interval.

0.60.811.21.41.61.822.2−4−22468xy(1, −3)(2, 5)x = 1.375y = x³ + x − 5chord
For f(x) = x³ + x − 5 the chord from (1, −3) to (2, 5) meets the x-axis at x = 1.375, the first estimate of the root.
  • Estimate xxa+∣f(a)∣∣f(a)∣+∣f(b)∣(b−a)a+\dfrac{|f(a)|}{|f(a)|+|f(b)|}(b-a)

Worked example

Use linear interpolation twice on f(x)=x3+x−5f(x)=x^3+x-5 with f(1)=−3f(1)=-3 and f(2)=5f(2)=5.

In linear interpolation, f(a)=−2f(a)=-2 and f(b)=6f(b)=6 with a=1a=1, b=3b=3. What is the estimate?

Choosing and checking

Interpolation is usually faster when the curve is nearly straight, but bisection always halves the interval.

To prove a root is correct to a stated accuracy, find the interval of half the final unit either side. To show α=2.208\alpha=2.208 to 3 d.p., show f(2.2075)f(2.2075) and f(2.2085)f(2.2085) have opposite signs.

These methods find a root in an interval, not all roots: choose intervals with one sign change, and work in radians if ff involves trigonometry.

Bisection

Speed:
Always halves the interval
Behaviour:
Slow but reliable
Uses:
Uses signs only

Linear interpolation

Speed:
Usually faster on a near-straight curve
Behaviour:
Estimate can stay on one side of the root
Uses:
Uses the values of ff

To show a root is 1.461.46 to 2 d.p., which sign change do you show?

Try an exam question

f(x)=x3+2x−7f(x)=x^3+2x-7. Show that f(x)=0f(x)=0 has a root in [1,2][1,2], then use interval bisection twice to find an interval of width 0.250.25 containing the root.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the value of f(1.5)f(1.5).

1 mark, marked against the mark scheme

Revision notes