Please enable JavaScript.

Coggle requires JavaScript to display documents.

CSC336 (Interpolation(Polynomial) (Different Bases for polynomial…

- - - - matrix B called Vandermonde matrix
        
        B non-singular \iff the points are distinct
      - not realistic for large n (points to interpolate) thus not used in real-life practice generally except for small cases
  - - - for a pp n intervals N, n-1 interior points variables are fixed
    - - fourth order converges of residuals(when n subintervals doubles, max residual gets reduced by at least a factor of 16, linear's reduction factor is 4.)
      - also looks nicer than linear spline
      - natural: end conditions is 0
      - clamped: end conditions to model target function f
  - - - reduce from Theta(3n) to Theta(2n)
      - Can also use similar idea to speed up NDD
  - - - ill-conditioned for large n
    - - messy, format good for proofs
    - - Well-balanced, clean & efficient
- - - - representation error
        
        round-off error
      - propagation of error
        
        [consequences]
      - computational error
        
        truncation error (e.g. Taylor Theorem's remainder)
        
        rounding error (limited storage space during computation)
        
        catastrophic cancellation
- - - - Question: Why does Newton's method(for roots) only find roots but not minimum??? My Answer: Because it takes f'(x) at the bottom which encourages deviation from the critical points (subsequently, the minimum or maximum)
      - note: using Newton's method, we can find a critical point, i.e. f'(x) =0, but not necessarily the actual max/min??? So we need to prefilter to make sure?
- - - - Theorem 4b: g(x) contraction mapping + g(x): I -> I IMPLIES guaranteed convergence of g(x) in I
      - Theorem 5: existence of fixed point + contraction mapping IMPLIES guaranteed convergence of g(x) in I (method of finding unknown?)
      - contraction mapping: |g’(x)| < 1 in I
    - - can be treated as a fixed-point function
      - convergence not guaranteed (but can be determined through fixed-point iteration)
      - converges very slowly at a root with multiplicity > 1 (since any root with multiplicity higher than 1 has like, two sides both approach 0 so the expression overall gets reduced slower as it approaches the root. converges with linear order/rate with k=1-1/m
    - - f(a)·f(b) <0 IMPLIES guaranteed root of f(x)
  - - - 1d derivative replaced by Jacobian matrix of system of equations.
      - Jacobian matrix has to be non-singular (in place of 1d derivative != 0)
      - other conditions in 1D also needs to be satisfied
  - - - beta: rate of convergence
      - k: only has to be smaller than 1 when order b is 1, doesn't matter that much otherwise.
- - - - (stabler) pivoting: partial, complete
      - efficient with Symmetic Positive Definite, Choleski Factorization
      - properties with banded matrix