Phương pháp Gradient liên hợp giải hệ phương trình đại số tuyến tính

Bùi Thị Thanh Xuân và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 116 (02): 117 - 121<br /> <br /> PHƢƠNG PHÁP GRADIENT LIÊN HỢP GIẢI HỆ PHƢƠNG TRÌNH<br /> ĐẠI SỐ TUYẾN TÍNH<br /> Bùi Thị Thanh Xuân*, Dƣơng Thị Nhung<br /> Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên<br /> <br /> TÓM TẮT<br /> Phƣơng pháp Gradient liên hợp đƣợc Hestenses và Stiefel nêu ra đầu tiên vào những năm 1950 để<br /> giải hệ phƣơng trình đại số tuyến tính (PTĐSTT). Vì việc giải một hệ phƣơng trình tuyến tính<br /> tƣơng đƣơng với việc tìm cực tiểu của một hàm toàn phƣơng xác định dƣơng nên năm 1960<br /> Fletcher – Reeves đã cải biên và phát triển nó thành phƣơng pháp Gradient liên hợp cho cực tiểu<br /> không ràng buộc. Phƣơng pháp Gradient liên hợp (CG) chỉ cần tới đạo hàm bậc nhất nhƣng làm<br /> tăng hiệu quả và độ tin cậy của thuật toán. Trên cơ sở đó, bài báo nghiên cứu thuật toán CG và cài<br /> đặt thử nghiệm trên Matlab.<br /> Từ khóa: hệ phương trình đại số tuyến tính, phương pháp lặp, phương pháp Gradient liên hợp,<br /> CG, dạng toàn phương.<br /> <br /> TỔNG QUAN*<br /> Xét hệ phƣơng trình đại số tuyến tính Ax b<br /> trong đó A là ma trận vuông cấp n, x và b là<br /> véc tơ n chiều<br /> a11<br /> a21<br /> ...<br /> an1<br /> <br /> a12<br /> a22<br /> ...<br /> an 2<br /> <br /> ... a1n<br /> ... a2 n<br /> ... ...<br /> ... ann<br /> <br /> x1<br /> x2<br /> ...<br /> xn<br /> <br /> b1<br /> b2<br /> ...<br /> bn<br /> <br /> Hệ phƣơng trình đại số tuyến tính xuất hiện<br /> trong rất nhiều lĩnh vực nhƣ trong kinh tế,<br /> thống kê, hệ thống điện, xử lý ảnh, tối ƣu hóa,<br /> giải số các phƣơng trình vi phân,... với kích<br /> thƣớc của bài toán n có thể là 2 hoặc đến hàng<br /> chục triệu. Do đó một yêu cầu cần thiết là cần<br /> có các phƣơng pháp hiệu quả để giải hệ đại số<br /> tuyến tính nói trên. Các nhà Toán học đã<br /> nghiên cứu các phƣơng pháp giải hệ ĐSTT và<br /> phân loại thành 2 nhóm phƣơng pháp giải:<br /> phƣơng pháp trực tiếp (phƣơng pháp cho ta<br /> nghiệm đúng của hệ sau một số hữu hạn các<br /> phép tính) và phƣơng pháp lặp (phƣơng pháp<br /> k<br /> xây dựng một dãy vô hạn các xấp xỉ x mà<br /> giới hạn của nó là nghiệm đúng của hệ)<br /> Các nhà toán học cũng đƣa ra sự hạn chế của<br /> các phƣơng pháp trực tiếp. Chẳng hạn nhƣ<br /> phƣơng pháp Cramer về mặt lý thuyết là giải<br /> đƣợc hệ với n tùy ý, trong thực tế nếu ta có hệ<br /> *<br /> <br /> n ẩn số phƣơng pháp Cramer cần n!(n+1)(n-1)<br /> phép tính số học, khi đó máy tính hiện đại<br /> không thể tính đƣợc với n =20! Hay với<br /> 2<br /> phƣơng pháp Gauss đòi hỏi n 3 phép tính và<br /> 3 ổn định. Nhƣ<br /> hơn nữa thuật toán Gauss không<br /> vậy để giải số các bài toán có kích thƣớc lớn<br /> cần dùng đến các phƣơng pháp lặp.Các<br /> phƣơng pháp lặp có thể kể đến nhƣ phƣơng<br /> pháp Jacobi, Gauss-Seidel, phƣơng pháp độ<br /> dốc lớn nhất (Steepest descent), ...đặc biệt là<br /> phƣơng pháp Gradient liên hợp (Conjugate<br /> Gradient method) tỏ ra hiệu quả khi ma trận<br /> hệ số là ma trận đối xứng, xác định dƣơng.<br /> Trong không gian R n ta đƣa vào một tích vô<br /> hƣớng mới đƣợc xác định bởi công thức:<br /> x, y A<br /> Ax, y , trong đó .,. là tích vô<br /> hƣớng thông thƣờng cho bởi x, y<br /> <br /> n<br /> <br /> xi yi .<br /> i 1<br /> <br /> Tích vô hƣớng mới này đƣợc gọi là tích năng<br /> lượng và chuẩn cảm sinh bởi nó đƣợc gọi là<br /> chuẩn năng lượng. Nhƣ vậy x<br /> <br /> A<br /> <br /> Ax, x<br /> <br /> Xét quá trình lặp<br /> B<br /> <br /> x(k<br /> <br /> 1)<br /> <br /> x(k )<br /> <br /> Ax ( k )<br /> <br /> b,k<br /> <br /> 0,1, 2...<br /> <br /> (*)<br /> <br /> 0<br /> <br /> với x bất kỳ.<br /> Định lý Samarski: Giả sử A là ma trận đối<br /> xứng xác định dƣơng và B là ma trận xác định<br /> <br /> Tel: 0906 062458, Email: bttxuan@ictu.edu.vn<br /> <br /> 117<br /> <br /> Bùi Thị Thanh Xuân và Đtg<br /> <br /> dƣơng. Khi đó nếu B<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> A thì phƣơng pháp<br /> <br /> 2<br /> lặp (*) hội tụ theo chuẩn năng lƣợng của A,<br /> tức là lim x k x<br /> 0.<br /> k<br /> <br /> A<br /> <br /> PHƢƠNG PHÁP ĐỘ DỐC LỚN NHẤT<br /> (STEEPEST DESCENT)<br /> Cho hệ phƣơng trình đại số tuyến tính Ax b<br /> với giả thiết A là ma trận đối xứng xác định<br /> dƣơng xT Ax 0,<br /> x 0.<br /> Bài toán trên tƣơng đƣơng với bài toán cực<br /> x , trong<br /> tiểu hóa dạng toàn phƣơng: minn<br /> x <br /> <br /> đó dạng toàn phƣơng<br /> x<br /> <br /> 1 T<br /> x Ax<br /> 2<br /> <br /> b x<br /> <br /> Gradient của dạng toàn phƣơng:<br /> T<br /> <br /> x<br /> <br /> x1<br /> <br /> x ,<br /> <br /> x2<br /> <br /> x ,..,<br /> <br /> xn<br /> <br /> x<br /> <br /> .<br /> <br /> Gradient là trƣờng véc tơ hƣớng theo hƣớng<br /> x tại điểm x đã cho<br /> giảm nhanh nhất của<br /> <br /> x<br /> <br /> 1 T<br /> 1<br /> A x<br /> Ax b .<br /> 2<br /> 2<br /> <br /> x Ax b . Cho<br /> Nếu A đối xứng thì<br /> gradient bằng 0 ta thu đƣợc nghiệm của<br /> phƣơng trình Ax b . Nghiệm của phƣơng<br /> trình là điểm tới hạn của hàm .<br /> Nếu A vừa đối xứng vừa xác định dƣơng thì<br /> nghiệm của phƣơng trình Ax b là điểm cực<br /> x .<br /> tiểu toàn cục của<br /> <br /> Do<br /> <br /> x<br /> <br /> đạt<br /> <br /> cực<br /> <br /> trị<br /> <br /> khi<br /> <br /> gradient<br /> <br /> x Ax b 0 nên bài toán tìm cực trị<br /> tƣơng đƣơng với việc giải hệ phƣơng trình đại<br /> số tuyến tính Ax b . Ta biết rằng gradient là<br /> hƣớng hàm tăng nhanh nhất. Nhƣ thế muốn đi<br /> đến cực tiểu ta cho x, tính gradient và tìm<br /> theo hƣớng ngƣợc lại cho đến khi hàm không<br /> giảm nữa. Phƣơng pháp độ dốc lớn nhất<br /> (steepest desceent) thực hiện nhƣ sau:<br /> <br /> - Xuất phát từ x0 tạo ra dãy x1 , x2 ,... tiến gần<br /> đến nghiệm x.<br /> - Tại mỗi bƣớc chọn hƣớng<br /> giảm nhanh<br /> nhất – hƣớng ngƣợc lại với gradient của tại<br /> xi b Axi<br /> xi :<br /> 118<br /> <br /> Sai số ei<br /> <br /> xi<br /> <br /> vậy<br /> <br /> Aei ; ri<br /> <br /> ri<br /> <br /> x . Độ lệch ri<br /> <br /> b<br /> <br /> Axi . Nhƣ<br /> <br /> độ lệch là<br /> <br /> xi<br /> <br /> hƣớng giảm nhanh nhất của hàm<br /> <br /> x .<br /> <br /> Thuật toán Steepest Descent<br /> Cho x0<br /> Tính r0<br /> <br /> b<br /> <br /> Ax0<br /> <br /> Lặp k =1,2,...<br /> <br /> rk T rk<br /> rk T Ark<br /> <br /> k<br /> <br /> xk<br /> rk<br /> <br /> T<br /> <br /> 116 (02): 117 - 121<br /> <br /> xk<br /> <br /> 1<br /> <br /> b<br /> <br /> 1<br /> <br /> r<br /> <br /> k k<br /> <br /> Axk<br /> <br /> 1<br /> <br /> cho tới khi hội tụ.<br /> Phƣơng pháp Steepest descent lặp theo hƣớng<br /> của các bƣớc trƣớc nên hội tụ không nhanh,<br /> sẽ hiệu quả hơn nếu trong mỗi bƣớc của thuật<br /> toán khi ta trƣợt theo hƣớng nào đó thì ta<br /> trƣợt đến chỗ thuật toán dừng tại bƣớc lặp<br /> cuối cùng.<br /> PHƢƠNG PHÁP GRADIENT LIÊN HỢP<br /> Phƣơng pháp Gradient liên hợp là phƣơng<br /> pháp tìm cực tiểu hóa của dạng toàn phƣơng:<br /> x* arg minn<br /> <br /> x<br /> <br /> x R<br /> <br /> (1)<br /> <br /> 1 T<br /> x Ax bT x<br /> 2<br /> <br /> x<br /> <br /> trong đó A R n n là ma trận đối xứng xác<br /> định dƣơng và b Rn là véc tơ cho trƣớc. Rõ<br /> ràng ta có:<br /> x<br /> <br /> 2<br /> <br /> Ax b,<br /> <br /> A<br /> <br /> (2)<br /> <br /> Từ (2) ta thấy rằng x* cũng chính là nghiệm<br /> của phƣơng trình tuyến tính Ax b .<br /> y tz<br /> Từ định lý Taylor cho g t<br /> chúng ta thu đƣợc với mọi t  và với mọi<br /> y n và z  n ta có:<br /> <br /> y tz<br /> <br /> y<br /> <br /> t<br /> <br /> y<br /> <br /> T<br /> <br /> t2 T<br /> z<br /> z Az (3)<br /> 2<br /> <br /> Phƣơng pháp tìm kiếm theo hƣớng: Cho<br /> một xấp xỉ x j của phƣơng án tối ƣu x* và một<br /> véc tơ hƣớng p j , phƣơng pháp CG sẽ đƣa ra<br /> một xấp xỉ tiếp theo x j<br /> <br /> 1<br /> <br /> thông qua 2 bƣớc:<br /> <br /> Bùi Thị Thanh Xuân và Đtg<br /> <br /> Tìm<br /> <br /> j<br /> <br /> Đặt x j<br /> <br /> 1<br /> <br /> argmin<br /> xj<br /> <br /> j<br /> <br /> xj<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Cần chứng minh (*) đúng với k i 1 , tức là<br /> cần chứng minh xi 1 arg min y trong đó<br /> <br /> pj<br /> <br /> pj<br /> <br /> y Ui<br /> <br /> Giả sử rằng x0 là xấp xỉ ban đầu, sau đó, áp<br /> dụng k bƣớc lặp sẽ trả về kết quả là một dãy<br /> k 1<br /> <br /> lặp x j<br /> <br /> j 0<br /> <br /> . Từ (2) và (3) chúng ta tìm đƣợc<br /> <br /> xi<br /> <br /> p r<br /> <br /> x<br /> <br /> y<br /> <br /> p Ap j<br /> <br /> 2<br /> <br /> xj<br /> <br /> b , ở đây r j<br /> <br /> Ax j<br /> <br /> Định nghĩa 1. Tập hƣớng<br /> <br /> là tập<br /> <br /> j 0<br /> <br /> hƣớng liên hợp nếu<br /> <br /> p Api<br /> <br /> 0 i<br /> <br /> j<br /> <br /> x Ui<br /> <br /> W0<br /> <br /> 1<br /> <br /> z Rn z<br /> <br /> Wk<br /> <br /> U0<br /> <br /> x0<br /> <br /> Bổ<br /> <br /> đề<br /> <br /> 1.<br /> <br /> xj<br /> <br /> j<br /> <br /> trƣớc.<br /> pi , ri<br /> <br /> x<br /> <br /> min<br /> y Ui<br /> <br /> 1<br /> <br /> y<br /> <br /> minn<br /> <br /> <br /> piT ri<br /> <br /> 2<br /> <br /> Cho<br /> <br /> x0<br /> <br /> wk , wk<br /> <br /> pi<br /> <br /> liên<br /> <br /> p j . Cho rj<br /> <br /> Ax j<br /> <br /> pi , f ( y )<br /> <br /> Wk<br /> <br /> hợp,<br /> <br /> b , x0 cho<br /> <br /> p j . Khi đó<br /> <br /> y Ui<br /> <br /> y Wi và A xi<br /> <br /> xi<br /> <br /> pi , ri<br /> <br /> y<br /> <br /> pi , Axi<br /> <br /> b<br /> <br /> pi , ri<br /> <br /> pi , Axi<br /> Ay b<br /> <br /> pi ,<br /> <br /> arg min<br /> <br /> y<br /> <br /> y<br /> <br /> 0<br /> <br /> liên hợp. Khi đó<br /> j<br /> <br /> k<br /> <br /> *<br /> <br /> Chứng minh: Ta chứng minh định lý bằng<br /> phƣơng<br /> pháp<br /> quy<br /> nạp<br /> k 1: x1 arg min y . Giả sử (*) đúng với<br /> <br /> pk<br /> <br /> k 1<br /> <br /> Ark , p j<br /> <br /> j 0<br /> <br /> Ap j , p j<br /> <br /> rk<br /> <br /> y Uj<br /> <br /> y<br /> <br /> 1<br /> <br /> và<br /> <br /> j i<br /> <br /> .<br /> <br /> pj<br /> <br /> 0, 0 m<br /> <br /> j k<br /> <br /> Chứng minh bằng phƣơng pháp quy nạp:<br /> Với k 1 kiểm tra trực tiếp ta thấy<br /> Ap0 , p1 0 . Giả sử với k i , hệ véc tơ<br /> i<br /> <br /> là liên hợp từng đôi một. Chúng ta<br /> <br /> j 0<br /> <br /> cần<br /> Apm , pi<br /> <br /> 1<br /> <br /> chứng<br /> minh<br /> 0, 0 m i .<br /> <br /> rằng<br /> <br /> Đặt m i , sau đó ta có:<br /> <br /> y U1<br /> <br /> arg min<br /> <br /> xi<br /> <br /> Nhƣ vậy để xây dựng thuật toán Gradient liên<br /> hợp ta phải:<br /> Xây dựng công thức truy toán sinh các hƣớng<br /> liên hợp pi<br /> Rút gọn một số công thức tính toán<br /> Sử dụng các hƣớng liên hợp tính toán các xi<br /> r0 , r0 Ax0 b<br /> Bổ đề 2. Cho p0<br /> <br /> pj<br /> <br /> y Uj<br /> <br /> k i , tức là x j<br /> <br /> y<br /> <br /> T<br /> i<br /> <br /> Kết luận: Apm , p j<br /> <br /> y Ui<br /> <br /> pi<br /> 1<br /> <br /> 0<br /> <br /> y<br /> <br /> pi , A xi<br /> <br /> ( y)<br /> <br /> Định lý 1. Cho<br /> <br /> y , pi<br /> <br /> b<br /> <br /> piT Api .<br /> <br /> p r<br /> . Vế trái đạt cực tiểu chính<br /> p Api<br /> xác khi xi 1 xi<br /> i pi .<br /> i<br /> <br /> Chứng minh: Nhận xét rằng xi U i . Lấy<br /> <br /> xj<br /> <br /> piT Api<br /> <br /> T<br /> i i<br /> <br /> 0<br /> <br /> arg min f x j<br /> <br /> j<br /> <br /> y Ui<br /> <br /> 2<br /> <br /> Vế phải đạt cực tiểu khi<br /> <br /> span p0 , p1 ,.., pn<br /> <br /> 1<br /> <br /> y<br /> <br /> Ta có:<br /> min<br /> <br /> Siêu phẳng:<br /> <br /> xj<br /> <br /> piT Api<br /> <br /> 2<br /> <br /> 2<br /> <br /> T<br /> j<br /> <br /> Ký hiệu:<br /> <br /> x0<br /> <br /> piT<br /> <br /> y<br /> <br /> k 1<br /> <br /> pj<br /> <br /> y<br /> <br /> 2<br /> <br /> thƣờng đƣợc gọi là độ lệch (residual).<br /> <br /> Uk<br /> <br /> pi<br /> <br /> piT<br /> <br /> y<br /> <br /> trong đó rj<br /> <br /> Wk<br /> <br /> nghĩa U i 1 ,<br /> pi trong đó<br /> <br /> Áp dụng (3) và bổ đề 1 ta có:<br /> <br /> T<br /> j<br /> <br /> Api , p j<br /> <br /> 1<br /> <br /> xi<br /> Theo định<br /> 1<br /> i pi .<br /> x U i 1 có thể viết x y<br /> , y U i<br /> <br /> T<br /> j j<br /> <br /> j<br /> <br /> 116 (02): 117 - 121<br /> <br /> Apm , pi<br /> <br /> 1<br /> <br /> Apm , rk<br /> <br /> i<br /> <br /> Ari 1 , p j<br /> <br /> j 0<br /> <br /> Ap j , p j<br /> <br /> 1<br /> <br /> Apm , p j<br /> 119<br /> <br /> Bùi Thị Thanh Xuân và Đtg<br /> <br /> Ari 1 , pm<br /> Apm , pm<br /> <br /> 1<br /> <br /> Bổ đề 3. Giả sử<br /> <br /> pj<br /> <br /> Bổ đề 2. Khi đó Wk<br /> <br /> rj , rm<br /> <br /> 0,<br /> <br /> 0<br /> <br /> rj , pk<br /> <br /> k<br /> j 0<br /> <br /> Apm , pm<br /> <br /> 0<br /> <br /> đƣợc xây dựng theo<br /> <br /> span r0 , r1 ,.., rk<br /> <br /> 1<br /> <br /> j m k<br /> <br /> rk , rk<br /> <br /> 0<br /> <br /> j k<br /> <br /> pk thỏa mãn<br /> <br /> pk<br /> <br /> rk<br /> <br /> k 1<br /> <br /> pk 1 ,<br /> <br /> rk , rk<br /> rk 1 , rk<br /> <br /> k 1<br /> <br /> 1<br /> <br /> Thuật toán CONJUGATE GRADIENT<br /> - Cho xấp xỉ ban đầu x0<br /> - Đặt r0<br /> <br /> Ax0<br /> <br /> b , p0<br /> <br /> r0<br /> <br /> k=0<br /> For k = 1: k max<br /> pk rk<br /> k<br /> pk Apk<br /> <br /> xk<br /> rk<br /> <br /> 1<br /> <br /> k<br /> <br /> rk<br /> <br /> 1<br /> <br /> k<br /> <br /> pk<br /> <br /> Apk<br /> <br /> pk Ark 1<br /> pk Apk<br /> <br /> k<br /> <br /> pk<br /> <br /> xk<br /> <br /> 1<br /> <br /> rk<br /> <br /> k<br /> <br /> pk<br /> <br /> end<br /> Ta thấy rằng phƣơng pháp CG nếu không có<br /> sai số tính toán thì sẽ dừng sau không quá n<br /> bƣớc và thu đƣợc nghiệm đúng. Tuy nhiên<br /> trong quá trình giải có sai số tính toán nên<br /> phƣơng pháp CG coi nhƣ phƣơng pháp lặp để<br /> tìm nghiệm gần đúng.<br /> Đánh giá sai số của phƣơng pháp Gradient<br /> liên hợp:<br /> <br /> 1<br /> 1<br /> <br /> 2<br /> <br /> A<br /> <br /> for npot = 0.1:0.4:2<br /> A = (R'*R)^npot;<br /> lamb = eig(A);<br /> kappa = max(lamb)/min(lamb);<br /> xsol = rand(n,1);<br /> b = A*xsol;<br /> Norm2 = sqrt(xsol'*xsol);<br /> NormA = sqrt(xsol'*A*xsol);<br /> x = zeros(size(b));<br /> g = A*x-b;<br /> p = -g;<br /> for i = 1:n<br /> Ap = A*p;<br /> alfa = -(p'*g)./(p'*Ap);<br /> x = x + alfa*p;<br /> g = g + alfa*Ap;<br /> beta = (g'*Ap)./(p'*Ap);<br /> p = -g + beta*p;<br /> err2(i) = sqrt((x-xsol)'*(x-xsol))/Norm2;<br /> errA(i) = sqrt((x-xsol)'*A*(x-xsol))/NormA;<br /> end<br /> subplot(1,2,1);<br /> plot(lamb,zeros(size(lamb)),'o');<br /> Tittel = ['Eigenvalues, n=' num2str(n)];<br /> title(Tittel);<br /> subplot(1,2,2); semilogy(1:n, err2, 1:n,<br /> errA);<br /> legend('chuan 2', 'chuan A');<br /> xlabel('So lan lap');<br /> ylabel('Sai so');<br /> Tittel = ['npot = ',num2str(npot),'\kappa =<br /> ',num2str(kappa)];<br /> title(Tittel);<br /> pause;<br /> end<br /> Eigenvalues, ndim=100<br /> <br /> 10<br /> <br /> -4<br /> <br /> 10<br /> 0.4<br /> <br /> A<br /> <br /> -6<br /> <br /> 10<br /> <br /> 0.2<br /> <br /> -0.2<br /> <br /> A<br /> <br /> n<br /> <br /> chuan 2<br /> chuan A<br /> <br /> -2<br /> <br /> 0<br /> <br /> với<br /> <br /> = 3.5136<br /> <br /> 10<br /> <br /> 0.6<br /> <br /> x * x0<br /> <br /> npot = 0.1<br /> <br /> 0<br /> <br /> 1<br /> 0.8<br /> <br /> l<br /> <br /> x * xl<br /> <br /> 116 (02): 117 - 121<br /> <br /> sai so<br /> <br /> Apm , rk<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> là số điều kiện của A<br /> <br /> -8<br /> <br /> 10<br /> <br /> -10<br /> <br /> 10<br /> <br /> -0.4<br /> <br /> -12<br /> <br /> 10<br /> -0.6<br /> <br /> 1<br /> <br /> Thử nghiệm trên MATLAB<br /> n = 100;<br /> R = randn(n);<br /> <br /> 120<br /> <br /> -14<br /> <br /> 10<br /> <br /> -0.8<br /> -1<br /> 0.5<br /> <br /> -16<br /> <br /> 1<br /> <br /> 1.5<br /> <br /> 2<br /> <br /> 10<br /> <br /> 0<br /> <br /> 50<br /> So lan lap<br /> <br /> 100<br /> <br /> Hình 1. Ma trận có điều kiện tốt, hội tụ nhanh<br /> <br /> Bùi Thị Thanh Xuân và Đtg<br /> Eigenvalues, ndim=100<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> npot = 0.5<br /> <br /> 0<br /> <br /> 1<br /> <br /> trên cơ sở đó nghiên cứu đến một phƣơng<br /> pháp hiệu quả giải hệ ĐSTT, đó chính là<br /> phƣơng pháp Gradient liên hợp (CG). Ngoài<br /> ra chúng tôi cũng đã mô phỏng thuật toán CG<br /> bằng Matlab để so sánh sự hiệu quả của<br /> phƣơng pháp trong các điều kiện của ma trận<br /> hệ số A.<br /> <br /> = 535.4972<br /> <br /> 10<br /> <br /> chuan 2<br /> chuan A<br /> <br /> 0.8<br /> 0.6<br /> 0.4<br /> <br /> -5<br /> <br /> 10<br /> <br /> sai so<br /> <br /> 0.2<br /> 0<br /> -0.2<br /> -10<br /> <br /> 10<br /> <br /> -0.4<br /> -0.6<br /> -0.8<br /> -1<br /> <br /> -15<br /> <br /> 0<br /> <br /> 5<br /> <br /> 10<br /> <br /> 15<br /> <br /> 10<br /> <br /> 20<br /> <br /> 0<br /> <br /> 50<br /> So lan lap<br /> <br /> 100<br /> <br /> Hình 2. Ma trận có điều kiện trung bình<br /> Eigenvalues, ndim=100<br /> <br /> npot = 1.3<br /> <br /> 0<br /> <br /> 1<br /> <br /> TÀI LIỆU THAM KHẢO<br /> <br /> = 12438519.0126<br /> <br /> 10<br /> <br /> chuan 2<br /> chuan A<br /> <br /> 0.8<br /> 0.6<br /> 0.4<br /> <br /> -1<br /> <br /> 10<br /> <br /> sai so<br /> <br /> 0.2<br /> 0<br /> -0.2<br /> -2<br /> <br /> 10<br /> <br /> -0.4<br /> -0.6<br /> -0.8<br /> -1<br /> <br /> -3<br /> <br /> 0<br /> <br /> 1000<br /> <br /> 2000<br /> <br /> 3000<br /> <br /> 10<br /> <br /> 0<br /> <br /> 50<br /> So lan lap<br /> <br /> 116 (02): 117 - 121<br /> <br /> 100<br /> <br /> Hình 3. Ma trận với điều kiện xấu, tốc độ hội tụ chậm<br /> <br /> KẾT LUẬN<br /> Trong bài báo này chúng tôi đã giới thiệu đến<br /> một số phƣơng pháp giải hệ đại số tuyến tính,<br /> <br /> 1. A. van der Sluis and H. A. van derVorst (1986),<br /> The Rate of Convergence of Conjugate Gradients,<br /> Numerische Mathematik 48, no. 5, 543–560.<br /> 2. Magnus R. Hestenes and Eduard Stiefel (1952),<br /> Methods of Conjugate Gradients for Solving<br /> Linear Systems, Journal of Research of the<br /> National Bureau of Standards 49, 409–436.<br /> 3. R. Fletcher and M. J. D. Powell (1963), A<br /> Rapidly Convergent Descent Method for<br /> Minimization, Computer Journal 6,163–168.<br /> 4. Đặng Quang Á (2009), Giáo trình Phương pháp<br /> số, Nxb Đại học Thái Nguyên.<br /> 5. Nguyễn Hoàng Hải (2006), Lập trình Matlab và<br /> ứng dụng, Nxb Khoa học kỹ thuật<br /> <br /> SUMMARY<br /> THE CONJUGATE GRADIENT METHOD<br /> FOR SOLVING THE SYSTEM OF LINEAR EQUATIONS<br /> Bui Thi Thanh Xuan*, Duong Thi Nhung<br /> College of Information & Communication Technology – TNU<br /> <br /> The conjugate gradient method (CG) has been first introduced in 1952 by M. R. Hestenes and E.<br /> Stiefel. It has been the subject of intense analysis for more than 50 years. The method was<br /> originally consider to be direct method for linear equations, but its favorable properties as an<br /> iterative method was soon realized, and it was later generalized to more general optimization<br /> problems. It provides a very effective way to optimize large, deterministic systems by gradient<br /> descent. In this paper, we introduce about CG and experiment with CG method using Matlab.<br /> Key words: iterative method, linear equations, conjugate gradient method, CG, quadratic<br /> functions.<br /> <br /> Ngày nhận bài:23/09/2013; Ngày phản biện:04/10/2013; Ngày duyệt đăng: 26/02/2014<br /> Phản biện khoa học: TS. Trương Hà Hải – Trường ĐH Công nghệ Thông tin & Truyền thông - ĐHTN<br /> *<br /> <br /> Tel: 0906 062458, Email: bttxuan@ictu.edu.vn<br /> <br /> 121<br /> <br />