numerical analysis

Question 1

Prove ∃pn ∈ Πn such that pn(xi) = fi
for i = 0, 1, . . . , n.

Answer 1

• 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)]

Question 2

Prove that the interpolating polynomial of degree <=n is unique

Answer 2

• 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

Question 3

What is the error function for an interpolating polynomial?

Answer 3

e(x) = f(x) - p_n(x)

Question 4

What is the Lagrange interpolating polynomial and when is it used?

Question 5

What is the Hermite interpolating polynomial and when is it used?

Question 6

What is the error theorem for a Hermite interpolating polynomial?

Question 7

What is the error theorem for a Lagrange interpolating polynomial?

Question 8

What is a lower triangular matrix?

Question 9

What is an upper triangular matrix?

Question 10

How do lower triangular matrices help to solve linear systems and what is the procedure called?

Question 11

How do upper triangular matrices help to solve linear systems and what is the procedure called?

Question 12

How do we reduce Ax=b to Ux=c, where U is upper triangular?

Answer 12

Gauss elimination

Question 13

What is a multiplier in Gaussian elimination?

Answer 13

aij/ajj, what we multiply the row we are adding/subtracting by to get 0

Question 14

What is a pivot in Gaussian elimination?

Answer 14

ajj

Question 15

How do we obtain a LU factorisation of a matrix?

Answer 15

• 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

Question 16

How do we use LU factorisation to solve linear systems?

Answer 16

• Factorise A = LU
• Solve Ly = b
• Then solve Ux = y

Question 17

When does LU fail and how can we solve it?

Answer 17

• When a pivot ajj is 0
• Can swap the rows before performing GE

Question 18

What is partial pivoting?

Answer 18

• 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.

Question 19

Prove that GE with partial pivoting cannot fail if A is non-singular

Question 20

What is a permutation matrix?

Answer 20

A matrix P with the same rows as the identity, but in a different order.

Question 21

What is an orthogonal matrix?

Answer 21

Q^T = Q^−1

Question 22

Prove that the product of orthogonal matrices is orthogonal

Answer 22

(ST)^T (ST)
= T^T S^T S T
= T^T (S^T S) T
= T^T T
= I

Question 23

What does it mean for two vectors to be orthogonal?

Answer 23

x.y = x^T y = 0

Question 24

Prove that The columns of an orthogonal matrix Q form an orthogonal set, which is an orthonormal basis for R

Question 25

Prove that If u ∈ R^n, P is n-by-n orthogonal matrix and v = Pu, then
u^T u = v^T v.

Question 26

What is the outer product of two vectors x and y?

Answer 26

xy^t

Question 27

What is a householder reflector matrix?