Homework assigned 9/30, due 10/9
Are these methods cubically convergent?
In class, I propsed
viewing Newton's method x_{n+1} = x_n - f(x_n)/f'(x_n) = g(x_n) as
functional iteration. If the functional iteration converges to a
point, r, then from the definition of g, r must be a root of f. To
show that the above Newton's method converges quadratically, it
sufficed to know that g, g', and g'' exist and are continuous and g(r)
= g'(r) = 0.
Analogously, if x_n converges to r and g(r) = g'(r) = g''(r) = 0 then
the method converges cubically. Using this, and Maple, verify that
Olver's method converges cubically:
x_{n+1} = x_n - f(x_n)/f'(x_n) - 1/2 f''(x_n) f(x_n)^2/f'(x_n)^3
(This is problem 9 on page 117.) Does it always converge cubically?
If not, when does it fail?
Section 4.3
Written problems: 1, 2, 7, 8, 10, 11, 13b, 14
Verifying convergences
We define three different versions
of the first derivative of f:
Df_1(x) = ( f(x+h)-f(x) )/h
Df_2(x) = ( f(x+h)-f(x-h) )/(2h)
Df_3(x) = 4/3 (
f(x+h/2)-f(x-h/2) )/h - 1/3 ( f(x+h)-f(x-h) )/(2 h)
Choose a
function and for each of the above finite-difference definitions of
the first derivative, demonstrate that the errors are decreasing like
the appropriate power of h.
Note, for some functions, like
quadratic functions, these finite-difference approximations appear to
be exactly correct. Prove this, for one of the above approximations
and some sufficiently low-degree polynomial.
Using polynomial interpolation instead of finite-differences
Use maple to help out with the grunt-work on this problem.
Instead of using finite-differences to calculate the derivative,
assume that you're given the function at the points x and x+h. Find
the interpolating polynomial for these points and find its derivative
at x.
Now assume you're given the function at the points x-h and
x+h. Again, find the interpolating polynomial for these points and
find its derivative at x.
Now assume you're given the function at
the points x-h, x-h/2, x+h/2, x+h. Find the interpolating polynomial
for these points and find its derivative at x
Section 5.1
Written problems: 2, 3, 7, 8, 12
Computer problems: 1, 3, 4