Database Reference
In-Depth Information
6.2.3 Model-Free Case: TD with Additive Preconditioner
We would now like to deploy the multilevel approach to accelerate the TD
(
)-method. To this end, we invoke the approach of a so-called preconditioner,
which we shall present in the following.
We consider the inter-level operators I lþ1 , I l as described in Sect. 6.2.1 .
Moreover, let I l be the prolongator from level l to level m defined as
I l ¼ I m 1 I m 1
λ
I l 1
l
...
,
ð 6
:
16 Þ
m 2
and I l
is stipulated to be the identity matrix. Let a preconditioner C 1
t
be given by
¼ X
L
0 β l , t I l I 0 :
C 1
t
ð 6
:
17 Þ
It is summarized in Algorithm 6.3.
Algorithm 6.3: BPX preconditioner (Ziv)
Input: residual y , number of grids L, interpolator I 1 , restrictor I 1
, coefficient
l
vectors
β l
Output: new guess x
n
R
1: procedure BPX( y )
2:
x 0
: ¼ y
3:
for k ¼ 1,
...
, L do
x l
: ¼ I l 1 x l 1
4:
restriction
5:
end for
6:
for k ¼ 0,
...
, L do
x l
: ¼ β l x l
7:
scaling
8:
end for
for k ¼ L ,
...
9:
,1do
x l 1
: ¼ I l 1
l
x l
10:
interpolation
11: end for
12: return x 0
13: end procedure
The preconditioner of Ziv ( 6.17 ) can be viewed as an algebraic counterpart to the
BPX preconditioner [BPX90] well known in numerical analysis.
Then the preconditioned TD(
λ
)-method (for simplicity we avoid the iteration
indexes)
:¼ w þ α t C 1
t
w
z t d t
ð 6
:
18 Þ
converges almost surely to the same solution as the TD(
)-method ( 3.20 ).
The proof of convergence is essentially based on the subsequent theorem from
[Ziv04], a further generalization of which has been devised in [Pap10].
λ
Search WWH ::




Custom Search