Period 1 Flashcards
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
How to get the formula of a Gaussian integral?
Create the following system of equations:
A_0 + A_1 + A_2 + … + A_n = (b-a)/1
A_0 x_0 + A_1 x_1 + A_2 x_ 2+ … + A_n x_n = (b-a)^2/2
A_0 x_0^2+ A_1 x_1^2 + A_2 x_2^2 + … + A_n x_n^2 = (b-a)^3/3
…
Every A represents a size before f(x)
What is the formula of an integral created using the Midpoint rule?
h * Sum from 0 to n -1 of f((x_i + x_(i+1))/2).
I.e. h*(f(x_0.5) + f(x_1.5) + f(x_2.5) + …)
What is the formula of an integral created using the trapezium rule?
0.5h * (f(x_0) + 2 f(x_1) + 2 f(x_2) + … + f(x_n))
What is the formula of an integral created using Simpsons rule?
i.e. h/3 * (f(a) + 4 * sum^(n/4)_(i=1) f(a + (2i-1)h) + 2 * sum^(n/2 -1)_(i=1) f(a +2ih) + f(b).
h/3 * (f(x_0) + 4 f(x_1) + 2 f(x_2) + 4 f(x_3) + … f(x_n))
How to compute a Gaussian integral using a given formula?
- Create a small formula to rewrite a and b into a and b given in the integral e.g. (y = 1/10 x -1), rewrite this to x = ..
- Fill in the formula in the integral with f(x)
- Calculate using the given formula.
What is the algorithm for the bisection method?
- Get a, and b
- Find c = (a+b)/2
- Check sign(a) == sign(c), if so then c = a_(n+1)
else c = b_(n+1) - Repeat until interval is small enough or f(c) < error_2
What are advantages and disadvantages of the False Position method?
+ Convergence guaranteed
+ Faster convergence then bisection
- More calculations per iteration
- No calculation for the speed of the convergence
What are advantages and disadvantages of the Newtons Method for root finding?
- does not always work
- no interval given
+ fast convergence
+ generalization in higher dimensions
+ has error estimation
+ just 1 initial estimate needed
What is the Secant method?
Same method as Newtons method, however this uses an estimation for the derivative.
x_(n+1) = x_n - (x_n - x_(n-1))/(f(x_n) - f(x_(n-1))
How to get a Polynomial using the Vandermonde Matrix?
Create the following system of equations:
p_0 + p_1 x + p_2 x^2 + p_3 x^3 + … = y
for every data point.
How to get the number of Intervals for an integral within an error?
- Use the formula given by the test to get maximum error for one.
- Apply this for all.
- Rewrite this to n > …
What does it mean for an integration rule to be more efficient?
For the same partitions, the error of rule a is smaller then rule b. Or for a certain error you need fewer intervals.
What is the algorithm of the False Position method?
- Get a and b
- Draw a line between trough (a, f(a)) and (b, f(b))
- Crosses x-axis at c in (a, b)
- Check sign of f(c), then choose new a and b
- Repeat until interval is small enough, or f(c) < error_2
What is the formula of the Gaussian rule?
G_n(f) = A_0 f(x_0) + A_1 f(x_1) + … + A_n f(x_n)
How many degrees of polynomial is a Gaussian integral accurate?
The number of nodes + number of weights - 2, is the number of unknown variables. This -1.
