Nội suy và xấp xỉ

Một đa thức bậc n có đúng n+1 hệ số tự do, và việc cố định n+1 giá trị điểm dùng hết đúng bấy nhiêu bậc tự do — không hơn không kém — nên chỉ đủ chỗ cho một nghiệm và không đủ chỗ cho hai nghiệm khác nhau.

Bước 1 (tồn tại). Cách xây dựng Lagrange $P(x) = \sum_{i=0}^{n} y_i L_i(x)$ với $L_i(x) = \prod_{j\ne i} \dfrac{x-x_j}{x_i-x_j}$ đã thỏa $P(x_k)=y_k$ với mọi $k$, vì $L_i(x_k)$ bằng $1$ khi $i=k$ và $0$ khi khác, nên tổng thu gọn thành một số hạng duy nhất $y_k \cdot 1 = y_k$. Vậy tồn tại ít nhất một $P$ hợp lệ, và mỗi $L_i$ có bậc đúng bằng $n$ (tích của $n$ thừa số tuyến tính), nên $P$ có bậc không quá $n$.

Bước 2 (giả sử có hai nghiệm). Giả sử $Q$ là bất kỳ đa thức nào khác có bậc không quá $n$ với $Q(x_i)=y_i$ với mọi $i$. Xét hiệu $D(x) = P(x) - Q(x)$. Vì cả $P$ và $Q$ đều có bậc không quá $n$, nên $D$ cũng vậy.

Bước 3 (đếm nghiệm của hiệu). Với mỗi nút $x_i$, $D(x_i) = P(x_i)-Q(x_i) = y_i - y_i = 0$. Vì có $n+1$ nút phân biệt $x_0, x_1, \dots, x_n$, $D$ có ít nhất $n+1$ nghiệm phân biệt.

Bước 4 (buộc D đồng nhất bằng 0). Một đa thức khác không có bậc không quá $n$ có thể có nhiều nhất $n$ nghiệm (mỗi nghiệm góp một thừa số tuyến tính, và một đa thức bậc $n$ không thể chứa nhiều hơn $n$ thừa số như vậy). Vì $D$ có $n+1$ nghiệm, nhiều hơn bậc của nó cho phép trừ khi $D$ là đa thức không, ta kết luận $D(x)\equiv0$, tức $Q=P$. Vậy đa thức nội suy tìm được ở Bước 1 là duy nhất.

Đa thức nội suy khớp chính xác với f tại các nút nhưng không biết gì về f ở giữa, nên sai số còn lại phải triệt tiêu tại mọi nút — đúng là điều số hạng tích buộc phải xảy ra — được nhân với một đạo hàm còn lại đo mức độ cong của f vượt quá những gì một đa thức bậc n có thể nắm bắt.

Bước 1 (một hàm phụ khéo léo). Cố định một điểm $x$ không phải là một trong các nút (nếu là nút, sai số tầm thường bằng $0$). Đặt $w(t) = \prod_{i=0}^{n} (t - x_i)$ và định nghĩa hằng số $c = \dfrac{f(x)-P(x)}{w(x)}$ (xác định tốt vì $w(x)\ne0$). Định nghĩa hàm phụ $g(t) = f(t) - P(t) - c\, w(t)$.

Bước 2 (đếm nghiệm của g). Tại mỗi nút $x_i$, cả $f(x_i)-P(x_i)=0$ (theo tính chất nội suy) và $w(x_i)=0$ (theo định nghĩa của $w$), nên $g(x_i)=0$ với tất cả $n+1$ nút. Ngoài ra, theo cách chọn $c$, $g(x) = f(x)-P(x) - c\,w(x) = f(x)-P(x) - [f(x)-P(x)] = 0$. Vậy $g$ có $n+2$ nghiệm phân biệt: $n+1$ nút cộng thêm chính $x$.

Bước 3 (áp dụng định lý Rolle nhiều lần). Giữa mỗi cặp nghiệm liên tiếp của $g$ (có $n+1$ khoảng như vậy giữa $n+2$ nghiệm), định lý Rolle cho một điểm nơi $g'$ triệt tiêu, nên $g'$ có ít nhất $n+1$ nghiệm. Lặp lại lập luận này trên $g', g'', \dots$ mất đi một nghiệm mỗi lần lấy đạo hàm, nên sau $n+1$ lần áp dụng, $g^{(n+1)}$ có ít nhất một nghiệm $\xi$ trong khoảng.

Bước 4 (lấy đạo hàm và giải sai số). Vì $P$ có bậc không quá $n$, đạo hàm cấp $(n+1)$ của nó là $0$; và $w$ là đa thức monic bậc $n+1$, nên $w^{(n+1)}(t) = (n+1)!$ với mọi $t$. Lấy đạo hàm $g$ cho $g^{(n+1)}(t) = f^{(n+1)}(t) - 0 - c\,(n+1)!$, và đặt $g^{(n+1)}(\xi)=0$ cho $c = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}$. Nhớ lại $c=\dfrac{f(x)-P(x)}{w(x)}$ và giải sai số cho đúng $f(x) - P(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n} (x - x_i)$.

Một đa thức bậc cao duy nhất đi qua nhiều điểm có xu hướng lượn sóng, nhưng khâu nhiều mảnh bậc ba nhẹ nhàng lại với nhau và chỉ yêu cầu chúng khớp trơn tru tại các mối nối cho vừa đủ tự do để khớp dữ liệu mà không có dao động dữ dội nào, và các điều kiện biên tự nhiên cung cấp đúng hai phương trình bổ sung cần thiết để làm cho toàn bộ hệ giải được.

Bước 1 (ẩn số: đạo hàm cấp hai tại các nút). Đặt $M_i = S''(x_i)$ với $i=0,\dots,n$. Các điều kiện biên tự nhiên cố định ngay $M_0=0$ và $M_n=0$, còn lại $n-1$ ẩn số $M_1,\dots,M_{n-1}$ cần xác định.

Bước 2 (dựng lại mỗi mảnh bậc ba từ các giá trị M). Trên $[x_i,x_{i+1}]$, vì $S$ là bậc ba, $S''$ là tuyến tính, nên nó phải là đường thẳng qua $(x_i,M_i)$ và $(x_{i+1},M_{i+1})$. Lấy tích phân hàm tuyến tính này hai lần và cố định hai hằng số tích phân bằng cách dùng $S(x_i)=y_i$ và $S(x_{i+1})=y_{i+1}$ xác định hoàn toàn $S$ trên mảnh đó, theo $M_i, M_{i+1}, y_i, y_{i+1}$ và khoảng cách $h_i=x_{i+1}-x_i$. Vậy khi mọi $M_i$ đã biết, $S$ hoàn toàn được xác định.

Bước 3 (khớp hệ số góc cho một hệ tuyến tính). Theo cách xây dựng, $S$ và $S''$ đã liên tục qua mỗi nút. Yêu cầu đạo hàm cấp một $S'$ cũng khớp từ hai phía tại mỗi nút trong $x_i$ ($i=1,\dots,n-1$) tạo ra một phương trình tuyến tính cho mỗi nút trong liên hệ ba ẩn liên tiếp: $h_{i-1} M_{i-1} + 2(h_{i-1}+h_i) M_i + h_i M_{i+1} = 6\left(\dfrac{y_{i+1}-y_i}{h_i} - \dfrac{y_i-y_{i-1}}{h_{i-1}}\right)$. Điều này cho $n-1$ phương trình tuyến tính trong $n-1$ ẩn $M_1,\dots,M_{n-1}$ (dùng $M_0=M_n=0$).

Bước 4 (hệ có nghiệm duy nhất). Ma trận hệ số của hệ này là ba đường chéo với các mục trên đường chéo $2(h_{i-1}+h_i)$ và các mục ngoài đường chéo $h_{i-1}$ và $h_i$; vì $2(h_{i-1}+h_i) > h_{i-1}+h_i$ (do mọi khoảng cách $h_i>0$), ma trận chiếm ưu thế đường chéo chặt, và một ma trận chiếm ưu thế đường chéo chặt luôn khả nghịch. Vậy hệ tuyến tính cho $M_1,\dots,M_{n-1}$ có đúng một nghiệm, và theo Bước 2 điều này xác định đúng một spline $S$, chứng minh cả sự tồn tại lẫn duy nhất.