<\body> AM117 Homework set #2, Sample solutions <\itemize> If you are proving something, write down and . It doesn't take much time, but it helps you and me understand what you're writing and tells me that you know what you're talking about. Please don't use red pen in your answers. If you are asked for the apparent order of convergence, , don't guess. We are considering <\equation*> f(x)\+3*x*a|3x+a>. (Compare this to the second problem of the last homework set.) Verifying that > is a fixed point is a matter of plugging it in: <\equation*> f()=+3*aa|3a+a>=|4a>=. To obtain the order of convergence ``the new way'', we obtain the first derivative of : <\equation*> f(x)=-6*a*x+3a|9x+6*a*x+a> and observe <\equation*> f()=-6*a*a+3a|9a+6*a*a+a>=0. By the theorems in Section 2.3, we may exclude linear convergence, and we need to keep looking. <\equation*> f(x)=-48*ax|27x+27a*x+9ax+a>. It's easy to see that ()=0>, so we don't have quadratic convergence, either. Next: <\equation*> f(x)=+864ax-48a|81x+108*a*x+54ax+12*ax+a>. We find <\equation*> f()=, thus by our theorem, we know (in agreement with last time) that our convergence is of third order. Further, we find the asymptotic error constant <\equation*> lim\>\||\|e\|>=()|3!>== agrees as well. (If you need a computer algebra system to do tedious calculations like these, I can recommend either Maxima<\footnote> or Axiom<\footnote> . Both are open-source and free to download.) a) Let's start by visualizing the situation: We shall apply the theorem on p. 84 to <\equation*> f(x)\exp(-x). We need to verify the following: <\itemize> is continuous on the closed interval : > It maps to : > (Note: not necessarily .) It's differentiable: > <\equation*> f(x)=-2x*exp(*-x). The magnitude of > is bounded away from 1 on : Observe \0> on , (0)=0>. Consider <\equation*> f(x)=exp(-x)(4x-2)=0\x=\. Let \ >and observe (x)\0>, so there's a local minimum of > at >. It's not hard to verify <\equation*> f(x)\-1, and by C>(\)> we know that (x)\f(x)> for [0,1]>. As a consequence, the theorem on p. 84 yields the claim. b) and c) Let >> be the fixed point whose existence and uniqueness is guaranteed by a). It's easy to see that (x>)=0>, so convergence will be at best linear. We may thus use the error estimates (1) and (2) on p. 92 to estimate our progress. After the first iteration, we use the a-priori bound <\equation*> \|p-p\|\|1-k>\|p-p\| with (x)\|\0.8578> to estimate the number of iterations needed: <\equation*> (1-k)|\|p-p\|>\k\log(1-k)|\|p-p\|>log*k\n We obtain these results, noting that the estimate of the number of iterations is fairly good--it tells us at least the order of magnitude of steps to expect. <\with|par-par-sep|0> from the following Matlab code: <\with|par-par-sep|0> We obtain <\with|par-par-sep|0> On double precision systems, the error is below machine precision from the fourth iteration onwards. The apparent order of convergence approaches three, which makes sense since x=-sin x>, which is zero at >, accelerating Newton's method to third order according to the discussion on p. 100. Here's the code: <\with|par-par-sep|0> Results: <\with|par-par-sep|0> Discussion: The apparent order of convergence is roughly one, which is the same as the bisection method. Unfortunately, though, the bisection method would converge slightly faster--it would cut its error in half in each iteration, which our method fails to achieve by a slight margin--its convergence in this case is of order )=O((2/3))> (cf. p. 101). The polyomial can be factored as <\equation*> 27*x^4+162*x^3-180*x^2+62*x-7=(27x+189)(x-1/3), so is a root of multiplicity three. Code: <\with|par-par-sep|0> We begin by plotting the function <\equation*> f(x)\x-18x+45. This plot provides sufficient verification of the existence of the roots in parts a) and b), by the Intermediate Value Theorem. Let's take a look at the data: <\with|par-par-sep|0> Discussion: a) appears to converge of order greater than two, while b) appears to converge at just about the order predicted for the secant method, namely )/2\1.618>. The explanation for the difference in behaviors (or, rather, for the exceptionally good behavior in a)) lies in the fact that is nearly linear around >, in fact ()=0>. If you look up the error term of the secant method, you will find that it is dominated by the second derivative (cf. p. 109). Also, if you consider that the secant method finds the root of a linear function in a single step, you will agree that this behavior makes sense.\ Here's the code: <\with|par-par-sep|0> Data: <\with|par-par-sep|0> Discussion: Convergence appears to be third order (or better) for both problems. In the third problem, we learned that the order of convergence of Newton's method depends on the second and third derivatives. Since we are dealing with a zero of multiplicity three (, =0>, =0>), it seems justified to expect better than quadratic convergence. Code: <\with|par-par-sep|0> <\initial> <\collection> <\references> <\collection> > >