Cách đơn giản để tìm ra nguồn gốc thực sự của đa thức (khối) là gì?

Question

điều này có vẻ như là một câu hỏi rõ ràng đối với tôi, nhưng tôi không thể tìm thấy nó ở bất cứ đâu trên SO. Tôi có một đa thức khối và tôi cần phải tìm nguồn gốc thực sự của hàm. THE cách làm việc này là gì?

Tôi đã tìm thấy một số công thức dạng đóng cho rễ của một hàm khối, nhưng tất cả chúng đều sử dụng số phức hoặc nhiều chức năng trắc tuyến và tôi không thích chúng (và cũng không biết chọn cái nào) .

Tôi cần điều gì đó đơn giản; nhanh hơn là tốt hơn; và tôi biết rằng cuối cùng tôi sẽ cần phải giải quyết các đa thức của trật tự cao hơn, do đó, có một người giải quyết số sẽ có thể giúp đỡ quá. Tôi biết tôi có thể sử dụng một số thư viện để làm công việc khó khăn cho tôi, nhưng hãy nói rằng tôi muốn làm điều này như một bài tập.

Tôi đang mã hóa bằng C, vì vậy không cần import magic_poly_solver.

Câu hỏi tiền thưởng: Làm cách nào để chỉ tìm thấy các gốc trong một khoảng thời gian nhất định?

Answer 1

Đối với đa thức khối có closed form solutions, nhưng chúng không đặc biệt thích hợp cho phép tính số.

Tôi sẽ làm như sau đối với trường hợp khối: bất kỳ đa thức khối nào có ít nhất một gốc thực, bạn có thể dễ dàng tìm thấy nó bằng phương pháp Newton. Sau đó, bạn sử dụng deflation để có được đa thức bậc hai còn lại để giải quyết, hãy xem câu trả lời của tôi there để biết cách thực hiện bước thứ hai này một cách chính xác.

Một lời cảnh báo: nếu phân biệt đối xử gần bằng không, sẽ có một số thực nhiều gốc, và phương pháp của Newton sẽ thất bại thảm hại. Hơn nữa, vì vùng lân cận của gốc, đa thức giống như (x - x0)^2, bạn sẽ mất một nửa các chữ số có nghĩa (vì P (x) sẽ là < epsilon ngay khi x - x0 < sqrt (epsilon)). Vì vậy, bạn có thể muốn loại trừ điều này và sử dụng giải pháp biểu mẫu đóng trong trường hợp cụ thể này hoặc giải quyết đa thức phái sinh.

Nếu bạn muốn tìm nguồn gốc trong một khoảng thời gian nhất định, hãy kiểm tra Sturm's theorem.

Thuật toán tổng quát hơn (phức tạp) để giải quyết đa thức chung là Jenkins-Traub algorithm. Điều này rõ ràng là quá mức cần thiết ở đây, nhưng nó hoạt động tốt trên hình khối. Thông thường, bạn sử dụng triển khai của bên thứ ba.

Vì bạn làm C, sử dụng số GSL chắc chắn là cược tốt nhất của bạn.

Một phương pháp chung khác là tìm giá trị riêng của companion matrix với ví dụ. phân tích QR cân bằng, hoặc giảm xuống dạng chủ hộ gia đình. Đây là cách tiếp cận của GSL.

Answer 2

Nếu bạn không muốn sử dụng đóng từ các giải pháp (hoặc mong đợi các đa thức có thứ tự lớn hơn), phương pháp rõ ràng nhất là tính toán các gốc gần đúng bằng cách sử dụng Newton's method.

Thật không may là bạn không thể quyết định nguồn gốc nào bạn sẽ nhận được khi lặp lại, mặc dù nó phụ thuộc vào giá trị bắt đầu.

Đồng thời xem here.

Answer 3

Xem Solving quartics and cubics for graphics bởi D Herbison-Evans, được xuất bản trong Đồ họa Gems V.

Answer 4

/******************************************************************************* 
* FindCubicRoots solves: 
*  coeff[3] * x^3 + coeff[2] * x^2 + coeff[1] * x + coeff[0] = 0 
* returns: 
*  3 - 3 real roots 
*  1 - 1 real root (2 complex conjugate) 
*******************************************************************************/ 

int FindCubicRoots(const FLOAT coeff[4], FLOAT x[3]); 

http://www.realitypixels.com/turk/opensource/index.html#CubicRoots