# 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 built-in 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 built-in 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 |