Đa thức nội suy Newton và Hermite

Đăng trong 18 Tháng Năm 2015 bởi TTC

Bài toán là như sau: cho trước các số thực hoặc phức \alpha_1,\ldots, \alpha_N phân biệt và p_1,\ldots,p_N không nhất thiết phân biệt. Tìm một đa thức f bậc nhỏ nhất có thể sao cho f(\alpha_i)=p_i với mọi 1\leq i\leq N.

Đa thức nội suy Newton sẽ giải quyết bài toán này, nhưng trước tiên cần định nghĩa một cái gọi là sai phân chia.

Giả sử f là một hàm (một biến) và x_0, x_1 là các điểm nào đó.

1) Định nghĩa \Delta^0f[x] = f(x), \Delta^1f[x_0,x_1] = \dfrac{f(x_0)-f(x_1)}{x_0-x_1}. Định nghĩa quy nạp cho \Delta^jf[x_0,x_1,\ldots,x_j] = \dfrac{\Delta^{j-1}f[x_0,x_1,\ldots,x_{j-1}]-\Delta^{j-1}f[x_1,x_2,\ldots,x_j]}{x_0-x_j}.

Sai phân chia không phụ thuộc vào thứ tự của các điểm lấy sai phân. Mình sưu tầm được vài file khá hay về món sai phân chia này: 2010 Newton Polynomials De Boor, divided differences Kahan, Fateman 1999, Symbolic Computation of Divided Differences

2) Công thức nội suy Newton (có lẽ chính xác hơn, phải là công thức sai phân chia Newton)

f(x) = \Delta^0f[x_0] + \Delta^1f[x_0,x_1](x-x_0) + \ldots +\Delta^{n-1}f[x_0,x_1,\ldots,x_{n-1}](x-x_0)(x-x_1)\cdots (x-x_{n-2})+\Delta^nf[x,x_0,x_1,\ldots,x_{n-1}](x-x_0)\cdots (x-x_{n-1}).

3) Nội suy Hermite.

Trong bài toán nội suy trên, không có sự xuất hiện của đạo hàm tại \alpha_j.  Đa thức nội suy Hermite sẽ giải quyết bài toán với đạo hàm. Thật ra ý tưởng khá đơn giản, đó là cho các điểm lấy sai phân gần sát lại nhau tới trùng nhau.

Ta cần kết quả sau: \Delta^jf[\underbrace{x,\ldots,x}_{j+1}] = \dfrac{f^{(j)}(x)}{j!}, và ta tiến hành nội suy như trong trường hợp đa thức nội suy Newton.

Bài này đã được đăng trong analyse numérique, interpolation và được gắn thẻ , , , . Đánh dấu đường dẫn tĩnh.

Bình luận về bài viết này