Numerical mathematics

Fourier transform

Metaphoric explanation

Given a smoothie, it finds the recipe.

How? Run the smoothie through filters to extract each ingredient.

Why? Recipes are easier to analyze, compare and modify than the smoothie itself,

How do we get the smoothie back? Blend the ingredients.

Mathematical motivation

The Fourier transform takes a time-based pattern, measure every possible cycle, and return the overall "cycle recipe" (amplitude, offset and rotation speed).

process

Requirements?

The filters are independent to each other, banana filters only capture banana, adding mango does not affect it.

The ingredients is blendable and the order of blending does not matter so that we always end up with the same smoothie.

The set of filters is complete, every ingredient is captured.

Circular path

Start with a time-based signal.

Apply filters to measure each possible "circular ingredient".

Collect the full recipe, listing the amount of each "circular ingredient".

Frequency (speed)

Phase angle (starting point)

Amplitude (size)

DFT

FFT

Motivation

How? Use FFT to find $(d+1)$ data points for each polynomials.

Why? It is easier to multiply data points then algebraic multiplication

How do we get the product? Just use the IFFT on the data points.

Evaluation example

Let $P(x)=x^3+x^2-x-1$ which has degree $d$

Formulas & explanation

click to edit

So we need $N=d+1$ data points in positive negative pairs

Let the pairs be $x_1, -x_1, x_2, -x_2$

Now we start from the beginning with evaluating $x_1\cdot(-x_1)=x_1^2$ and $x_2\cdot(-x_2)=x_2^2$ instead.

We need those two points to be a positive-negative pair s.t. $x_1^4=x_1^2\cdot x_2^2$

Remember we can choose the points, so let $x_1=1$.

Then $(x_1^2=1)\Rightarrow(-x_1^2=-1)\Rightarrow(x_2^2=-1)\Rightarrow(x_2=i,-x_2=-i)$

Which means $x_1^4=1$

Evaluation overview

Now split the polynimial in an od d and an even polynomial and repeat

Let $x_1=1$ and solve for $x_1^{N+1}=1$

Let the polynomial of degree $d$ have $2^k\ge d+1$ positive-negative data pairs

Given two polynomials, find the product in an efficient way.

Roots of unity

Solve for $z^n=1$.

Then the solutions are $\{\omega^0,\ldots,\omega^{N-1}\}$

Let $\omega=e^{i2\pi/n}$.

An important property for FFT is $\omega^{j+N/2}=-\omega^j$, i.e. they are positive-negative paired.

Integration

1 point per subinterval -> 0st degree rectangle top

Right sum

Midpoint rule

2 points per subinterval -> 1st degree rectangle top

Left sum

Right

Midpoint

Trapezoidal rule

Trapezoidal

\[\sum_{i=1}^nf\left(\frac{x_{i-1}+x_i}{2}\right)\Delta x\]

\[\sum_{i=1}^nf(x_i)\Delta x\]

\[\sum_{i=1}^nf(x_{i-1})\Delta x\]

\[\sum_{i=1}^n\frac{f(x_{i-1})+f(x_i)}{2}\Delta x\]

Left

3 points per subinterval - 2st degree rectangle top

Simpsons rule

click to edit

\[\sum_{i=1}^n\frac{f(x_{i-1})+4f\left(\frac{x_{i-1}+x_i}{2}\right)+f(x_i)}{6}\Delta x\]

Linear multistep method (LMM)

Orderf

Numerical terms

Stability

Condition number

Accuracy

Definition

A measure how sensitive a function is to changes in the input, and how much change in the output results from a change in the input.

Linear system $Ax=y$

$\mathrm{cond}(A)=|A^{-1}||A|$

$f:\mathbb{R}\to\mathbb{R}$

$f:\mathbb{R}^n\to\mathbb{R}$

$|x|\frac{|J(x)|}{|f(x)|}$

$\left|x\frac{f'(x)}{f(x)}\right|$

differential equations

linear algebra

Floating-representation

n points -

click to edit

gaussian integration