Trang 1 / 2 12 LastLast
Hiển thị kết quả từ 1 đến 10 / 13
  1. #1
    Tham gia
    15-09-2002
    Location
    Tp.Hcm
    Bài viết
    1,171
    Like
    0
    Thanked 2 Times in 2 Posts

    Thuật toán giải tuyến tính

    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)
    Quote Quote

  2. #2
    Tham gia
    03-01-2004
    Bài viết
    903
    Like
    0
    Thanked 11 Times in 7 Posts
    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...+linear+system

    (có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)

    -thân
    Được sửa bởi bete lúc 19:06 ngày 25-01-2005

  3. #3
    Tham gia
    17-09-2002
    Location
    SMA
    Bài viết
    749
    Like
    0
    Thanked 3 Times in 3 Posts
    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...
    Được sửa bởi Mach2 lúc 22:10 ngày 25-01-2005

  4. #4
    Tham gia
    15-09-2002
    Location
    Tp.Hcm
    Bài viết
    1,171
    Like
    0
    Thanked 2 Times in 2 Posts
    woa, sorry, lâu quá không vô box này, 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

  5. #5
    Tham gia
    17-09-2002
    Location
    SMA
    Bài viết
    749
    Like
    0
    Thanked 3 Times in 3 Posts
    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.

  6. #6
    Tham gia
    08-07-2003
    Location
    Hanoi
    Bài viết
    13
    Like
    0
    Thanked 0 Times in 0 Posts

    Thông tin Tính Ln(x) như thế thì phức tạp thật!

    Quote Được gửi bởi Mach2
    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

  7. #7
    Tham gia
    17-09-2002
    Location
    SMA
    Bài viết
    749
    Like
    0
    Thanked 3 Times in 3 Posts
    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.
    Được sửa bởi Mach2 lúc 16:28 ngày 19-03-2005

  8. #8
    Tham gia
    28-09-2004
    Location
    Hà Nội
    Bài viết
    290
    Like
    0
    Thanked 1 Time in 1 Post
    Anh Mach2 có biết nhìu về Interval tree không? Giải thích hay cho em tài liệu đi

  9. #9
    Tham gia
    03-01-2004
    Bài viết
    903
    Like
    0
    Thanked 11 Times in 7 Posts
    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
    Được sửa bởi bete lúc 01:14 ngày 20-03-2005

  10. #10
    Tham gia
    28-09-2004
    Location
    Hà Nội
    Bài viết
    290
    Like
    0
    Thanked 1 Time in 1 Post
    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 .
    Attached Files

Trang 1 / 2 12 LastLast

Bookmarks

Quy định

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
  •