In this article, we study the sparse grid discretization for the numerical solution of the algebraic Riccati equation (ARE). This approach is of particular interest for the solution of large scale AREs. Such AREs arise, for example, from the discretization of operator Riccati equations associated with the linear quadratic control of systems evolving in a Hilbert space H. Following [<CitationRef CitationID="CR5">5</CitationRef>, <CitationRef CitationID="CR47">47</CitationRef>], we formulate the ARE as a nonlinear operator equation on the space of Hilbert–Schmidt operators and derive the matrix equation for the sparse grid discretization. If we use N degrees of freedom to discretize the space H, the sparse grid approximation of the ARE has a memory requirement of order <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathscr {O}(N \log N)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo>log</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We further propose an algorithm that evaluates the sparse grid approximation of the ARE with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathscr {O}(N^{3/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mrow> <mn>3</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> operations. This considerably reduces the cost of solving the ARE compared to the <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathscr {O}(N^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> memory requirement and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathscr {O}(N^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> complexity of the regular tensor product discretization. Numerical results are presented to validate the approach.

Sparse grid approximation of the Riccati equation

期刊论文
发表日期：

2026年5月13日

查看全文

Helmut Harbrecht,
Ilja Kalmykov

摘要

In this article, we study the sparse grid discretization for the numerical solution of the algebraic Riccati equation (ARE). This approach is of particular interest for the solution of large scale AREs. Such AREs arise, for example, from the discretization of operator Riccati equations associated with the linear quadratic control of systems evolving in a Hilbert space H. Following [5, 47], we formulate the ARE as a nonlinear operator equation on the space of Hilbert–Schmidt operators and derive the matrix equation for the sparse grid discretization. If we use N degrees of freedom to discretize the space H, the sparse grid approximation of the ARE has a memory requirement of order $\mathscr {O}(N \log N)$ $O (N log N)$ . We further propose an algorithm that evaluates the sparse grid approximation of the ARE with $\mathscr {O}(N^{3/2})$ $O (N^{3 / 2})$ operations. This considerably reduces the cost of solving the ARE compared to the $\mathscr {O}(N^2)$ $O (N^{2})$ memory requirement and $\mathscr {O}(N^3)$ $O (N^{3})$ complexity of the regular tensor product discretization. Numerical results are presented to validate the approach.