Tag: đa thức

Lagrange interpolating polynomial


Đây là bài thứ bốn về đa thức của tôi, các bạn học sinh nên xem lại ba bài trước để học cho dễ dàng hơn.

[1] https://nttuan.org/2007/10/26/poly01/

[2] https://nttuan.org/2009/01/11/poly02/

[3] https://nttuan.org/2018/08/25/poly03/

—

Đa thức có thể được sử dụng để xấp xỉ các đường cong phức tạp, hay tính giá trị của các hàm logarit và lượng giác. Đầu tiên, chọn một vài dữ liệu đã biết, sau đó tìm một đa thức có bậc đủ bé có cùng dữ liệu đã chọn, cuối cùng xem đa thức vừa tìm được như là hàm số đang xét. Điều này dẫn đến việc tính toán nhanh hơn đáng kể.

Định lí. Cho số nguyên dương n và n+1 số phức đôi một khác nhau x_0, x_1, \ldots, x_{n}. Khi đó với mỗi n+1 số phức y_0, y_1, \ldots, y_n, có đúng một đa thức P(x) với hệ số phức có bậc không lớn hơn n sao cho

P(x_i)=y_i,\quad \forall i=\overline{0,n}.

Chứng minh. Nếu P và Q là các đa thức thỏa mãn các điều kiện của định lí thì đa thức P-Q có bậc không lớn hơn n và có ít nhất n+1 nghiệm, suy ra P-Q là đa thức không và P=Q. Mặt khác, đa thức \displaystyle P(x)=\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x-x_j}{x_i-x_j} thỏa mãn P(x_i)=y_i,\quad \forall i=\overline{0,n}, do đó định lí được chứng minh. \Box

Hệ quả (Công thức nội suy Lagrange). Cho số nguyên dương n và đa thức P(x) với hệ số phức có bậc không lớn hơn n. Khi đó với mỗi n+1 số phức đôi một khác nhau x_0, x_1, \ldots, x_{n}, ta có

\displaystyle P(x)=\sum_{i=0}^nP(x_i)\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}.

Trong công thức trên, n+1 số phức x_0, x_1, \ldots, x_{n} được gọi là các nút nội suy. Ta thường dùng công thức nội suy Lagrange trong tình huống: Biết thông tin của P tại các x_i, cần tìm thông tin của P tại y\not\in \{x_i\}.

Ví dụ 1. Cho hai đa thức A(x)=x^{81}+x^{49}+x^{25}+x^9+x và B(x)=x^3-x. Tìm dư khi chia A(x) cho B(x).

Lời giải. Giả sử Q(x) và R(x) lần lượt là thương và dư trong phép chia A(x) cho B(x). Ta có A(x)=B(x)Q(x)+R(x) và \deg R<3. Vì B(0)=B(1)=B(-1)=0 nên R(0)=0, R(1)=5 và R(-1)=-5, do đó áp dụng công thức nội suy Lagrange cho R với các nút 0;1 và -1 ta có

\displaystyle R(x)=R(0).\frac{(x-1)(x+1)}{(0-1)(0+1)}+R(1).\frac{(x-0)(x+1)}{(1-0)(1+1)}+R(-1).\frac{(x-0)(x-1)}{(-1-0)(-1-1)}

\displaystyle =\frac{5}{2}x(x+1)-\frac{5}{2}x(x-1)=5x. \Box

Ví dụ 2. Cho số nguyên dương n và đa thức P có bậc n thỏa mãn \displaystyle P(k)=\frac{k}{k+1},\quad \forall k=\overline{0,n}. Tính P(n+1).

Lời giải. Do P có bậc n nên áp dụng công thức nội suy Lagrange cho P với n+1 nút 0, 1, \ldots, n ta có \displaystyle P(x)=\sum_{k=0}^nP(k)\prod_{j\not =k}\frac{x-j}{k-j}

\displaystyle =\sum_{k=0}^n\frac{k}{k+1}\prod_{j\not =k}\frac{x-j}{k-j}=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(x-j),\quad\forall x\in\mathbb{R}. Suy ra

\displaystyle P(n+1)=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(n+1-j)

\displaystyle =\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}.\frac{(n+1)!}{n+1-k}

\displaystyle =\frac{1}{n+2}\sum_{k=0}^nk(-1)^{n-k}C^{k+1}_{n+2}=\frac{1}{n+2}\sum_{k=0}^n\left[(k+1)(-1)^{n-k}C_{n+2}^{k+1}+(-1)^{n-k+1}C_{n+2}^{k+1}\right]

\displaystyle =\frac{1}{n+2}\left(\sum_{k=0}^n(-1)^{n-k}(n+2)C_{n+1}^k+\sum_{i=1}^{n+1}(-1)^{n+2-i}C_{n+2}^i\right)=\dfrac{n+1+(-1)^{n+1}}{n+2}. \Box

Ví dụ 3. Cho số nguyên dương n và các số nguyên x_0 > x_1 > \ldots > x_n. Chứng minh rằng một trong các số |F(x_0)|, |F(x_1)|, |F(x_2)|, \ldots, |F(x_n)| lớn hơn hoặc bằng \displaystyle \frac{n!}{2^n}. Trong đó

F(x) = x^n + a_1x^{n-1} + \cdots+ a_n

là một đa thức với hệ số thực.

Lời giải. Giả sử \displaystyle |F(x_i)|<\dfrac{n!}{2^n},\quad \forall i=\overline{0,n}. Áp dụng công thức nội suy Lagrange cho P với n+1 nút x_0, x_1, \cdots, x_n ta có

\displaystyle x^n + a_1x^{n-1} + \cdots+ a_n\equiv \sum_{k=0}^nF(x_k)\prod_{j\not =k}\frac{x-x_j}{x_k-x_j}, để ý đến hệ số của x^n trong hai vế ta có  \displaystyle 1=\left|\sum_{k=0}^n\prod_{j\not =k}\frac{F(x_k)}{x_k-x_j}\right|\leq \sum_{k=0}^n\prod_{j\not =k}\frac{|F(x_k)|}{|x_k-x_j|}< \displaystyle \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|x_k-x_j|}\leq \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|k-j|}=1, không thể xảy ra điều này. \Box

Ví dụ 4. Chứng minh rằng với mỗi số thực a và với mỗi số nguyên dương n ta có

\displaystyle \sum_{k = 0}^n( - 1)^k\binom{n}{k}(a - k)^n = n!.

Lời giải. Vế trái là đa thức của a nên chỉ cần chứng minh đẳng thức khi a là số nguyên. Sau đây ta chứng minh đẳng thức khi a= 0 và n\geq 3, hay chứng minh

\displaystyle \sum_{k = 0}^n( - 1)^{n + k}\binom{n}{k}k^n = n!. Theo công thức nội suy Lagrange với các nút 1, 2, \ldots, n ta có \displaystyle x^n - (x - 1)(x - 2)\cdots (x - n) \equiv \sum_{k = 1}^nk^n\cdot\prod_{i\not = k}\dfrac{x - i}{k - i},\quad\forall x\in\mathbb{R}. Nói riêng, khi x = 0 ta có \displaystyle ( - 1)^{n + 1}\cdot n! = \sum_{k = 1}^nk^n\cdot \dfrac{1}{k}\cdot \dfrac{( - 1)^{n - 1}\cdot n!}{(k - 1)!\cdot (n - k)!\cdot ( - 1)^{n - k}}, từ đây thu được điều cần chứng minh. \Box.

Continue reading “Lagrange interpolating polynomial” →

Polynomials with integer coefficients


Đây là bài thứ ba về đa thức của tôi, các bạn học sinh nên xem lại hai bài trước để học cho dễ dàng hơn. Như các bài trước, các bạn học sinh tự hoàn thiện các lời giải một cách chi tiết.

[1] https://nttuan.org/2023/06/30/poly01/

[2] https://nttuan.org/2023/08/11/poly02/

Mục đích của bài này là giới thiệu một số kết quả cơ bản về các đa thức với hệ số nguyên, chẳng hạn như định lí nghiệm hữu tỷ và tiêu chuẩn bất khả quy của Eisenstein.

Định lí 1 (Định lí nghiệm hữu tỷ). Cho số nguyên dương n và đa thức

P(x)=a_n x^n+a_{n-1} x^{n-1}+\ldots+a_1 x+a_0

có bậc bằng n với hệ số nguyên. Khi đó nếu r / s là một nghiệm hữu tỷ khác không của P(x) thỏa mãn (r, s)=1, thì r \mid a_0 and s \mid a_n.

Chứng minh. Từ giả thiết ta có a_n r^n+a_{n-1} r^{n-1} s+\cdots+a_1 r s^{n-1}+a_0 s^n=0,
suy ra r \mid a_0 s^n và s \mid a_n r^n. Nhưng r và s nguyên tố cùng nhau, nên r \mid a_0 và s \mid a_n. \Box

Theo định lí này, khi P có hệ số cao nhất bằng 1 thì mọi nghiệm hữu tỷ của P đều là số nguyên. Với một đa thức khác hằng với hệ số nguyên, từ định lí ta cũng thấy muốn tìm nghiệm hữu tỷ của đa thức ta chỉ cần tìm trong một tập hợp hữu hạn.

Ví dụ 1. Giả sử ta muốn tìm tất cả các nghiệm hữu tỷ của đa thức P(x)=x^3-5x^2+x+10. Theo định lí, nghiệm hữu tỷ của P phải là nghiệm nguyên và nó bằng 0 hoặc là ước của 10. Suy ra nghiệm hữu tỷ của P thuộc tập hợp \{0,\pm 1,\pm 2,\pm 5,\pm 10\}. Kiểm tra trực tiếp ta thấy nghiệm hữu tỷ của đa thức là 2.

Định nghĩa 1. Một đa thức khác không với hệ số nguyên được gọi là nguyên bản nếu các hệ số của nó chỉ có ước dương chung là 1.

Định lí 2 (Bổ đề Gauss). Tích của hai đa thức nguyên bản là một đa thức nguyên bản.
Chứng minh. Giả sử f(x)=g(x) h(x) là tích của hai đa thức nguyên bản và p là một số nguyên tố chia hết mọi hệ số của f. Viết g(x)=\sum a_kx^k và h(x)=\sum b_mx^m. Do f và g là nguyên bản nên ta có thể chọn các chỉ số i và j lớn nhất để p\nmid a_i và p\nmid b_j. Khi đó hệ số của x^{i+j} trong f bằng a_ib_j, số này không chia hết cho p, vô lý. \Box

Hệ quả. Cho f(x) là một đa thức khác hằng với hệ số nguyên sao cho f(x)=g(x)h(x), ở đây g và h là các đa thức khác hằng với hệ số hữu tỷ. Khi đó f là tích của hai đa thức với hệ số nguyên có bậc bằng bậc của g và h.
Chứng minh. Từ giả thiết ta có thể viết \displaystyle f(x)=\frac{m}{n}g_1(x)h_1(x), trong đó m và n là hai số nguyên dương nguyên tố cùng nhau, và g_1,h_1 là hai đa thức nguyên bản có bậc lần lượt bằng bậc của g_1, h_1. Nếu a là một hệ số của g_1h_1 thì n \mid m a do f có hệ số nguyên, suy ra n \mid a. Như vậy n là số nguyên dương chia hết mọi hệ số của đa thức g_1h_1, là một đa thức nguyên bản theo bổ đề Gauss, suy ra n=1. Khi đó f=(m g_1)(h_1), đây là phân tích ta cần. \Box
Bằng quy nạp ta dễ dàng mở rộng kết quả trên cho nhiều hơn hai thừa số.

Định lí 3 (Tiêu chuẩn Eisenstein). Cho số nguyên dương n và đa thức f(x)=a_0+a_1x+\cdots+a_nx^n có bậc n với hệ số nguyên. Giả sử có số nguyên tố p sao cho a_n không chia hết cho p, các hệ số a_0,a_1,\ldots,a_{n-1} chia hết cho p và a_0 không chia hết cho p^2. Khi đó f là đa thức bất khả quy trên \mathbb{Q}.

Chứng minh. Giả sử f không bất khả quy trên \mathbb{Q}. Khi đó theo hệ quả trên, tồn tại các đa thức khác hằng với hệ số nguyên g và h sao cho f=gh. Viết g(x)=b_0+b_1x+\cdots+b_kx^k và h(x)=c_0+c_1x+\cdots+c_mx^m, trong đó k, m là các số nguyên dương và b_kc_m\not=0. Vì b_0c_0=a_0 chia hết cho p nhưng không chia hết cho p^2 nên p\mid b_0 hoặc p\mid c_0 và không xảy ra cả hai. Giả sử mà không làm mất tính tổng quát rằng p\mid b_0 và p\nmid c_0.

Nếu b_0,b_1,\ldots,b_u (u<k) chia hết cho p thì bằng cách để ý đến hệ số của x^{u+1} trong hai vế của f=gh ta có b_{u+1} cũng chia hết cho p. Vậy bằng quy nạp theo l, ta có p\mid b_l với mỗi l=0,1,\ldots,k. Suy ra a_n=b_kc_m chia hết cho p, vô lý. \Box

Hệ quả. Với mỗi số nguyên tố p, đa thức \Phi_p(x)=1+x+\cdots+x^{p-1} bất khả quy trên \mathbb{Q}.

Chứng minh. Xét một số nguyên tố p. Ta có

\displaystyle \Phi_p(x+1)=\frac{(x+1)^p-1}{x}=x^{p-1}+C_p^1x^{p-2}+C_p^2x^{p-3}+\cdots+p, và khi 1 \leq i \leq p-1 thì p chia hết C_p^i. Suy ra theo tiêu chuẩn Eisenstein, đa thức \Phi_p(x+1) bất khả quy trên \mathbb{Q}, do đó \Phi_p(x) bất khả quy trên \mathbb{Q}. \Box

Continue reading “Polynomials with integer coefficients” →

Z – K[x]


Các bạn học sinh chắc rất quen thuộc với cuốn từ điển ANH – VIỆT đúng không? Hôm nay tôi sẽ giới thiệu vài trang trong cuốn từ điển SỐ NGUYÊN – ĐA THỨC. Để theo bài cho dễ dàng các bạn nên đọc lướt qua các bài sau:

[1] https://nttuan.org/2023/06/30/poly01/

[2] https://nttuan.org/2023/07/14/divisibility/

[3] https://nttuan.org/2023/08/04/prime/

Mục đích của bài này là giới thiệu một số kết quả về đa thức tương tự với các kết quả trong số học sơ cấp (xem [2] và [3]), chẳng hạn như thuật toán chia, thuật toán Euclid, và định lí cơ bản của số học. Bởi vì chúng thực sự rất tương tự nên một số chứng minh sẽ bị bỏ qua, hoặc viết vắn tắt. Các em học sinh nên viết lại cẩn thận tất cả các chứng minh để hiểu thêm về đa thức.

Trong bài K là \mathbb{C},\mathbb{R},\mathbb{Q}, hay \mathbb{F}_p.

Định lí 1 (Thuật toán chia). Cho f và g là các phần tử của K[x] với g\neq 0. Khi đó tồn tại duy nhất cặp phần tử (q,r) của K[x] thỏa mãn f=q g+r, và \deg (r)<\deg(g) hoặc r=0.

Chứng minh. Khẳng định là đúng một cách hiển nhiên nếu f=0 hoặc bậc của f bé hơn bậc của g. Bây giờ ta xét trường hợp còn lại và chứng minh nó bằng quy nạp theo bậc của f.

Nếu bậc của f bằng 0 thì bậc của g bằng 0 và khẳng định là đúng. Giả sử khẳng định đúng với mọi đa thức f có bậc bé hơn m. Xét một đa thức f có bậc m và một đa thức g khác không có bậc n\leq m. Viết f(x)=a_m x^m+\ldots+a_1 x+a_0 và g(x)=b_n x^n+\ldots+b_0.

Xét đa thức f_1(x)=f(x)-a_m b_n^{-1} x^{m-n} g(x). Ta có f_1 có bậc bé hơn m hoặc f_1=0 nên theo giả thiết quy nạp, ta có thể viết f_1=q_1 g+r, trong đó bậc của r bé hơn n hoặc r=0. Từ đây ta có f(x)=\left(q_1(x)+a_m b_n^{-1} x^{m-n}\right) g(x)+r(x). Bây giờ ta đi chứng minh phần còn lại, thương và dư là duy nhất. Giả sử f=q_1 g+r_1 và f=q_2 g+r_2. Khi đó \left(q_1-q_2\right) g=r_2-r_1. Nếu q_2-q_1 \neq 0 thì bậc của \left(q_2-q_1)\right) g không bé hơn bậc của g, trong khi bậc của r_2-r_1 bé hơn bậc của g, vô lý. Vậy q_1=q_2, và đương nhiên r_1=r_2. \Box

Định nghĩa 1. Cho hai đa thức không đồng thời bằng không f và g với hệ số trong K. Một đa thức monic d với hệ số trong K được gọi là ước chung lớn nhất của f và g nếu

(1) d là một ước của f và g, và

(2) mỗi ước của f và g cũng là một ước của d.

Ước chung lớn nhất của f và g được ký hiệu bởi (f, g). Nếu (f, g)=1 thì ta nói f và g nguyên tố cùng nhau.

Ước chung lớn nhất nếu có sẽ là duy nhất. Thật vậy, giả sử d và d_1 cùng là ước chung lớn nhất của f và g. Khi đó d \mid d_1 và d_1 \mid d, suy ra d=a d_1 và d_1=b d, do đó d=a b d. Từ đây ta có ab=1, suy ra a và b đều có bậc không. Do đó d_1 bằng d nhân với một đa thức hằng, nhưng chúng cùng monic nên d=d_1. Định lí sau chứng tỏ ước chung lớn nhất tồn tại.

Định lí 2. Với các đa thức không đồng thời bằng không f, g \in K[x], ước chung lớn nhất tồn tại và có thể biểu diễn dưới dạng (f, g)=a f+b g, với a,b \in K[x].

Chứng minh. Xét tập hợp I=\{a f+b g \mid a, b \in K[x]\}. Tập hợp I chứa ít nhất một đa thức khác không nên tồn tại đa thức monic d thuộc I mà có bậc nhỏ nhất. Dễ chứng minh được d=(f, g). \Box

Thuật toán Euclid. Cho f, g \in K[x] là hai đa thức khác không. Dùng thuật toán chia ta có f=q g+r, trong đó \deg(r)<\deg(g) hoặc r=0. Nếu r=0 thì g chia hết f, do đó (f, g)=c g với c\in K. Nếu không, ta có tập các ước chung của f và g bằng tập các ước chung của g và r, do đó (f,g)=(g,r). Quy trình này làm giảm bậc của đa thức nên nó phải kết thức sau hữu hạn bước, lúc đó ta tìm được (f,g). Tương tự như với số nguyên, dùng thuật toán này ta có thể tìm được các đa thức a và b sao cho (f, g)=a f+b g.

Định lí 3. Cho f, g,h \in K[x] với (h, f)=1 và h\mid fg. Khi đó h\mid g.

Chứng minh. Bạn đọc tự chứng minh xem như bài tập. \Box

Định nghĩa 2. Một đa thức khác hằng với hệ số trong K được gọi là bất khả quy trên K nếu nó không thể phân tích trong K[x] thành tích của hai đa thức có bậc nhỏ hơn. Nó được gọi là khả quy trên K nếu có phân tích như vậy.

Ví dụ. Đa thức x^2-x+1 bất khả quy trên \mathbb{R} nhưng khả quy trên \mathbb{C}.

Tất cả những đa thức bậc 1 là bất khả quy trên K. Mỗi đa thức có bậc lớn hơn 1 có nghiệm trong K sẽ khả quy trên K. Ngược lại không đúng, một đa thức khả quy vẫn có thể không có nghiệm trong K. Tuy nhiên, với các đa thức bậc 2 hay 3 ta có kết quả sau:

Định lí 4. Một đa thức có bậc 2 hay 3 bất khả quy trên K khi và chỉ khi nó không có nghiệm trong K.

Tương tự như với số nguyên ta có các định lí sau. Bạn đọc tự chứng minh chúng xem như bài tập.

Định lí 5. Đa thức khác hằng p \in K[x] bất khả quy trên K khi và chỉ khi với mỗi f,g \in K[x], p\mid fg kéo theo p \mid f hoặc p \mid g.

Định lí 6. Mỗi đa thức khác hằng với hệ số trong K có thể viết như là một phần tử của K nhân với tích của các đa thức monic bất khả quy trên K. Nếu không kể đến thứ tự của các nhân tử thì biểu diễn này là duy nhất.

Continue reading “Z – K[x]” →