2.6. Phương pháp tính giá trị đa thức¶
Cho đa thức
ta cần tìm giá trị \(p(x)\) tại \(x = c\), tức là tính \(p(c)\).
2.6.1. Tính giá trị đa thức với phép thế trực tiếp¶
Cách đơn giản nhất để tìm \(p(c)\) là thế trực tiếp giá trị \(c\) vào đa thức
Sau đó ta tính từng hạng tử
\(a_1 c\) cần một phép nhân;
\(a_2 c^2\) cần hai phép nhân \(a_2 \cdot c \cdot c\);
tương tự, a_i c^i cần \(i\) phép nhân.
Tổng cộng chúng ta cần
phép nhân. Sau đó ta cộng tất cả hạng tử lại với \(n+1\) phép cộng.
Vấn đề là số lượng phép nhân cần để tính rất lớn nên chúng ta sẽ tìm hiểu những phương án tính toán khác hiệu quả hơn.
2.6.2. Tính giá trị đa thức với việc ghi nhớ lũy thừa¶
Mình đề xuất một giải pháp đơn giản cho việc tính lũy thừa \(c^i\). Ở phần trên, mỗi hạng tử ta luôn phải tính lại \(c \cdot c \cdots c\) nên mình sẽ dùng dãy \(c_i\) cho lũy thừa và dãy \(p_i\) cho tổng:
khởi tạo \(c_0 = 1\) và \(p_0 = a_0\);
tính \(c_{i+1} = c_i \cdot c\) với \(0 \leqslant i \leqslant n - 1\);
tính \(p_{i+1} = p_i + a_{i+1} \cdot c_{i+1}\) với \(0 \leqslant i \leqslant n - 1\).
Như vậy mình cần thực hiện \(n\) phép cộng và \(2n\) phép nhân (tính \(c_i\) và \(a_{i+1} \cdot c_{i+1}\)).
Tiếp theo mình sẽ nói về phương pháp phổ biến để tính giá trị đa thức gọi là phương pháp Hoocner.
2.6.3. Phương pháp Hoocner¶
Để tính giá trị đa thức
tại \(x = c\), ta thực hiện:
khởi tạo \(p_0 = a_n\);
tính \(p_1 = p_0 c + a_{n-1}\);
tính \(p_2 = p_1 c + a_{n-2}\);
tương tự, tính \(p_{i} = p_{i-1} c + a_{n-i}\) với mọi \(1 \leqslant i \leqslant n\).
Cuối cùng, \(p_n\) chính là kết quả \(p(c)\).
Phương pháp Hoocner tốn \(n\) phép cộng và \(n\) phép nhân (ở mỗi bước cần một phép cộng và một phép nhân).
Tuy nhiên, phương pháp Hoocner có hai ứng dụng quan trọng khác trong đại số là xác định đa thức khi thay \(x\) thành \(y + c\) (với \(c\) là hằng số) và phân tích nhanh đa thức thành nhân tử khi biết một nghiệm.
Trước khi tìm hiểu phương pháp Hoocner tổng quát, mình sẽ trình bày phương pháp chia Hoocner trước.
2.6.4. Phương pháp chia Hoocner¶
Giả sử ta có đa thức
và ta biết một nghiệm của đa thức \(x = c\). Khi đó ta có thể phân tích đa thức \(p(x)\) thành nhân tử dạng
với \(p_1(x)\) là đa thức bậc \(n - 1\).
Đầu tiên ta viết các hệ số của đa thức theo bậc giảm dần \(a_n\), \(a_{n-1}\), ..., \(a_1\), \(a_0\) và giá trị \(c\) vào bảng.
\(a_n\) |
\(a_{n-1}\) |
\(\ldots\) |
|
\(x = c\) |
Tiếp theo ta điền các giá trị vào dưới chân các ô \(a_i\) bắt đầu từ \(a_n\) theo quy tắc "đầu rơi - nhân ngang - cộng chéo", có nghĩa là:
giữ nguyên \(a_n\);
các ô kế tiếp là kết quả của phép nhân ô trước đó với \(c\) rồi cộng cho ô bên trên.
\(a_n\) |
\(a_{n-1}\) |
\(\ldots\) |
|
\(x = c\) |
\(a_n\) |
\(a_n \cdot c + a_{n-1}\) |
Ví dụ, phân tích đa thức
khi biết một nghiệm \(x = 2\) của nó.
Đầu tiên ta viết các hệ số thành bảng:
\(1\) |
\(-1\) |
\(-1\) |
\(-2\) |
|
\(x = 2\) |
Ta giữ lại hệ số bậc cao nhất \(a_n\):
\(\color{blue}1\) |
\(-1\) |
\(-1\) |
\(-2\) |
|
\(x = 2\) |
\(\color{blue}1\) |
Tiếp theo, lấy kết quả vừa nhận được \(1\), nhân với \(x = 2\) rồi cộng ô chéo bên phải
\(\color{blue}1\) |
\(\color{red}-1\) |
\(-1\) |
\(-2\) |
|
\(x = 2\) |
\(\color{blue}1\) |
\({\color{blue}1} \cdot 2 + {\color{red}(-1)} = 1\) |
Như vậy kết quả dưới \(-1\) là \(1\), thực hiện tương tự ta có
\(1\) |
\(-1\) |
\(-1\) |
\(-2\) |
|
\(x = 2\) |
\(1\) |
\(1\) |
\(1 \cdot 2 + (-1) = 1\) |
Hệ số cuối cùng chắc chắn bằng \(0\)
\(1\) |
\(-1\) |
\(-1\) |
\(-2\) |
|
\(x = 2\) |
\(1\) |
\(1\) |
\(1\) |
\(1 \cdot 2 + (-2) = 0\) |
Như vậy \((1, 1, 1)\) là hệ số của đa thức \(p_1(x)\) theo bậc giảm dần, tức là
2.6.5. Phương pháp Hoocner tổng quát¶
Cho đa thức
ta sẽ xác định các hệ số của đa thức \(p(y + c)\) với \(y\) là biến mới và \(c\) là giá trị cho trước.
Giả sử
với \(b_i\) là các hệ số cần tìm.
Nếu \(y = 0\) thì \(p(c) = b_0\). Ta tính được \(b_0\) bằng phương pháp Hoocner bên trên.
Đặt
với \(p_1(x)\) là đa thức bậc \(n - 1\). Khi đó
và nếu ta đặt \(x = y + c\) thì
thì khi đồng nhất hai biểu thức \(p(x)\) ta được
Lặp lại quá trình trên, cho \(y = 0\) thì \(p_1(c) = b_1\), nói cách khác ta có thể tính \(b_1\) từ phương pháp Hoocner ở trên.
Tương tự ta tính \(b_i = p_i(c)\) với \(i = 1, 2, \ldots, n\), trong đó \(p_i(c)\) là giá trị đa thức bậc \(n - i\) tại \(x = c\).
Ví dụ 2.4 (Ví dụ phương pháp Hoocner tổng quát)
Cho
tính \(p(y - 1)\).
Ở đây \(c = -1\), ta sử dụng phương pháp chia Hoocner ở trên khi \(x = -1\).
\(2\) |
\(4\) |
\(0\) |
\(0\) |
\(-1\) |
\(1\) |
\(2\) |
|
\(x = -1\) |
\(2\) |
\(2\) |
\(-2\) |
\(2\) |
\(-3\) |
\(4\) |
\(-2\) |
Lúc này, hệ số \(b_0\) là giá trị ngoài cùng bên phải ở dòng thứ hai, nghĩa là \(b_0 = -2\).
Tiếp tục sử dụng phương pháp chia Hoocner để tìm hàng thứ ba từ hàng thứ hai
\(2\) |
\(4\) |
\(0\) |
\(0\) |
\(-1\) |
\(1\) |
\(2\) |
|
\(x = -1\) |
\(2\) |
\(2\) |
\(-2\) |
\(2\) |
\(-3\) |
\(4\) |
\(-2\) |
\(x = -1\) |
\(2\) |
\(0\) |
\(-2\) |
\(4\) |
\(7\) |
\(11\) |
Hệ số \(b_1\) là giá trị ngoài cùng bên phải ở dòng thứ ba, hay \(b_1 = 11\).
Tương tự, từ hàng trên ta áp dụng phương pháp chia Hoocner để tìm hàng dưới với độ dài trừ đi \(1\). Khi độ dài hàng bằng \(1\) thì ta kết thúc thuật toán.
\(2\) |
\(4\) |
\(0\) |
\(0\) |
\(-1\) |
\(1\) |
\(2\) |
|
\(x = -1\) |
\(2\) |
\(2\) |
\(-2\) |
\(2\) |
\(-3\) |
\(4\) |
\(-2\) |
\(x = -1\) |
\(2\) |
\(0\) |
\(-2\) |
\(4\) |
\(7\) |
\(11\) |
|
\(x = -1\) |
\(2\) |
\(-2\) |
\(0\) |
\(4\) |
\(-11\) |
||
\(x = -1\) |
\(2\) |
\(-4\) |
\(4\) |
\(0\) |
|||
\(x = -1\) |
\(2\) |
\(-6\) |
\(10\) |
||||
\(x = -1\) |
\(2\) |
\(-8\) |
|||||
\(x = -1\) |
\(2\) |
Như vậy, lấy kết quả ngoài cùng bên phải ở mỗi hàng ta có hệ số của đa thức \(p(y - 1)\), ở đây là