Numerical Analysis

gradient descent

line search

gradient descent momentum

stochastic gradient descent (SGD)

integration

followed from Riemann sum

$f\in c[a,b]$, partition evenly into $N$ subinterval

$$h:=x_i-x_{i-1}=\frac{b-a}{N}$$

first-order method

$$R_N:=\sum _{i=1}^{N}f(x_i^{\ast })(x_i-x_{i-1})=h\sum _{i=1}^{N}f(x_i^{\ast })$$

$|f^{\prime }(x)|\le M\Rightarrow$

$$\left|{\int }_a^{b}f(x)dx-R_N\right|\le Mh(b-a)$$

second-order method

$$\begin{gathered} T^i(x):=f(x_{i-1})+f^{\prime }(x_{i-1})(x_i-x_{i-1}) \\ {T}_N:=\sum _{i=1}^N{\int }_{x_{i-1}}^{x_i}{T}^i(x)dx=h\sum _{i=1}^{N}f(x_{i-1})+\frac{h^2}{2}\sum _{i=1}^N{f}^{\prime }(x_{i-1}) \end{gathered}$$

$|f^{\prime \prime }(x)|\le M\Rightarrow$

$$\left|{\int }_a^{b}f(x)dx-T_N\right|\le \frac{M{h}^2(b-a)}{6}$$

midpoint rule

$$R_N:=\sum _{i=1}^{N}f({\bar{x}}_i)(x_i-x_{i-1}),{\bar{x}}_i=\frac{x_{i-1}+x_i}{2}$$

$|f^{\prime \prime }(x)|\le M\Rightarrow$

$$\left|{\int }_a^{b}f(x)dx-R_N\right|\le \frac{M{h}^2(b-a)}{24}$$

Last edited: 2024-09-13