I have f = $\sum_{ij} a_{ij} x_i x_j$ with reals $a_{ij}$ and $x_i$ from $R^N$ inside sphere $x_1^2+x_2^2+x_3^2+...+x_N^2 < r$.
It is obvious that
$|f|=|\sum...|<=\sum_{ij}|a_{ij} x_i x_j|<=r^2 \sum_{ij}|a_{ij}|$.
But I believe that it is usually possible to get more accurate estimate. For example:
$f_{example}=x^2 + 2 x y + y^2 = (x+y)^2$
and I can give exact lower and upper bounds:
$0 < f_{example} < 2$
What approach can I use? For my task $a_i$ is array of doubles, is there some standard approach for finding some good estimates of max and min of f?
Thanx
Let $A=[a_{ij}]\in \mathbb{R}^{n\times n}$. Let $S:=\frac{1}{2}(A+A^t)$ be its symmetric part (it is clear that $x \cdot Ax=x \cdot Sx$). Since $S$ is a symmetric matrix, all its eigenvalues are real and its eigenvectors form an orthonormal basis. Suppose that the eigenvalues are $\lambda_1\ge \lambda_2\ge\ldots\geq \lambda_n$ and $u_1,\cdots,u_n$ is the basis of eigenvectors. Hence we can write any vector $x$ with $||x||= 1$ in this basis, namely $x=\sum_i \alpha_i u_i$ with $\sum \alpha_i^2= 1$
Therefore $$\sum_{ij} a_{ij} x_i x_j = x \cdot Ax=x \cdot Sx = \sum_{i=1}^n \lambda_i \alpha_i^2$$ and it is easy to see that the maximum is attained for $\alpha_1=1$ (and the other components zero) and the minimum for $\alpha_n=1$.
In your example $x^2 + 2 x y + y^2$ you have that $A=\begin{bmatrix}1 & 1\\1 & 1\end{bmatrix}$ which is already symmetric and its eigevalues solve $(1-\lambda)^2=1$, that is $\lambda_1=2$ and $\lambda_2=0$.