numerical analysis Flashcards
Prove ∃pn ∈ Πn such that pn(xi) = fi
for i = 0, 1, . . . , n.
- Write down L_n,k
- L_n,k(xi) = δ_i,k
- p_n(x) = sum from k=0 to n[f_k * L_n,k(x)]
Prove that the interpolating polynomial of degree <=n is unique
- Suppose p_n, q_n are both interpolating polynomials
- Let d_n = p_n - q_n
- So d has at most degree n
- Then d_n(x_i) = 0 for i = 0,…,n
- So d has at least n+1 roots
- So d = 0, i.e. p_n = q_n
What is the error function for an interpolating polynomial?
e(x) = f(x) - p_n(x)
What is the Lagrange interpolating polynomial and when is it used?
What is the Hermite interpolating polynomial and when is it used?
What is the error theorem for a Hermite interpolating polynomial?
What is the error theorem for a Lagrange interpolating polynomial?
What is a lower triangular matrix?
What is an upper triangular matrix?
How do lower triangular matrices help to solve linear systems and what is the procedure called?
How do upper triangular matrices help to solve linear systems and what is the procedure called?
How do we reduce Ax=b to Ux=c, where U is upper triangular?
Gauss elimination
What is a multiplier in Gaussian elimination?
aij/ajj, what we multiply the row we are adding/subtracting by to get 0
What is a pivot in Gaussian elimination?
ajj
How do we obtain a LU factorisation of a matrix?
- Perform Gaussian Elimination
- The matrices we multiply by to perform the row operations are lower triangular, and products of lower triangular matrices remain lower triangular.
- The matrix we end up with after GE is upper triangular
How do we use LU factorisation to solve linear systems?
- Factorise A = LU
- Solve Ly = b
- Then solve Ux = y
When does LU fail and how can we solve it?
- When a pivot ajj is 0
- Can swap the rows before performing GE
What is partial pivoting?
- When creating the zeros in the jth column, find:
|ak,j| = max(|aj,j|, |aj+1,j|, . . . , |an,j|),
then swap rows j and k.
Prove that GE with partial pivoting cannot fail if A is non-singular
What is a permutation matrix?
A matrix P with the same rows as the identity, but in a different order.
What is an orthogonal matrix?
Q^T = Q^−1
Prove that the product of orthogonal matrices is orthogonal
(ST)^T (ST)
= T^T S^T S T
= T^T (S^T S) T
= T^T T
= I
What does it mean for two vectors to be orthogonal?
x.y = x^T y = 0
Prove that The columns of an orthogonal matrix Q form an orthogonal set, which is an orthonormal basis for R
Prove that If u ∈ R^n, P is n-by-n orthogonal matrix and v = Pu, then
u^T u = v^T v.
What is the outer product of two vectors x and y?
xy^t
What is a householder reflector matrix?
