Try our Free Online Math Solver!

MATH 4073 Homework 4
Problem 1. Assume that the sequence
is generated by some iterative method
for finding a root of an equation. Also assume that we know that the sequence
converges to some number p of some order α with some asymptotic error
constant λ, but
we don’t know the values of α and λ. The goal of this problem is to
develop a method
for determining the numerical value of α from the numerical values of the
members of the
sequence .
Let be the error at the nth step of the
iteration , and define .
(a) Show that for large n, the following approximate identity holds:
Hint: Just look at the definition of order of convergence.
(b) Using the approximate identity derived in (a) show that
Note that this approximate formula for α does not depend on the base of the
logarithms;
if is defined as the log base 10 of
, the formula will remain the same.
(c) The Mathematica notebook rate_of_convergence1.nb (which you can download
from the class website) computes the value of the solution of the equation sin
x+ x = 1
using (i) Newton’s method, (ii) the secant method, (iii) the fixed point
iteration
method, (iv) the fixed point iteration method combined with Aitken
extrapolation,
and (v) the fixed point iteration method combined with Steffensen ’s method for
accelerating
convergence. Run all the programs from the notebook and use the formula
for α derived in part (b) to find empirically the numerical values of α
for all these
methods. Does the values of α you have obtained match the theoretical
predictions?
Discuss briefly. One can prove (but you do not need to do this!) that the order
of
convergence of the secant method is
Note: Since we are using a very high accuracy (namely, 10000 digits), you have
to be
patient when runnig the programs; make sure that a program is finished before
you
run the next one. There is no need to attach the printout of running the
programs –
it will be too long. Give only the numbers that you use and show your
calculations
in detail. Recall that to perform some calculation in Mathematica , you need to
put
the cursor on that part of the program, press shift , and while holding it down,
press
return. Finally, note that in the notebook rate_of_convergence1.nb logarithms
base 10 are used.
Problem 2. In this problem you will develop a
modification the Newton’s method to find
a zero of multiplicity m ≥1 of the equation f(x) = 0.
(a) Let the sequence be defined by the
recurrence relation (and
is some initial guess), where . Prove that,
if the point p is a zero of
multiplicity m of f, then g'(p) = 0. This implies that the sequence
converges
faster than linearly .
Hint: The calculations you need to do are very similar to the ones on pages
80–81 of
the book involving the function μ(x).
(b) Find the multiplicity of the root of the
equation .
(c) The following Mathematica code similar to the codes from Problem 1
can be used (after an appropriate modification) to find empirically the order of
convergence
of the method. What is the order of the convergence that you observe? Explain
briefly your reasoning. (Again, be patient – Mathematica can take a while
because
you are doing the calculations with accuracy or 50000 decimal digits!)
(d) The number is a root of the equation
of multiplicity 5. Run the
Mathematica code from part (c) after modifying it appropriately and use the
output
to find the order of convergence in this case. What do you observe?
(e) Modify the Matlab code newton.m to write a code newton_m.m that implements
the
algorithm from part (a) for finding zeros of multiplicity m of the equation f(x)
= 0.
The first line of your code must be
Note that in Matlab the name of a file must be the same as the name of the code
in it.
(f) One can estimate roughly the order of convergence m of an iterative method
as follows.
If after iterating enough number of times the error is significantly smaller
than 1 (say,
0.01 or smaller), then the number of correct digits of
is roughly m times the
number of correct digits of
. You can observe
this, in the following quadratically
convergent sequence (coming from using Newton’s method to find
as in Problem 4
of Homework 3)
Give a theoretical explanation of this rule of thumb.
Hint: For example, in the number 3.162277665175674 . . . in the sequence above,
you
know the result with 8 correct digits after the decimal point, namely,
3.16227766;
the next one, 3.162277660168379335963284232 . . ., has 17 correct digits,
namely, the
correct digits are 3.16227766016837933. If you know a number
with k digits of
accuracy, what can you say about ?
Problem 3. Use the synthetic division algorithm to find consecutively the
following ratios:
Use this result to find all roots (including the non real ones ) of the
polynomial equation
The builtin Matlab command roots finds (possibly complex) roots of polynomials.
The
argument of roots is a vector of all coefficients of the polynomial, starting
with the one at
the highest power . For example, to find all roots of the polynomial
,
type and press return. Use this command to
find the roots of
the polynomial equation (1) after you deflate it by eliminating the roots −1 and
2 (so that
you have to use roots to solve a cubic equation ). Attach your Matlab printout.
Remark: One can find out more information about Matlab functions, say roots, by
typing
help roots
Use this to see the description of Matlab command fzero which is a builtin zero
finder. By
typing
help help
you will get information about the command help itself, and
help /
will give you a description of all operators and special characters.
Problem 4. Directly from the definition, find the rates of convergence α
and the asymptotic
error constants λ for each of the sequences (all of which tend to 0)
Prev  Next 