Đa thức nội suy Newton


Hôm nay chúng ta sẽ học về công thức nội suy cho đa thức.

Giả sử chúng ta có đa thức sau đây $$P(x) = 2x^2 - 3x + 3$$

Cho $x$ một vài giá trị, chúng ta tính được giá trị của $P(x)$ như sau $$P(1) = 2 - 3 + 3 = 2,$$ $$P(2) = 8 - 6 + 3 = 5,$$ $$P(3) = 18 - 9 + 3 = 12, \dots$$

Câu hỏi đặt ra là, nếu ngược lại, chúng ta biết được $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12,$$ liệu chúng ta có thể tìm lại được đa thức $P(x)$ hay không?

Câu trả lời là được. Công thức đa thức nội suy giúp cho chúng ta tìm lại được đa thức $P(x)$. Hôm nay chúng ta sẽ học về công thức nội suy Newton, kỳ sau chúng ta sẽ học về công thức nội suy Lagrange.


Trước khi đi vào chi tiết về công thức nội suy, chúng ta có nhận xét như sau.


Nhận xét 1. Nếu chúng ta không hạn chế về bậc của đa thức $P(x)$ thì sẽ tồn tại vô số các đa thức $P(x)$ thõa mãn điều kiện $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$

Vì sao vậy? Đó là vì nếu chúng ta tìm ra được một đa thức $P(x)$ thoã mãn điều kiện này thì chúng ta có thể tạo ra vô số các đa thức $G(x)$ khác cũng thõa mãn điều kiện trên bằng cách cho
$$G(x) = P(x) + (x-1)(x-2)(x-3)H(x),$$ và chúng ta có $$G(1) = P(1), ~~G(2) = P(2), ~~G(3) = P(3).$$


Nhận xét 2. Nếu chúng ta hạn chế về bậc của đa thức và yêu cầu rằng đa thức $P(x)$ phải có bậc bé thua hoặc bằng $2$ thì sẽ tồn tại duy nhất một đa thức $P(x)$ có bậc bé thua hoặc bằng $2$ thõa mãn điều kiện $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$

Lý do là vì nếu $G(x)$ là một đa thức khác có bậc bé thua hoặc bằng $2$ thõa mãn điều kiện $$G(1) = 2, ~~G(2) = 5, ~~G(3) = 12,$$ thì chúng ta lấy $$D(x) = G(x) - P(x),$$ $D(x)$ là một đa thức có bậc bé thua hoặc bằng $2$ thõa mãn $$D(1) = D(2) = D(3) = 0,$$ điều này chứng tỏ $D(x)$ có đến $3$ nghiệm, trong khi bậc của nó thì bé thua hoặc hằng $2$, vậy $D(x)$ phải là đa thức hằng số $0$. Do đó $G(x) = P(x)$, điều này chứng minh là chỉ tồn tại duy nhất một đa thức $P(x)$.


Chúng ta phát biểu định lý tổng quát như sau.
Định lý. Nếu $x_1, x_2, \dots, x_n, x_{n+1}$ là $n+1$ số thực khác nhau. Và $y_1$, $y_2$, $\dots$, $y_n$, $y_{n+1}$ là $n+1$ số thực bất kỳ. Thì sẽ tồn tại duy nhất một đa thức $P(x)$ có bậc bé thua hoặc bằng $n$ thõa mãn điều kiện $$P(x_1) = y_1, ~~P(x_2) = y_2, \dots, ~~P(x_n) = y_n, ~~P(x_{n+1})=y_{n+1}.$$

Định lý trên nói rằng một đa thức có bậc bé thua hoặc bằng $n$ sẽ được xác định một cách duy nhất bằng $n+1$ giá trị của nó.



Bây giờ chúng ta bắt đầu tìm hiểu về công thức nội suy Newton. Chúng ta sẽ tìm cách xác dịnh đa thức $P(x)$ thõa mãn điều kiện $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$

Ở một bài viết trước, tôi có chia xẻ một kinh nghiệm của mình khi làm toán, đó là khi đối diện với một bài toán mà chúng ta không biết phải làm như thế nào, thì việc đầu tiên chúng ta có thể làm là xem xét các trường hợp đặc biệt của bài toán. Ở đây chúng ta sẽ giải quyết bài toán từng bước, từ đơn giản đến phức tạp.

Đầu tiên, nếu chúng ta chỉ có một điều kiện là $P(1) = 2$ thì chúng ta có xác định được đa thức $P(x)$ hay không? Hiển nhiên, đa thức đơn giản nhất thõa mãn điều kiện là đa thức hằng số $A(x) = 2$.

Tiếp đến, nếu chúng ta muốn tìm đa thức $B(x)$ để cho $B(1) = 2$ và $B(2) = 5$, thì chúng ta có thể xem xét đa thức có dạng $$B(x) = A(x) + \alpha (x-1) = 2 + \alpha (x-1)$$

Dạng ở trên rất là thuận lợi bởi vì chúng ta có ngay được là $B(1) = A(1) = 2$. Còn $B(2) = 2 + \alpha$, vậy để $B(2) = 5$ chúng ta sẽ chọn $\alpha = 3$, và cuối cùng chúng ta có $$B(x) = 2 + 3(x-1)$$

Bây giờ, tương tự như trên, muốn tìm đa thức $P(x)$ để cho $P(1) = 2$, $P(2) = 5$, và $P(3) = 12$, chúng ta xem xét đa thức có dạng $$P(x) = B(x) + \alpha (x-1)(x-2) = 2 + 3(x-1) + \alpha (x-1)(x-2)$$

Bởi vì $P(x) = B(x) + \alpha (x-1)(x-2)$, chúng ta có ngay được rằng $$P(1) = B(1) = 2, ~~P(2) = B(2) = 5. $$ Còn $P(3) = 8 + 2 \alpha$. Để $P(3)= 12$ thì $\alpha = 2$, và chúng ta có $$P(x) = 2 + 3(x-1) + 2 (x-1)(x-2)$$

Tóm lại chúng ta đã tìm ra đa thức thõa mãn điều kiện $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$ Đó là $$P(x) = 2 + 3(x-1) + 2 (x-1)(x-2)$$
Khai triển ra, chúng ta có được chính đa thức ban đầu ở trên, đó là $$P(x) = 2 + 3(x-1) + 2 (x-1)(x-2) = 2x^2 - 3x + 3$$




Bây giờ, chúng ta sẽ xem xét bài toán tổng quát. Nếu $x_1$, $x_2$, $\dots$, $x_n$, $x_{n+1}$ là $n+1$ số thực khác nhau, và $y_1$, $y_2$, $\dots$, $y_n$, $y_{n+1}$ là $n+1$ số thực bất kỳ. Chúng ta sẽ tìm đa thức $P(x)$ có bậc bé thua hoặc bằng $n$ thõa mãn điều kiện $$P(x_1) = y_1, ~~P(x_2) = y_2, \dots, ~~P(x_n) = y_n, ~~P(x_{n+1})=y_{n+1}.$$

Theo như trường hợp đặc biệt mà chúng ta đã giải ở trên, thì đa thức $P(x)$ sẽ có dạng $$P(x) = \alpha_1 + \alpha_2 (x-x_1) + \alpha_3 (x-x_1)(x-x_2) + \dots + \alpha_{n+1} (x-x_1)(x-x_2)\dots(x-x_n)$$

Công thức này gọi là công thức nội suy Newton. Nếu chúng ta thay $x=x_1$ vào công thức nội suy Newton, thì chúng ta sẽ xác định được giá trị của hệ số $\alpha_1$. Tiếp đó, nếu chúng ta thay $x=x_2$ vào công thức nội suy thì chúng ta sẽ xác định được giá trị của hệ số $\alpha_2$. Tương tự như vậy, hệ số cuối cùng $\alpha_{n+1}$ sẽ được xác định nếu chúng ta thay $x=x_{n+1}$.



Chúng ta xem xét một vài ví dụ.

Ví dụ 1. Tìm đa thức $P(x)$ có bậc bé thua hoặc bằng $4$ sao cho $$P(1) = 1, ~~P(2) = 1, ~~P(3) = 2, ~~P(4) = 3, ~~P(5) = 5$$

Chúng ta dùng công thức nội suy Newton $$P(x) = \alpha_1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=1$ vào công thức trên, chúng ta có $P(1) = \alpha_1 = 1$, vậy $$P(x) = 1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=2$, chúng ta có $P(2) = 1 + \alpha_2 = 1$, do đó $\alpha_2 = 0$, vậy $$P(x) = 1 + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=3$, chúng ta có $P(3) = 1 + 2 \alpha_3 = 2$, do đó $\alpha_3 = \frac{1}{2}$, vậy $$P(x) = 1 + \frac{1}{2} (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=4$, chúng ta có $P(4) = 4 + 6 \alpha_4 = 3$, do đó $\alpha_4 = -\frac{1}{6}$, vậy $$P(x) = 1 + \frac{1}{2} (x-1)(x-2) -\frac{1}{6} (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=5$, chúng ta có $P(5) = 3 +  24 \alpha_5 = 5$, do đó $\alpha_5 = \frac{1}{12}$.  

Do đó đa thức cần tìm là $$P(x) = 1 + \frac{1}{2} (x-1)(x-2) - \frac{1}{6} (x-1)(x-2)(x-3) + \frac{1}{12} (x-1)(x-2)(x-3)(x-4).$$



Ví dụ 2. Tìm đa thức $P(x)$ có bậc bé thua hoặc bằng $4$ sao cho $$P(1) = 1, ~~P(2) = 4, ~~P(3) = 9, ~~P(4) = 16, ~~P(5) = 25$$

Chúng ta dùng công thức nội suy Newton $$P(x) = \alpha_1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=1$ vào công thức trên, chúng ta có $P(1) = \alpha_1 = 1$, vậy $$P(x) = 1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=2$, chúng ta có $P(2) = 1 + \alpha_2 = 4$, do đó $\alpha_2 = 3$, vậy $$P(x) = 1 + 3 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=3$, chúng ta có $P(3) = 7 + 2 \alpha_3 = 9$, do đó $\alpha_3 = 1$, vậy $$P(x) = 1 + 3 (x-1) + (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=4$, chúng ta có $P(4) = 16 + 6 \alpha_4 = 16$, do đó $\alpha_4 = 0$, vậy $$P(x) = 1 + 3 (x-1) + (x-1)(x-2) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$

Thay $x=5$, chúng ta có $P(5) = 25 +  24 \alpha_5 = 25$, do đó $\alpha_5 = 0$.

Do đó đa thức cần tìm là $$P(x) = 1 + 3(x-1) + (x-1)(x-2) = x^2$$



Từ hai ví dụ trên chúng ta thấy rằng đa thức $P(x)$ xác định bởi điều kiện $$P(x_1) = y_1, ~~P(x_2) = y_2, \dots, ~~P(x_n) = y_n, ~~P(x_{n+1})=y_{n+1},$$ có thể có bậc bằng $n$ (như ở ví dụ 1), nhưng cũng có thể có bậc bé thua $n$ (như ở ví dụ 2).



Chúng ta tạm dừng ở đây. Kỳ sau, chúng ta sẽ học về một công thức nội suy khác có tên là công thức nội suy Lagrange. Hẹn gặp lại các bạn.





Bài tập về nhà.

1. Tìm đa thức $P(x)$ có bậc bé thua hoặc bằng $4$ sao cho $$P(1) = 2, ~~P(2) = 4, ~~P(3) = 6, ~~P(4) = 8, ~~P(5) = 10$$


2. Dãy số Fibonacci được xác định như sau: $F_0=0$, $F_1=1$, $F_{n+1}=F_n+F_{n−1}$. Do đó $$F_0=0, ~F_1=1, ~F_2=1, ~F_3=2, ~F_4=3, ~F_5=5, ~F_6=8, \dots$$
Cho đa thức $P(x)$ thoã mãn điều kiện sau $$P(0) = 2011^{F_{2012}}, ~~P(1) = 2011^{F_{2011}}, ~~P(2) = 2011^{F_{2010}}, \dots $$ $$P(2010) = 2011^{F_{2}}, ~~P(2011) = 2011^{F_{1}}. $$
Chứng minh rằng đa thức $P(x)$ phải có bậc lớn hơn hoặc bằng $2011$.



3 nhận xét: