profile pic
⌘ '
raccourcis clavier

Machine epsilon

fl(x)=x(1+ϵ) where ϵufl(x) = x(1+\mathbf{\epsilon}) \space\text{where }|\epsilon|\leq{u} fl(x)xx=ϵu is called relative error.|\frac{fl(x)-x}{x}|=|\epsilon|\leq u \space\text{is called relative error.} Cancellations occur when subtracting nearby number containing roundoff.\text{Cancellations occur when subtracting nearby number containing roundoff.}

Taylor series

f(x)=k=0inff(k)(c)k!(xc)k En+1=f(n+1)(ξ)(n+1)!(h:=xc)n+1 En+1chn+1 \begin{aligned} f(x) &= \sum_{k=0}^{\inf}\frac{f^{(k)}(c)}{k!}(x-c)^k\\\ E_{n+1} &= \frac{f^{(n+1)}(\xi)}{(n+1)!}(h:=x-c)^{n+1}\\\ |E_{n+1}| \leq ch^{n+1}\\\ \end{aligned}

Polynomial Interpolation

v(x)=j=0ncjϕj(x) linearly independent iff v(x)=0  xcj=0  j)  Linear system: [ϕ0(x0)ϕ1(x0)ϕn(x0)ϕ0(x1)ϕ1(x1)ϕn(x1)ϕ0(xn)ϕ1(xn)ϕn(xn)][c0c1cn]=[y0y1yn]\begin{aligned} v(x) = &\sum_{j=0}^{n}c_j\phi_{j}(x) \space \rightarrow \text{linearly independent iff} \space v(x) = 0 \space \forall \space x \rightarrow c_j=0 \space \forall \space j)\\\ &\\\ \text{Linear system: } &\begin{bmatrix} \phi_0(x_0) & \phi_1(x_0) & \cdots & \phi_n(x_0) \\ \phi_0(x_1) & \phi_1(x_1) & \cdots & \phi_n(x_1) \\ \vdots & \vdots & \ddots & \vdots \\ \phi_0(x_n) & \phi_1(x_n) & \cdots & \phi_n(x_n) \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_n \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix} \end{aligned} Monomial basis: ϕj(x)=xj, j=0,1,...,n v(x)=j=0ncjxj pn(xi)=c0+c1xi+c2xi2++cnxin=yi  X:Vandermonde matrixdet(X)=i=0n1[j=i+1n(xjxi)] if xi are distinct:  det(X)0  X is nonsingular  system has unique solution  unique polynomial of degreen that interpolates the data  can be poorly conditioned, work is O(n3) \begin{aligned} \text{Monomial basis: }&\phi_j(x)=x^j, \space j=0,1,...,n \space \rightarrow v(x)=\sum_{j=0}^{n}c_jx^j\\\ &p_n(x_i) = c_0 + c_1x_i + c_2x_i^2 + \cdots + c_nx_i^n = y_i \\\ &\\\ X: &\text{Vandermonde matrix} \rightarrow \text{det}(X)=\prod_{i=0}^{n-1} \left[ \prod_{j=i+1}^{n} (x_j - x_i) \right]\\\ \text{if } &x_i \space\text{are distinct:}\\\ &\bullet\space \text{det}(X) \neq 0\\\ &\bullet\space X\space \text{is nonsingular}\\\ &\bullet\space \text{system has unique solution}\\\ &\bullet\space \text{unique polynomial of degree}\leq{n}\space \text{that interpolates the data}\\\ &\bullet\space \text{can be poorly conditioned, work is }O(n^3)\\\ \end{aligned} Lagrange basis: Lj(xi)={0if ij1if i=j Lj(x)=i=0,ijnxxixjxi pn(xi)=j=0nyjLj(xi)=j=0i1yjLj(xi)+yiLi(xi)+j=i+1nyjLj(xi)=yi \begin{aligned} \text{Lagrange basis: }&L_j(x_i) = \begin{cases} 0 & \text{if } i \neq j \\ 1 & \text{if } i = j \end{cases} \\\ &L_j(x) = \prod_{i=0,i\neq{j}}^{n}\frac{x-x_i}{x_j-x_i}\\\ &p_n(x_i) = \sum_{j=0}^{n} y_jL_j(x_i) = \sum_{j=0}^{i-1} y_jL_j(x_i) + y_iL_i(x_i) + \sum_{j=i+1}^{n} y_jL_j(x_i) = y_i\\\ \end{aligned} Newton’s basis: ϕj(x)=i=0j1(xxi),j=0:n pn(xi)=c0+c1(xix0)++cn(xix0)(xix1)(xixn1)=f(xi) \begin{aligned} \text{Newton's basis: }&\phi_j(x)=\prod_{i=0}^{j-1}(x-x_i), j=0:n\\\ &p_n(x_i)=c_0 + c_1(x_i-x_0)+ \cdots + c_n(x_i-x_0)(x_i-x_1)\cdots(x_i-x_{n-1})=f(x_i)\\\ \end{aligned} Divided differences: f[xi,,xj]=f[xi+1,,xj]f[xi,,xj1]xjxi  at x=x0 then c0=f(x0)=f[x0]  at x=x1 then c1=f(x1)f(x0)x1x0=f[x0,x1]  at x=x2 then c2=f(x2)c0c1(x2x0)(x2x0)(x2x1)=f(x2)f(x1)x2x1f(x1)f(x0)x1x0x2x0=f[x0,x1,x2]  x[a,b]  ξ=ξ(x)(a,b) : f(x)pn(x)=fn+1(ξ)(n+1)!i=0n(xxi)  Error: f(x)pn(x)M4(n+1)hn+1 where:   M=maxatbfn+1(t)  h=ban  xi=a+ih for i=0,1,,n\begin{aligned} &\text{Divided differences: }f[x_i,\cdots,x_j] = \frac{f[x_{i+1},\cdots,x_j]-f[x_i,\cdots,x_{j-1}]}{x_j-x_i}\\\ &\bullet\space\text{at } x=x_0 \text{ then } c_0 = f(x_0) = f[x_0]\\\ &\bullet\space\text{at } x=x_1 \text{ then } c_1 = \frac{f(x_1)-f(x_0)}{x_1-x_0} = f[x_0, x_1]\\\ &\bullet\space\text{at } x=x_2 \text{ then } c_2 = \frac{f(x_2)-c_0-c_1(x_2-x_0)}{(x_2-x_0)(x_2-x_1)} = \frac{\frac{f(x_2)-f(x_1)}{x_2-x_1}-\frac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0} = f[x_0, x_1, x_2]\\\ &\\\ &\therefore\forall x\in{[a,b]}\space\exists\space\xi=\xi(x)\in(a,b)\space : \space f(x)-p_n(x)=\frac{f^{n+1}(\xi)}{(n+1)!} \prod_{i=0}^{n} (x - x_i)\\\ &\therefore\space\text{Error: } |f(x)-p_n(x)|\leq\frac{M}{4(n+1)}h^{n+1}\\\ &\text{where: }\\\ &\bullet\space M=max_{a\leq{t}\leq{b}}|f^{n+1}(t)|\\\ &\bullet\space h=\frac{b-a}{n}\\\ &\bullet\space x_i=a+ih \text{ for }i=0,1,\cdots,n \end{aligned}

Basic Numeric Integration

If=abf(x)dxj=0najf(xj) (quadrature rule)  x0,,xn be distinct points in [a,b]  pn(x) be interpolating polynomial of f abf(x)dxabpn(x)dx  Uses Lagrange form: abf(x)dxj=0nf(xj)abLj(x)dx=j=0nf(xj)aj \begin{aligned} &I_f = \int_{a}^{b}{f(x)dx} \approx \sum_{j=0}^{n}a_jf(x_j)\space\text{(quadrature rule)}\\\ &\bullet\space x_0,\cdots,x_n\space\text{be distinct points in } [a,b]\\\ &\bullet\space p_n(x)\space\text{be interpolating polynomial of }f\rightarrow\space \int_{a}^{b}f(x)dx\approx\int_{a}^{b}p_n(x)dx\\\ &\bullet\space \text{Uses Lagrange form: }\int_{a}^{b}f(x)dx\approx\sum_{j=0}^{n}f(x_j)\int_{a}^{b}L_j(x)dx=\sum_{j=0}^{n}f(x_j)a_j\\\ \end{aligned} Trapezoidal rule: f(x)p1(x)=f(x0)L0(x)+f(x1)L1(x) (n=1,x0=a,x1=b)  If=abf(x)dxf(a)abxbabdx+f(b)abxabadx     =ba2[f(a)+f(b)] Error: f(x)p1(x)=12f(ξ(x))(xa)(xb) then: ab(f(x)p1(x))dx=12abf(ξ(x))(xa)(xb)dx From MVT:  η(a,b) : abf(ξ(x))(xa)(xb)dx=f(η)ab(xa)(xb)dx  Error of Trapezoidal rule:  IfItrap=f(η)12(ba)3 \begin{aligned} \text{Trapezoidal rule: } &f(x) \approx p_1(x)=f(x_0)L_0(x) + f(x_1)L_1(x)\space(n=1, x_0=a,x_1=b)\\\ \therefore\space &I_f=\int_{a}^{b}f(x)dx \approx f(a)\int_{a}^{b}{\frac{x-b}{a-b}dx} + f(b)\int_{a}^{b}{\frac{x-a}{b-a}dx} \\\ &\space\space\space\space=\frac{b-a}{2}[f(a) + f(b)]\\\ \text{Error: } &f(x) - p_1(x) = \frac{1}{2}f^{''}(\xi(x))(x-a)(x-b)\\\ \text{then: }&\int_{a}^{b}{(f(x)-p_1(x))dx} = \frac{1}{2}\int_{a}^{b}{f^{''}(\xi(x))(x-a)(x-b)dx}\\\ \text{From MVT: } &\exists\space\eta\in(a,b) \space : \space \int_{a}^{b}{f^{''}(\xi(x))(x-a)(x-b)dx} = f^{''}(\eta)\int_{a}^{b}{(x-a)(x-b)dx}\\\ \therefore\space&\text{Error of Trapezoidal rule: }\space I_f - I_{trap} = -\frac{f^{''}(\eta)}{12}(b-a)^3\\\ \end{aligned} Midpoint rule: IfImid=(ba)f(a+b2) Let m=a+b2f(x)=f(m)+f(m)(xm)+12f(ξ(x))(xm)2  If=abf(x)=(ba)f(m)+12abf(ξ(x))(xm)2dx  η(a,b) : 12abf(ξ(x))(xm)2dx=f(η)24(ba)3  Error of Midpoint rule:  IfImid=f(η)24(ba)3 \begin{aligned} \text{Midpoint rule: } &I_f \approx I_{mid} = (b-a)f(\frac{a+b}{2})\\\ &\text{Let } m=\frac{a+b}{2}\rightarrow f(x)=f(m)+f^{'}(m)(x-m)+\frac{1}{2}f^{''}(\xi(x))(x-m)^2\\\ \therefore\space&I_f = \int_{a}^{b} f(x) = (b - a)f(m) + \frac{1}{2} \int_{a}^{b} f''(\xi(x))(x - m)^2 \, dx\\\ &\exists\space\eta\in(a,b)\space : \space \frac{1}{2} \int_{a}^{b} f''(\xi(x))(x - m)^2 \, dx = \frac{f''(\eta)}{24}(b - a)^3\\\ \therefore\space&\text{Error of Midpoint rule: }\space I_f - I_{mid} = \frac{f^{''}(\eta)}{24}(b-a)^3\\\ \end{aligned}