Absolute Error

The absolute error is the magnitude of the difference between the true value and the approximation:

E_abs = |x - x̂|

where x is the true value and x̂ is the approximation.

Relative Error

The relative error is the absolute error divided by the magnitude of the true value:

E_rel = |x - x̂| / |x|

Relative error is often expressed as a percentage and is more meaningful when comparing errors across different scales.

Bisection Method

The bisection method is a simple and robust technique based on the Intermediate Value Theorem.

Algorithm:

1. Start with an interval [a, b] where f(a) and f(b) have opposite signs
2. Compute the midpoint c = (a + b) / 2
3. Evaluate f(c)
4. If f(c) = 0 or the interval is sufficiently small, return c as the root
5. If f(a) and f(c) have opposite signs, set b = c; otherwise, set a = c
6. Repeat steps 2-5 until convergence

Convergence:

The bisection method always converges, but it is slow (linear convergence). The error is approximately halved in each iteration.

Newton-Raphson Method

The Newton-Raphson method uses derivative information to converge more quickly to a root.

Algorithm:

1. Start with an initial guess x₀
2. Compute the next approximation using the formula:

x_n+1 = x_n - f(x_n) / f'(x_n)

3. Repeat step 2 until convergence

Convergence:

The Newton-Raphson method generally exhibits quadratic convergence, which is much faster than the bisection method. However, it may fail to converge in some cases, especially if the initial guess is poor or if f'(x) is close to zero.

Gaussian Elimination with Partial Pivoting

Gaussian elimination converts the system to an upper triangular form and then uses back-substitution.

Algorithm:

1. Augment matrix A with vector b: [A|b]
2. For each row i:
• Find the pivot (largest absolute value) in column i
• Swap rows to move the pivot to row i
• Eliminate elements below the pivot
3. Use back-substitution to find the solution

[  2   1  -1  |  8  ]
[ -3  -1   2  | -11 ]
[ -2   1   2  | -3  ]

[  2   1  -1  |  8  ]
[  0   0.5  0.5  | -2.5 ]
[  0   2   1  |  5  ]

[  2   1  -1  |  8  ]
[  0   0.5  0.5  | -2.5 ]
[  0   0  -3  |  15  ]

LU Decomposition

LU decomposition factorizes matrix A into a lower triangular matrix L and an upper triangular matrix U: A = LU.

Algorithm:

1. Factorize A into L and U
2. Solve Ly = b for y using forward substitution
3. Solve Ux = y for x using back substitution

Advantages:

• Efficient for solving multiple systems with the same coefficient matrix but different right-hand sides
• Can be used to calculate the determinant and inverse of a matrix

Newton's Method for Systems

Newton's method can be extended to systems of nonlinear equations:

x^(k+1) = x^(k) - J(x^(k))^-1F(x^(k))

where J is the Jacobian matrix of partial derivatives.

Advantages:

• Quadratic convergence when close to the solution

Disadvantages:

• Requires computing and inverting the Jacobian matrix
• Sensitive to the initial guess

Lagrange Interpolation

Lagrange interpolation constructs a polynomial that passes through all given points.

Formula:

P(x) = ∑_i=0ⁿ y_iL_i(x)

where L_i(x) are the Lagrange basis polynomials:

L_i(x) = ∏_j=0,j≠iⁿ (x - x_j) / (x_i - x_j)

Newton's Divided Differences

Newton's divided differences method is another way to construct interpolating polynomials, but it's often more computationally efficient than Lagrange's method.

Formula:

P(x) = f[x₀] + f[x₀, x₁](x - x₀) + f[x₀, x₁, x₂](x - x₀)(x - x₁) + ...

where f[x_i, x_i+1, ..., x_i+k] are the divided differences.

Computing Divided Differences:

• First divided difference: f[x_i, x_i+1] = (f[x_i+1] - f[x_i]) / (x_i+1 - x_i)
• Higher-order divided differences: f[x_i, ..., x_i+k+1] = (f[x_i+1, ..., x_i+k+1] - f[x_i, ..., x_i+k]) / (x_i+k+1 - x_i)

Finite Difference Formulas

Forward Difference:

f'(x) ≈ (f(x + h) - f(x)) / h

Error: O(h)

Backward Difference:

f'(x) ≈ (f(x) - f(x - h)) / h

Error: O(h)

Central Difference:

f'(x) ≈ (f(x + h) - f(x - h)) / (2h)

Error: O(h²)

Second Derivative Approximation:

f''(x) ≈ (f(x + h) - 2f(x) + f(x - h)) / h²

Error: O(h²)

Richardson Extrapolation

Richardson extrapolation improves the accuracy of finite difference approximations by combining results from different step sizes.

Algorithm:

1. Compute approximations D₁ and D₂ using step sizes h and h/2
2. Combine them using the formula:

D ≈ D₂ + (D₂ - D₁) / (2^p - 1)

where p is the order of accuracy of the original method.

Example:

For central differences (p = 2):

D ≈ D₂ + (D₂ - D₁) / 3

Rectangle Methods

Left Rectangle Rule:

∫_a^b f(x) dx ≈ h ∑_i=0^n-1 f(a + ih)

where h = (b - a) / n

Right Rectangle Rule:

∫_a^b f(x) dx ≈ h ∑_i=1ⁿ f(a + ih)

Midpoint Rule:

∫_a^b f(x) dx ≈ h ∑_i=0^n-1 f(a + (i + 0.5)h)

Error Estimates:

• Left/Right Rectangle: O(h)
• Midpoint Rule: O(h²)

Trapezoidal Rule

The trapezoidal rule approximates the integral using trapezoids:

∫_a^b f(x) dx ≈ h/2 [f(a) + 2∑_i=1^n-1 f(a + ih) + f(b)]

where h = (b - a) / n

Error Estimate:

The error for the trapezoidal rule is O(h²).

Simpson's Rules

Simpson's 1/3 Rule:

For even n, Simpson's 1/3 rule approximates the integral using parabolic arcs:

∫_a^b f(x) dx ≈ h/3 [f(a) + 4∑_i=1,3,5,...^n-1 f(a + ih) + 2∑_i=2,4,6,...^n-2 f(a + ih) + f(b)]

Simpson's 3/8 Rule:

An alternative for n = 3, 6, 9, ...:

∫_a^b f(x) dx ≈ 3h/8 [f(a) + 3f(a + h) + 3f(a + 2h) + f(a + 3h)]

Error Estimates:

• Simpson's 1/3 Rule: O(h⁴)
• Simpson's 3/8 Rule: O(h⁴)

Euler's Method

Euler's method is the simplest numerical approach for solving ODEs:

y_n+1 = y_n + hf(t_n, y_n)

where h is the step size.

Error Analysis:

Euler's method has a local truncation error of O(h²) and a global error of O(h).

Runge-Kutta Methods

Runge-Kutta methods improve accuracy by evaluating the function at intermediate points.

Second-Order Runge-Kutta (RK2):

k₁ = f(t_n, y_n)

k₂ = f(t_n + h, y_n + hk₁)

y_n+1 = y_n + h(k₁ + k₂)/2

Fourth-Order Runge-Kutta (RK4):

k₁ = f(t_n, y_n)

k₂ = f(t_n + h/2, y_n + (h/2)k₁)

k₃ = f(t_n + h/2, y_n + (h/2)k₂)

k₄ = f(t_n + h, y_n + hk₃)

y_n+1 = y_n + (h/6)(k₁ + 2k₂ + 2k₃ + k₄)

Error Analysis:

• RK2: Global error of O(h²)
• RK4: Global error of O(h⁴)

Finite Difference Methods

Finite difference methods approximate derivatives using difference quotients.

Example: Heat Equation

For the one-dimensional heat equation u_t = αu_xx:

Explicit Scheme:

(u_iⁿ⁺¹ - u_iⁿ)/Δt = α(u_i+1ⁿ - 2u_iⁿ + u_i-1ⁿ)/(Δx)²

This leads to:

u_iⁿ⁺¹ = u_iⁿ + r(u_i+1ⁿ - 2u_iⁿ + u_i-1ⁿ)

where r = αΔt/(Δx)²

Stability:

The explicit scheme is stable if r ≤ 1/2.

Implicit Scheme:

(u_iⁿ⁺¹ - u_iⁿ)/Δt = α(u_i+1ⁿ⁺¹ - 2u_iⁿ⁺¹ + u_i-1ⁿ⁺¹)/(Δx)²

This scheme is unconditionally stable but requires solving a system of equations at each time step.