Data fitting and optimization for machine learning · Lecture 24

Polynomial, Exponential and Trigonometric Fitting

Curved trends with the same least-squares machinery: polynomial regression, straightening growth and power laws with logarithms, fitting periodic data, and choosing a model that follows the trend without memorising the noise.

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

Why this lecture

The problem: how fast do the bacteria double?

A lab counts bacteria every hour. Each hour the count is multiplied by about 1.5. When does the culture double, and how many cells will there be after 8 hours?

A straight line misses the curve: residuals $+74, -5, -55, -76, -36, +96$ , and it predicts only 1063 cells at 8 h
The model is $N = ae^{bt}$ : $b$ is inside the exponential, not linear in the unknowns
Least squares from Lecture 23 needs a model linear in its coefficients
Idea: take logarithms, and the curve becomes a straight line

time $t$ (h)	count $N$
0	100
1	150
2	230
3	340
4	510
5	770
8	?

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

2 / 23

Today's goals

Fit a polynomial of degree $m$ by least squares (normal equations of size $m + 1$ )
Linearise $y = ae^{bx}$ and $y = ax^{b}$ with logarithms and fit them
Fit a trigonometric model to periodic data
Recognise overfitting and choose the degree by test error
Know what linearisation changes, and when a direct nonlinear fit is needed

Last time

Least squares for $y = a + bx$ ; matrix form $A^{T}A\mathbf{c} = A^{T}\mathbf{y}$ ; conditioning (Lecture 23).

Today

Same normal equations with new columns: $x^2, x^3, \dots$ , $\cos\omega x$ , $\sin\omega x$ ; and logarithms for growth laws.

Data fitting and optimization for machine learning · you are here

L23 · Least Squares and Linear Regression→L24 · Polynomial, Exponential and Trigonometric Fitting→L25 · Numerical Optimization for Machine Learning

Builds on: L23

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

3 / 23

Start here

The idea in one picture

Bacteria counts: they grow faster and faster.The model is an exponential curve. A line fit (Lecture 23) cannot handle it directly.Trick: take the logarithm of every count.Plot ln N against t …… the dots now lie on a straight line.Fit that line with last lecture's formulas, then read b and a from its slope and intercept.

In plain words

Many laws are curves: growth, decay, powers, cycles
A logarithm can turn a curve into a straight line
Then last lecture's line fit does the work

New words today

linearise: transform the data so the model becomes a line
polynomial fit: least squares with x², x³, … added
overfitting: following the noise instead of the trend
test error: error on data not used for the fit

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

4 / 23

Polynomial least squares: more columns, same method

Model of degree m, and its least-squares criterion

\hat y = a_0 + a_1x + a_2x^2 + \cdots + a_mx^m, \qquad S = \sum_{i}\big(y_i - \hat y_i\big)^2

Parabola (m = 2): set ∂S/∂a₀ = ∂S/∂a₁ = ∂S/∂a₂ = 0

\begin{bmatrix} n & \sum x & \sum x^2 \\ \sum x & \sum x^2 & \sum x^3 \\ \sum x^2 & \sum x^3 & \sum x^4 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} \sum y \\ \sum xy \\ \sum x^2y \end{bmatrix}

Still linear in the unknowns $a_0, \dots, a_m$ : the curve is nonlinear, the problem is not
Entry $(j, k)$ is $\sum x^{j+k}$ : this is $A^{T}A$ with columns $1, x, x^2$
Need $n > m + 1$ points (with $n = m + 1$ it is interpolation)
Solve by Gaussian elimination or Cholesky (Lectures 12–13)

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

5 / 23

The method, step by step

Polynomial fitting, step by step

Choose the degree $m$ (plot the data first; start low)
Tabulate the powers: $\sum x^k$ for $k = 0, \dots, 2m$ and $\sum x^ky$ for $k = 0, \dots, m$
Fill the $(m + 1) \times (m + 1)$ normal equations: entry $(j, k) = \sum x^{j+k}$
Solve for $a_0, \dots, a_m$ (Gauss with pivoting)
Compute residuals, $S$ , $R^2$ ; check the pattern; for new $x$ evaluate by Horner

Pseudocode

input x[1..n], y[1..n], degree m
for k = 0 … 2m:  P[k] ← Σ x^k
for k = 0 … m:   r[k] ← Σ x^k·y
for j, k = 0 … m:
    M[j][k] ← P[j + k]
a ← solve(M, r)      # Gauss / Cholesky
S ← Σ (y − poly(a, x))²
return a, S

For large $m$ use QR on centred, scaled $x$ instead (see the limitations).

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

6 / 23

Problem 1: fit a parabola $y = a_0 + a_1x + a_2x^2$

Data:

x

= 1, 2, 3, 4, 5, 6;

\;y

= 2.1, 3.9, 8.2, 15.8, 26.1, 37.7. A straight line leaves the residual pattern

+, -, -, -, -, +

.

sum	value	sum	value
$n$	6	$\sum y$	93.8
$\sum x$	21	$\sum xy$	454.4
$\sum x^2$	91	$\sum x^2y$	2354
$\sum x^3$	441
$\sum x^4$	2275

Normal equations:

6a_0 + 21a_1 + 91a_2 = 93.8

,

\;21a_0 + 91a_1 + 441a_2 = 454.4

,

\;91a_0 + 441a_1 + 2275a_2 = 2354

. Solving: $a_0 = 2.580$ , $a_1 = -1.9193$ , $a_2 = 1.3036$ .

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

7 / 23

Explore: choose the model and the degree

Raise the degree: $S$ always falls, but does the curve still look sensible?
Bacteria preset: compare "polynomial" with "exponential"
Pendulum: the power law $T = aL^{b}$ gives $b \approx 0.5$
Temperature: one sine wave per day

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

8 / 23

Linearisation: straighten the curve, then fit a line

Exponential: plot ln y against x

y = ae^{bx} \;\Longrightarrow\; \underbrace{\ln y}_{Y} = \underbrace{\ln a}_{A} + b\,x

Power law: plot ln y against ln x

y = ax^{b} \;\Longrightarrow\; \underbrace{\ln y}_{Y} = \underbrace{\ln a}_{A} + b\,\underbrace{\ln x}_{X}

Saturation (Michaelis–Menten): plot 1/y against 1/x

y = \frac{ax}{b + x} \;\Longrightarrow\; \frac1y = \frac1a + \frac ba\cdot\frac1x

Fit $Y = A + bX$ with Lecture 23's formulas, then $a = e^{A}$
Test: if the transformed points lie on a line, the model is right
Needs $y > 0$ (and $x > 0$ for the power law)
Caution: this minimises errors in $\ln y$ , not in $y$ , so large $y$ get less weight

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

9 / 23

Problem 2: fit $N = ae^{bt}$ to the bacteria counts

1

Y = \ln N

: 4.6052, 5.0106, 5.4381, 5.8289, 6.2344, 6.6464

2

\sum t = 15

,

\sum t^2 = 55

,

\sum Y = 33.76363

,

\sum tY = 91.54323

,

n = 6

3

b = \dfrac{6(91.54323) - 15(33.76363)}{6(55) - 15^2} = \dfrac{42.80493}{105} = 0.407666

4

A = \dfrac{33.76363 - 15(0.407666)}{6} = 4.608108

,

\;a = e^{A} = 100.29

5

Doubling time

\ln 2/b = 1.70

h;

\;N(8) = 100.29\,e^{0.407666 \times 8} \approx 2616

N = 100.3\,e^{0.4077t}

: the count grows 50.3% per hour (

e^{b} = 1.503

) and doubles every 1.70 hours.

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

10 / 23

Problem 3: a power law for the pendulum, $T = aL^{b}$

Lengths

L

(m) = 0.25, 0.5, 1, 1.5, 2; periods

T

(s) = 1.00, 1.42, 2.01, 2.46, 2.84. Find

a

and

b

.

1

X = \ln L

:

-1.3863, -0.6931, 0, 0.4055, 0.6931

2

Y = \ln T

:

0, 0.3507, 0.6981, 0.9002, 1.0438

3

Line fit of

Y

on

X

:

b = 0.5018

,

\;A = 0.6970

4

a = e^{0.6970} = 2.0077

T = 2.008\,L^{0.502}

. Theory:

T = \dfrac{2\pi}{\sqrt g}L^{1/2} = 2.006\,L^{0.5}

: the fit recovers the physics, and

g = (2\pi/a)^2 = 9.79

m/s².

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

11 / 23

Periodic data: a trigonometric fit

Known period P, ω = 2π/P; still linear in a₀, a₁, b₁

\hat y = a_0 + a_1\cos\omega x + b_1\sin\omega x

n points equally spaced over one period: the normal equations decouple

a_0 = \frac1n\sum y_i, \quad a_1 = \frac2n\sum y_i\cos\omega x_i, \quad b_1 = \frac2n\sum y_i\sin\omega x_i

Amplitude and time of the peak

C = \sqrt{a_1^2 + b_1^2}, \qquad \hat y = a_0 + C\cos\big(\omega(x - x_{\text{peak}})\big)

Temperature every 3 h over a day ( $P = 24$ ): $a_0 = 27.44$ , $a_1 = -4.12$ , $b_1 = -3.64$
Amplitude $C = 5.50$ °C; peak at $\omega x = \text{atan2}(b_1, a_1)$ : about 14.8 h (2:45 pm)
More harmonics ( $\cos 2\omega x$ , …) give the Fourier series: the FFT does this fast
Tides, seasons, electricity demand, heart rhythms

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

12 / 23

Choosing the degree

Overfitting: a perfect fit to the training data, a bad model

Ten noisy samples of $\sin 2\pi x$ ; "test error" compares the fit with the true curve
Degree 1: underfits (train 0.62, test 0.46)
Degree 3–5: test error lowest (about 0.12)
Degree 9: passes through every point (train 0) but test error 0.58: it memorised the noise
Choose the degree by error on data not used for fitting

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

13 / 23

Classical vs numerical

Same growth data, two approaches

Logarithms

Classical (linearise by hand)

Take $\ln N$ , fit a line with the sums formulas
$a = 100.29$ , $b = 0.407666$
Works only for models that can be straightened

vs

Algorithm

Numerical (minimise $S$ directly)

Minimise $\sum (N_i - ae^{bt_i})^2$ by Gauss–Newton
$a = 100.44$ , $b = 0.407153$ in 3 iterations
Any model, errors measured in the original units

When the classical approach cannot work

Logistic growth $N = \dfrac{K}{1 + e^{-r(t - t_0)}}$ with unknown capacity $K$

No logarithm turns this into a straight line in $K$ , $r$ and $t_0$ together. The only way is to minimise $S(K, r, t_0)$ iteratively: Gauss–Newton or gradient descent (Lecture 25). This is how epidemic and market-adoption curves are fitted.

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

14 / 23

Polynomial and exponential fits in code

Builds the $(m+1) \times (m+1)$ normal equations from power sums
Gaussian elimination with pivoting
Prints coefficients, $S$ and $R^2$
Lab: the exponential fit through logarithms

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

15 / 23

When curve fitting misleads

Limitations shown failing

problem	what happens	remedy
High degree, normal equations	cond( $A^{T}A$ ) for 10 points in $[0, 1]$ : degree 3: $10^{4}$ , degree 5: $10^{7}$ , degree 9: $2\times10^{14}$	centre and scale $x$ ; QR; orthogonal polynomials
Overfitting	degree 9 through 10 noisy points: train error 0, test error 0.58	choose the degree by validation; regularise (ridge)
Extrapolating a polynomial	Lecture 23 data, degree 5: 40.4 min at 12 km, 32.9 at 13 km	use a model with physical meaning; do not extrapolate far
Log transform	needs $y > 0$ ; a count of 0 gives $\ln 0 = -\infty$	add a small constant, or fit directly
Log transform weights	minimises relative error: small $y$ dominate, large $y$ fit worse	weights $w_i = y_i^2$ , or Gauss–Newton (L25)

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

16 / 23

Practice

Practice problem

Problem 4"Fit a second-degree parabola

y = a + bx + cx^2

to the data

x

: 0, 1, 2, 3, 4 and

y

: 1, 1.8, 1.3, 2.5, 6.3 by the method of least squares."

How to write a complete answer

Sums: $\sum x = 10$ , $\sum x^2 = 30$ , $\sum x^3 = 100$ , $\sum x^4 = 354$ , $\sum y = 12.9$ , $\sum xy = 37.1$ , $\sum x^2y = 130.3$
Normal equations: $5a + 10b + 30c = 12.9$ ; $\;10a + 30b + 100c = 37.1$ ; $\;30a + 100b + 354c = 130.3$
Eliminate: $c = 0.55$ , $\;b = -1.07$ , $\;a = 1.42$
Answer $y = 1.42 - 1.07x + 0.55x^2$ ; check one residual, e.g. at $x = 4$ : $1.42 - 4.28 + 8.8 = 5.94$ vs 6.3

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

17 / 23

When to use it

Polynomial, exponential and trigonometric fitting: method profile

Best case

Smooth trends with noise; low degree (1–3)
Growth and decay (exponential) or scaling laws (power) seen as straight lines on log axes
Periodic data with a known period

Worst case

High-degree polynomials: ill-conditioned, wiggly, extrapolate badly
Log transforms with zeros or very noisy small values
Models that cannot be made linear in the parameters

Best suited for

Growth of populations, investments, epidemics (early phase)
Physics and engineering laws ( $T \propto L^{1/2}$ , Kepler $T \propto a^{3/2}$ )
Seasonal and daily cycles

Avoid when

Choosing the degree by $R^2$ on the same data
Predicting far beyond the data with polynomials
Fitting $\ln y$ when errors in $y$ matter (use a direct fit)

Rule of thumb: pick the model from the physics or from the shape on log axes, keep the degree low, and check it on data not used for fitting.

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

18 / 23

Comparative analysis: models for curved data

Model	Linear in unknowns?	How to fit	Size of system	Typical use
$a + bx$	yes	sums formulas (L23)	2 × 2	trends
$a_0 + a_1x + \dots + a_mx^m$	yes	normal equations / QR	$(m+1)$ square	smooth curves, low $m$
$ae^{bx}$	no, but linearisable	line fit to $(x, \ln y)$	2 × 2	growth, decay, cooling
$ax^{b}$	no, but linearisable	line fit to $(\ln x, \ln y)$	2 × 2	scaling laws
$a_0 + a_1\cos\omega x + b_1\sin\omega x$	yes (ω known)	decoupled formulas	3 diagonal	cycles, seasons
$\dfrac{K}{1 + e^{-r(t - t_0)}}$	no	Gauss–Newton (L25)	iterative	saturation, adoption

"Linear least squares" means linear in the coefficients, not a straight-line curve.

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

19 / 23

Roadmap

Limitations, and where we fix them

Every fit so far was a single linear solve. The last lecture replaces the linear solve with an iteration that can minimise anything.

What it does well (keep this)

Any model linear in its coefficients: one linear solve
Logarithms straighten growth and power laws
Trigonometric terms for cycles
Validation error picks the degree

LimitationHow it is overcomeWhere

Linearisation fits

\ln y

, not

y

→

Fit the original model directly: Gauss–Newton

Lecture 25 →

Models that cannot be linearised (logistic, neural networks)

→

Minimise

S

by gradient descent

Lecture 25 →

Choosing a regularisation λ and a degree

→

Minimise validation error: a 1-D optimisation (golden section)

Lecture 25 →

Huge data sets: forming

A^{T}A

is too costly

→

Stochastic gradient descent, one batch at a time

Lecture 25 →

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

20 / 23

Applications

Where this method runs in the real world

Click a card to fit real-world laws.

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

21 / 23

Checkpoint

Checkpoint · think, then discuss with your neighbourTo fit

y = ae^{bx}

by linearisation, which pairs do you put into the straight-line formulas?

A

(x_i, \ln y_i)

B

(\ln x_i, \ln y_i)

C

(\ln x_i, y_i)

D

(x_i, y_i)

, then take logs of

a

and

b

A.

\ln y = \ln a + bx

is a line in

x

and

\ln y

; the slope is

b

and

a = e^{\text{intercept}}

. Option B is for the power law

y = ax^{b}

.

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

22 / 23

Summary

Key points

Polynomial of degree $m$ : $(m+1)$ normal equations with entries $\sum x^{j+k}$ ; keep $m$ low
$y = ae^{bx}$ : line through $(x, \ln y)$ ; $\;y = ax^{b}$ : line through $(\ln x, \ln y)$
Periodic: $a_0 + a_1\cos\omega x + b_1\sin\omega x$ ; equally spaced data decouple
Choose the model by validation error, not by training error

Opening problem: solved

$N = 100.3\,e^{0.4077t}$ : the bacteria double every 1.70 hours, and after 8 hours there will be about 2600 cells (direct nonlinear fit: 2609).

Homework

Fit $y = a + bx + cx^2$ to $x$ : 1, 2, 3, 4, 5, 6 and $y$ : 2.1, 3.9, 8.2, 15.8, 26.1, 37.7 and verify Problem 1.
Fit $y = ae^{bx}$ to $x$ : 0, 1, 2, 3 and $y$ : 2.0, 3.3, 5.4, 9.0.
Fit $y = ax^{b}$ to $x$ : 1, 2, 4, 8 and $y$ : 3.0, 4.2, 6.1, 8.4.
With the overfitting widget, record train and test error for degrees 0–9 and explain the shape of both curves.

Next lecture

Lecture 25: numerical optimisation for machine learning. Golden-section search, gradient descent, Newton and Gauss–Newton: minimising any error function.

Md Mahbub E Noor

Lecture 24: Polynomial, exponential and trigonometric fits

University of Barishal

23 / 23

Polynomial, Exponential and Trigonometric Fitting

The problem: how fast do the bacteria double?

Today's goals

The idea in one picture

Polynomial least squares: more columns, same method

Polynomial fitting, step by step

Problem 1: fit a parabola $y = a_0 + a_1x + a_2x^2$

Explore: choose the model and the degree

Linearisation: straighten the curve, then fit a line

Problem 2: fit $N = ae^{bt}$ to the bacteria counts

Problem 3: a power law for the pendulum, $T = aL^{b}$

Periodic data: a trigonometric fit

Overfitting: a perfect fit to the training data, a bad model

Same growth data, two approaches

Classical (linearise by hand)

Numerical (minimise $S$ directly)

Logistic growth $N = \dfrac{K}{1 + e^{-r(t - t_0)}}$ with unknown capacity $K$

Polynomial and exponential fits in code

Limitations shown failing

Practice problem

Polynomial, exponential and trigonometric fitting: method profile

Comparative analysis: models for curved data

Limitations, and where we fix them

Where this method runs in the real world

🪐 Kepler's third law

💻 Moore's law

🌡️ Daily and seasonal cycles

💊 Drug concentration in blood

Checkpoint

Summary

Polynomial, Exponential and Trigonometric Fitting

The problem: how fast do the bacteria double?

Today's goals

The idea in one picture

Polynomial least squares: more columns, same method

Polynomial fitting, step by step

Problem 1: fit a parabola y=a0+a1x+a2x2y = a_0 + a_1x + a_2x^2y=a0​+a1​x+a2​x2

Explore: choose the model and the degree

Linearisation: straighten the curve, then fit a line

Problem 2: fit N=aebtN = ae^{bt}N=aebt to the bacteria counts

Problem 3: a power law for the pendulum, T=aLbT = aL^{b}T=aLb

Periodic data: a trigonometric fit

Overfitting: a perfect fit to the training data, a bad model

Same growth data, two approaches

Classical (linearise by hand)

Numerical (minimise SSS directly)

Logistic growth N=K1+e−r(t−t0)N = \dfrac{K}{1 + e^{-r(t - t_0)}}N=1+e−r(t−t0​)K​ with unknown capacity KKK

Polynomial and exponential fits in code

Limitations shown failing

Practice problem

Polynomial, exponential and trigonometric fitting: method profile

Comparative analysis: models for curved data

Limitations, and where we fix them

Where this method runs in the real world

🪐 Kepler's third law

💻 Moore's law

🌡️ Daily and seasonal cycles

💊 Drug concentration in blood

Checkpoint

Summary

Problem 1: fit a parabola $y = a_0 + a_1x + a_2x^2$

Problem 2: fit $N = ae^{bt}$ to the bacteria counts

Problem 3: a power law for the pendulum, $T = aL^{b}$

Numerical (minimise $S$ directly)

Logistic growth $N = \dfrac{K}{1 + e^{-r(t - t_0)}}$ with unknown capacity $K$