Notes: Rate of Convergence

Notes: Rate of Convergence Suppose we have a sequence of real numbers that converge to some point x: x 0 , x1 , x 2 , . . . → x Is there a way to talk about how fast the numbers are converging to x? Definition: If |xn+1 − x| =λ<∞ |xn − x| then the sequence converges linearly to x. The constant λ > 0 is called the asymptotic error. lim n→∞ Definition: If |xn+1 − x| =λ<∞ |xn − x|2 (where λ > 0) then the sequence converges quadratically to x. lim n→∞ Definition: If |xn+1 − x| =λ<∞ n→∞ |x − x|α n then the sequence converges to x of order α. This is the definition we use to actually compute the rate of convergence- Typically, this means that we need to see if α = 1 or 2. Examples: lim 1. Let xn = n1k for some fixed k > 0. Then we know this sequence converges to 0. Compute the rate of convergence: |xn+1 | = n→∞ lim lim n→∞ |x |α n 1 (n+1)k 1 nαk  = n→∞ lim nα n+1 k We get convergence for α = 1, but not α = 2, so this sequence converges linearly to 0. This is interesting- Sequences like the following: xn = 1 , n xn = 1 , n2 xn = 1 ,... n3 all converge linearly to zero. n 2. Let xn = 10−2 (which converges to 0). Compute the rate of convergence: n+1 10−2 |xn+1 | = lim lim n→∞ |x |α n→∞ 10−2n ·α n It’s easy to see that if α = 2, we get convergence. In fact, using this as a template sequence, we can see how fast a quadratically convergent sequence moves. Compute the terms of the sequence: 10−2 , 10−4 , 10−8 , 10−16 , 10−32 , 10−64 so that after just 6 steps, we’re already past machine . Algorithms that are quadratically convergent are highly prized! 1 0.1 Fixed Point Iteration Now let’s analyze the fixed point algorithm, xn+1 = f (xn ) with fixed point r. We will see below that the key to the speed of convergence will be f 0 (r). Theorem (Convergence of Fixed Point Iteration): Let f be continuous on [a, b] and f 0 be continuous on (a, b). Furthermore, assume there exists k < 1 so that |f 0 (x)| ≤ k for all x in (a, b). • If f 0 (r) 6= 0, the sequence converges linearly to the fixed point. • If f 0 (r) = 0, the sequence converges at least quadratically to the fixed point (this is sometimes called superconvergence in the dynamical systems literature). Proof: This is more than we did in class- We will also prove that the sequence xn → r, which we do first. The following computations show this (they come from a repeated application of the Mean Value Theorem): |x1 − r| = |f (x0 ) − f (r)| ≤ |f 0 (x∗)||x0 − r| ≤ k|x0 − r| where x∗ is between x0 and r. Continuing, we see that: |xn − r| ≤ |f 0 (x∗ )||xn−1 − r| ≤ k|xn−1 − r| ≤ k n |x0 − r| with 0 ≤ k < 1, so that k n → 0 as n → ∞. Therefore, |xn − r| → 0 as n → ∞. An important note: While x∗ depended on xn−1 , the value of k does not depend on n- The assumption that |f 0 (x)| ≤ k < 1 was important for this step. Now we show that the sequence converges linearly if f 0 (r) 6= 0: lim n→∞ |f (xn ) − f (r)| |xn+1 − r| = lim = lim |f 0 (cn )| n→∞ n→∞ |xn − r| |xn − r| where cn is between xn and r. Note that, because xn → r, then cn → r as well. Because f 0 is continuous on our interval that contains all the cn ’s and r, 0 lim |f (cn )| = f 0   lim cn n→∞ n→∞ = |f 0 (r)| To get an idea about why the second case should give quadratic convergence, consider the Taylor expansion of f about the fixed point r: 1 f (x) = f (r) + f 0 (r)(x − r) + f 00 (c)(x − r)2 2 where c is in the interval between x and r. Now, if f 0 (r) = 0, and rearranging terms, we see that: f (x) − f (r) f 00 (x∗) = (x − r)2 2 2 Now to prove the quadratic convergence, |xn+1 − r| |f (xn ) − f (r)| |f 00 (cn )| = lim = lim n→∞ |x − r|2 n→∞ n→∞ |xn − r|2 2 n lim where cn is in the interval between xn and r. And the proof is finished just as before (by assuming that f 00 is continuous on the interval). Before continuing, there is a property of continuous functions that we want to consider (used in the next section): Lemma: Let f be continuous on some open interval I which contains a point a where f (a) 6= 0. Then there exists an interval about a (contained in I), [a − δ, a + δ] such that f (x) 6= 0 for all x in [a − δ, a + δ]. Proof: The proof is by contradiction- That is, if we want to prove that statement A implies statement B, assume A and not B. In this case, we assume that f is continuous, and for every δ-sized interval about a, there is at least one point so that f (x) = 0. If that is true, then let δ be any number, and choose a1 6= a in the interval about a so that f (a1 ) = 0. Next, let δ be half the distance between a and a1 . In this interval, we can find a2 6= a so that f (a2 ) = 0. Next, we repeat by letting δ be half the distance from a2 to a, and find a3 . Repeat this process. Now we have constructed a sequence of points, an , which converge to a. Furthermore, f (an ) = 0 for all n, which means that: lim f (an ) = 0 n→∞ But, since an → a and f is continuous at a, we must have:  lim f (an ) = f n→∞  lim an = f (a) 6= 0 n→∞ This is a contradiction. Therefore, we conclude the opposite- That there must be an interval about a so that f (x) 6= 0 in the entire interval. 0.2 Newton’s Method As we will recall, Newton’s Method was an algorithm to solve g(x) = 0 (this is not yet a fixed point algorithm). Given an initial x0 , we compute a sequence of points defined via: xn+1 = xn − g(xn ) g 0 (xn ) Some questions we’d like to answer: • Under what conditions will Newton’s Method converge? • If the sequence does converge, at what rate does it converge? • Let r be the root of g. What happens if g 0 (r) = 0? 3 As you might expect, the answer to the first question is not as exact as it was for Fixed Point Iteration: Theorem (Convergence of Newton’s Method): Let g be twice continuously differentiable on the interval (a, b). If r ∈ (a, b) such that g(r) = 0 and g 0 (r) 6= 0, then there exists δ > 0 such that Newton’s Method will converge if started in the interval [r − δ, r + δ]. In this case, the sequence converges quadratically. We make one observation to begin: Newton’s Method is a form of Fixed Point iteration: xn+1 = F (xn ) where F (x) = x − g(x) g 0 (x) and the convergence of fixed point iteration depended on the derivative of F : F 0 (x) = 1 − g 0 (x)g 0 (x) − g(x)g 00 (x) g(x)g 00 (x) = (g 0 (x))2 (g 0 (x))2 we also see that F 0 (r) = 0. To be able to use the Fixed Point Theorem (Item 3 above), we would need to show that F satisfies those conditions- Namely, that there is an interval (a, b) about r where F 0 is continuous and |F 0 (x)| < 1. Let’s see how our assumptions create the appropriate δ so that we guarantee the convergence of Newton’s Method. Here are some observations: • (Continuity of F and F 0 ) F will be continuous if g and g 0 are continuous, and g 0 (x) 6= 0. Now we have no problem with g- It is continuous on (a, b). Since g 0 (r) 6= 0, and g 0 is continuous, we can guarantee that there exists δ1 so that g 0 (x) 6= 0 for all x in [r − δ1 , r + δ1 ] (note that this interval needs to be contained in (a, b), so make the choice of δ1 appropriately). In this interval, F is continuous. Since we also assumed that g 00 is continuous on (a, b), then F 0 will also be continuous on [r − δ1 , r + δ1 ] • (The size of F 0 (x)) We know that F 0 (r) = 0, and we know that F 0 (x) is continuous on [r − δ1 , r + δ1 ]. By the continuity of F 0 , there must exist 0 < δ2 ≤ δ1 so that |F 0 (x)| < 1 for all x in [r − δ2 , r + δ2 ]. The value δ2 is the δ in our Theorem. By our two previous observations, we can apply the Fixed Point Convergence theorem to the function F - That proves both convergence and (at least) quadratic convergence. 0.2.1 EXERCISE: Prove that, if g(r) = 0 and g is continuous on an interval about r, then there exists δ so that |g(x)| ≤ k < 1 for all x in (r − δ, r + δ). (HINT: Follow the proof of the Lemma) 0.2.2 EXERCISE: Give an interval on which we can guarantee the convergence of Newton’s Method, if g(x) = x2 − 1 (give the interval about the root r = 1). 4 0.2.3 Failure to Converge Quadratically: Consider g(x) = x2 . Will Newton’s Method converge quadratically to the root x = 0? First, we convert to the Fixed Point Iteration method and see what we can conclude: F (x) = x − g(x) x2 x 1 = x − =x− = x 0 g (x) 2x 2 2 In this case, F 0 (0) = 12 6= 0, so Newton’s Method will converge, but only linearly. This happened because there was a multiple root at x = 0: Definition: A function f (x) has a root of multiplicity m at x = a if: f (a) = 0, f 0 (a) = 0, f 00 (a) = 0, . . . , f (m) (a) = 0, but f (m+1) (a) 6= 0 Be sure to keep the conclusions of the Fixed Point Method and Newton’s Method distinct: • In Fixed Point Iteration, if F 0 (r) = 0, we get at least quadratic convergence. If F 0 (r) 6= 0, we get linear convergence. • In Newton’s Method, if g 0 (r) 6= 0, we get quadratic convergence, and if g 0 (r) = 0, we get only linear convergence. 0.2.4 Exercise: The function f (x) = x3 − 4x has a root at r = 2. If the error ei = xi − r after 4 steps of Newton’s Method is e4 = 10−6 , estimate e5 . (Hint: What is the limit of en+1 /en as n → ∞?) 0.2.5 Practical Notes for Newton’s Method: If you believe your function has a “simple” root (that is, g(r) = 0 and g 0 (r) 6= 0), and you have a reasonable starting guess, x0 , then Newton’s Method is the method of choice. In practice, we will not know if we have a simple root, and we may not have a very good starting estimate- In that case, you might use something like Bisection to get you started, then switch to Newton’s Method once you’re close. We’ll see this in a method later on. 1 Methods without Derivatives There are methods other than bisection if the function’s derivative is not known (or not easily computed). We discuss the ideas briefly below: • Secant Method Rather than using the x−intercept of the tangent line (as in Newton), we begin with two points, x0 and x1 , then use the x−intercept of the secant line as our new estimate, x2 . In this method, we do not need to start with the root bracketed (as in bisection), and in fact the root may not be bracketed. • Method of False Position Similar to bisection, but the midpoint is replaced by the x−intercept of the line between (a, f (a)) and (b, f (b)). The new interval is chosen so that the root is still bracketed. Note that this method may not do as well as bisection, which halves the interval at each step. 5 • Muller’s Method This is a generalization of the Secant Method in that it uses three points, x0 , x1 , x2 and uses a parabola instead of a line to get the next point. Kind of an interesting idea, and we’ll discuss finding that parabola later. These methods work fairly well under the right circumstances. The next method we will do in some detail, as it forms the basis of Matlab’s fzero function. 1.0.6 Exercise: From the description of the Method of False Position, give an explicit algorithm for finding a root of f . You can assume that you are given [a, b] such that f (a)f (b) < 0. Apply the algorithm to f (x) = x3 − 2x2 + 23 x on [−1, 1]. Take special note of the sizes of the intervals that you create. 1.1 Inverse Quadratic Interpolation (IQI) In the IQI algorithm, we construct the quadratic polynomial x = p(y) rather than y = p(x). This has the major benefit that (i) the x−intercept is very easy to find and (ii) we are always guaranteed that the parabola passes through the x−axis once. As we know, three points defines a parabola. These three points: (a, A), (b, B), (c, C) can be used to construct the following quadratic polynomial: P (y) = a (y − A)(y − C) (y − A)(y − B) (y − B)(y − C) +b +c ((A − B)(A − C) ((B − A)(B − C) ((C − A)(C − B) (This is a Lagrange polynomial, and we’ll discuss them later) Note that P (A) = a, P (B) = b, and P (C) = c (that is what it means to say that the polynomial interpolates the data points). So, given a = xi , b = xi+1 and c = xi+2 , then xi+3 is computed as the x−intercept of P (y) (computed as P (0)): xi+3 = P (0) = 1.2 aBC bAC cAB + + (A − B)(A − C) (B − A)(B − C) (C − A)(C − B) Brent’s Method Brent’s method is the actual workhorse in root-finding without the use of derivatives. It is what Matlab uses in fzero1 . Brent’s Method combines root bracketing, bisection and IQI to converge from the neighborhood of a zero crossing. To see what Matlab actually does, enter the following in the command window: type fzero. Most of what you see is “error handling”- That is, in a professional piece of software, you have to try to anticipate all the problems that might come up. Here are a few problems associated with fzero: 1 Matlab also has a roots command specifically for polynomials, but this technique uses eigenvalues to solve for the roots- We’ll see that later. 6 • How is the function being defined? It can be entered as an inline function (like our examples), or as the name of an M-file. • Did the user input an appropriate bracket for the root, or an initial guess, from which we have to construct an initial bracket? Is the initial guess appropriate (for example, √ did the user input −1 for x)? • How much output does the user want? The default is for Matlab to stay quiet until the final result, but you can have it output details about what it is doing. You might try this example: fzero(’x.^3+x-1’,1,optimset(’Display’,’iter’)) You can see fzero trying to do an initial bracketing before the algorithm proceeds. • How should the algorithm stop, and what information should be presented? Lots of options here. 7