Period 1 Flashcards
(39 cards)
How to calculate f(x) when close to 0?
Usually this can be solved by using the Taylor polynomial, or by L’Hopital.
How to explain miscalculations for x is close to 0?
First show what the actual value is
Then show that the value is below 2^-53 or 2^-52 (if 1 + x)
How to explain outliers when x close to 0?
Usually you need to check for 1 - 2^-53
How to show an error in a magnitude?
O(x^n), this is important
How to proof a unique root?
First show that a and b have a different sign.
Then show that f(x) is continuous.
Then show that f(x) is monotone (i.e. increasing or decreasing) by its derivative.
What is Newtons formula for root finding?
x^(n+1) = x^n - f(x^n)/f’(x^n)
When Newtons algorithm converge monotone?
If the function that is approximated is monotone convex, or monotone concave.
What is the error formula for the bisection method?
n = floor(log_2((b-a)/epsilon))
What is the formula for the False Position method?
c = (af(b) - bf(a))/(f(b)-f(a))
What are advantages and disadvantages of the Bisection method?
+ Works always
+ Bounding interval
+ No derivatives
+ Error estimation
- Slow convergence
- No generalization in higher dimensions
How to find the interpolating polynomial using a system of linear equation?
Create for every entry
p_0 + p_1 x + p_2 x^2 + p_3 x^3 + …. = y
Solve for p
What is are the advantages and disadvantages of polynomials and splines?
Polynomials are just 1 function
The values are sensitive for small changes (ill-conditioned)
Big oscillations at the end of the interval (Runge-effect).
Splines usually give a better fit of the data.
How to proof that you get a unique polynomial?
Proof by contradiction:
Let two polynomials of degree n p(x), q(x), with p(x) != q(x)
Create r(x) = p(x) - q(x), a polynomial of degree n
Because p(x) and q(x) go through the points, r(x) = 0 n + 1 times
However a polynomial of degree n at most n roots. So contradiction.
How to get interpolating polynomial using Lagrange?
p(x) = y_0 * (x - x_1)(x-x_2)…/(x_0 - x_1)(x_0 - x_2)…
+ y_1 * (x-x_0)(x-x_2)…/(x_1-x_0)(x_1/x_2)…
+ …
What is the formula of Newtons Divided Differences?
Table: (f(bottom) - f(top))/(x_bottom - x_top)
Final formula: y_0 + f(., .)(x - x_0) + f(., ., .)(x-x_0)(x-x_1) + ….
What are the advantages and disadvantages of the Vandermonde matrix?
- needs solving a system of equations
- is illconditioned
+ gives explicitly the coefficients
+ very efficient evaluation
What are the advantages and disadvantages of the Lagrange form?
+ no preprocessing
+ gives immediately a formula of the polynomial
- needs more computation for evaluation, which makes it less useful for many points
What are advantages of Newtons Divided Differences?
- need to preprocess
+ Gives one line formula, which is useful for many x
+ Adding new datapoints leads to computing just a single new row
How to interpolate f(x) using a polynomial?
Just create n points on the line within the interval, then let p(x) go trough those points.
How to interpolate f(x) using a spline?
Just create n point on the function within the interval, then create a spline
How to create a spline?
Create the following system of equations:
S_i(x) = a_i + b_i x + c_i x^2 + d_i x^3 (to degree n)
S’_i(x) = b_i + 2c_i x = 3d_i x^2
… to the n-1 derivative.
What is the definition of a spline?
Spline S: R -> R is a cubic spline iff.
- S is n-1 times differentiable
- S, S’, S’’, .., S^(n-1) are continuous
- S interpolates the data
- S is at most of degree n at every interval
- S’‘(x_0)=S’‘(X_n) = 0
How to find the number of points needed for interpolating with a spline?
- Use the formula on the test, however use f^(n+1)(x) with n is the degree of the spline.
- Use for the product the other formula, with n the degree of the spline
- Write this formula smaller then the error
- Solve for n
How to find the number of points needed for interpolating with a polynomial?
- Use the formula on the test, rewrite f^(n+1)(x) to something that you know is bigger.
- Use for the product the other formula on the test
- Write this formula smaller then the error
- Solve for n
