PDA

View Full Version : chia sẻ kiến thức về giải pt bậc n



txt
31-08-2004, 01:12
mình đang viết 1 chương trình giải pt bậc n (đa thức f(x)=0trên tập R),nhưng đang gặp 1 số khó khăn trong việc tìm 1 thuật giải tối ưu:đó là:
_1 pt bậc lẻ luôn có ít nhất 1 nghiệm->dùng pp Newton-raphson là có thể tìm được ngay 1 nghiệm(gọi là a).Sau đó chia horner(nhanh thôi) cho (x-a),thu được 1 pt bậc chẵn.
_Nhưng giải 1 pt bậc chẵn như thế nào,khi mà pt này có thể có toàn nghiệm thực;nghiệm thực và phức;hoặc chỉ có nghiệm phức(= pt vô nghiệm khi ta chỉ giải tìm nghiệm thực).Mình chỉ quan tâm việc tìm nghiệm thực mà thôi.
_Rắc rối ở đây là:làm sao biết được 1 pt bậc chẵn có nghiệm hay không?
1)_Dùng quy tắc xét nghiệm thực dương hay âm (hay quy tắc xét số nghiệm thực của Buydanh) thì KHÔNG rõ ràng vì trong trường hợp pt VN nó lại cho số nghiệm là k hay KÉM nó 1 số chẵn(=có nghiệm hoặc không).
2)_Quy tắc Stuôcmơ: lại phức tạp và tính toán lâu do phải chia đa thức(cấp k cho cấp k-1 nhiều lần để lấy phần dư),khi phải giải 1 pt bậc cao mà dùng cách này để chỉ biết có nghiệm hay không,theo mình thì không phù hợp.
_Vậy bạn nào am tường về pp tính ,hay đã từng lập trình giải pt bậc n thì xin chỉ giáo giùm thật toán và giải thuật giải pt bậc n hiệu quả.Có thể liên lạc để trao đổi thêm.
_Xin lưu ý là những trình bày trên với muc đích giải hoàn toàn TỰ ĐỘNG TRÊN MÁY TÍNH.(không dính dáng gì tới giải = tay cả),và mình đang lập trình bằng C++.
_Xin cám ơn đã đọc tin.

whitepenguin
31-08-2004, 12:24
Thế bác có biết tìm giao điểm giữa tia với đường cong Bspline cấp n không chĩ cho tui với ,tui đang bí đây

bete
31-08-2004, 18:21
Thân gửi txt: bạn thử coi ở
http://oakroadsystems.com/math/polysol.htm

-thân

Mach2
02-09-2004, 01:31
Hehehehe, nhiều người máu me cái vụ polynomial solver này nhỉ?
cái link của bete thực chất ko thể giải quyết được trường hợp tổng quát, gặp pt kiểu như vầy:
(x^2+2x+2)^100 = 0
thì giải làm sao?

Giờ bàn đến chuyện giải polynomial solver. Ko giải chính xác nhé, tôi ko chơi chính xác. 2/3 thì có ý nghĩa gì so với 0.67?
Nếu bạn đã dùng vài commerical math soft như Matlab chẳng hạn, bạn sẽ thấy nó chơi tuốt bất cứ polynomial bậc nào, nghiệm phức hay thực. Thế nó dùng cái gì vậy?
Tổng kết cho đến bây giờ, các pp như hạ dần cấp (tìm 1 nghiệm bằng N-R, bisection,... gì gì rồi chia xuống để hạ cấp) đều ko thể giải trong trường hợp tổng quát (ko có can thiệp của người sử dụng). Vậy ý tưởng chính là: muốn giải tổng quát 1 polynomial, ta PHẢI tìm cả nghiệm phức của nó.
Các pp giải polynomial được biết đến bao gồm:
- Bairstow's method:
Pp này chỉ giải cho polynomial với real coeffs. Với polynomial loại này, các nghiệm phức là các cặp số phức conjugate với nhau. Bairstow sẽ tìm các quadratic term và cũng sử dụng hạ bậc. Như vậy pp này là "gần với tự nhiên" nhất so với các polynomial solver khác.
- Bernoulli's method:
Bernoulli's method dùng ý tưởng của linear difference equation và nghiệm đặc trưng của nó. Ý tưởng là dùng pp trội hơn của 1 nghiệm nào đó để tìm nghiệm này. Bernoulli tìm được nghiệm max và min rất nhanh. Bernoulli's method chỉ áp dụng cho trường hợp polynomial chỉ toàn nghiệm thực.
- Graeffe's method:
Pp này chuyển polynomial thành 1 polynomial tương đương, các nghiệm là square của các nghiệm của original polynomial. Tốc độ giải rất nhanh (quadratic) vì magnitude của các nghiệm cách nhau rõ hơn so với polynomial ban đầu, tuy có 1 số trường hợp hạn chế (như polynomial có các cặp nghiệm có magnitude bằng nhau như 3/-3 chẳng hạn thì phải thử để nhận). Pp này có thể áp dụng để giải các ill-polynomial có các nghiệm nhảm gần nhau như 1.00001 và 1.000000001 chẳng hạn.
- Muller's method:
Pp này khá complex về ý tưởng, tuy nhiên về cái đặt thì ko quá phức tạp. Đây là 1 pp sure-win, tuy nhiên tốc độ chỉ là superlinear.
- Laguerre's method:
Giống Muller's method.
- Jenkins-Traud method:
Very complex method and sure-win :D.
- Eigenvalues:
Chuyển bài toán polynomial thành bài toán tìm eigenvalues. Ý tưởng là khi giải eigenvalues của 1 ma trận, characteristic equation của nó là 1 polynomial. Do đó các pp giải eigenvalues của ma trận có thể được sử dụng để giải polynomial problem. Pp này có hạn chế là bạn phải lưu ma trận (tốn từ O(N^2) đến O(N^3)) nên khi gặp polynomial lớn (>10k) thì héo. Một số pp sparse storage ma trận có thể giúp đựơc phần nào. Tôi thích pp này. Sure-win and highly recommmend :D

Để tham khảo, bạn có thể xem thử các commercial soft xài pp nào.
Matlab: "roots" xài Eigenvalues method.
Mathematica: "NSolve" dùng J-T.
Một số opensourse, như Numerical Recipes dùng Laguerre's method. Bạn có thể tham khảo code.

Muốn tìm chi tiết pp nào, search tên pp đó trên google. Tôi cũng có tài liệu nhưng cũng chỉ lấy từ nguồn google. Hay đọc chương 9 Numerical Recipes.

Pyre
13-09-2004, 14:01
Thân gửi txt: bạn thử coi ở
http://oakroadsystems.com/math/polysol.htm

-thân
Không ngờ Bete cũng lang thang sang đây à! :D .
Bài này mình giải bên net rồi mà! Mời bạn chạy vào đây coi thử 1 tý.
Cả vấn đề tìm ước số chung của các đa thức cũng được thực hiện rồi, Nhưng bây giờ tôi không nhớ link! Vào đây :
http://ddth.org/forum/?action=msg&msg=1023479185&page=3

bete
13-09-2004, 23:23
Thân gửi Pyre: tui vốn là ở bên này, tình cờ lang thang sang bên kia đó chớ :)
Vậy là bạn lang thang qua bên này rồi hả :)
Mấy cái phương pháp của Mach2 nêu lên có vẻ hay đó chớ; để khi nào rảnh sẽ coi lại kỹ hơn để học hỏi thêm. Tui cũng thích cái cách của bạn đưa ra lắm. Tui cũng nhớ là có 1 cái thread bên đó về ước chung lớn nhứt của 2 đa thức, nhưng mà lần cuối cùng tui coi thì chưa có ai trả lời; nếu có người trả lời rồi thì tui cũng muốn coi giải ra sao để học hỏi. Tui cũng có viết thử, nhưng bằng PERL, khá lộn xộn nên cũng không muốn đăng lên làm gì

-thân

rongbattuvl
23-12-2009, 23:18
Các bạn ơi ai có tài liệu giải phương trình bậc n kể cả nghiệm phức cho mình xin với

byrainiu123
25-12-2009, 16:49
Có ai rành về tích chập matrix không giúp mình với

Cho ma trận Hx:
-1 0 1
-1 0 1
-1 0 1
Và ma trận I sau:
0 0 0 0 0 0
5 5 5 5 0 0
5 5 5 5 0 0
5 5 5 5 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Tính Tích Chập I*Hx //"*" Thể hiện phép tích chập