Cheatsheet

Binary Representation

Decimal to Binary

1. Multiply by 2, \(x^{(1)} = x_{10}^{(0)}\cdot2\), then:
   $$\begin{cases}
   \text{store 1, subtract 1} & \text{if } x^{(1)} > 0 \\
   \text{store 0} & \text{otherwise.}
   \end{cases}$$
2. If the pattern is repeating or \(x=0\) then stop.

Binary to Decimal

Example of converting \((0.\overline{1011})_{2}\) to decimal:

$$
\begin{aligned}
x &= (0.\overline{1011})_{2} \\
2^4x &= 1011.\overline{1011} \\
x &= 0000.\overline{1011} \\
(2^4-1)x &= (1011)_2 = (11)_{10} \\
x &= (.\overline{1011})_2 = \left(\frac{11}{15}\right)_{10}
\end{aligned}
$$

IEEE Floating Point Representation

When converting a binary representation to the floating-point representation \(fl(x)\) you have to normalize it, so the integer part is 1.

Round to nearest

For double precision, if the 53rd bit to the right of the binary point is 0, then round down (truncate after the 52nd bit). If the 53rd bit is 1, then round up (add 1 to the 52 bit), unless all known bits to the right of the 1 are 0’s, in which case 1 is added to bit 52 if and only if bit 52 is 1.

Absolute and Relative error

Absolute error: \(e_{abs} = |fl(x) - x|\)

Relative error: \(e_{rel}=\frac{e_{abs}}{x}\)

Fixed Point Iteration

• \(g(x)\) is a contraction for all \(x\) where \(|g'(x)| < 1\)
• Convergence rate \(S=|g'(x)|=\lim_{i \to \infty} \frac{e_{i+1}}{e_i}\)

Iterative Equation System Solvers

Jacobi Method

\(A = L + D + U\)

\(D\) is diagonal, \(L\) and \(U\) are lower and upper triangles of \(A\).

Rewrite the equation \(Ax=b\):

$$
\begin{aligned}
Ax &=b \\
(D+L+U)x &=b \\
Dx &=b-(L+U)x \\
x &=D^{-1}(b-(L+U)x).
\end{aligned}
$$

Iteration step: \(x_{k+1}=D^{-1}(b-(L+U)x_k)\)

Gauss-Seidel Method

Same as Jacobi Method but iteration uses latest calculated variables.

Iteration step: \(x_{k+1}=D^{-1}(b-Ux_{k}-Lx_{k+1})\)

Successive Over-Relaxation (SOR)

TODO

Norms

Properties that must hold for a function to be a norm:

• Triangle inequality: \(||x+y|| \leq ||x||+||y||\)
• Absolute homogeneity: \(||sx||=|s|\cdot||x||\)
• Positiveness: \(||x||=0 \iff x=0\)

Equivalent Norms

Suppose \(p\) and \(q\) are two norms. Then \(p \equiv q\) if there exists \(c,C\in \mathbb{R}^+\) with \(c > 0\) such that for every \(x \in X\), \(cq(x) \leq p(x) \leq Cq(x)\).

Vector Norm

\(||x||_p = \left(\sum_{i=1}^nx_i^p\right)^{\frac{1}{p}}\)

Matrix Norm

• \(\|A\|_1=\max_{1\leq j\leq n}\sum_{i=1}^m|a_{ij}|\)
• \(\|A\|_\infty=\max_{1\leq i\leq m}\sum_{j=1}^n|a_{ij}|\)
• \(\|A\|_2=\sqrt{\lambda_{\max}\left(A^*A\right)}=\sigma_{\max}(A)\)
• \(\|A\|_p=\sup_{x\neq0}\frac{\|Ax\|_p}{\|x\|_p}\)

Bezier Curves

Given \(
\begin{aligned}
&\text{endpoints }(x_{1},y_{1}),(x_{4},y_{4}) \\
&\text{control points } (x_2,y_2), (x_3,y_3)
\end{aligned}
\)

Set
$$
\begin{aligned}
&b_{x} =3(x_{2}-x_{1}) \\
&c_{x} =3(x_3-x_2)-b_x \\
&d_{x} =x_{4}-x_{1}-b_{x}-c_{x} \\
&b_{y} =3(y_2-y_1) \\
&c_{y} =3(y_3-y_2)-b_y \\
&d_{y} =y_4-y_1-b_y-c_y. \\
\\
&x(t)=x_{1}+b_{x}t+c_{x}t^{2}+d_{x}t^{3} \\
&y(t)=y_{1}+b_{y}t+c_{y}t^{2}+d_{y}t^{3}.
\end{aligned}
$$

Interpolation

Newton Interpolation

• Newton basis: \(B_0=1\), \(B_n = \prod_{m<n}(x-x_m)\)
• Divided Differences: The top diagonal contains the coefficients for the Newton Polynomial.

QR decomposition

\(A=QR\).

\(rank(A) = \#\{r_{ii}\neq 0 \mid i=1\ldots n\} \).

\(Q\) is orthogonal, which means it is square and \(Q^\top Q=I\).

This means \(A^\top A=(QR)^\top QR)=R^\top Q^\top QR=R^\top R\)