Text
A Deterministic Kaczmarz Algorithm for Solving Linear Systems
We propose a new deterministic Kaczmarz algorithm for solving consistent linear systems
. Basically, the algorithm replaces orthogonal projections with reflections in the original scheme of Stefan Kaczmarz. Building on this, we give a geometric description of solutions of linear systems. Suppose is , we show that the algorithm generates a series of points distributed with patterns on an -sphere centered on a solution. These points lie evenly on lower-dimensional spheres
, with the property that for any , the midpoint of the centers of is exactly a solution of . With this discovery, we prove that taking the average of points on any effectively approximates a solution up to relative error , where characterizes the eigengap of the orthogonal matrix produced by the product of reflections generated by the rows of . We also analyze the connection between and , the condition number of . In the worst case , while for random matrices on average. Finally, we prove that the algorithm indeed solves the linear system , where is the lower-triangular matrix such that . The connection between this linear system and the original one is studied. The numerical tests indicate that this new Kaczmarz algorithm has comparable performance to randomized (block) Kaczmarz algorithms.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art144708 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain