9

Let $V$ be a finite-dimensional vector space with norm $\|\cdot\|$ and let $F : V \rightarrow \mathbb R$ be a bounded linear functional. It is only given as black-box.

I would like to estimate the norm of $F$ (from above and below). As $F$ is a black-box, the only way to do so is to test it with unit vectors from $V$ and, based on the result, find $v \in S^1 V$ that maximizes $|F(v)|$.

Do you know such an algorithm? In the application that I have in mind, $V$ is a finite-element space and $F$ is a complicated functional on that space.

EDIT: My first idea is to choose $v \in S^1 V$ randomly, perturb it into several directions, say, $v_1,\dots,v_k$, and then repeat the procedure with the $v_i$ that got the biggest $F(v_i)$. I do not know where to find algorithms and analysis for this problem.

shuhalo
  • 3,660
  • 1
  • 20
  • 31
  • Is the norm a black box as well? Or is it the usual norm for Banach spaces, $|\cdot|_\infty$? – Jack Poulson Apr 18 '12 at 03:06
  • Also, are you interested in the norm in a region (or at a point) where the function has continuous derivative? – Jed Brown Apr 18 '12 at 04:32
  • @Jack: The norm of the vector space is computable, and on a finite element space it can be computed by the mass matrix and the stiffness matrix. ($0$-th and $1$-st derivatives). – shuhalo Apr 18 '12 at 08:03
  • @Jed: $F$ is linear, so it is already differentiable. – shuhalo Apr 18 '12 at 08:03

2 Answers2

2

If your space $V$ is a Hilbert space, then Riesz theorem says that you can represent $F(v)=\left< f, v \right>$ and you can compute $f$ as you mention by trying out unit vectors. If the space is higher dimensional, then this becomes impractical, but you can at least compute estimates of $f$ by computing $F(v)$ for a sequence of random vectors $v$.

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
0

Maybe you can modify Hager's condition number estimator (see, e.g., the paper http://eprints.ma.man.ac.uk/321/01/35608.pdf), which bounds $\|A^{-1}\|$ when a factorization of $A$ is known, to work for your particular case.

Arnold Neumaier
  • 11,318
  • 20
  • 47