Selekcja residualna w metodach rzutowych dla problemów dopuszczalności liniowej

W pracy rozważa się problem dopuszczalności liniowej (PDL), do którego sprowadza się wiele praktycznych problemów. Do rozwiązywania niesprzecznego PDL zaproponowano metodę rzutową, w której do konstrukcji wektora rzutowego wykorzystuje się tzw. model selekcji residualnej. Zaproponowano też rozszerzenie tej metody dla przypadku, kiedy nie zakłada się niesprzeczności badanego problemu. Przeprowadzono testy numeryczne, w których porównano prezentowaną metodę z innymi znanymi metodami.

In this paper there is considered the linear feasibility problem. The projection methods for this problem are studied. The so called residual selection model with a Cholesky factorization for construction of projection vector in each iteration is presented. There is proposed modification of this method for the assumption of inconsistency of the system of linear inequalities. If the considered system is inconsistent, we can find the so called ?-optimal solution. The computation results of numerical experiments are presented for projection methods with relaxation parameter equal to 1.0 and 1.5. The presented methods were programmed in Fortran 90. It can be observed that for each tested problem, the results for the projection method with residual selection are better than for others methods: the projection method with largest residuum and the projection method with regular obtuse cone selection. The influence of the relaxation parameter on the convergence is essential. All methods behave better for a bigger relaxation parameter.