Week 4

Question 1

Difference between exact function and interpolation polynomial

Answer 1

Question 2

Intermediate Value Theorem

Answer 2

For any C¹ function which vanishes at A and B

There is at least one point inside [A,B] where it’s derivative vanishes

Question 3

Theorem of error of polynomial interpolation

Answer 3

Question 4

Error on a mesh

Answer 4

Question 5

Prove

Answer 5

Introducing q(y) which is equal to zero for N + 2 points y = x₀,…,x _N and x

Apply derivative N times (at each point a zero vanishes) then by IVT q^(N+1(y) vanishes at some ζ € [a,b]

Then for y = ζ we get

r(x) = (f^(N+1)(ζ))/(N+1)!

See pg 39 LN

Question 6

Interpolation error estimation error function

Answer 6

Where ζ is some point

Question 7

Approximate 1/(1+x)

Answer 7

~ 1 - x + x^2 - x^3 + O(x^4)

Question 8

Break down components of approximation of f’(x)

Answer 8

Question 9

Consequence of machine error for approximation of f’(x)

Answer 9

O(ε/h) therefore choosing small h causes machine error to grow

Question 10

Explain this graph

Answer 10

You are decreasing h along x axis which is causing method error to decrease (inversely) on y

After certain h, machine error starts to increase overall error hence jagged line as machine error is random

Question 11

How to choose h for numerical differentiation to minimise error? Why?

Answer 11

We want machine error to (roughly) equal method error
=>
O(h) ~ O(ε/h)
=>
O(h²) ~ O(ε)
=>
O(h) ~ O(sqrt(ε))

Now order of ε is 10^-16 in Py
=> h = 10^-8

Question 12

Central difference approximation

Answer 12

Question 13

How to find method error for central difference approximation

Answer 13

Question 14

General formula for order of overalll error given method error

Answer 14

As this is bounded by ε, this shows you can’t get rid of machine error

Question 15

Importance of Chebyshev Points

Answer 15

Chebyshev polynomials and are used to minimize the problem of Runge’s phenomenon in polynomial interpolation. Here’s a detailed explanation:

-polynomial interpolation, especially with high-degree polynomials, a phenomenon known as Runge’s phenomenon can occur. This is where large oscillations appear at the edges of the interval of interpolation, leading to poor approximations outside a specific set of points.

Question 16

What are chebyshev polynomials

Answer 16

Chebyshev polynomials are a sequence of orthogonal polynomials that arise in various approximation problems. They are defined over the interval [-1,1]

Question 17

What are chebyshev nodes

Answer 17

Chebyshev nodes of the first kind for a polynomial of degree are typically defined as the roots of the Chebyshev polynomial of the first kind, . These nodes are calculated using the formula:

These points are spaced more densely near the ends of the interval and are more sparse near the middle.

Question 18

Which assumption is required for Taylor expansion

Answer 18

Function is sufficiently smooth

Question 19

Taylor expansion of f(x+h), f(x-h), f(x+2h)

Answer 19

Question 20

Taylor expansion of first deriv (central difference)

Answer 20

For small h (less than 1)

Question 21

Numerical evaluation of approximation of first derivative

Answer 21

Question 22

Find optimal h for O(ε/h)

Answer 22

Let ε = uh + vε/h

Find minimum wrt h

Which is obtained at:
u - vε/h² = 0

=> h = sqrt((εv)/u) = O(sqrt(ε))

Which is often 10^-8