Numerical Analysis Homework 1 Solved

I.           Consider the bisection method starting with the ini-tial interval [1.5,3.5]. In the following questions “the interval” refers to the bisection interval whose width changes across different loops.

•   What is the width of the interval at the nth step?

•   What is the maximum possible distance between the root r and the midpoint of the interval?

II.         In using the bisection algorithm with its initial in-terval as [a0,b0], we want to determine the root with its relative error no greater than . Assume a0 0.

Prove that the number of steps n must satisfy

 .

III.        Perform four iterations of Newton’s method for thepolynomial equation p(x) = 4x3 − 2x2 + 3 = 0 with the starting point x0 = −1. Use a hand calculator and organize results of the iterations in a table.

IV.        Consider a variation of Netwon’s method in whichonly the derivative at x0 is used,

 .

Find C and s such that

 .

V.         Within ( ), will the iteration xn+1 = tan−1 xn converge?

VI.        Let p 1. What is the value of the following continued fraction?

 

Prove that the sequence of values converges. (Hint: this can be interpreted as x = limn→∞ xn, where  , and so forth.

Formulate x as a fixed point of some function.)

VII.      What happens in problem II if a0 < 0 < b0? Derive an inequality of the number of steps similar to that in II. In this case, is the relative error still an appropriate measure?

VIII.     (∗) Consider solving f(x) = 0 by Newton’s method with the starting point x0 close to a root of multiplicity k. We assume that f ∈Ck+1. Note that α is a zero of multiplicity k of the function f iff f(k)(α) 6= 0; ∀i < k, f(i)(α) = 0.

•   How can a multiple zero be detected by examining the behavior of the points (xn,f(xn))?

•   Prove that if r is a zero of multiplicity k of the function f, then quadratic convergence in Newton’s iteration will be restored by making this modification:

 .

IX.        (∗) Analysis of the secant method for a root of multiplicity k by assuming that it converges.

•   Prove that if r is a zero of multiplicity k 1 of the function f, the secant method only has linear convergence.

•   Use the same argument to show that the convergence rate of the secant method is  .

Each of the first six problems weighs 5 points. Each of the other problems weighs 10 points. In particular, the last two problems are for extra credit and you do not have to solve them. However, special students such as my graduate students who audit this class have to solve all problems.

2        C++ programming
A.    Implement the bisection method in C++. Test your program on these functions and intervals.

•   x−1 − tanx on [0, ],

•   x−1 − 2x on [0,1],

•   2−x + ex + 2cosx − 6 on [1,3],

•   (x3+4x2+3x+5)/(2x3−9x2+18x−2) on [0,4].

B.    Implement Newton’s method in C++ to solve the equation x = tanx. Find the roots near 4.5 and 7.7.

C.    Implement the secant method in C++. Test your program on the following functions and initial values.

1

•   sin(x/2) − 1 with ,

•   ex − tanx with x0 = 1,x1 = 1.4,

•   x3 − 12x2 + 3x + 1 with x0 = 0,x1 = −0.5.

You should play with other initial values and (if you get different results) think about the reasons.

Each of the above three coding assignments weighs 10 points. The total number of points of this homework without extra credit is thus 5 × 6 + 10 + 10 × 3 = 70. IMPORTANT:

•   Under the signature of your function in .m file, you must clearly state

–   the purpose of this C++ function,

–   the meaning of each input parameter,

–   preconditions on each input parameter,

–   the meaning of each output parameter,

–   postconditions on each output parameter.

•   You must present in your solution your C++ code and corresponding test results.

•   You need to send your source code to the course email NumApproximation@163.com.