Thuật toán trung bình thành phần giải phương trình thưa, kích thước lớn

Bài viết trình bày một cách có hệ thống phương pháp trung bình thành phần để giải hệ phương trình tuyến tính thưa, kích thước lớn. Kết quả cho thấy phương pháp trung bình thành phần và các kết quả hội tụ của nó không phụ thuộc vào hệ tương thích hay không tương thích.
Nội dung trích xuất từ tài liệu:
Thuật toán trung bình thành phần giải phương trình thưa, kích thước lớn KHOA HỌC CÔNG NGHỆ THUẬT TOÁN TRUNG BÌNH THÀNH PHẦN GIẢI PHƯƠNG TRÌNH THƯA, KÍCH THƯỚC LỚN Phạm Kim Phượng* ABSTRACT This study is a literature review of parallel iterative algorithms, with emphasis on the componentaveraging (CAV) algorithm as well as its numerical testing. The results show that: i) Instead oforthogonal projections and scalar weights are used in Cimino algorithm by oblique projection anddiagonal weight matrix system. ii) The convergence of the component mean method does not dependon whether the system is compatible or not. iii) A numerical test illustrating the convergence of CAVusing Matlab software. Keywords: The Cimmino Algorithm, the CAV Algorithm. Received: 8/11/2021; Accepted: 23/11/2021; Published: 12/12/2021 1. Đặt vấn đề bình thành phần Ta đã biết bài toán chấp nhận lồi: “Tìm một Trong thuật toán song song, Cimmino làđiểm thuộc tương giao của các tập lồi đóng trong phương pháp cơ bản nhất. Trước hết, ta xét thuậtkhông gian Hilbert, biết rằng giao của chúng là toán Cimmino sau.khác rỗng” là bài toán có nhiều ứng dụng trong Thuật toán Cimminolý thuyết tối ưu, xử lý ảnh, lý thuyết trò chơi… Chiếu x k ∈ R n lên các tập Ci , ta thu được cácKhi các tập lồi đóng là siêu phẳng, Kaczmarz điểm trung gian(1937) và Cimmino (1938) đã đề xuất các thuật x k +1,i = Pi ( x k ) , với i = 1,2,3,..., m . (1.1)toán chiếu tuần tự và song song kinh điển để giải Công thức lặp thu được làbài toán nói trên. Von Neumann (1933) xét bàitoán tìm giao của hai không gian con đóng bằng  m  x k + λk  ∑ w i x k +1,i − x k  x k +1 = (1.2)phương pháp chiếu xoay vòng. Censor (2000) đề  i =1 xuất phương pháp chiếu tổng quát cho bài toán Trong trường hợp hệ phương trình tuyến tính,chấp nhận lồi với các siêu phẳng. Giải hệ phương với bất kì z ∈ R n , phép chiếu trực giao của z lêntrình đại số tuyến tính là trường hợp đặc biệtcủa bài toán chấp nhận lồi. Nếu số phương trình Hi làbằng số ẩn, các phương pháp lặp truyền thống bi − a i , z Pi ( z )= z + ai như Jacobi, Gauss-Seidel, lặp giảm dư, vv.... tỏ ra ai 2 2khá hữu hiệu trong việc tìm gần đúng nghiệm củahệ phương trình. Phương pháp trung bình thành Ở thuật toán Cimmino, ta xét với w i = 1/ m ,phần (CAV) là một kỹ thuật lặp song song mới để bước lặp x k +1 là trung bình các phép chiếu của x kgiải hệ này. lên tập lồi Ci . Các bước thuật toán như sau 2. Nội dung nghiên cứu Bước 0 : Cho x 0 ∈ R n bất kỳ . 2.1. Tổng quan lý thuyết về thuật toán trung Bước thứ k+1 : Cho x k ta thu được  m 1 * ThS Bộ môn Toán, Khoa Cơ sở-Cơ bản, Đại Học Hàng x k + λk  ∑ x k +1,i − x k  x k +1 =Hải Việt Nam  i =1 m  TẠP CHÍ QUẢN LÝ VÀ CÔNG NGHỆ - Số 19 Quý 4/2021 55KHOA HỌC CÔNG NGHỆ  m 1  Để chứng minh sự hội tụ của (1.5), phần tiếp x k + λk  ∑ Pi x k − x k  = ( ) theo, ta thay phép chiếu trực giao lên siêu phẳng  i =1 m  bởi phép chiếu xiên theo ma trận trọng số.  m  k b − ai , x k   Phép chiếu xiên tổng quát lê ...