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.

—

Đ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$ .

Ví dụ 5. Cho $ABC$ là một tam giác với $BC=a,$ $CA=b$ và $AB=c.$ Chứng minh rằng với mỗi hai điểm $P,$ $Q$ trong mặt phẳng $(ABC)$ ta có $\displaystyle a.PA.QA+b.PB.QB+c.PC.QC\geq abc.$

Lời giải. Trong mặt phẳng phức $(ABC),$ giả sử

$A=x_1,B=x_2,C=x_3,P=p,Q=q.$ Theo công thức nội suy Lagrange với các nút $x_1,$ $x_2,$ và $x_3$ ta có

$\displaystyle (x-p)(x-q)\equiv \sum_{i=1}^3(x_i-p)(x_i-q)\prod_{j\not=i}\frac{x-x_j}{x_i-x_j},$ để ý đến hệ số của $x^2$ trong cả hai vế ta có $\displaystyle \frac{(x_1-p)(x_1-q)}{(x_1-x_2)(x_1-x_3)}+\frac{(x_2-p)(x_2-q)}{(x_2-x_3)(x_2-x_1)}+\frac{(x_3-p)(x_3-q)}{(x_3-x_1)(x_3-x_2)}=1,$ suy ra $\displaystyle 1\leq \frac{|x_1-p|.|x_1-q|}{|x_1-x_2|.|x_1-x_3|}+\frac{|x_2-p|.|x_2-q|}{|x_2-x_3|.|x_2-x_1|}+\frac{|x_3-p|.|x_3-q|}{|x_3-x_1|.|x_3-x_2|}.$ Nhưng $|x_2-x_1|=AB,\ldots$ và $|x_1-p|=AP,\ldots$ , do đó $\displaystyle 1\leq \frac{PA.QA}{AB.AC}+\frac{PB.QB}{BC.BA}+\frac{PC.QC}{CA.CB},$ và ta có điều cần chứng minh. $\Box$

Ví dụ 6. Cho đa thức $P(x)$ với hệ số thực sao cho với mỗi số nguyên dương $n$ , tồn tại số hữu tỷ $r$ để $P(r)=n$ . Chứng minh rằng $\deg P=1.$

Lời giải. Dễ thấy $P$ không thể là đa thức hằng, suy ra $d:= \deg P\ge 1.$ Với mỗi số nguyên dương $n$ , gọi $r_n$ là một số hữu tỷ sao cho $P(r_n) = n.$ Dùng công thức nội suy Lagrange cho $P$ với $d+1$ nút $r_1,$ $r_2,\cdots,$ $r_{d+1}$ ta được $P$ có hệ số hữu tỷ. Giả sử $d>1$ và gọi $t$ là một số nguyên dương sao cho $tP$ là một đa thức có hệ số nguyên với hệ số đầu $m.$ Với mỗi số nguyên dương $n$ , $tP(x) - tn$ là một đa thức với hệ số nguyên nhận $r_n$ là một nghiệm hữu tỷ, suy ra theo định lí nghiệm hữu tỷ thì $\displaystyle r_n\in \frac{1}{m}\mathbb{Z}.$

Vì $\displaystyle\left |\frac{P(x)}{x}\right |\to +\infty$ khi $|x|\to +\infty$ nên tồn tại số nguyên dương $N$ đủ lớn sao cho $\displaystyle\left |\frac{P(x)}{x}\right | > 2|m|$ với mọi $x$ thỏa mãn $|x|\ge N.$ Mặt khác, $\displaystyle\frac{1}{m}\mathbb{Z}\cap ( - N,N)$ có đúng $2|m|N - 1$ phần tử, suy ra trong $2|m|N$ số khác nhau $\displaystyle r_1,r_2,\ldots,r_{2|m|N}\in\frac{1}{m}\mathbb{Z},$ tồn tại số $r_k$ để $|r_k|\ge N.$ Khi đó $\displaystyle 2|m| < \left |\frac{P(r_k)}{r_k}\right | = \frac{k}{|r_k|}\le {2|m|N\over N} = 2|m|,$ không thể xảy ra điều này. $\Box$