MATLAB Examples

# Convergence of the Quasi-Optimal Kaczmarz algorithm.

Demonstrates the change in the rate of convergence of the Quasi-Optimal Kaczmarz algorithm (awaiting publication).

## Author & Reference

Dept. of Applied Mathematics, S. P. Korolyov Samara State Aerospace University (National Research University), Faculty of Computer Science, Samara, Russia.

• [1] A. I. Zhdanov, The method of augmented regularized normal equations, Computational Math- ematics and Mathematical Physics, 52 (2012), pp. 194-197.
• [2] T. Strohmer and R. Vershynin, A randomized Kaczmarz algorithm for linear systems with exponential convergence, J. Fourier Analysis and Applications, 15 (2009), pp. 262-278.
• [3] A.A. Ivanov and A.I. Zhdanov, On a modification of the iterative Kaczmarz algorithm, Abstracts of Conference Matematicheskoe Modelirovanie i Kraevye Zadachi (Mathematical modeling and boundary value problems), MMIKZ-2010, Vol.4, pp.75-77 (In Russian), http://matmod.ucoz.ru/2010/maket4.pdf

## See more for Regularization Tools dependency

```addpath ('../libs/regu/'); ```

## See more for AIRTools dependency

```addpath ('../libs/AIRtools/AIRtools/'); ```

## Generate test problem

Discretization of the "famous" Fredholm integral equation of the frst kind deviced by D. L. Phillips, see more in [6].

```[A,f,u_true] = phillips(512); [m,n] = size(A); N = [1:1:6000]; ```

## Execute the Kaczmarz (KM) alg

```[x0 info0] = kaczmarz(A,f,N); error_x0 = zeros(1,size(x0,2)); for i = 1:1:length(error_x0) error_x0(i) = norm(x0(:,i)-u_true,2); end; ```

## Execute the Randomized Kaczmarz (RKM) alg

```[x2 info2] = randkaczmarz(A,f,N); error_x2 = zeros(1,size(x0,2)); for i = 1:1:length(error_x0) error_x2(i) = norm(x2(:,i)-u_true,2); end; options.stoprule.type = 'NR'; options.stoprule.epsilon = 10^-8; ```

## Execute the QO-Kaczmarz (QO-KM) alg.

```[x1 info1] = qoptimalkaczmarz(A,f,N,[],options); error_x1 = zeros(1,size(x1,2)); for i = 1:1:length(error_x1) error_x1(i) = norm(x1(:,i)-u_true,2); end; ```

## Compare solutions

```figure; plot(1:1:length(x0(:,end)), x0(:,end), 'r', ... 1:1:length(x1(:,end)), x1(:,end), 'g', ... 1:1:length(x2(:,end)), x2(:,end), 'b--', ... 1:1:length(u_true) , u_true , 'c'); legend('KM', ... 'QO-KM', ... 'RKM', ... 'Exact Solution'); ```

## Compare convergence rate

```figure; semilogy (1:1:length(error_x0), error_x0, 'r',... 1:1:length(error_x1), error_x1, 'g', ... 1:1:length(error_x2), error_x2, 'b'); legend('KM', ... 'QO-KM', ... 'RKM'); ```