Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let's say I have a multivariate function $$ f:D \to D, D \subset \mathbb R ^n, D \text{ compact}, $$ for which there is no closed form.
That is the only way to evaluate the function is to do it numerically.

For example, the price of some exotic insurance contracts: the rule governing the payout are simple, but have no closed formula.

If I suspect my function $f$ is a contraction, is it possible to prove it numerically?

My first though will be to evaluate numerically $f'$ at 1000 points of $D$.
Is this sufficient?
Probably not, have there been some work on such numerical tests?

My second though will be to assume $f'$ follows a normal distribution, then perform an hypothesis test.
Is this reasonable?

My use case is that, I search for a fixed point of $f$ using dynamic programming.
But the state space becomes too large.
If I can proove $f$ is a contraction, then I avoid the curse of dimensionality.

share|improve this question
1  
Why don't you just do many Piquard iterations and see if the convergence is geometric and the last iteration is nearly a fixed point? If it is, who cares why (you just need to find a fixed point, right?) if it isn't, $f$ is certainly not contractive enough and you've got to try something else. –  fedja Jun 19 '13 at 16:26
1  
Interesting... I do not think anything useful can be said in such generality (obviously, in principle there may be small scale wiggles that no particular finite number of checks can catch) but if you tell exactly how the function is defined, someone may be able to come up with some good idea. –  fedja Jun 19 '13 at 18:26
1  
Maybe Tischler's "Solving Decidability Problems with Interval Arithmetic" would be of some help? (You can google the paper name to find a free copy.) –  Benjamin Dickman Jun 19 '13 at 20:01
1  
Did you mean to write $f:D \to D$ rather than $f:D \to \mathbb R$? –  Barry Cipra Jun 19 '13 at 20:05
1  
You suspect that $f$ is a contraction, so that means you've already selected a metric space...do you want use a specific metric space? –  Suvrit Sep 30 '13 at 1:38
show 7 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.