Tau method

$\tau$ method

A method initially formulated as a tool for the approximation of special functions of mathematical physics (cf. also Special functions), which could be expressed in terms of simple differential equations. It developed into a powerful and accurate tool for the numerical solution of complex differential and functional equations. A main idea in it is to approximate the solution of a given problem by solving exactly an approximate problem.

Lanczos' formulation of the tau method.

In [a17], C. Lanczos remarked that truncation of the series solution of a differential equation is, in some way, equivalent to introducing a perturbation term in the right-hand side of the equation. Conversely, a polynomial perturbation term can be used to produce a truncated series, that is, a polynomial solution.

Assume one wishes to solve by means of a power series expansion the simple linear differential equation (cf. also Linear differential operator)

\begin{equation*} \mathbf{D} y ( x ) : = y ^ { \prime } ( x ) + y ( x ) = 0,0 \leq x \leq 1, \end{equation*}

\begin{equation*} y ( 0 ) = 1, \end{equation*}

which defines $y ( x ) = \operatorname { exp } ( - x )$. To find the coefficients of a formal series expansion of $y ( x )$, one substitutes the series in the equation and generates a system of algebraic equations for the coefficients: $j a_j + a_{j - 1} = 0$ for $j = 1,2 , \dots$, solving it in terms of $a_{0}$. The value of $a_{0}$ is fixed using the initial condition. To find a finite expansion, say of order $n$, one needs to make all coefficients $a _ { j }$ with $j > n$ equal to zero. This is achieved by adding a term of the form $\tau x ^ { n }$ to the right-hand side of the differential equation. One has $( n + 1 ) a _ { n + 1 } + a _ { n } = \tau$, so that $a _ { n + 1 }$ and all the coefficients following it, will be equal to zero if one chooses $a _ { n } = \tau$. The same condition follows by substituting a segment of degree $n$ of the series expansion of $y ( x ) = \operatorname { exp } ( - x )$ into the equation. If the solution of the perturbed differential equation is regarded as an approximation to that of the original equation with, say, a right-hand side equal to zero, it seems natural to replace it by the best uniform approximation of zero over the same interval $J$, which is a Chebyshev polynomial $T _ { n } ^ { * } ( x )$ of degree $n$, defined over $J$ (cf. also Chebyshev polynomials).

Therefore, to find an accurate polynomial approximation of $y ( x )$, Lanczos proposed solving exactly the more complex perturbed problem (the tau problem):

\begin{equation*} \mathbf{D} y _ { n } ^ { * } ( x ) = \tau T _ { n } ^ { * } ( x ) \end{equation*}

with the same initial conditions as before. The polynomial $y _ { n } ^ { * } ( x )$ is called the tau method approximation of $y ( x )$ over the given interval $J$.

This tau problem can be solved for the unknown coefficients of $y _ { n } ^ { * } ( x )$ using several alternative procedures. One of them is described above, that is, to set up and solve a system of linear algebraic equations linking the unknown coefficients of $\mathbf{D} y _ { n } ^ { * } ( x )$ with those of $\tau T _ { n } ^ { * } ( x )$. In this process one can assume that $y _ { n } ^ { * } ( x )$ itself can be expressed in either powers of $x$, or in Chebyshev, Legendre or other polynomials. The first choice was Lanczos' original choice, and he explicitly indicated the possibility of choosing the others.

The second choice is a tau method, often [a8] called the Chebyshev method (or Legendre method) and, also, the spectral method. This last formulation of the tau method has been extensively used and applied, since 1971, to complex problems in fluid dynamics by S.A. Orsag [a11].

There are at least three other approaches to the tau method. One of them is to find the coefficients of the approximant through a process of interpolation at the zeros of the perturbation term. This early form of collocation was termed the "method of selected points" by Lanczos [a17]. When the perturbation term is an orthogonal polynomial (such as a Chebyshev, Legendre, or other polynomial), this process is called "orthogonal collocation" . This is the name by which Lanczos' method of selected points is usually designated today (as of 2000); the name "pseudo-spectral method" is also often applied to it. Algorithms for these methods have been well developed.

Recursive formulation of the tau method based on canonical polynomials.

In his classic [a18], Lanczos noted that if a sequence of polynomials $Q _ { n } ( x )$, $n = 0,1 , \dots$, such that $\mathbf{D} Q _ { n } ( x ) : = x ^ { n }$ for all $n \in \mathbf N$ can be found for any linear differential operator with polynomial coefficients $\mathbf D$, then, since $T _ { n } ^ { * } ( x ) : = c _ { 0 } ^ { n } + c _ { 1 } ^ { n } x + \ldots + c _ { n } ^ { n } x ^ { n }$ (the coefficients of which are tabulated), the solution of the tau problem would be immediately given by:

\begin{equation*} y _ { n } ^ { * } ( x ) = \tau \sum _ { k = 0 } ^ { n } c _ { k } ^ { n } Q _ { k } ( x ), \end{equation*}

where the parameter $\tau$ is fixed using the initial condition.

An extension of this approach to a wider range of differential operators than the trivial one, given in the example, has several advantages: canonical polynomials are independent of the interval in which the solution is sought, allowing for easy segmentation of the domain; they are permanent, in the sense that if an approximation of a higher degree is required, the computation does not need to be repeated from scratch; they are also independent of the supplementary conditions of the problem, which can now equally be initial, boundary or multi-point conditions. Furthermore, the tau method does not require a stage of discretization of the given differential operator, as discrete-variable methods do.

A sequence of canonical polynomials defined as simply as $\mathbf{D} Q _ { n } ( x ) : = x ^ { n }$ for all $n = 0,1 , \dots$, need not always exist or need not be unique. An algebraic and algorithmic theory of the tau method, initially constructed for elements $D$ of the class $\mathcal{D}$ of linear differential operators of arbitrary integer order, with polynomial or rational coefficients (essentially the tools a computer handles) was discussed by E.L. Ortiz in [a24]. In this work, canonical polynomials are defined as realizations of classes of equivalence of polynomials, for which the algebraic kernel of the differential operator is the modulus. These classes have gaps in their index sequence. Elements $D \in \mathcal{D}$ are then uniquely associated with representatives of such classes of canonical sequences. The codimension of the image of the space of polynomials under operators $D \in \mathcal{D}$ is usually small, and bounded by the order of $D$ plus the height $h : = \operatorname { max } _ { n \in \bf N } \{ \sigma _ { n } - n \}$ (where $\sigma _ { n }$ is the degree of $D x ^ { n }$) of the differential operator.

For more general operators than the one used as an example, more than a single $\tau$ term is usually required to satisfy the more elaborate supplementary conditions and, also, internal conditions of the method. In the case of a problem defined by a differential operator $D$ in $\mathcal{D}$, of order $\mu > 1$ and with non-constant coefficients, the question of the number of $\tau$ terms required for a tau method approximation has been shown to be related to the size of the gap in the canonical sequence, and to the existence of a non-empty algebraic kernel in $D$. The number of $\tau$ terms can be easily determined in this approach using information on the degree of polynomial (or rational) coefficients and the order of differentiation of the function to which they apply. It was also shown in [a24] that canonical sequences can be generated recursively. This approach was used to formulate the first recursive algorithms for the automatic solution of differential equations using the tau method. The theory of canonical polynomials has been discussed and extended by several authors; see [a10] and the references given therein.

Theoretical error analysis for the tau method [a18], [a30], [a9], [a22], [a26] have shown that tau method approximations are of the order of best uniform approximations by polynomials defined over the same interval. This connection with best approximation is preserved when a tau method based on rational approximation [a18], [a21] is used [a6].

Operational formulation of the tau method.

There is yet another way in which tau method approximations can be constructed. An operational formulation of the tau method was introduced by Ortiz and H. Samara in [a27]. In this formulation, derivatives and polynomial coefficients of operators in $\mathcal{D}$ are represented in terms of multiplicative diagonal matrices. Furthermore, the differential operator and the supplementary conditions are decoupled. Through a simple and systematic algorithm, which treats the differential operator and supplementary conditions with similar machinery, this technique transforms a given differential tau method problem into one in linear algebra. The approximate solution can be generated, indistinctively, in terms of powers of the variables or in terms of elements of a more stable polynomial basis, such as Chebyshev, Legendre or other polynomials. The operational formulation further simplified the development of software for the tau method.

Numerical applications of the tau method.

The recursive and operational approaches to the tau method have been extended in several directions. To systems of linear differential equations [a9], [a4]; to non-linear problems [a25], [a23], [a26]; to partial differential equations [a28], [a29]; and, in particular, to the numerical solution of non-linear systems of partial differential equations the solution of which has sharp spikes, with high gradients, as in the case of soliton interactions [a13], [a14]; to the approximate solution of ordinary and partial functional-differential equations [a25], [a20], [a16]; and to singular problems for partial differential equations related to crack propagation [a7]. The tau method is well adapted to produce accurate approximations in the numerical treatment of differential eigenvalue problems with one or multiple spectral parameters, entering either linear or non-linearly into the equation [a2], [a19]. The tau method has been extensively used for the high-precision approximation of real- [a15] and complex-valued functions. A weak formulation of the tau method has been proposed and applied to inverse problems for partial differential equations [a1].

Analytical applications of the tau method.

The tau method has also been used in a totally different direction, as a tool in the discussion of problems in mathematical analysis, for example, in complex function theory [a12].

Possible connections between the tau method, collocation, Galerkin's method, algebraic kernel methods, and other polynomial or discrete-variable techniques have also been explored [a31], [a14], [a5].

The tau method has also received some attention as an analytic tool in the discussion of equivalence results across numerical methods [a5]. It has been found that, with it, it is possible to construct special "tau methods" , which recursively generate solutions numerically identical to those of collocation, Galerkin's and other weighted residual methods, and to those of discrete-variable methods, such as sophisticated forms of Runge–Kutta methods. This work suggests a way of unifying a large group of continuous- and discrete-variable approximation techniques.

References

[a1]	H.T. Banks, J.G. Wade, "Weak tau approximations for distributed parameter systems in inverse problems" Numer. Funct. Anal. Optim. , 12 (1991) pp. 1–31
[a2]	T. Chaves, E.L. Ortiz, "On the numerical solution of two point boundary value problems for linear differential equations" Z. Angew. Math. Mech. , 48 (1968) pp. 415–418
[a3]	M.R. Crisci, E. Russo, "A-stability of a class of methods for the numerical integration of certain linear systems of differential equations" Math. Comput. , 41 (1982) pp. 431–435
[a4]	M.R. Crisci, E. Russo, "An extension of Ortiz's recursive formulation of the tau method to certain linear systems of ordinary differential equations" Math. Comput. , 41 (1983) pp. 27–42
[a5]	M. El Daou, E.L. Ortiz, "The tau method as an analytic tool in the discussion of equivalence results across numerical methods" Computing , 60 (1998) pp. 365–376
[a6]	M. El Daou, S. Namasivayam, E.L. Ortiz, "Differential equations with piecewise approximate coefficients: discrete and continuous estimation for initial and boundary value problems" Computers Math. Appl. , 24 (1992) pp. 33–47
[a7]	A.E.M. El Misiery, E.L. Ortiz, "Tau-lines: a new hybrid approach to the numerical treatment of crack problems based on the tau method" Computer Methods in Applied Mechanics and Engin. , 56 (1986) pp. 265–282
[a8]	L. Fox, I.B. Parker, "Chebyshev polynomials in numerical analysis" , Oxford Univ. Press (1968)
[a9]	J.G. Freilich, E.L. Ortiz, "Numerical solution of systems of differential equations: an error analysis" Math. Comput. , 39 (1982) pp. 467–479
[a10]	M.E. Froes Bunchaft, "Some extensions of the Lanczos–Ortiz theory of canonical polynomials in the tau method" Math. Comput. , 66 : 218 (1997) pp. 609–621
[a11]	D. Gotlieb, S.A. Orszag, "Numerical analysis of spectral methods: Theory and applications" , Philadelphia (1977)
[a12]	W.K. Hayman, E.L. Ortiz, "An upper bound for the largest zero of Hermite's function with applications to subharmonic functions" Proc. Royal Soc. Edinburgh , 75A (1976) pp. 183–197
[a13]	M. Hosseini Ali-Abadi, E.L. Ortiz, "A tau method based on non-uniform space-time elements for the numerical simulation of solitons" Computers Math. Appl. , 22 (1991) pp. 7–19
[a14]	M. Hosseini Ali-Abadi, E.L. Ortiz, "The algebraic kernel method" Numer. Funct. Anal. Optim. , 12 : 3–4 (1991) pp. 339–360
[a15]	H.G. Khajah, E.L. Ortiz, "Ultra-high precision computations" Computers Math. Appl. , 27 : 7 (1993) pp. 41–57
[a16]	H.G. Khajah, E.L. Ortiz, "Numerical approximation of solutions of functional equations using the tau method" Appl. Numer. Anal. , 9 (1992) pp. 461–474
[a17]	C. Lanczos, "Trigonometric interpolation of empirical and analytic functions" J. Math. and Physics , 17 (1938) pp. 123–199
[a18]	C. Lanczos, "Applied analysis" , New Jersey (1956)
[a19]	K.M. Liu, E.L. Ortiz, "Tau method approximation of differential eigenvalue problems where the spectral parameter enters nonlinearly" J. Comput. Phys. , 72 (1987) pp. 299–310
[a20]	K.M. Liu, E.L. Ortiz, "Numerical solution of ordinary and partial functional-differential eigenvalue problems with the tau method" Computing , 41 (1989) pp. 205–217
[a21]	Y.L. Luke, "The special functions and their approximations I—II" , New York (1969)
[a22]	S. Navasimayan, E.L. Ortiz, "Best approximation and the numerical solution of partial differential equations with the tau method" Portugal. Math. , 41 (1985) pp. 97–119
[a23]	P. Onumanyi, E.L. Ortiz, "Numerical solution of stiff and singularly perturbed boundary value problems with a segmented-adaptive formulation of the tau method" Math. Comput. , 43 (1984) pp. 189–203
[a24]	E.L. Ortiz, "The tau method" SIAM J. Numer. Anal. , 6 (1969) pp. 480–492
[a25]	E.L. Ortiz, "On the numerical solution of nonlinear and functional differential equations with the tau method" R. Ansorge (ed.) W. Törnig (ed.) , Numerical Treatment of Differential Equations in Applications , Berlin (1978) pp. 127–139
[a26]	E.L. Ortiz, A. Pham Ngoc Dinh, "Linear recursive schemes associated with some nonlinear partial differential equations in one dimension and the tau method" SIAM J. Math. Anal. , 18 (1987) pp. 452–464
[a27]	E.L. Ortiz, H. Samara, "An operational approach to the tau method for the numerical solution of nonlinear differential equations" Computing , 27 (1981) pp. 15–25
[a28]	E.L. Ortiz, H. Samara, "Numerical solution of partial differential equations with variable coefficients with an operational approach to the tau method" Computers Math. Appl. , 10 : 1 (1984) pp. 5–13
[a29]	K.S. Pun, E.L. Ortiz, "A bidimensional tau-elements method for the numerical solution of nonlinear partial differential equations, with an application to Burgers equation" Computers Math. Appl. , 12B (1986) pp. 1225–1240
[a30]	T.J. Rivlin, "The Chebyshev polynomials" , New York (1974) (2nd. ed. 1990)
[a31]	K. Wright, "Some relationships between implicit Runge–Kutta, collocation and Lanczos tau methods" BIT , 10 (1970) pp. 218–227