ADE gives best accuracy for average values of NX and NT (which should be more or less the same size). Brennan IE is N/A because it is first order.ADE for early exercise is in total about 15 lines of core code. I took your advice on the earlty check and that helped a lot. So my results to tene were before the fix.Values above NY = NT = 500 are becoming computationally intensive. Even IE gets the result with NY = NT = 4000 but it's a sledgehammer. Now, i would like to put in discrete dividends with early exercise! can ADE and AOPT do that

QuoteOriginally posted by: boriciQuoteOriginally posted by: CuchulainnThe Brennan Schwarz algo using Implicit Euler, LU and the standard check100, 100, P = 2.97486200,200, P = 3.04300,300, P = 3.060636400,400, P = 3.06462500, 500, P = 3.064269600,600, P = 3.06568700,7000, P = 3.0665683500, 3500, P = 3.0696654000,4000, P = 3.070014 (ADE needs 300X300)It's clear, yes?So, a numerical analysis in general is just a variation of the standard approach.I look forward to AOPT performance results.The Brennan-Schwarz algorithm has the same problem with the optimality. See the book "American put options", D. M. Salopek, p93 concludes that "the lagorithm itself leads to a false solution".What is the optimality problem with the Brennan-Schwartz algorithm inthe above mentioned book?The following paper shows that the algorithm does give the correct solution:Patrick Jaillet, Damien Lamberton, and Bernard Lapeyre,Variational inequalities and the pricing of American options,Acta Appl. Math. 21(1990), pp. 263-289.

QuoteOriginally posted by: Cuchulainn Tene,What is the rationale for the relationship between NS and NT (5:1 approx).Smax = 4 * K. edit: had a look at the Bren/Sch algo. Basically, one uses CN(for example) and modified LU to take early exercise constraint. This is almost the same as my scheme except I have explicit in time ADE. LU is not needed.The relationship between NS and NT as well as Smax = 4 K are based on numerical experimentswith the considered option.The used ratio between NS and NT seem to be nearly optimal on the used nonuniform grids inthe sense that a given accuracy is obtained with a minimum CPU time.Smax = 4 K is sufficiently far to lead highly accurate prices. As my grids are nonuniform Smaxcan be fairly large without much impact on CPU time.Of course with other options the ratio between NS and NT as well as Smax should/could besomething else.

QuoteOriginally posted by: TeneQuoteOriginally posted by: Cuchulainn Tene,What is the rationale for the relationship between NS and NT (5:1 approx).Smax = 4 * K. edit: had a look at the Bren/Sch algo. Basically, one uses CN(for example) and modified LU to take early exercise constraint. This is almost the same as my scheme except I have explicit in time ADE. LU is not needed.The relationship between NS and NT as well as Smax = 4 K are based on numerical experimentswith the considered option.The used ratio between NS and NT seem to be nearly optimal on the used nonuniform grids inthe sense that a given accuracy is obtained with a minimum CPU time.Smax = 4 K is sufficiently far to lead highly accurate prices. As my grids are nonuniform Smaxcan be fairly large without much impact on CPU time.Of course with other options the ratio between NS and NT as well as Smax should/could besomething else.In ADE case, I transform to y~ [0,1] so no truncation is needed but there is kind of singularity at y = 1 but this is no problem since I just shift the boundary a wee bit and then I get a very simple DE on y = 1.As you say, each scheme has its own truncation error profile; for ADE NY and NT are within a certain distance of each other. Smax = 4*K seems to a good one. I wonder if the Kangro result would be better and how it extends to n-factors. But it is not necessary if I used a box transformation.PS I accidentally removed the image; sorry, I well reinstate it

QuoteOriginally posted by: TeneQuoteOriginally posted by: boriciQuoteOriginally posted by: CuchulainnThe Brennan Schwarz algo using Implicit Euler, LU and the standard check100, 100, P = 2.97486200,200, P = 3.04300,300, P = 3.060636400,400, P = 3.06462500, 500, P = 3.064269600,600, P = 3.06568700,7000, P = 3.0665683500, 3500, P = 3.0696654000,4000, P = 3.070014 (ADE needs 300X300)It's clear, yes?So, a numerical analysis in general is just a variation of the standard approach.I look forward to AOPT performance results.The Brennan-Schwarz algorithm has the same problem with the optimality. See the book "American put options", D. M. Salopek, p93 concludes that "the lagorithm itself leads to a false solution".What is the optimality problem with the Brennan-Schwartz algorithm inthe above mentioned book?The following paper shows that the algorithm does give the correct solution:Patrick Jaillet, Damien Lamberton, and Bernard Lapeyre,Variational inequalities and the pricing of American options,Acta Appl. Math. 21(1990), pp. 263-289.I made an erratic quotation, which is true was for American calls without reordering indices. The book cited the above paper for the correctness of the algorithm, my apologies. However, the paper does NOT prove the correctness of the algorithm, only that the original LCP , algorithms D and D' lead to correct solution! I thought that the book referred to this observation and I was quick to quote it.

Here is the original data again. I accidentally removed it.I tried it with the modified scheme with tene's mesh. Now I get {2.87596, 3.051706, 3.08829, 3.098484, 3.079979, 3.064416}I guess these values is for nonunifom meshes. Experimenting, I get ADE100,100, 3.0044200,200,3.059068300,300, 3.070758400,400, 3.072222500,500,3.070198600,600,3.0705700,700,3.070683NY, NT200,500, 3.053243400,500, 3.068531Note I used exponential fitting above which is robust but first order (I can use higher-order fitting but have not done so). Now I get w/o EF100,100, 3.000654200,200,3.05812300,300, 3.07034400,400, 3.07198500,500,3.070048600,600,3.070447700,700,3.070606So, nonfitted is slightly more accurate, risk is convection dominance. I have not examined round-off errors (more NY, NT means more roundoff).

I had a look at both Jaillet (1980) and A. Borici's papers. These papers do realise that the mesh size in S needs to be chosen in such a way that the resulting matix is a Z matrix. This is 5.1 in Jaillet and p. 6.7 in Borici.Actually, this phenomenon is well-known in CFD and is called the Cell Reynolds number. If it is not not satisfied then you get spatial instability and the remedy is smaller (non-uniform?) meshes. The fitted schemes solve this problem and dat from the 50's but were little known up until the 80's.Wih fitting, you get good accuracy with coarse meshes, see here The first article discusses fitting based on work from 1980. Higher-order fitting schemes exist as well.Here is a stress test just to see how the various schemes behaver = 0, sig = 1r = 0.01, sig = 0.5r = 0.15, sig = 0.1r = 0.15, sig = 0.05(S = K = 100, T = 0.25)editsig = 0.02, T = 50, S = K = 100, r =.1How much effort is needed to get 3 places accuracy, for example. Experiment with NS, NT. Computing the Greeks, too, especially if you employ CN. I can almost guarantee your solution will oscillate in this case ..

QuoteOriginally posted by: CuchulainnI had a look at both Jaillet (1980) and A. Borici's papers. These papers do realise that the mesh size in S needs to be chosen in such a way that the resulting matix is a Z matrix. This is 5.1 in Jaillet and p. 6.7 in Borici.Actually, this phenomenon is well-known in CFD and is called the Cell Reynolds number. If it is not not satisfied then you get spatial instability and the remedy is smaller (non-uniform?) meshes. The fitted schemes solve this problem and dat from the 50's but were little known up until the 80's.Wih fitting, you get good accuracy with coarse meshes, see here The first article discusses fitting based on work from 1980. Higher-order fitting schemes exist as well.Here is a stress test just to see how the various schemes behaver = 0, sig = 1r = 0.01, sig = 0.5r = 0.15, sig = 0.1r = 0.15, sig = 0.05(S = K = 100, T = 0.25)How much effort is needed to get 3 places accuracy, for example. Experiment with NS, NT. Computing the Greeks, too, especially if you employ CN. I can almost guarantee your solution will oscillate in this case ..In Jaillet the 5.1 is not sign symmetric for r-sigma^2/2 which leads to confusion what to do if sign reveses. Anyway, a condition such as 6.7 is very easy to be met in practice. However, the main problem with the Jaillet et al paper is that it is quoted as the paper which proves the validity of the Brennan-Schwartz algorithm. In fact, it proves that the LCPs D and D' give the right solution. What they missed is that multiplying both sides by L^{-1} destroys the sign structure of right-hand-side and hence the conditions of their proofs.Regarding the fits I had a look at your paper which explains it. This is important for multi-factor options, whereas for single factor securities PCs do well on moderate to fine grids, so no need for coarse grids.

dbl

QuoteRegarding the fits I had a look at your paper which explains it. This is important for multi-factor options, whereas for single factor securities PCs do well on moderate to fine grids, so no need for coarse grids.Fitting is also applicable to n factors.The question of fine/coarse grids is not as important as the amount of effort to get a decent accuracy, which is the OP. Saying that in 1d we just throw more CPU at the problem does not resolve the numerical difficulties that emerge.My examples were to test the *robustness* of schemes..QuoteIn Jaillet the 5.1 is not sign symmetric for r-sigma^2/2 which leads to confusion what to do if sign reveses. Anyway, a condition such as 6.7 very easy to be met in practice5.1 is a well-known inequality in all of PDE/FDM and it is good that they mentiond it. It is a fact of life and has a physical meaning.6.7 may indeed be more flexible but it still needs human tweaking to make sure you have a Z matrix. With fitting, you are automatically assured of this, for any value of any parameter. That's one tweak less

QuoteOriginally posted by: TraderJoeQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: londonerAnyone can suggest which numerical method works best for computing the value of an american put option? e.g. least-square, duality, etc.Define bestConvergence, speed and accuracy - the usual suspects.I would add Robustness and ease of maintenance/extension to more case.For example, can we use these schemes for CEV model, or do we have to rewrite our code and check if we have a coercive/Z matrix all over again? For fit no, for some schemes I suspect yes.

bump