Information Technology Reference
In-Depth Information
Ta b l e 5 . 1 Description of the
PSOR algorithm
Choose an initial guess x 0
c .
Choose ω
and ε> 0.
For k = 0 , 1 , 2 ,... ,
For i = 1 ,...,N ,
( 0 , 1
]
b i
A ij x j
1
i
N
1
A ii
x k + 1
i
A ij x k + 1
j
:=
j
=
1
j
=
i
+
1
max c i ,x i
x i )
x k + 1
i
+ ω(x k + 1
i
:=
Next i
If
x k + 1
x k
2 stop else
Next k
5.4.1 Projected Successive Overrelaxation Method
AsshowninEqs.( 5.9 ) and ( 5.10 ), the numerical pricing by both the FDM and FEM
of an American option reduces to solving (in each time step) an LCP. Both can be
written in the abstract form: find x
N
∈ R
such that
A x b ,
x
c ,
(5.11)
c) ( A x
( x
b )
=
0 .
Problem ( 5.11 ) was solved by Cryer [47]usingthe projected successive overre-
laxation (PSOR) method for matrices A being symmetric and positive definite. In
applications in finance, however, A is not symmetric due the presence of a drift term
in the infinitesimal generator of the price process. It can be shown that PSOR works
also for matrices which are not symmetric, but diagonally dominant.
The algorithm is described in Table 5.1 where we denote by A ij the entries
of A ,i.e. A
i . If the step x k + 1
i
=
( A ij ) 1 i,j N , and we assume that A ii =
0,
:=
c i ,x i
x k + 1
i
x i )
max
{
+
ω(
}
is replaced by
x k + 1
i
x i
x k + 1
i
x i ),
=
+
ω(
then we get the classical SOR for the solution of A x
=
b . This step ensures the
inequality condition x
c . The parameter ω is a relaxation parameter. Since the
PSOR is an iterative algorithm, we have to discuss its convergence. The following
result is proven in [1, Chap. 6].
Proposition 5.4.1 Assume A satisfies
(i) There exist constants C 1 ,C 2 > 0 such that C 1 v v
v A v
C 2 v v ,
N ;
v
∈ R
> j = i |
(ii) It is diagonally dominant , i . e .
|
A ii |
A ij |
,
i .
x k
Furthermore , assume ω
( 0 , 1
]
. Then , the sequence
{
}
generated by PSOR con-
verges , as k
→∞
, to the unique solution x of ( 5.11 ).
Search WWH ::




Custom Search