%% 28. Analytic continuation and convergence acceleration ATAPformats %% % % We have considered techniques for rational approximation % by best approximation on an % interval (Chapter 24, {\tt remez}), % interpolation or linearized least-squares fitting on an % interval or disk (Chapter 26, {\tt ratinterp} and {\tt ratdisk}), % and Pad\'e approximation at a point or Chebyshev--Pade approximation % on an interval (Chapter 27, {\tt padeapprox} and {\tt chebpade}). % In this final chapter, we turn to the application of such approximations for % extrapolating a function to real or complex values $z$ outside the region % where it is initially known. Three of the applications listed in Chapter % 23 fall into this category: those numbered 3 (convergence acceleration for sequences % and series), 4 (determination of poles), and 5 (analytic continuation). % %% % It will be a chapter more of examples than theory. For an example to % begin the discussion, suppose we pretend that we can evaluate % $$f(z) = \tanh(z)$$ % for real values of $z$ but know nothing about complex values, and we wish to % estimate where $f$ has poles. How might we proceed? (Of course we really % know the answer: there are poles at all the odd multiples of $\pm \pi % i/2$.) %% % The first thing to try might be polynomials. For example, we could use % Chebfun to construct a polynomial that approximates $f$ to 16 digits on % $[-1,1]$, %% % \vskip -2em f = @(z) tanh(z); p = chebfun(f); length(p) %% % % From here, however, it is hard to make much progress. As we know from % Chapter~8, $p$ will be a good approximation to $f$ within a certain % Bernstein ellipse, the Chebfun ellipse, which can be plotted by the % command {\tt chebellipseplot}. We can expect this ellipse to reach % approximately out to the first singularities at $\pm \pi i/2$. Once we % hit the ellipse, however, everything will change. % According to the theory of Walsh  and Blatt and Saff  mentioned in Chapter~18, % zeros of $p$ will cluster all along the boundary, and a further result of Blatt and % Saff states that outside the ellipse, there will be no convergence at all. The % polynomial $p$ will simply grow rapidly, its behavior having nothing % to do with that of $f$. We can confirm this prediction with contour % plots. Here are plots of $|f(z)|$ and $|\kern .7pt p(z)|$ in the upper % half-plane, with black contours at levels $0.25, 0.5, \dots , 3$ and red % contours at $10^1, 10^3, 10^5, \dots, 10^{19}$. We see immediately that % $p$ matches $f$ very well inside the Chebfun ellipse, which is marked in % blue, but not at all outside. % %% % \vskip -2em x = -4:.05:4; y = 0:.05:8; [xx yy] = meshgrid(x,y); zz = xx + 1i*yy; ff = f(zz); pp = p(zz); lev1 = .25:.25:2; lev2 = 10.^(1:2:19); subplot(1,2,1), hold off, contour(x,y,abs(ff),lev1,'k'), hold on contour(x,y,abs(ff),lev2,'r'), FS = 'fontsize'; axis([-4 4 0 8]), axis square, title('tanh(z) in upper half-plane',FS,9) subplot(1,2,2), hold off, contour(x,y,abs(pp),lev1,'k'), hold on contour(x,y,abs(pp),lev2,'r') axis([-4 4 0 8]), axis square, title('Degree 29 polynomial approx',FS,9) chebellipseplot(p,'b','linewidth',2) %% % \vskip 1pt %% % To get better information, we turn to rational approximation. A practical % approach is to use |ratinterp| to compute rational linearized least-squares % approximations of $f$ in $[-1,1]$. Specifically, suppose we take $r$ to % be the type $(7,8)$ approximation to $f$ in 1000 Chebyshev % points and draw the same contour plots as before. The picture changes % completely, showing very impressive agreement over most of the range % plotted. This is the power and the promise of rational approximation. d = domain(-1,1); [p,q,r,mu,nu,poles] = ratinterp(d,f,7,8,1000); rr = r(zz); subplot(1,2,1), hold off, contour(x,y,abs(ff),lev1,'k'), hold on contour(x,y,abs(ff),lev2,'r') axis([-4 4 0 8]), axis square, title('tanh(z) in upper half-plane',FS,9) subplot(1,2,2), hold off, contour(x,y,abs(rr),lev1,'k'), hold on contour(x,y,abs(rr),lev2,'r') axis([-4 4 0 8]), axis square, title('Type (7,8) rational approx',FS,9) chebellipseplot(p,'b','linewidth',2) %% % \vskip 1pt %% % For a direct measure of the accuracy of $r$ as an approximation to $f$, % we can look at $|f(z)-r(z)|$. In the following plot the contours, from % bottom to top, lie at $10^{-14}, 10^{-12}, \dots, 10^{-2}$. % Evidently the approximation is excellent over a wide region. %% % \vskip -2em levels = 10.^(-14:2:-2); clf, subplot(1,2,1), contour(x,y,abs(ff-rr),levels,'k') axis([-4 4 0 8]), axis square, title('|tanh(z) - r(z)|',FS,9) %% % \vskip 1pt %% % Results like these become all the more remarkable when one recalls that % the problem of analytic continuation is ill-posed: analytic continuations % are unique, but they do not depend continuously on the data. For % example, the following observation shows the ill-posedness of the problem % of continuing a function analytically from the interval $(-1,1)$ to the % unit disk. If $f$ is analytic in the disk, then for any $\varepsilon>0$, % there is another function $g$ analytic in the disk such that $\|f-g\|\ge % 1$ on the disk and yet $\|f-g\|\le \varepsilon$ on the interval. (Proof: % perturb $f$ by $\varepsilon\sin(Mz)$ for a suitable value of $M$.) % Because of this ill-posedness, every successful example of numerical % analytic continuation must entail some smoothness assumptions about $f$, % whether implicit or explicit. That is to say, numerical analytic % continuation always involves some kind of regularization. (A standard % reference on this subject is [Hansen 1998].) In the computations just % shown, the regularization is introduced by the use of the SVD in % |ratinterp|. %% % The question with which we opened the discussion was, where are the poles % of $\tanh(z)\kern .7pt$? To experiment with this, let us now apply % |ratinterp| to compute approximants of types $(2,2), (3,3), \dots , % (8,8)$, and examine the poles of these approximations. In the next % output, following the convention of the past few chapters, $(m,n)$ % represents the permitted type of each approximant and $(\kern .5pt % \mu,\nu)$ the exact type, with $\mu\le m$ and $\nu\le n$. Note that % $(\kern .5pt \mu,\nu)$ always comes out in the form % $(\hbox{odd},\hbox{even})$, because $f$ is an odd function. Thus there % are always an even number of poles, which come in complex conjugate pairs % and are pure imaginary, and we print just their positive imaginary parts. %% % \vskip -2em for n = 2:8 [p,q,r,mu,nu,poles] = ratinterp(d,f,n,n,1000); fprintf('\n(m,n)=(%d,%d), (mu,nu)=(%d,%d):\n',n,n,mu,nu) yi = sort(imag(poles)); fprintf('%15.10fi',yi(yi>0)) end %% % The table shows that for larger values of $(m,n)$, two of the poles lie % near $1.5707963i$ and $4.71i$. We compare these with the actual first % three poles of $\tanh(z)$ in the upper half-plane: %% % \vskip -2em disp('Exact poles:'), fprintf('%15.10fi',(pi/2)*[1 3 5]) %% % Evidently the type $(7,8)$ approximation has captured the first two poles % to 9 and 3 digits of accuracy, respectively, numbers that are consistent % with the contour levels near $z=1.57i$ and $4.71i$ in the last contour % plot. %% % % To understand computations like this, it is important to recognize that % the goal'' of $r$ is not to find the poles of $f$, but simply to % approximate $f$ over $[-1,1]$. If $r$ turns out to have poles near those % of $f$, this is a by-product, a side effect that happened because placing % poles there is an effective strategy for approximation.\footnote{Still, % side effects can be the basis of powerful algorithms. An example is the % Lanczos iteration in numerical linear algebra, which is the standard % method of computing extreme eigenvalues of large symmetric matrices % [Trefethen \& Bau 1997]. Using this method, it is often possible % to find a few dozen eigenvalues of a matrix even if the dimension is in % the millions. Yet at bottom, the Lanczos iteration does nothing but % construct a polynomial to minimize a certain norm. The accurate % eigenvalues are a by-product of the minimization, since the optimal % polynomial has roots close to some of the eigenvalues of the matrix % [Trefethen \& Greenbaum 1994, Kuijlaars 2006].} To illustrate this, % suppose we compare the type $(7,8)$ approximation above to one of type % $(15,8)$. One might expect that with more degrees of freedom, the new % approximation would capture the first pole more accurately. In fact, the % approximation returned has exact type $(15,2)$, and the accuracy of the % pole has deteriorated, because the denominator is less important to the % quality of the least-squares approximation: % %% % \vskip -2em [p,q,r,mu,nu,poles] = ratinterp(d,f,15,8,1000); fprintf('\n(m,n)=(15,8), (mu,nu)=(%d,%d):\n',mu,nu) yi = sort(imag(poles)); fprintf('%15.10fi',yi(yi>0)) %% % If we go further and ask for a type $(35,8)$ approximant, |ratinterp| % returns an approximation with no poles at all. The numerator now % provides so much flexibility for the least-squares problem that the % degrees of freedom in the denominator are not needed in 16-digit % arithmetic, putting us back in the situation of the Chebfun ellipse of % the first plot of this chapter. %% % \vskip -2em [p,q,r,mu,nu,poles] = ratinterp(d,f,35,8,1000); fprintf('\n(m,n)=(35,8), (mu,nu)=(%d,%d):\n',mu,nu) %% % One must always bear this in % mind when using rational approximations for extrapolation: increasing $m$ % and/or $n$ does not always improve the accuracy of the quantities one % cares about. %% % One way to get an idea of the dependence of an approximation on $m$ and % $n$ is to print a table of digits of accuracy. The following table, for % example, indicates the number of digits of accuracy in the computed first % pole of $\tanh(z)$ for $m = 1,3,5,\dots,19$ and $n = 2,4,6,\dots,20$, all % based on robust least-squares fits in 200 Chebyshev points in 16-digit % arithmetic. The table shows again the effect that increasing $m$ beyond % a certain small value---moving right in the table---diminishes the % accuracy of the pole. %% % \vskip -2em err = zeros(1,10); disp('DIGITS OF ACCURACY: LEAST-SQUARES') for n = 2:2:20 for m = 1:2:19 [p,q,r,mu,nu,poles] = ratinterp(d,f,m,n,200); p1 = imag(poles(abs(poles-1.6i)==min(abs(poles-1.6i)))); err((m+1)/2) = -round(log10(abs(p1-pi/2))); end fprintf('%3d',err), disp(' ') end %% % The use of rational approximations for locating poles or other % singularities has an honorable history. Many applications are mentioned % in the monograph by Baker and Graves-Morris , which is a standard % reference on $\hbox{Pad\'e}$ approximation. One interesting kind of % application is to locating singularities of solutions of ODEs or PDEs % computed numerically, an idea explored among others by Weideman . % For Chebfun-based explorations, including the application of |ratinterp| % to find complex singularities of solutions to the Lorenz and % Lottka--Volterra equations, see $\hbox{[Pach\'on 2010]}$ and [Webb 2012]. %% % Having just mentioned $\hbox{Pad\'e}$ approximation, which was the % subject of the last chapter, let us now turn to this alternative method % of constructing rational approximations. Here is a repetition of the % last experiment, the table of digits of accuracy in the first pole of % $\tanh(z)$, but now based on $\hbox{Pad\'e}$ approximation instead of % rational least-squares. The results are similar, but better. This is not % a general conclusion: it depends on the problem. %% % \vskip -2em disp(' DIGITS OF ACCURACY: PADE') for n = 2:2:20 for m = 1:2:19 [r,a,b,mu,nu,poles] = padeapprox(f,m,n); p1 = imag(poles(abs(poles-1.57i)==min(abs(poles-1.57i)))); err((m+1)/2) = -round(log10(abs(p1-pi/2))); end fprintf('%3d',err), disp(' ') end %% % In principle, least-squares fitting and $\hbox{Pad\'e}$ approximation are % very different techniques, since the first uses function values only % at many different points, whereas the second uses values of the function % and its derivatives at a single point. (These are the extreme cases of % the general notion of $\hbox{{\em multipoint Pad\'e approximation.})}$ % In our actual computation, however, the difference is diminished, because % |padeapprox| begins by computing Taylor coefficients numerically by the % FFT based on samples of the function at roots of unity, a standard % technique. So in fact, in this comparison, |ratinterp| and |padeapprox| % both work from function values: the first from samples on $[-1,1]$, the % second from samples on the unit circle. This raises the question, what is % achieved by passing through the intermediate stage of Taylor % coefficients? It is a fair point, and indeed, another effective approach % would be to solve a rational least-squares problem on the circle directly % as in Chapter 26. Explorations of this kind are presented in % $\hbox{[Pach\'on 2010].}$ %% % We now turn to the topic of acceleration of convergence of % sequences and series. The challenge here is as follows. % Suppose we know some of the initial terms of a convergent sequence, % $$s_0, s_1, s_2, s_3, \dots \to S, \eqno (28.1)$$ % and we want to estimate the limit $S$. Equivalently, suppose we % wish to estimate the limit of an infinite sum, % $$S = a_0 + a_1 + a_2 + \cdots. \eqno (28.2)$$ % The two problems are equivalent since we may regard (28.1) as a sequence % of partial sums, % $$s_n = \sum_{k=0}^n a_k, \quad a_k = s_{k+1}-s_k. \eqno (28.3)$$ % If the sequence or series converges slowly, how might we speed it up? For % example, perhaps we can afford to compute 20 terms, but this gives just % 2-digit accuracy. Can we process the data further somehow to improve the % accuracy to 6 digits? %% % % There is a long history to such questions, reaching from Stirling and Euler % to the recent tour de force % solution of nine of the ten SIAM 100-Digit Challenge'' problems to % 10,000 digits of accuracy [Bornemann et al.\ 2004]. % It is probably fair to say that almost every method for % accelerating convergence is based on the idea of embedding the sequence % in an analytic function, though this may not be how the original authors % conceived or described their method. % %% % % One way in which a sequence might be embedded in an analytic function is % if the terms of the sequence can be regarded as values of a fixed % function at different arguments. For example, suppose we define a function % $f(z)$ at the points $z = 1, 2^{-1}, 2^{-2}, \dots$ by the formula $f(2^{-k}) % = s_k$. Then (28.1) becomes % $$f(1), f(2^{-1}), f(2^{-2}), \dots \to S. \eqno (28.4)$$ % Does this point of view help us estimate $S$? The answer will probably % be yes if there exists a function $f$ that is analytic in a neighborhood % of $z=0$ and takes the given values at $z=2^{-k}$. In such a case, to % estimate $S$, it is enough to interpolate some of the data by a % polynomial $p(z)$ and then compute $p(0)$. This is the method known as % {\em Richardson extrapolation}, which is of % great practical importance in applications.\footnote{Lewis Fry Richardson % used such ideas as early as 1910, and for a systematic % treatment see his charming article [Richardson 1927]. There are various earlier % roots of Richardson extrapolation too, including Huygens in the 17th century.} % In a typical application, % $h$ might be the mesh size of a numerical discretization and $f(h), % f(h/2), f(h/4),\dots$ the estimates obtained of a quantity of interest as % the mesh is successively refined. Often only even powers of $h$ appear, % indicating that $f$ is an even function, so one could take the view that % the data are given at $\pm h, \pm h/2, \dots$ % and Richardson extrapolation is really % Richardson interpolation. In the specific case in which % $f(h)$ is an estimate of an integral by the trapezoid or rectangle rule % with step length $h$, this becomes the quadrature method known as {\em % Romberg quadrature}. Nor is the idea of polynomial extrapolation from % data such as (28.4) limited to cases in which the sample points are % related by factors of $2$. If they are $1, 1/2, 1/3,\dots,$ this is % called {\em Salzer extrapolation} [Salzer 1955]. % %% % Often, however, the limit of a sequence or series is not in the interior % of a region of analyticity of an analytic function. In such a case there % may be less mileage in Richardson extrapolation, and one looks for % formulations adapted to the edge of a region of analyticity. For such % problems, there is a basic starting point: to insert a parameter $z$ in % (28.2) so that it becomes the series % $$S(z) = a_0 + a_1z + a_2z^2 + \cdots . \eqno (28.5)$$ % Now we have the problem of evaluating $S(1)$ for a function $S(z)$ with % known Taylor coefficients. If (28.2) converges, then $z=1$ is a point of % convergence of (28.5), and if (28.2) converges more slowly than % geometrically, then $z=1$ must be on the boundary of the disk of % convergence of (28.5). So by introducing a parameter $z$, we have % converted the problem of the summation of a slowly convergent series to a % problem of evaluating an analytic function at a point on the boundary of % the disk of convergence of its Taylor series. %% % The simplest idea would be to evaluate $S(z)$ for a succession % of values of $z$ and use the identity % $$S(1) = \lim_{z\to 1} S(z),$$ % where the limit is over real values of $z$ increasing to $1$. % This idea is known as _Abel summation_ [Hardy 1991]. %% % % A more powerful and general approach is to use rational functions, % specifically Pad\'e approximants since the data are given as Taylor % coefficients. Two variants of this idea have received special attention. % We could construct a sequence of type $(m,1)$ Pad\'e approximants, with % one pole, and evaluate them at $z=1$: % $$r_{01}(1), r_{11}(1), r_{21}(1), \dots.$$ % This is called {\em Aitken extrapolation} or {\em Aitken's % $\Delta^2$ method,} used by Aitken  though with % origins further back. Or we could work with type $(n,n)$ % Pad\'e approximants, % $$r_{00}(1), r_{11}(1), r_{22}(1), \dots.$$ % This is called {\em epsilon extrapolation} (originally for sequences) % [Shanks 1955, Wynn 1956] or {\em eta extrapolation} (originally for series) [Bauer 1959]. % An earlier appearance of essentially the same idea is due % to Schmidt . % %% % Here is an example showing how powerful eta extrapolation can be for some % problems. What is the value of % $$S = \sum_{n=2}^\infty {\sin(n)\over \log(n)} ?$$ % The series is extremely slow to converge, as we see by taking partial % sums of as many as a million terms: %% % \vskip -2em S = @(n) sum(sin(2:n)./log(2:n)); disp(' n S(n)') for n = 10.^[1:6] fprintf('%6.1e %10.6f\n',n,S(n)) end %% % To get 10-digit accuracy by summing the series in this fashion, we would % need $10^{10000000000}$ terms! The actual answer (not known analytically) % is % $$S \approx 0.68391378641828\dots .$$ %% % Here are the diagonal extrapolants, that is, the results of eta extrapolation. % Now we just go from $2^1$ to $2^6$ instead of from $10^1$ to $10^6$, yet we get % 14 digits of accuracy instead of 1: %% % \vskip -2em n = 2:150; c = [0 0 sin(n)./log(n)]; disp(' ( n, n) (mu,nu) r_nn(1) ') disp(' ------- ------- -----------') for n = 2.^(1:6) [r,a,b,mu,nu] = padeapprox(c,n,n,0); fprintf(' (%2.0d,%2.0d) (%2.0d,%2.0d) %19.15f\n',n,n,mu,nu,r(1)) end %% % The convergence is excellent. Note that we have computed $\hbox{Pad\'e}$ % approximants non-robustly by specifying a tolerance of $0$ to |padeapprox|. % In typical applications, this use of non-robust formulas % seems advantageous in extrapolation applications, though % it brings a risk of sensitivity to noise. For this example, % calling |padeapprox| with its default tolerance $10^{-14}$ leads % to stagnation at type $(15,15)$ with just 7 digits of accuracy. %% % This simple method of eta extrapolation, at least as % implemented by Chebfun's $\hbox{Pad\'e}$ approximation code, can be encapsulated % in a single Matlab command we may call |extrap|. Given a sequence % $a_0, a_1, ..., a_N$, we can round $N/2$ to integers (say, round up % for $m$ and down for $n$) and then use |padeapprox| to compute % the type $(m,n)$ $\hbox{Pad\'e}$ approximation $r$. The % accelerated value is then $r(1)$. Here is the code. %% % \vskip -2em eval_at_1 = @(r) r(1); N2 = @(c) length(c)/2; extrap = @(c) eval_at_1(padeapprox(c,ceil(N2(c)),floor(N2(c)),0)); %% % The $\sin(n)/\log(n)$ example just treated is this: %% % \vskip -2em extrap([0 0 sin(2:150)./log(2:150)]) %% % For another example, suppose we extrapolate the alternating series % $$1 - {1\over 2} + {1\over 3} - \cdots = \log(2), \eqno (28.6)$$ % The result is accurate to machine precision: %% % \vskip -2em extrap((-1).^(0:30)./(1:31)), exact = log(2) %% % Note that here, the function $f$ of (28.5) is % $\log(1+z)$, so this example shows that eta extrapolation can be effective for % functions with branch cuts as well as poles. %% % Another famous alternating series, which we can obtain by setting % $t=0$ in equation (9.3), is % $$1 - {1\over 3} + {1\over 5} - \cdots = {\pi\over 4}, \eqno (28.7)$$ % Again, extrapolation gives machine precision: %% % \vskip -2em extrap((-1).^(0:30)./(1:2:61)), exact = pi/4 %% % These examples are very impressive, but it is not always so. For example, % here is what happens if we attempt to extrapolate the series % $$\zeta(2) = 1 + {1\over 2^2} + {1\over 3^2} + \cdots = {\pi^2\over 6}, \eqno (28.8)$$ %% % \vskip -2em extrap(1./(1:30).^2), exact = pi^2/6 %% % The convergence is very poor because in this case the function $f(z)$ of (28.5), % known as the dilogarithm, has a branch point at $z=1$ itself. As it happens, % this is a case where Salzer extrapolation is effective (Exercise 28.3). %% % The discussion of convergence acceleration of the last five pages has % little in common with the large literature of this subject, because our % focus has been solely on the underlying approximations, particularly % $\hbox{Pad\'e}$ approximants, and not at all on the mechanics. % Our numerical illustrations have utilized the linear algebra of % Chapter 27, based on the SVD and requiring $O(n^3)$ floating-point % operations to compute a single estimate based on a type $(n,n)$ % approximant. The literature of convergence acceleration is quite different, for it % emphasizes recurrence relations and triangular or rhomboidal arrays related % to continued fractions that % can be used to generate a sequence of approximations at great speed % without solving matrix problems. These approaches are certainly faster, % and in fact they may often be more accurate for extrapolation, though they come with a % risk of sensitivity to noise and the possibility of breakdown % if there is a division by $0$. %% % % A major reason why we have ignored the mechanical or implementational aspects of % convergence acceleration is that these % matters are complicated---and, one might say, distracting. % The differences between various % extrapolation algorithms in practice can be quite intricate, and in a % discussion of such matters, one quickly loses sight of the underlying % mathematics of approximation. For details of these aspects of convergence % acceleration see surveys such as Chapter 3 of % [Baker \& Graves-Morris 1996], [Brezinski \& Redivo Zaglia 1991], [Gragg 1972], % [Joyce 1971], [Sidi 2003], [Weniger 1989], [Wimp 1981], or the appendix % by Laurie in [Bornemann, et al.\ . Such literature also points % to many further acceleration methods beyond those we have mentioned, % such as Levin's sequence transformation and Brezinski's % theta method. % %% % We finish with an observation that points to exciting further % territories of interest to mathematicians at least since Euler. % The series (28.5) consists just of Taylor coefficients, so it % is meaningful even if the radius of convergence is less than $1$. Therefore our % methods based on analytic continuation can sum divergent series as well % as convergent ones. For example, the Taylor series % $${1\over 1+z} = 1 - z + z^2 - z^3 + \cdots$$ % suggests the result % $$1 - 1 + 1 - 1 + \cdots = {1\over 2} , \eqno (28.9)$$ % if we set $z=1$. Similarly, setting $z = 2$ suggests % $$1 - 2 + 4 - 8 + \cdots = {1\over 3} . \eqno (28.10)$$ % Are these identities actually correct''? As usual % in mathematics, the answer depends on what definitions we choose. % The formulas (28.9) and (28.10) are not too problematic since they correspond to Taylor series % with positive radii of convergence. In more challenging cases, % the series is only asymptotic. For example, % what about this series with factorial coefficients considered by Euler , % $$0! - 1! + 2! - 3! + \cdots = ~? \eqno (28.11)$$ % The factorials grow too fast to be Taylor coefficients for any function analytic % in a neighborhood of $z=0$. However, they are the asymptotic % series coefficients at $z=0$ % for a function analytic in the right half-plane, namely % $$f(z) = \int_0^\infty {e^{-t}\over 1+zt} \kern .7pt dt. \eqno (28.12)$$ % So a plausible candidate for the sum of (28.11) is % $$0! - 1! + 2! - 3! + \cdots = f(1) = % 0.596347362\dots . \eqno (28.13)$$ % Our code |extrap| makes a creditable attempt at computing this number: %% % \vskip -2em extrap((-1).^(0:10).*factorial(0:10)) %% % % \begin{displaymath} % \framebox[4.7in][c]{\parbox{4.5in}{\vspace{2pt}\sl % {\sc Summary of Chapter 28.} % Rational approximations provide one of the basic technologies for analytic % continuation and extrapolation. In particular, Pad\'e approximants are % the basis of standard methods of convergence acceleration for sequences % and series including the Aitken $\Delta^2$, Shanks, epsilon and eta % methods. % \vspace{2pt}}} % \end{displaymath} % %% % \small % \parskip=2pt % \par % {\bf Exercise 28.1. Contour plot for Taylor polynomials.} % Draw a contour plot like the pair in this chapter for the Taylor polynomial % approximants to $f(z) = \tanh(z)$. Comment on the result. % \par % {\bf Exercise 28.2. The divergent factorial series.} % Compute numerically the Pad\'e approximants % $r_{33}, r_{44}, \dots , r_{77}$ for the Taylor coefficients (28.11), % and show that they match $f(1)$ to better than $1\%$, where $f$ is defined by (28.12). % What accuracy do these approximants give for $f(1/2)$? % \par % {\bf Exercise 28.3. Zeta function.} It was noted in the text that % eta extrapolation is ineffective for the series (28.8). Study the behavior % of Richardson and Salzer extrapolation instead. % \par % {\bf Exercise 28.4. Alternating square roots.} (a) To 8 digits of accuracy, % what do you think is the limit of $1-1/\sqrt2 + 1/\sqrt 3 - \cdots\,$? % (b) To the same accuracy, what number would you propose as a good % choice for the sum of the divergent series $1-\sqrt2 + \sqrt 3 - \cdots\,$? % \par % {\bf Exercise 28.5. Approximations to \boldmath$e^z$.} Compute type % $(1,1)$ approximations to $e^z$ on $[-1,1]$ by % (a) Pad\'e approximation, % (b) best approximation, % (c) Chebyshev--Pad\'e approximation, % (d) Carath\'eodory--Fej\'er approximation, % (e) interpolation in 3 Chebyshev points, and % (f) linearized least-squares approximation in a number of Chebyshev points large % enough to be effectively infinite. In each case list the coefficients, % measure the $L^2$ and $L^\infty$ errors, and plot the error curve. % \par % {\bf Exercise 28.6. Nonlinear least-squares approximation.} Find % a way to compute the true type $(1,1)$ nonlinear least-squares approximation to % $e^z$ on $[-1,1]$, and report the same data for this function as % for the approximations of Exercise 28.7. % \par % {\bf Exercise 28.7. An alternating series.} % The following identity is known: % $$1 + {1\over 2} - {1\over 3} % - {1\over 4} + {1\over 5} % + {1\over 6} - {1\over 7} - \cdots = {\pi\over 4} + {1\over 2} \log 2. % \eqno (28.14)$$ % How many digits do you get by taking $10^1, 10^2, \dots, 10^6$ terms of the series? % Can you get more by extrapolation? %