Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients

Hoang Tran, Clayton G. Webster, Guannan ZhangNumerische Mathematik 2017 · DOI

TL;DR

This paper introduces a novel, generalized framework for analyzing the convergence of polynomial approximations for parameterized PDEs. It offers a new approach to estimating approximation errors without relying on traditional, often computationally expensive, methods, leading to sharper and more broadly applicable convergence rates.

What Problem Does This Paper Address?

Many real-world problems involve solving partial differential equations (PDEs) where some input parameters are uncertain or vary. These parameters can be deterministic (e.g., material properties) or stochastic (e.g., random fields). Accurately approximating the solution of these parameterized PDEs is crucial for tasks like uncertainty quantification, optimization, and reliable predictions. Traditional methods like Monte Carlo simulations can be slow to converge, especially in high-dimensional parameter spaces. Polynomial approximation methods, such as Taylor and Legendre expansions, offer faster convergence but require careful selection of approximation terms (index sets) to be efficient. The challenge lies in finding "optimal" index sets that balance accuracy with computational cost, especially when dealing with complex coefficient behaviors. This paper addresses the problem of efficiently analyzing and estimating the convergence rates of these polynomial approximations, particularly for "quasi-optimal" methods that use readily available bounds on coefficients rather than exact values.

Methods

The authors propose a generalized methodology for analyzing the convergence of quasi-optimal Taylor and Legendre approximations for parameterized elliptic PDEs. The core of their approach involves:

  • Generalized Framework for Error Estimation: Instead of relying on the traditional Stechkin inequality, they develop a new method to directly estimate the truncation error. This involves partitioning the set of coefficient bounds into intervals and approximating the cardinality of index sets within these intervals using Lebesgue measure.
  • Extension to Continuous Domains: They extend discrete multi-index sets to continuous domains, allowing for the use of geometric concepts like volume to approximate the number of relevant indices.
  • Sharp Upper Bounds on Coefficients: The analysis focuses on obtaining sharp upper bounds for polynomial coefficients. This is crucial for quasi-optimal methods, as it allows for the construction of near-optimal index sets without needing to compute the exact coefficients.
  • Analyticity of Solutions: They leverage the analyticity of the PDE solution with respect to the parameters, under assumptions of holomorphic continuation of the input coefficient. This property is key to establishing convergence for both Taylor and Legendre expansions.
  • Asymptotic and Pre-asymptotic Analysis: The paper provides both asymptotic convergence rates (for large numbers of degrees of freedom) and pre-asymptotic estimates (effective for smaller numbers of degrees of freedom), offering a more complete picture of the approximation's behavior.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses examples of parameterized PDEs with specific coefficient structures for illustration and validation.

Key Insights and Ideas

  • Beyond Stechkin Inequality: The development of a new error estimation framework that bypasses the Stechkin inequality is a significant contribution, offering a more direct and potentially more generalizable approach.
  • Geometric Interpretation of Index Sets: Using Lebesgue measure to approximate the cardinality of index sets in continuous domains provides a powerful geometric intuition and a computational tool for error analysis.
  • Optimality of Legendre Approximations: The analysis highlights the advantages of Legendre approximations over Taylor approximations, particularly for non-affine coefficient dependencies, due to their ability to handle more general holomorphic extensions.
  • Sub-exponential Convergence Rates: The framework yields sharp asymptotic error estimates with sub-exponential convergence rates (of the form $M \exp(-(kM)^{1/N})$), which are significantly faster than typical Monte Carlo rates.
  • Bridging Theory and Practice: The work aims to bridge the gap between theoretical convergence rates and practical implementation by focusing on "quasi-optimal" approximations that rely on computable coefficient bounds.

Key Results

  • The paper establishes a generalized methodology for analyzing quasi-optimal polynomial approximations for parameterized elliptic PDEs.
  • It derives sharp asymptotic error estimates for both Taylor and Legendre approximations, achieving sub-exponential convergence rates.
  • The analysis provides a new framework for estimating best M-term approximation errors without using the Stechkin inequality.
  • Theoretical examples demonstrate the effectiveness of the proposed method and illustrate the advantages of Legendre over Taylor approximations in certain scenarios.
  • The paper provides both asymptotic and pre-asymptotic estimates for truncation errors, offering a comprehensive view of approximation behavior.

Limitations and Future Work

  • Scope of PDEs: The current analysis is primarily focused on linear elliptic equations with input coefficients that are affine or have specific holomorphic extensions. Extending the framework to more general classes of PDEs (e.g., nonlinear, parabolic, hyperbolic) and more complex coefficient dependencies remains an area for future work.
  • Algorithm Development: While the paper provides a theoretical framework, developing practical algorithms for identifying quasi-optimal subspaces and implementing the proposed estimation methods is identified as a crucial next step.
  • A Posteriori Procedures: The paper suggests exploring a posteriori procedures for adaptively building index sets, which could lead to more efficient and accurate approximations in practice.
  • Non-intrusive Methods: Extending the quasi-optimal approach to non-intrusive interpolation or collocation methods is proposed as an important future research direction.
  • Computational Validation: While theoretical examples are provided, extensive computational validation and comparison with existing methods across a wider range of problems would be beneficial.

Summary updated

BibTeX
@article{tran2017analysis,
  author = {Hoang Tran and Clayton G. Webster and Guannan Zhang},
  title = {{Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients}},
  journal = {Numerische Mathematik},
  year = {2017},
  doi = {10.1007/s00211-017-0878-6},
}
Figure