Foundations of numerical computing · Lecture 3

Taylor Series and Order of Accuracy

Almost every formula in this course comes from a Taylor series cut off after a few terms. The first neglected term tells us the error, and "O(h²)" tells us how fast it shrinks.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Today's goals

Write the Taylor series of a function and its remainder term
Approximate values and bound the truncation error using the remainder
Explain big-O notation and the order of accuracy of a method
Derive the forward and central difference formulas and their $O(h)$ , $O(h^2)$ errors
See the Taylor series as the engine of later methods: Newton (L9), difference operators (L15), ODE solvers (L21)

Last time

Round-off: doubles keep about 16 significant digits ( $\varepsilon \approx 2.2\times10^{-16}$ ).

Today

The other source of error, truncation. The Taylor series lets us predict it before computing anything, and compare methods by their order.

Foundations of numerical computing · you are here

L1 · Why Numerical Methods?→L2 · Floating-Point Numbers→L3 · Taylor Series and Order of Accuracy→L4 · Errors and Their Propagation→L5 · Conditioning and Stability

Builds on: L1

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

2 / 15

Start here

The idea in one picture

The true curve sin x: hard to compute directly.One term: a straight line. Good only very close to 0.Two terms: the curve is followed further out.Three terms: almost exact from −π/2 to π/2.More terms = wider good zone. The part we cut off is the truncation error.

In plain words

Near one point, any smooth curve looks like a simple polynomial
More terms: the polynomial follows the curve further away
What we leave out is an error we can estimate in advance

New words today

Taylor series: a function written as a sum of powers of (x − a)
truncation: stopping after a finite number of terms
remainder: the part that was cut off
order: how fast the error shrinks when the step shrinks

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

3 / 15

The Taylor series

About the point a

\begin{aligned} f(x) = {} & f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 \\ & + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n + R_n(x) \end{aligned}

Lagrange remainder (the error of stopping at degree n)

R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}(x-a)^{n+1}, \qquad \xi \text{ between } a \text{ and } x

$a = 0$ gives the Maclaurin series
The polynomial matches $f$ , $f'$ , $f''$ , … at $a$
We never know $\xi$ , but we can bound $|f^{(n+1)}|$ on the interval, which bounds the error
Close to $a$ , $(x-a)^{n+1}$ is tiny: the approximation is excellent

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

4 / 15

Series worth knowing by heart

$e^{x}$

all $x$

1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots

$\sin x$

all $x$ (radians)

x - \frac{x^3}{3!} + \frac{x^5}{5!} - \cdots

$\cos x$

all $x$ (radians)

1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \cdots

$\ln(1+x)$

$-1 < x \le 1$ only

x - \frac{x^2}{2} + \frac{x^3}{3} - \cdots

$\dfrac{1}{1-x}$

$|x| < 1$ only

1 + x + x^2 + x^3 + \cdots

$\sqrt{1+x}$

$|x| \le 1$

1 + \frac{x}{2} - \frac{x^2}{8} + \cdots

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

5 / 15

Explore: adding terms

Increase the degree: the polynomial hugs $f$ over a wider range
The error at a point is close to the first neglected term
Choose $\ln(1+x)$ and go past $x = 1$ : more terms make it worse
Choose $\sin x$ : odd degrees only add new terms

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

6 / 15

Problem 1: $e^{0.5}$ with an error bound

Problem 1Approximate

e^{0.5}

using the first four terms of the Maclaurin series, and bound the error.

1

e^{x} \approx 1 + x + \dfrac{x^2}{2} + \dfrac{x^3}{6}

, so

e^{0.5} \approx 1 + 0.5 + 0.125 + 0.0208333 = 1.6458333

2

Remainder:

R_3 = \dfrac{e^{\xi}}{4!}(0.5)^4

with

0 < \xi < 0.5

3

Bound:

e^{\xi} < e^{0.5} < 2

, so

|R_3| < \dfrac{2 \times 0.0625}{24} = 0.0052

(sharper:

e^{0.5}(0.5)^4/24 = 0.0043

)

4

Check: true

e^{0.5} = 1.6487213

, actual error

= 0.0028879

, inside the bound ✓

e^{0.5} \approx 1.6458

with error less than

0.005

. The bound is honest (never too small) but a little pessimistic.

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

7 / 15

How many terms do we need?

Problem 2How many terms of

e^{x} = \sum x^k/k!

are needed to compute

e

(that is,

x = 1

) with error less than

10^{-6}

?

1

Stopping after degree

n

:

|R_n| = \dfrac{e^{\xi}}{(n+1)!} < \dfrac{3}{(n+1)!}

since

e^{\xi} < e < 3

2

Need

\dfrac{3}{(n+1)!} < 10^{-6}

, i.e.

(n+1)! > 3\times10^{6}

3

9! = 362{,}880

(too small),

10! = 3{,}628{,}800

✓, so

n + 1 = 10

,

n = 9

4

Degree 9 means the terms

k = 0, 1, \dots, 9

: 10 terms. Check:

\sum_{k=0}^{9} 1/k! = 2.7182815

, error

3.0\times10^{-7}

✓

10 terms. This is how library designers decide the length of a polynomial: from the remainder bound, before writing any code.

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

8 / 15

Step form and big-O notation

Taylor series with step h

f(x+h) = f(x) + h f'(x) + \frac{h^2}{2} f''(x) + \frac{h^3}{6} f'''(x) + \cdots

Big-O

E(h) = O(h^p) \iff |E(h)| \le C\,h^p \text{ for small } h

Order of accuracy

E(h/2) \approx E(h)/2^{p} \qquad \Rightarrow \qquad p \approx \log_2 \frac{E(h)}{E(h/2)}

$O(h)$ : halve $h$ → error halves (first order)
$O(h^2)$ : halve $h$ → error ÷ 4 (second order)
$O(h^4)$ : halve $h$ → error ÷ 16 (RK4, Simpson)
Higher order = far fewer steps for the same accuracy

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

9 / 15

Deriving the difference formulas

Problem 3From the Taylor series, derive the forward and central difference approximations of

f'(x)

and their truncation errors.

1

Forward:

f(x+h) = f(x) + hf'(x) + \tfrac{h^2}{2}f''(\xi)

⟹

f'(x) = \dfrac{f(x+h) - f(x)}{h} - \underbrace{\tfrac{h}{2}f''(\xi)}_{O(h)}

2

Write both

f(x \pm h) = f(x) \pm hf'(x) + \tfrac{h^2}{2}f''(x) \pm \tfrac{h^3}{6}f'''(x) + \cdots

3

Subtract:

f(x+h) - f(x-h) = 2hf'(x) + \tfrac{h^3}{3}f'''(x) + \cdots

(the

f

and

f''

terms cancel)

4

Divide by

2h

:

f'(x) = \dfrac{f(x+h) - f(x-h)}{2h} - \underbrace{\tfrac{h^2}{6}f'''(x)}_{O(h^2)} + \cdots

Forward difference: error

O(h)

. Central difference: error

O(h^2)

, for one extra function evaluation per point… and a much better answer.

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

10 / 15

Checking the order: $f(x) = \ln x$ at $x = 1$ (exact $f'(1) = 1$ )

$h$	forward	error	central	error	central error ratio
0.1	0.9531018	−4.69e−2	1.0033535	3.35e−3	—
0.05	0.9758033	−2.42e−2	1.0008346	8.35e−4	4.01
0.025	0.9877045	−1.23e−2	1.0002084	2.08e−4	4.00
0.0125	0.9938016	−6.20e−3	1.0000521	5.21e−5	4.00

Forward errors halve when h halves (order 1). Central errors fall by 4 (order 2). Theory: central error ≈ $\tfrac{h^2}{6}f'''(1) = \tfrac{h^2}{6}\cdot 2$ = 0.00333 for $h = 0.1$ ✓

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

11 / 15

Practice

Practice problem

Problem 4"Starting from the Taylor series expansion of

f(x)

about a point

x

, derive the central-difference approximation of

f'(x)

and show that its truncation error is

O(h^2)

. Using this formula with

h = 0.1

, estimate

f'(1)

for

f(x) = \ln x

. Compare your result with the exact derivative and compute the actual error, commenting on whether it is consistent with the theoretical

O(h^2)

order."

How to write a complete answer

Derivation as shown earlier: expand $f(x\pm h)$ , subtract, divide by $2h$ , name the leading error term $-\tfrac{h^2}{6}f'''(x)$
Numbers: $\dfrac{\ln 1.1 - \ln 0.9}{0.2} = \dfrac{0.0953102 + 0.1053605}{0.2} = 1.0033535$
Exact $f'(1) = 1$ ; actual error $= 0.0033535$
Theory: $\tfrac{h^2}{6}|f'''(1)| = \tfrac{0.01}{6}\times 2 = 0.0033333$ : matches, so consistent with $O(h^2)$
Add: halving $h$ to 0.05 gives error $8.35\times10^{-4}$ , a factor 4 smaller

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

12 / 15

Beyond the classroom

Where this shows up in CSE and machine learning

⬇️

Gradient descent is first-order Taylor

$L(w + \Delta) \approx L(w) + \nabla L^{T}\Delta$ . The decrease is largest for $\Delta = -\eta\nabla L$ : that is the update rule (Lecture 25).

🎯

Newton's method is second-order Taylor

Adding $\tfrac12\Delta^T H \Delta$ (the Hessian) and minimising gives Newton's step: the basis of fast optimisers.

🧮

Activation functions on chips

$\tanh$ , $e^x$ and GELU are computed with short polynomials whose length comes from remainder bounds.

🔁

Backpropagation checks

Gradient checking compares backprop with $\frac{L(w+h)-L(w-h)}{2h}$ , the central difference, with $h \approx 10^{-5}$ : the best step size, explained in Lecture 4.

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

13 / 15

Checkpoint

Checkpoint · think, then discuss with your neighbourA method gives error

8\times10^{-4}

with step

h

and

5\times10^{-5}

with step

h/2

. What is its order?

A1

B2

C3

D4

D. The ratio is

8\times10^{-4}/5\times10^{-5} = 16 = 2^4

, so

p = \log_2 16 = 4

.

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

14 / 15

Summary

Key points

Taylor: $f(x) = \sum \frac{f^{(k)}(a)}{k!}(x-a)^k + R_n$ , with $R_n = \frac{f^{(n+1)}(\xi)}{(n+1)!}(x-a)^{n+1}$
Bound $|f^{(n+1)}|$ to bound the truncation error; choose $n$ from the bound
$O(h^p)$ : halving $h$ divides the error by $2^p$ ; measure $p$ from two step sizes
Forward difference $O(h)$ ; central difference $O(h^2)$
Every method later in the course (Newton, difference formulas, Simpson, Runge–Kutta) is a truncated Taylor series

Homework

Approximate $\sin(\pi/4)$ with three non-zero terms of the Maclaurin series and bound the error.
How many terms of the series for $\cos x$ give $\cos 1$ with error below $10^{-8}$ ?
Derive the backward difference $f'(x) \approx [f(x) - f(x-h)]/h$ and its error term.
Lab: run the order program for $f(x) = e^x$ at $x = 0$ . Confirm the orders 1 and 2.

Next lecture

Errors and their propagation. Measuring errors, how round-off and truncation errors combine and grow through arithmetic, catastrophic cancellation, and the best step size $h$ .

Md Mahbub E Noor

Lecture 3: Taylor Series and Order of Accuracy

University of Barishal

15 / 15

Taylor Series and Order of Accuracy

Today's goals

The idea in one picture

The Taylor series

Series worth knowing by heart

exe^{x}ex

sin⁡x\sin xsinx

cos⁡x\cos xcosx

ln⁡(1+x)\ln(1+x)ln(1+x)

11−x\dfrac{1}{1-x}1−x1​

1+x\sqrt{1+x}1+x​

Explore: adding terms

Problem 1: e0.5e^{0.5}e0.5 with an error bound

How many terms do we need?

Step form and big-O notation

Deriving the difference formulas

Checking the order: f(x)=ln⁡xf(x) = \ln xf(x)=lnx at x=1x = 1x=1 (exact f′(1)=1f'(1) = 1f′(1)=1)

Practice problem

Where this shows up in CSE and machine learning

Gradient descent is first-order Taylor

Newton's method is second-order Taylor

Activation functions on chips

Backpropagation checks

Checkpoint

Summary

$e^{x}$

$\sin x$

$\cos x$

$\ln(1+x)$

$\dfrac{1}{1-x}$

$\sqrt{1+x}$

Problem 1: $e^{0.5}$ with an error bound

Checking the order: $f(x) = \ln x$ at $x = 1$ (exact $f'(1) = 1$ )