Thuật toán chia đa thức bậc n cho tam thức bậc 2.

Khi chia một đa thức bậc n cho 1 đa thức bậc 2, ta sẽ được thương là một đa thức bậc n – 2 và phần dư là nhị thức bậc nhất. Nếu đặt phép chia đa thức ta sẽ xác định được kết quả cần tìm, tuy nhiên, việc làm này vừa tốn thời gian, vừa dễ sai sót. Ta sẽ xây dựng sơ đồ thuật toán để có thể xác định nhanh chóng các hệ số của đa thức thương và đa thức phần dư giống như sơ đồ Hooc-ne chia đa thức cho nhị thức bậc nhất.

Giả sử, đa thức bị chia bậc n có dạng:

P_{n} = {a_{0}.x^{n} + a_{1}. x^{n-1} + a_{2}x^{n-2} + ... + a_{n-2} .x^{2} + a_{n-1}.x + a_{n}}

Ta xét trường hợp tam thức bậc 2 có dạng: {x^{2} + px  + q} . (trường hợp hệ số của {x^{2} \ne 1} dành cho các bạn tự xem xét).

Đa thức thương:

Q(x) = b_{0}.x^{n-2} + b_{1}. x^{n-3} + b_{2}x^{n-4} + ... + b_{n-4} .x^{2} + b_{n-3}.x + b_{n-2}

Và phần dư: R(x) = cx + d .

Ta có:

{a_{0}x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+ ...+ a_{n-2}x^{2}+a_{n-1}x + a_{n}} = \\ {(x^{2} + px  + q)}.{(b_{0}x^{n-2}+b_{1}x^{n-3}+...+b_{n-4}x^{2} +b_{n-3}x + b_{n-2})} \\ + {(cx + d)}

Đồng nhất các hệ số ta có:

\left \{ \begin{array}{l} {a_{0} = b_{0}} \\{a_{1} = b_{1} + p.b_{0}} \\{a_{2} = b_{2} + p.b_{1}+q.b_{0}} \\{a_{3} = b_{3} + p.b_{2}+q.b_{1}} \\{a_{4} = b_{4} + p.b_{2}+q.b_{1}} \\{\cdots} \\{a_{i} = b_{i} + p.b_{i-1}+q.b_{i-2}} \\{\cdots} \\{a_{n-2} = b_{n-2} + p.b_{n-3}+q.b_{n-4}} \\{a_{n-1} = c + p.b_{n-2}+q.b_{n-3}} \\{a_{n} = d + q.b_{n-2}} \end{array} \right.

Từ đây ta sẽ xác định được các hệ số của đa thức thương và đa thức phần dư như sau:

\left \{ \begin{array}{l} {b_{0} = a_{0}} \\{b_{1} = a_{1} - p.b_{0}} \\{b_{2} = a_{2} - p.b_{1} - q.b_{0}} \\{b_{3} = a_{3} - p.b_{2} - q.b_{1}} \\{b_{4} = a_{4} - p.b_{2} - q.b_{1}} \\{\cdots} \\{b_{i} = a_{i} - p.b_{i-1} - q.b_{i-2}} \\{\cdots} \\{b_{n-2} = a_{n-2} - p.b_{n-3} - q.b_{n-4}} \\{c = a_{n-1} - p.b_{n-2} - q.b_{n-3}} \\{d = a_{n} - q.b_{n-2}} \end{array} \right.

Dựa trên hệ đẳng thức trên ta có thể lập bảng thuật toán sau để có thể xác định nhanh các hệ số của đa thức thương và đa thức phần dư khi chia một đa thức bậc n cho tam thức bậc hai:

Đầu tiên, dựa vào đẳng thức xác định các hệ số b_{0}, b_{1} và d. Ta sẽ có bảng sau:

\begin{array}{c| c c c c c c c c c c c c| c c c} P_{n} & a_{0} &  {} & a_{1} & {}  & a_{2} & {} & a_{3} & \cdots & a_{n-3} &  {} & a_{n-2} &  {} & a_{n-1} &  {} & a_{n} \\ \hline -p & 0 & {} & {} & {} & {} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & 0 \\ \hline -q & 0 & {} & 0 & {} & {} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \hline Q(x) & b_{0} & {} & {} & {} & {} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \end{array}

Ta xác định các hệ số còn lại dựa vào đẳng thức sau:

{b_{i} = a_{i} - p.b_{i-1} - q.b_{i-2}}

Xác định hệ số b1:

\begin{array}{c| c c c c c c c c c c c c| c c c} P_{n} & a_{0} & {} & a_{1} & {} & a_{2} & {} & a_{3} & \cdots & a_{n-3} & {} & a_{n-2} & {} & a_{n-1} & {} & a_{n} \\ \hline -p & 0 & {} & -p.b_{0} & {} & {} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & 0 \\ \hline -q & 0 & {} & 0 & {} & {} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \hline Q(x)& b_{0} & {} & b_{1} & {} & {} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \end{array}

Cộng 3 dòng đầu tiên tương ứng với cột a1 ta sẽ có hệ số b1.

Xác định hệ số b2:

\begin{array}{c| c c c c c c c c c c c c| c c c} P_{n} & a_{0} & {} & a_{1} & {} & a_{2} & {} & a_{3} & \cdots & a_{n-3} & {} & a_{n-2} & {} & a_{n-1} & {} & a_{n} \\ \hline -p & 0 & {} & -p.b_{0} & {} & -p.b_{1} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & 0 \\ \hline -q & 0 & {} & 0 & {} &-q.b_{0}& {} & {} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \hline Q(x)& b_{0} & {} & b_{1} & {} & b_{2} & {} & {} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \end{array}

Cộng 3 dòng đầu tiên tương ứng với cột a2 ta sẽ có hệ số b2.

Ta xác định hệ số b3 hoàn toàn tương tự, ta có:

\begin{array}{c| c c c c c c c c c c c c| c c c} P_{n} & a_{0} & {} & a_{1} & {} & a_{2} & {} & a_{3} & \cdots & a_{n-3} & {} & a_{n-2} & {} & a_{n-1} & {} & a_{n} \\ \hline -p & 0 & {} & -p.b_{0} & {} & -p.b_{1} & {} & -p.b_{2} & \cdots & {} & {} & {} & {} & {} & {} & 0 \\ \hline -q & 0 & {} & 0 & {} &-q.b_{0}& {} & -q.b{1} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \hline Q(x)& b_{0} & {} & b_{1} & {} & b_{2} & {} & b_{3} & \cdots & {} & {} & {} & {} & {} & {} & {} \\ \end{array}

Cộng 3 dòng đầu tiên tương ứng với cột a3 ta sẽ có hệ số b3.

Các hệ số còn lại được xác định hoàn toàn tương tự. Ta có bảng thuật toán tổng quát sau:

\begin{array}{c| c c c c c c c c c c c | c c c} P_{n}&a_{0}&{}&a_{1}&{}&a_{2}&{}&a_{3}& \cdots &a_{n-3}&{}& a_{n-2}&a_{n-1}&{}&a_{n} \\ \hline -p&0&{}&-pb_{0}&{}&-pb_{1}&{}&-pb_{2}& \cdots &-pb_{n-4}&{}&-pb_{n-3}&-pb_{n-2}&{}&0 \\ \hline -q&0&{}&0&{}&-qb_{0}&{}&-qb{1}& \cdots &-qb_{n-5}&{}&-qb_{n-4}&-qb_{n-3}&{}&-qb_{n-2} \\ \hline Q(x)&b_{0}&{}&b_{1}&{}&b_{2}&{}&b_{3}& \cdots &b_{n-3}&{}&b_{n-2}&c&{}&d \\ \end{array}

Ví dụ 1:

Chia đa thức {4x^{4} - 3x^{3} + 2x^{2} - x} cho {x^{2} - x + 1}

Ta lập bảng thuật toán sau:

\begin{array}{c| c c c c c c | c c c} P_{n}&4&{}&-3&{}&2&{}&-1&{}&0 \\ \hline 1&0&{}&4&{}&1&{}&-1&{}&0 \\ \hline -1&0&{}&0&{}&-4&{}&-1&{}&1 \\ \hline {}&4&{}&1&{}&-1&{}&-3&{}&1 \\ \end{array}

Vậy ta có:

{4x^{4} - 3x^{3} + 2x^{2} - x} = {(x^{2} - x + 1)}.{(4x^{2} + x - 1)} -3x + 1

Ví dụ 2:

Chia đa thức {x^{6} - x^{5} + x^{4} - x^{3} + x^{2} - x + 1} cho {x^{2} - 2x + 3}

Tương tự, áp dụng sơ đồ thuật toán ở trên ta sẽ có:

\begin{array}{r| r r r r r r r r r | r r r} P_{n}&1&{}&-1&{}&1&{}&-1&{}&1&-1&{}&1 \\ \hline 2&0&{}&2&{}&2&{}&0&{}&-8&-14&{}&0 \\ \hline -3&0&{}&0&{}&-3&{}&-3&{}&0&12&{}&21 \\ \hline {}&1&{}&1&{}&0&{}&-4&{}&-7&-3&{}&22 \\ \end{array}

Vậy ta có:

{x^{6} - x^{5} + x^{4} - x^{3} + x^{2} - x + 1} \\ =  {(x^{2} - 2x + 3)}.{(x^{4} + x^{3} - 4x - 7)} -3x + 22


Bằng cách làm hoàn toàn tương tự, bạn sẽ thiết lập được sơ đồ thuật toán để tính nhanh kết quả của phép chia một đa thức bất kỳ cho một đa thức bậc 3, bậc 4, …

Bạn hãy thử xem thế nào nhé!

2Bo02B – thunhan.wordpress.com

3 responses to “Thuật toán chia đa thức bậc n cho tam thức bậc 2.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s