# round-off and truncation error# 舍入和截断误差
1. Round-off errors are due to approximate representation of floating-point number
from math import piprint(pi)
3.141592653589793
π\piπ=3.141592653589793238462643…
2. subtractive cancellation
x=1x=1x=1
y=1+10−152y=1+10^{-15}\sqrt{2}y=1+10−152
from math import sqrtx = 1.0y = 1.0 + 1e-15 * sqrt(2)dt = 1e-15 * sqrt(2)dn = y - xprint("dt = ", dt)print("dn = ", dn)print("Relative error: ", (dt - dn) / dt)
dt = 1.4142135623730953e-15dn = 1.3322676295501878e-15Relative error: 0.05794452478973511
similar accumulation of round-off in addition(large number + small number).
3. Truncation Errors
Truncation errors are created by truncating the math.
Example: MacLaurin Series for exponential function
ex=∑n=0∞xnn!e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!} ex=n=0∑∞n!xn
Now, we only use three terms
ex=∑n=0∞xnn!≈1+x+x22!e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}\approx 1 + x + \frac{x^2}{2!} ex=n=0∑∞n!xn≈1+x+2!x2
4. Numerical Differentiation and numerical errors
definition of true derivative
f′(x)=limdx→0f(x+dx)−f(x)dxf^{'}(x)=\lim_{dx\rightarrow 0}\frac{f(x+dx)-f(x)}{dx} f′(x)=dx→0limdxf(x+dx)−f(x)
approximation of derivative(numerical derivative)
f′(xi)=f(xi+1)−f(xi)xi+1−xif^{'}(x_i)=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i} f′(xi)=xi+1−xif(xi+1)−f(xi)
5. Truncation error estimate using Taylor series
f(xi+1)=f(xi)+f′(xi)(xi+1−xi)+R1f(x_{i+1})=f(x_i)+f^{'}(x_i)(x_{i+1}-x_i)+R_1 f(xi+1)=f(xi)+f′(xi)(xi+1−xi)+R1
f′(xi)=f(xi+1)−f(xi)xi+1−xi−R1xi+1−xif^{'}(x_i)=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}-\frac{R_1}{x_{i+1}-x_i} f′(xi)=xi+1−xif(xi+1)−f(xi)−xi+1−xiR1
where f(xi+1)−f(xi)xi+1−xi\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}xi+1−xif(xi+1)−f(xi) is the approximation term, and R1xi+1−xi\frac{R_1}{x_{i+1}-x_i}xi+1−xiR1 is the truncation error.
Rn=fn+1(ξ)(n+1)!hn+1=O(hn+1)R_n=\frac{f^{n+1}(\xi)}{(n+1)!}h^{n+1}=O(h^{n+1}) Rn=(n+1)!fn+1(ξ)hn+1=O(hn+1)
three expressions of numerical derivative:
(1) Forward formula
f′(xi)=f(xi+1)−f(xi)xi+1−xi+O(h)f^{'}(x_i)=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}+ O(h) f′(xi)=xi+1−xif(xi+1)−f(xi)+O(h)
(2) Backward formula
f′(xi)=f(xi)−f(xi−1)xi−xi−1+O(h)f^{'}(x_i)=\frac{f(x_{i})-f(x_{i-1})}{x_{i}-x_{i-1}}+ O(h) f′(xi)=xi−xi−1f(xi)−f(xi−1)+O(h)
(3) Centered formula
f′(xi)=f(xi+1)−f(xi−1)xi+1−xi−1+O(h2)f^{'}(x_i)=\frac{f(x_{i+1})-f(x_{i-1})}{x_{i+1}-x_{i-1}}+ O(h^2) f′(xi)=xi+1−xi−1f(xi+1)−f(xi−1)+O(h2)
so, centered formula is more accurate than forward and backward formula
6. Error propagation and condition number
f(x)=f(x∗)+f′(x∗)(x−x∗)f(x) = f(x^*)+f^{'}(x^*)(x-x^*) f(x)=f(x∗)+f′(x∗)(x−x∗)
f(x)−f(x∗)f(x∗)=f′(x∗)(x−x∗)f(x∗)\frac{f(x)-f(x^*)}{f(x^*)}=\frac{f^{'}(x^*)(x-x^*)}{f(x^*)} f(x∗)f(x)−f(x∗)=f(x∗)f′(x∗)(x−x∗)
f(x)−f(x∗)f(x∗)=x∗f′(x∗)f(x∗)x−x∗x∗\frac{f(x)-f(x^*)}{f(x^*)}=\frac{x^*f^{'}(x^*)}{f(x^*)}\frac{x-x^*}{x^*} f(x∗)f(x)−f(x∗)=f(x∗)x∗f′(x∗)x∗x−x∗
where x∗f′(x∗)f(x∗)\frac{x^*f^{'}(x^*)}{f(x^*)}f(x∗)x∗f′(x∗) is called condition number.
f(x)−f(x∗)f(x∗)=Condition_number×x−x∗x∗\frac{f(x)-f(x^*)}{f(x^*)}=Condition\_number \times\frac{x-x^*}{x^*} f(x∗)f(x)−f(x∗)=Condition_number×x∗x−x∗
Small condition number = error decreases.
Large condition number = ill-conditioned.