Implémentation des méthodes

Algorithme Brennan-Schwartz

M.J. Brennan and E.S. Schwartz ont introduit un algorithme de résolution des options américaines put avec conditions aux bords mixtes Dirichlet et Neumann (voir [9]) par différences finies. P. Jaillet, D. Lembertan et B. Lapeyre ont reformulé le problème avec des conditions aux bords Dirichlet, puis ils ont donné la justification de cet algorithme introduit par [9] pour le cas de différences finies. Nous avons remarqué que lors de la discrétisation soit par la méthode des éléments finis ou différences finies que le type de matrice qui apparaît est tridiagonale, de la forme : T =   b1 c1 0 ··· 0 a2 b2 c2 ··· 0 0 . . . . . . . . . . . . . . . ··· am−1 bm−1 cm−1 0 ··· 0 am bm   . La proposition 4.1.1 donne un algorithme directe de résolution du PCL de type Tu ≥ %, u ≥ ξ, (Tu −%, u −ξ) = 0, (4.1) Chapitre 4. Implémentation des méthodes 50 dans le cas où les éléments cj de T sont nuls. Proposition 4.1.1 (voir [10]) Une matrice du type T avec cj = 0 et bj > 0 pour j = 1,…,m, alors, pour tous vecteurs ξ et % le PCL suivant : Tu ≥ %, u ≥ ξ, (Tu −%, u −ξ) = 0, (4.2) a une solution unique donnée par les équations de récurrence : u1 = max  %1 b1 , ξ1  , uj = max ( 1 bj (%j −ajuj−1), ξj ) , 2 ≤ j ≤ m. La preuve de ce résultat découle des égalités : (Tu) 1 = b1 u1 et (Tu) j = bj uj +aj uj−1 (voir [10]). Afin de vérifier les hypothèses de la proposition 4.1.1, nous allons procédé à la décomposions LU. Dans le papier de S. Ikonnen et J. Toivannan ont combiné, sans justifier, l’algorithme de Brennan-Schwartz avec la décomposions LU (voir [11]) pour un problème de complémentarité linéaire issu de la discrétisation par différence finies pour l’option call. Dans ce qui suit, nous justifions cet l’algorithme, dans le cas des éléments finis pour l’option put.

La méthode PSOR

L’algorithme de relaxation, PSOR « Projected Successive Over-Relaxation » est un procédé itératif qui, introduit par [37] et l’extension de méthode de relaxation pour la résolution des systèmes linéaires sous la forme : Av = f, où A ∈ R m×m, v ∈ R m et f ∈ R m. La méthode de relaxation est basée sur la décomposition A = D−L−U, Chapitre 4. Implémentation des méthodes 66 où D, la matrice diagonale, L, matrice triangulaire inférieure stricte et U, matrice triangulaire supérieure, alors v est solution de Av = f, si et seulement, si v vérifie (D/ω −L)v = ((1/ω −1)D+U)v +f. Pour des valeurs de ω dans l’intervalle ]0,2[, on introduit la méthode de sur-relaxation successive (ou méthode SOR pour successive over relaxation) (voir [38, 39] ) 1 ω aiix n+1 i + X ji aijv n+1 j , (4.11) pour tout, i ∈ {1,…,m}. On peut écrire (4.11), sous la forme vectorielle :  I−ωD−1L  v n+1 = h (1−ω) I+ωD−1U i v n +ωD−1 f, d’ou on déduit la matrice d’itération Gω =  I−ωD−1L −1 h (1−ω) I+ωD−1U i . La méthode SOR converge si ([38]) ρ(Gω) < 1, pour ω ∈ ]0,2[, avec ρ(Gω) est le rayon spectral. Du faite que, le paramètre ω influence sur la vitesse de convergence ( voir [38]), le pas optimal est donné par cet relation : ωopt = 2 1 + q 1−ρ(GJacobi) 2 , avec GJacobi = D−1 (A−D) la matrice d’itération de Jacobi (voir [38]). En utilisant le théorème de Gerschgorin (voir [40]), On peut a priori borner les valeurs Chapitre 4. Implémentation des méthodes 67 propres par ρ(GJacobi) ≈ max 1 Ai i X j6=i |Ai j |. Nous intéressons maintenant, a appliqué la méthode PSOR, au problème de complémentarité linéaire suivant B u n+1 h ≥ d n , u n+1 h ≥ ψh,  B u n+1 h − d n  u n+1 h − ψh  = 0, (4.12) pour n = 0, …, N. Le problème 4.12, est équivalent à (voir [41]) minn B u n+1 h −d n ,un+1 h −ψh o = 0, pour, n = 0, …, N. Posons, A = B, v = u n+1 h et f = d n , on aura (voir [36]) min v n v −A−1 f,v −ψh o = 0. Où encore v = maxn A−1 f,ψh o . Ce problème peut être résolu par PSOR, ce dernier a été suggéré par Cryer (voir[37]) pour une discussion détaillée sur la méthode de Cryer voir [14]. Le principe est d’appliquer à la contrainte de maximisation (4.2) l’algorithme SOR. Alors ∀i ∈ {1,…,m}, vi = max {yi ,(ψh) i }, et les yi sont définis par 1 ω aiiy n+1 i + X ji aijy n+1 j . Chapitre 4. Implémentation des méthodes 68 L’algorithme de PSOR appliqué à 4.12, pour une itération du temps, est décris par Algorithm 3 PSOR for j = 1 to m do rj = dj − Pm i=1 Bjiui uj = uj +ω rj Bii uj = max[uj ,ψj ], end for.