New numerical methods are proposed for computing with smooth scalar and vector valued functions of two variables defined on rectangular domains. Functions are approximated to essentially machine precision by an iterative variant of Gaussian elimination that constructs near-optimal low rank approximations. Operations such as integration, differentiation, and function evaluation are particularly efficient. Explicit convergence rates are shown for the singular values of differentiable and separately analytic functions, and examples are given to demonstrate some paradoxical features of low rank approximation theory. Analogues of QR, LU, and Cholesky factorizations are introduced for matrices that are continuous in one or both directions, deriving a continuous linear algebra. New notions of triangular structures are proposed and the convergence of the infinite series associated with these factorizations is proved under certain smoothness assumptions. A robust numerical bivariate rootfinder is developed for computing the common zeros of two smooth functions via a resultant method. Using several specialized techniques the algorithm can accurately find the simple common zeros of two functions with polynomial approximants of high degree (≥ 1,000). Lastly, low rank ideas are extended to linear partial differential equations (PDEs) with variable coefficients defined on rectangles. When these ideas are used in conjunction with a new one-dimensional spectral method the resulting solver is spectrally accurate and efficient, requiring O(n²) operations for rank $1$ partial differential operators, O(n³) for rank 2, and O(n⁴) for rank &geq,3 to compute an n x n matrix of bivariate Chebyshev expansion coefficients for the PDE solution. The algorithms in this thesis are realized in a software package called Chebfun2, which is an integrated two-dimensional component of Chebfun.

Robust algorithms for the approximation of functions are studied and developed in this thesis. Novel results and algorithms on piecewise polynomial interpolation, rational interpolation and best polynomial and rational approximations are presented. Algorithms for the extension of Chebfun, a software system for the numerical computation with functions, are described. These algorithms allow the construction and manipulation of piecewise smooth functions numerically with machine precision. Breakpoints delimiting subintervals are introduced explicitly, implicitly or automatically, the latter method combining recursive subdivision and edge detection techniques. For interpolation by rational functions with free poles, a novel method is presented. When the interpolation nodes are roots of unity or Chebyshev points the algorithm is particularly simple and relies on discrete Fourier transform matrices, which results in a fast implementation using the Fast Fourier Transform. The method is generalised for arbitrary grids, which requires the construction of polynomials orthogonal on the set of interpolation nodes. The new algorithm has connections with other methods, particularly the work of Jacobi and Kronecker, Berrut and Mittelmann, and Egecioglu and Koc. Computed rational interpolants are compared with the behaviour expected from the theory of convergence of these approximants, and the difficulties due to truncated arithmetic are explained. The appearance of common factors in the numerator and denominator due to finite precision arithmetic is characterised by the behaviour of the singular values of the linear system associated with the rational interpolation problem. Finally, new Remez algorithms for the computation of best polynomial and rational approximations are presented. These algorithms rely on interpolation, for the computation of trial functions, and on Chebfun, for the location of trial references. For polynomials, the algorithm is particularly robust and efficient, and we report experiments with degrees in the thousands. For rational functions, we clarify the numerical issues that affect its application.

Ordinary differential equations (ODEs) play an important role in mathematics. Although intrinsically, the setting for describing ODEs is the continuous framework, where differential operators are considered as maps from one function space to another, common numerical algorithms for ODEs discretise problems early on in the solution process. This thesis is about continuous analogues of such discrete algorithms for the numerical solution of ODEs. This thesis shows how Newton's method for finite dimensional system can be generalised to function spaces, where it is known as Newton-Kantorovich iteration. It presents affine invariant damping strategies for increasing the chance of convergence for the Newton-Kantorovich iteration. The derivatives required in this continuous setting are Fréchet derivatives, the continuous analogue of Jacobian matrices. In this work, we present how automatic differentiation techniques can be applied to compute Fréchet derivatives. We introduce chebop, a Matlab solver for nonlinear boundary-value problems, which combines damped Newton iteration in function space and automatic Fréchet differentiation. By proving that affine operators have constant Fréchet derivatives, it is demonstrated how automatic linearity detection of computed quantities can be implemented. This is valuable for black-box solvers, which can use the information to determine whether an iteration scheme has to be employed for solving a problem. Like nonlinear systems of equations, nonlinear boundary-value problems can have multiple solutions. This thesis present two techniques for obtaining multiple solutions of operator equations: deflation and path-following. An algorithm combining the two techniques is proposed.

No description available.