SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
katastrofa
Topic Author
Posts: 6135
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Proofs of convergence of numerical algorithms

December 10th, 2017, 9:51 pm

I have a very general question (for the beginning, by an absolute beginner): what are the most common proofs of convergence of numerical algorithms? (I've encountered proofs based on energy minimisation so far.)
 
User avatar
outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

Re: Proofs of convergence of numerical algorithms

December 11th, 2017, 6:55 am

That's difficult. I practical you see empirical demonstrations of convergence to *some* value for *some* cases.

Do you/can you know the true value?

In maximum likelihood you can sometimes compute analytical derivatives of the likelihood function given your data, find the value where you derivatives is zero, proof that you have all the zeros, and then you can say the maximum must be at one of these positions where the derivatives is zero.
 
User avatar
outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

Re: Proofs of convergence of numerical algorithms

December 11th, 2017, 7:01 am

.. and for e.g. solving ode's numerically you have numerical methods like Euler, Runge Kuta,.. and for those you have "region of stability" that tell you what step size to pick, which numerical methods will work.
 
User avatar
Cuchulainn
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Proofs of convergence of numerical algorithms

December 11th, 2017, 7:36 am

katastrofa wrote:
I have a very general question (for the beginning, by an absolute beginner): what are the most common proofs of convergence of numerical algorithms? (I've encountered proofs based on energy minimisation so far.)

It depends on the problem  (my very general answer ::). But in many cases you want to solve a problem [$]F(x) = 0[$] in some Banach space by replacing it by a computable discretized problem [$]G(x^h,h) = 0 [$] where [$]h[$] is a parameter. Then all convergence proofs centre around computing the norm of [$]x^h - x[$] as a function of [$]h.[$]
In all cases a problem in uncountable space must be posed in countable space and then projected to a finite-dimensional problem. You don't need to know the exact solution (and in most cases it's not feasible).

The methods for proving convergence is a part of numerical analysis:

1. Taylor expansions
2. Polynomial and rational function approximation.
3. Divided differences to approximate derivatieves.
4. etc. etc.

5. Iterative processes that depend on an integer parameter [$]n[$], e.g. Newton.

Classic intros are Dahlquist/Bjorck 1974 and esp. Conte/de Boor 1980. A good 101 case is numerical quadrature or [$]e^A[$].
Many numerical analysts in academia spend time establishing convegence results for numerical processes.

http://web.mit.edu/10.001/Web/Course_No ... ration.pdf

http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf

Do you have a specific problem in mind?
Last edited by Cuchulainn on December 11th, 2017, 8:54 am
 
User avatar
Cuchulainn
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Proofs of convergence of numerical algorithms

December 11th, 2017, 8:00 am

.. and for PDE/FDM use the famous Peter Lax theorem to prove stability and convergence.

https://people.maths.ox.ac.uk/trefethen/4all.pdf
 
User avatar
katastrofa
Topic Author
Posts: 6135
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Proofs of convergence of numerical algorithms

December 17th, 2017, 7:11 pm

Thanks!
Cuchulainn, I will start from the info and sources you've suggested in your YACHAIC (yet another Cuchlainn's helpful and informative comment) :-)
Some time ago I needed to do a simple classification of data for my simulations. People commonly use k-means for this task, but I noticed that the method was not particularly suitable owing to the character of the data, so I typed in some formulas from the top of my head. Since the new method turned out to be better and performed well in tests, I gave my word that I would write it down, but I didn't realise that doing it properly requires more experience in algorithmics that I've earned during a course at the institute.
 
User avatar
Cuchulainn
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Proofs of convergence of numerical algorithms

May 4th, 2018, 7:05 pm

Any progress/insights?
 
User avatar
Cuchulainn
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Proofs of convergence of numerical algorithms

September 7th, 2018, 10:10 am

Are you referring to "probabilistic numerics" perchance? (Robbins and Monro)
 
User avatar
ExSan
Posts: 4512
Joined: April 12th, 2003, 10:40 am

Re: Proofs of convergence of numerical algorithms

September 14th, 2018, 12:27 am

Cuchulainn wrote:
.. and for PDE/FDM use the famous Peter Lax theorem to prove stability and convergence.

https://people.maths.ox.ac.uk/trefethen/4all.pdf

well explained, great paper
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...