Numerical methods

Doolittle form: $L$ is unit lower triangular (1s on its diagonal) and holds the multipliers $m_{ik}$ below the diagonal; $U$ is the upper-triangular matrix that Gaussian elimination without row swaps produces. Crout form puts the 1s on the diagonal of $U$ instead. For a non-singular $A$, the factorisation exists without row swaps exactly when every leading principal minor of $A$ is non-zero. One factorisation serves any number of right-hand sides $b$.

Every new component uses only the previous sweep's values. Needs $a_{ii}\ne 0$ (reorder the equations if necessary).

Each new component is used immediately, later in the same sweep. Needs $a_{ii}\ne 0$.

Here $D$ is the diagonal of $A$ and $L$, $U$ are its strictly lower and strictly upper triangular parts (not the LU factors). Each method has the form $x^{(k+1)}=T{x}^{(k)}+c$, and $\rho (T)$, the spectral radius, is the largest $|\lambda |$ over the eigenvalues of $T$.

If it holds, both Jacobi and Gauss-Seidel converge for every starting vector. It is sufficient, not necessary: a system that fails it may still converge. Gauss-Seidel also converges for every start when $A$ is symmetric positive definite.

$p=1$ is linear (it also needs $C<1$; the error shrinks by a roughly constant factor each step). $p>1$ is superlinear. $p=2$ is quadratic: the number of correct digits roughly doubles each step.

Needs $f$ continuous on $[a,b]$ with $f(a)f(b)<0$; keep the half on which the sign still changes. The $n$-th midpoint $x_n$ is within $(b-a)/2^n$ of a root, and the bracket after $n$ halvings has that length. The error bound halves at every step, which is why bisection is counted as linearly convergent with ratio $1/2$; the actual error need not decrease at every step. The number of steps for a tolerance $\epsilon$ does not depend on $f$.

The $x$-intercept of the chord joining $(a,f(a))$ and $(b,f(b))$. Needs $f(a)f(b)<0$, and the new bracket is whichever of $[a,c]$, $[c,b]$ keeps the sign change. Always converges for continuous $f$, but usually only linearly, because one end of the bracket often stays fixed.

The $x$-intercept of the tangent at $x_n$. For $f^{\prime \prime }$ continuous near a simple root ($f^{\prime }(\alpha )\ne 0$), convergence from a start close enough to the root is at least quadratic (faster when $f^{\prime \prime }(\alpha )=0$). At a root of multiplicity $m$ it is only linear, with $e_{n+1}/e_n\to (m-1)/m$; the modified step $x_{n+1}=x_n-mf(x_n)/f^{\prime }(x_n)$ restores quadratic convergence.

From $f(x)=x^2-N$, $f(x)=x^k-N$ and $f(x)=1/x-N$ respectively, with $N>0$. The $\sqrt{N}$ iteration converges from every $x_0>0$ (after the first step every iterate is at least $\sqrt{N}$, and they decrease). The reciprocal iteration uses no division; since $1-N{x}_{n+1}=(1-N{x}_n{)}^2$, it converges to $1/N$ exactly when $0<x_0<2/N$.

Newton-Raphson with $f^{\prime }(x_n)$ replaced by the slope through the last two iterates. Needs two starting values but no derivative and no sign change. Order $(1+\sqrt{5})/2\approx 1.618$ near a simple root; it can diverge because it does not keep a bracket.

Rewrite $f(x)=0$ as $x=g(x)$, with $g^{\prime }$ continuous near $\alpha$. Linear convergence with ratio $|g^{\prime }(\alpha )|$ when $0<|g^{\prime }(\alpha )|<1$; the iterates move away if $|g^{\prime }(\alpha )|>1$. Interval test: if $g$ maps $[a,b]$ into itself and $|g^{\prime }(x)|\le k<1$ for all $x$ in $[a,b]$, then $[a,b]$ contains exactly one fixed point and the iteration converges to it from every $x_0$ in $[a,b]$. Newton-Raphson is the choice $g(x)=x-f(x)/f^{\prime }(x)$, for which $g^{\prime }(\alpha )=0$ at a simple root, which is why it is faster than linear.

Any $n\ge 1$. A straight line on each subinterval. Exact for polynomials of degree $\le 1$.

Global error $O(h^2)$: halving $h$ cuts the error by a factor of about 4. If $f^{\prime \prime }>0$ on $[a,b]$ (convex $f$) the rule overestimates; if $f^{\prime \prime }<0$ it underestimates.

$n$ must be even (an odd number of points). A parabola through each pair of subintervals. Exact for polynomials of degree $\le 3$.

Global error $O(h^4)$: halving $h$ cuts the error by a factor of about 16.

$n$ must be a multiple of 3. A cubic through each group of three subintervals. Exact for polynomials of degree $\le 3$, the same degree as the 1/3 rule.

Also $O(h^4)$ globally, with a larger constant than the 1/3 rule at the same $h$. Useful when $n$ is odd and at least 3: apply the 3/8 rule to three subintervals and the 1/3 rule to the rest.

The second form follows from the substitution $x=m+\frac{b-a}{2}t$. Two function values at unequally placed points, yet exact for polynomials of degree $\le 3$, like Simpson's rules with three. Check: for ${\int }_0^2{x}^{3}dx$ it gives $(1-u{)}^3+(1+u{)}^3=2+6u^2=4$ with $u=1/\sqrt{3}$, the exact value.

Follows the tangent line at the start of the step. Order 1: local error $O(h^2)$, global error $O(h)$.

Order 1, but $y_{n+1}$ appears on both sides and must be solved for (directly when $f$ is linear in $y$). For $y^{\prime }=\lambda y$ with real $\lambda <0$ it gives $y_{n+1}=y_n/(1-h\lambda )$, which decays for every $h>0$.

An Euler predictor followed by a trapezoidal corrector. Order 2: local error $O(h^3)$, global error $O(h^2)$. The same computation written as $k_1=hf(x_n,y_n)$, $k_2=hf(x_n+h,y_n+k_1)$, $y_{n+1}=y_n+\frac{1}{2}(k_1+k_2)$ is one second-order Runge-Kutta method; the midpoint method below is another. Some texts apply the corrector repeatedly, putting each new $y_{n+1}$ back into $f(x_{n+1},\cdot )$ until two successive values agree; one application is the formula above.

Four evaluations of $f$ per step. Order 4: local error $O(h^5)$, global error $O(h^4)$. Note that $k_3$ uses $k_2$, not $k_1$, and $k_4$ uses a full step with $k_3$.

The higher derivatives come from differentiating the equation itself ($f_x$, $f_y$ are partial derivatives, evaluated at $(x_n,y_n)$). Truncating after the $h^p$ term gives a method of order $p$; keeping only the $h$ term is Euler's method.

Each iterate is a function, not a number. For $y^{\prime }=y$, $y(0)=1$: $y_1=1+x$, $y_2=1+x+\frac{x^2}{2}$, and each further iterate adds the next term of the series of $e^x$.

$\lambda$ real. For $0<h<1/|\lambda |$ the numerical solution decays without changing sign, like the exact $e^{\lambda x}$; at $h=1/|\lambda |$ it is $0$ after one step. For $1/|\lambda |<h<2/|\lambda |$ it alternates in sign while decaying. At $h=2/|\lambda |$ it alternates with constant magnitude, and for $h>2/|\lambda |$ it grows without bound.

Two linear equations in $a$ and $b$. For a parabola $y=a+bx+c{x}^2$ the same method gives three: $\sum y_i=na+b\sum x_i+c\sum x_i^2$, $\sum x_i{y}_i=a\sum x_i+b\sum x_i^2+c\sum x_i^3$, $\sum x_i^2{y}_i=a\sum x_i^2+b\sum x_i^3+c\sum x_i^4$. For a line through the origin, $y=bx$, the single normal equation gives $b=\sum x_i{y}_i/\sum x_i^2$.

The line passes through $(\bar{x},\bar{y})$ and its residuals sum to zero. It minimises vertical deviations, so it is the line for predicting $y$ from $x$.

Defined only when neither $S_{xx}$ nor $S_{yy}$ is zero. $-1\le r\le 1$, and $|r|=1$ exactly when all the points lie on one (non-horizontal, non-vertical) line. $r$ is unchanged by a change of origin and scale, $u=(x-A)/h$, $v=(y-B)/k$ with $hk>0$; if $hk<0$ only its sign changes. It measures linear association only: for $x=-1,0,1$ and $y=x^2$, $S_{xy}=0$ so $r=0$, although $y$ is a function of $x$.

Both lines pass through $(\bar{x},\bar{y})$, so when $|r|<1$ solving them together gives the means. The two coefficients have the sign of $r$, and $r=\pm \sqrt{b_{yx}{b}_{xy}}$ with that common sign. The lines coincide only when $|r|=1$; when $r=0$ they are $y=\bar{y}$ and $x=\bar{x}$, perpendicular. The coefficients are unchanged by a change of origin but not of scale: with $u=(x-A)/h$, $v=(y-B)/k$, $b_{yx}=(k/h)b_{vu}$.

For the least-squares line (with an intercept), $r^2$ is the fraction of the variation of $y$ about $\bar{y}$ that the line accounts for.

Rank the $x$ values and the $y$ values separately; $d_i$ is the difference between the two ranks of item $i$. This form is exact when there are no tied ranks (it is then Pearson's $r$ computed on the ranks). $-1\le {\rho }_s\le 1$.

$\eta >0$ is the learning rate. Every partial derivative is evaluated at the current (old) weights, and then all the weights are updated together.

$\hat{y}$ is the network output and $t$ the target. The factor $\frac{1}{2}$ is a convention that cancels the 2 from differentiation; without it every gradient doubles, so check which form a question uses.

$a_{\text{in}}$ is the neuron's input (the previous layer's output) and $\phi$ its activation. The last result is what is passed backwards to the previous layer.

$w_{ji}$ is the weight from unit $i$ into unit $j$, and the sum runs over every unit $k$ that unit $j$ feeds. A unit feeding several others collects a contribution from each. For an output unit with the squared-error loss above, ${\delta }_k=(a_k-t_k){\phi }^{\prime }(z_k)$.