View Full Version : Thuật toán giải tuyến tính
KEM_WALL
25-01-2005, 17:29
sorry, walls không nghiên cứu thuật toán nhiều nên cũng không rõ gọi tên vậy có đúng không nữa
bài toán là, giải 1 hệ n ẩn, n phương trình
walls nghe nói cái này gọi là hệ phương trình tuyến tính:
các bạn chỉ cho thuật toán giải với, không cần viết code đâu, nói sơ cũng được, code walls tự viết
còn 1 bài toán nữa về tối ưu, cũng hệ n ẩn, nhưng n-1 phương trình, còn 1 cái là bất phương trình, tìm nghiệm sao cho tối ưu bất phương trình đó (vb bất phương trình SUM(all ẩn) <= 100 chẳng hạn)
Thân gửi Kem Wall: nếu TẤT CẢ các ẨN trong TẤt CẢ các PHƯƠNG TRÌNH ĐỄU là bậc
nhứt thì là hệ phương trình TUYẾN TÍNH. Còn nếu có 1 ẩn nào đó trong phương trình nào đó có bậc khác 1 thì là hệ PHI TUYẾN
Nếu bạn muốn giải hệ tuyến tính thì có thể thử: giả sử hệ là:
a11*x1 + a12*x2 + ... + a1N*xN = b1
a21*x1 + a22*x2 + ... + a2N*xN = b2
........................
aN1*x1 + aN2*x2 + ... + aNN*xN = bN
=> thử đưa về hệ tương đương (đi từ trên xuống dưới: mỗi dòng bớt đi 1 ẩn):
c11*x1 + a12*x2 + ... + a1N*xN = d1 (N ẩn)
c22*x1 + a23*x2 + ... + a2N*xN = d2 (N-1 ẩn)
c33*x1 + a34*x2 + ... + a3N*xN = d3 (N-2 ẩn)
........................
aNN*xN = dN (1 ẩn)
Nói chi tiết hơn 1 chút: đánh số các dòng (phương trình) từ 1 tới N. Làm N-1 bước:
Ở bước 1, giảm số ẩn ở các dòng thứ 2, thứ 3,..., thứ N xuống còn N-1 ẩn
Ở bước 2, giảm số ẩn ở các dòng thứ 3, thứ 4,..., thứ N xuống còn N-2 ẩn
..............
Ở bước N-1, giảm số ẩn ở các dòng thứ N xuống còn 1 ẩn
Chi tiết hơn, ở bước i, giảm số ẩn ở các dòng thứ i+1, thứ (i+2),..., thứ N xuống còn N-i ẩn như sau:
1) Xét dòng thứ i: hệ số của các ẩn x[1],..., x[i-1] đã là 0 (do các bước trước). Nếu hệ số của ẩn x[i] cũng là 0 thì tìm một dòng thứ j (j từ i+1 tới N) có hệ số của x[i] khác 0:
1a) Nếu tìm không ra (dòng thứ j nào cũng có hệ số của x[i] là 0) thì kết luận: vô nghiệm hoặc vô số nghiệm và ngưng ngay.
1b) Nếu tìm ra thì đổi chỗ dòng thứ i và dòng thứ j.
4) Xét các dòng kế sau dòng thứ i (dòng thứ k : k từ i+1 tới N): hệ số của các ẩn x[1],..., x[i-1] đã là 0 (do các bước trước). Mình đưa hệ số của x[i] (ở dòng thứ k này) về 0 bằng cách nhân dòng thứ k với 1 số T[k] rồi trừ cho dòng thứ i: chọn T[k] sao cho sau khi nhân & trừ thì hệ số của ẩn x[i] là 0 (mỗi dòng k sẽ phải chọn T[k] khác nhau)
Sau khi làm N-1 bước thì hệ phương trình sẽ có dạng tam giác. Giải ngược từ dòng cuối lên dòng đầu
Cũng có thể đưa về dạng đường chéo: ở bước i, giảm số ẩn ở MỌI dòng xuống còn N-i ẩn (ở bước 4 phải xét mọi dòng). Sau N-1 bước thì dòng nào cũng chỉ có 1 ẩn.
Và còn có các cách giải khác nữa...
Bạn có thể coi thêm ở:
http://www.google.com/search?hl=en&q=solve+linear+system
(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)
-thân
to kem_wall: em làm cái này làm gì vậy?
cái mà bete mô tả là "Gaussian elimination". Anyway, 2 cái mà kem_wall đang tìm là:
1) Linear solver: có nhiều lắm, đơn giản nhất là "Gaussian elimination", "LU decomposition",... thuộc về direct solver, indirect solver cũng khá nhiều nhưng hơi advance. Recommmend kiếm cái "Gaussian elimination". Search chữ này trên google kiếm algorithm chứ nói ở đây thì thừa.
2) Linear programming: cái này cũng có nhiều, nhưng hông nhiều bằng linear solver. Pp classic nhất để giải cái này (và "tương đối" dễ nhất) là "Simplex method". Google plz. Nói thêm là cái này không dễ hiểu tí nào...
KEM_WALL
22-02-2005, 20:25
woa, sorry, lâu quá không vô box này:D, em hỏi chỉ để biết vậy thôi.
cám ơn bete nha
còn anh mach2 nè, cái thuật toán tính căn bậc n của 1 số thì làm sao ?
ah, còn cái hệ tuyến tính, có cách nào giải bằng matrix không vậy ? walls đang kiếm cái giải bằng matrix
Tính căn bậc n của 1 số hả? Em hỏi thật hay giỡn vậy? :P
Nói chứ tính chỉ dùng cộng trừ nhân chia thì như thế này:
sqrt(x,n) = x^(1/n) = exp(1/n*ln(x))
exp(x) tính bằng Maclaurin's formula
exp(x) = 1+x+x^2/2!+x^3/3!+....
nhưng ln(x) thì hơi phức tạp hơn, tách ra 2 trường hợp:
ln(1+x) = x-x^2/2+x^3/3-x^4/4+.... (-1<x<1)
ln(x) = ((x-1)/x) + 1/2*((x-1)/x)^2 + 1/3*((x-1)/x)^3+... (x>=1/2)
Hệ tuyến tính (gọi là hệ phương trình tuyến tính cho nó "sành điệu") giải bằng matrix chứ sao? Cái Gaussian chẳng hạn như bete mô tả sơ sơ thật ra là phép "trừ hàng", "trừ cột" của cái matrix đó.
Nói thêm là ngoài cách tính "mò" như thế, còn có thể tính sqrt(a,n) bằng giải pt x^n=a (giải numerical), bằng Newton chẳng hạn.
nhưng ln(x) thì hơi phức tạp hơn, tách ra 2 trường hợp:
ln(1+x) = x-x^2/2+x^3/3-x^4/4+.... (-1<x<1)
ln(x) = ((x-1)/x) + 1/2*((x-1)/x)^2 + 1/3*((x-1)/x)^3+... (x>=1/2)
Nếu tính ln(x) như thế này thì quả thật là phức tạp và khó nữa, không những thế mà còn gặp những khó khăn không giải quyết được.Mất nhiều vòng lặp lắm lắm vì các giá trị giảm xuống khá chậm (phần dư).
Tính ln(x) dựa vào công thức :
l[(1-x)/(1+x)] và chỉ cần x trong khoảng (-1,1) là quét tất cả các giá trị âm dương vô cùng và phần dư giảm xuống nhanh chóng. Dùng khải triển Taylor mà tính là ra thui á!!
Thân
Tôi thấy tính chỉ có cộng trừ nhân chia thì có gì mà phức tạp và khó đâu. Thật ra chia ra 2 trường hợp như thế thì các phần dư giảm rất nhanh chứ sao chậm? Chia ra 2 cái chủ yếu để giảm "điểm chết" thôi mà.
Ở CT (1) thì term x^n/n với abs(x)<1 thì x^n giảm nhanh, còn CT (2) thì (1-1/x)^n/n với x>1 (nếu 1/2<x<1 thì xài CT1) giảm cũng nhanh. Cũng có trường hợp chậm ví dụ với x=0.999999999 chẳng hạn nhưng CT của bạn thì cũng gặp 1-2 "điểm chết" tương tự.
Nhưng dù sao thì CT của bạn cũng đơn giản hơn nhiều.
Anh Mach2 có biết nhìu về Interval tree không? Giải thích hay cho em tài liệu đi lol
Thân gửi Rikku: tui cứ nghĩ bạn đã tìm ra câu trả lời rồi chứ (nhớ là bạn có hỏi về cái này trước đây & không thấy hỏi tiếp). Bạn muốn giải 1 bài toán cụ thể nào đó hay chỉ muốn biết về Interval Tree 1 cách tổng quát để nâng cao kiến thức ? Tui không có học về cái này, nhưng cũng sẽ thử đọc qua để bàn về bạn chơi cho vui (hy vọng Mach2 hay ai đó sẽ có câu trả lời cho bạn sớm). Khi bạn đặt câu hỏi trước đây, tui có đọc thoáng qua vài tài liệu => thấy hình như là có vài cách cài đặt khác nhau về chi tiết (nhưng căn bản là giống nhau về ý chính)
-thân
Trước đây Rikku cứ tưởng là tìm được tài liệu rồi, nhưng mãi mới biết mình nhầm, đọc phải cây hai chiều. Có bài Mobile IOI2001, lời giải bảo dùng Interval tree :(, đọc hổng hiều gì hết :wacko:.
Thân gửi Rikku, tui thử click vô 2 cái attachment
=> thấy nó nói "Done" mà màn hình trống trơn hổng thấy gì hết :(
=> nếu được thì Rikku cho thẳng cái link luôn được không !?
-thân
Hôm trước Rikku cũng định thế, nhưng mà expired rồi T_T.
Acrobat Reader 6.0 cơ. Rikku vẫn click được bình thường mà.
Thân gửi Rikku, tui thử click vô 2 cái attachment
=> thấy nó nói "Done" mà màn hình trống trơn hổng thấy gì hết :(
=> nếu được thì Rikku cho thẳng cái link luôn được không !?
To bete: Bạn save as chứ đừng chích thẳng vô.
To Rikku: Sorry tui cũng hông bít gì về cái này hết :( (tui dân toán ứng dụng chứ ko phải tin).
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.