• PDF
• Cite
• Share
Article Contents  Article Contents

# Convergence of a randomized Douglas-Rachford method for linear system

The research of the second author is partially supported by the NSFC grants 11871279, 11571178

• In this article, we propose a randomized Douglas-Rachford(DR) method for linear system. This algorithm is based on the cyclic DR method. We consider a linear system as a feasible problem of finding intersection of hyperplanes. In each iteration, the next iteration point is determined by a random DR operator. We prove the convergence of the iteration points based on expectation. And the variance of the iteration points declines to zero. The numerical experiment shows that the proposed algorithm performs better than the cyclic DR method.

Mathematics Subject Classification: 65F10, 65F20, 65K05, 90C25, 90C15, 15A06.

 Citation: • • Figure 1.  Comparison of number of projections/reflections between randomized Kaczmarz(RK), cyclic DR(CDR) and randomized DR(RDR) when the size of $A$ and $b$ is $m = 1000$ and $n = 100$

Table 1.  Number of Projections/Reflections(NPR) for $n = 50$

 $m$ $1000$ $2000$ $3000$ $4000$ $5000$ NPR CDR 1264 1404 1282 1488 1390 RK 725.3 701.1 696.1 671.3 683.8 RDR 705.2 683.8 696 669.6 698.8

Table 2.  Number of Projections/Reflections(NPR) for $n = 100$

 $m$ $1000$ $2000$ $3000$ $4000$ $5000$ NPR CDR 2620 2604 2692 2770 2770 RK 1508.4 1419 1425.5 1422.5 1395.1 RDR 1523.2 1425.8 1409.6 1421.4 1381.8

Table 3.  Number of Projections/Reflections(NPR) for $n = 150$

 $m$ $1000$ $2000$ $3000$ $4000$ $5000$ NPR CDR 4272 4286 4104 4096 3854 RK 2466.9 2194.4 2175.4 2092.1 2152 RDR 2574.2 2227.8 2160.8 2133 2113.8
• Figures(1)

Tables(3)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint