Finals Memorization

Root Defintion

A number α ∈ [a,b] s.t. f(α) = 0 is called a root or zero of f

Bisection Method

Let f ∈ c⁰([a,b]), a<b, and suppose that f(a)f(b) < 0. The sequence generated by the bisection method approximation of a root α of f with |x_k - α| ≤ b-a/2^k+1, ∀ k ≥ 0. In simple terms, you split it in half and find the root. Only works for roots that change through the x-axis, plus the method must have different signs at a and b.

Newtons Method

Given x₀, x_k+1 = x_k - f(x_k)/f’(x_k). This is illustrated through tangent lines

Secant Method

Given x₀,x₁, x_k+1 = x_k - f(x_k)(x_k-x_k-1)/f(x_k)-f(x_k-1). This is illustrated by a single tangent line, then pivoting around that point.

Fixed Point Definition

A number α s.t φ(x) = α is called a fixed point of p. For a given continuous p and an initial guess x₀, the fixed point iteration is simply: x_k+1 = φ(x_k). If a sequence {x_k}_{k ≥ 0} converges to some α, then α is necessarily a fixed point of φ. Indeed, we have α = lim_{k → ∞} x_k = lim_{k → ∞} φ(x_k-1) = φ(lim_{k→ ∞}x_k-1) = φ(x).

Linear Order Thm

Let φ ∈ c²([a,b]) and let α ∈ [a,b] be a fixed point of p. If 0 < |φ’(α)| < 1 and if x₀ is sufficiently close to x then fixed point iteration x_k+1 = φ(x_k), k ≥ 0 is only of order one.

p order convergence thm

Let p ∈ c^p[a,b] for some p>1 and let α ∈ [a,b] be a fixed point of p if φ’(α) = φ”(α) = … = φ^p-1(α) = 0 and φ^p(α) ≠ 0 and if x₀ is sufficiently close to α, then fixed point iteration x_k+1 = φ(x_k), k ≥ 0 is of order p.

Lagrange Basis

φ_k(x) = (x-x₀)(x-x₁)...(x-x_k-1)(x-x_k+1)...(x-x_n) / (x_k-x₀)(x_k-x₁)..(x_k-x_k-1)(x_k-x_k+1)..(x_k-x_n), then φ (x) = φ_k(x)*(x_k)

Newton Basis

 The tree method, 

x₀   f(x₀)

              >  f[x₀,x₁] = f(x₁)-f(x₀)/x₁-x₀

x₁   f(x₁)                                              > f[x₀,x₁,x₂] = f(x₁,x₂) - f(x₁,x₀)/x₂-x₀

              >  f[x₁,x₂] = f(x₂)-f(x₁)/x₂-x₁

x₂    f(x₂)

Cubic Spline Smoothness

 c⁰     s₀(b)    =   s₁(b) 

c¹       s₀’(b)   =  s₁’(b) 

 c²      s₀’’(b)  =  s₁”(b)

Cubic Spline Interpolation

s₀(a) = A

s₀(b) = B

s₁(b) = B

s₁(c) = C

Cubic Spline Natural Spline

s₀”(a) = 0 

s₁”(c) = 0

Forward Difference

S₊^h f(x̄) ≈ f(x̄+h)-f(x̄) / h.         Order One

Backward Difference

S_-^h f(x̄) ≈ f(x̄)-f(x̄-h) / h.           Order One

Centred Difference

S_c^h f(x̄) ≈ f(x̄+h) - f(x̄-h) / h.    Order Two

Approximation of f’’(x̄)

 S₂^h f(x̄) ≈ f(x̄+h) - 2f(x̄) + f(x̄-h) / h²

Midpoint Rule

  I_mp(f) = (b-a)f(a+b/2)

Trapezoidal Rule

I_t(f) = (b-a)/2*(f(a)+f(b))

Simpsons Rule

I_s(f) = (b-a)/6*(f(a)+4f(a+b/2)+f(b))

Composite Midpoint Rule

I_mp^h (f) = h Σ_i=0^n-1 (f(x_i+x_i+1)/2)

Composite Trapezodial Rule

I_t^h (f) = h/2f(x₀) + h Σ_i=0^n-1 f(x_i) + h/2f(x_n)

Composite Simpsons Rule

I_s^h (f) = h/6f(x₀) + h/3 Σ_i=0^n-1 f(x_i) + 2h/3 Σ_i=0^n-1 f(x_i+x_i+1/2) + h/6 f(x_n)