Bài giảng Phương pháp số - Bài 4: Nội suy bằng đa thức và làm khớp dữ liệu

BÀI 4

6

5

4

3

2

1

0

2

4

6

8

10

12

14

NỘI SUY BẰNG ĐA THỨC

VÀ LÀM KHỚP DỮ LIỆU

NỘI SUY BẰNG ĐA THỨC (1)

BÀI TOÁN NỘI SUY: Cho x₀, x₁, …, x_nlà n + 1 điểm phân biệt trên

trục số thực và f(x) là hàm nhận giá trị thực, xác định trên khoảng

I = [a, b] chứa các điểm này. Hãy xây dựng một đa thức p_n(x) có

bậc ≤ n mà tại các điểm x₀, x₁, …, x_n

p_n(x_i) = f(x_i) i = 0, …, n

SỰ TỒN TẠI ĐA THỨC NỘI SUY: (Đa thức nội suy Lagrange)

Cho hàm f(x) nhận giá trị thực và n + 1 điểm phân biệt

x₀, x₁, …, x_n, khi đó tồn tại đúng một đa thức bậc ≤ n nôi suy f(x)

tại x₀, x₁, …, x_nlà p_n(x) = a₀l₀(x) + a₁l₁(x) + … + a_nl_n(x) với

a_i= f(x_i) và

n

x  x_i

_i0x_k x_i

l_k(x) 

Π

ik

PHƢƠNG PHÁP SỐ - Bài 4

2

NỘI SUY BẰNG ĐA THỨC (2)

SỰ DUY NHẤT CỦA ĐA THỨC NỘI SUY

Bổ đề: Nếu z₁, …, z_nlà các nghiệm phân biệt của đa thức p(x) thì

p(x) = (x – z₁)(x – z₂) … (x – z_n) r(x)

với r(x) là một đa thức.

Hệ quả: Nếu p(x) và q(x) là hai đa thức bậc ≤ k có giá trị trùng

nhau ở k+1 điểm z₀, …, z_kphân biêt, thì p(x) ≡ q(x)

 có nhiều nhất một đa thức bậc ≤ n nội suy f(x) ở n + 1 điểm phân

biệt x₀, x₁, …, x_n

Mặt khác, từ sự tồn tại của đa thức nội suy Lagrange

 có ít nhất một đa thức bậc ≤ n nội suy f(x) ở n + 1 điểm phân biệt

x₀, x₁, …, x_n

 Kết luận: có đúng một đa thức bậc ≤ n nội suy f(x) ở n + 1 điểm

phân biệt x₀, x₁, …, x_n

PHƢƠNG PHÁP SỐ - Bài 4

3

NỘI SUY BẰNG ĐA THỨC (3)

Ví dụ 1: trường hợp n = 1, nghĩa là cho biết hàm f(x) và

hai điểm phân biệt x₀, x₁. Vậy ta có hai đa thức bậc nhất

x  x₁

x₀ x₁

x  x₀

x₁ x₀

l₀(x) 

l₁(x) 

 Trong ví dụ này, đa thức nội suy Lagrange là đa thức

nội suy tuyến tính (n = 1)

x  x₀

x₁ x₀

x  x₁

x₀ x₁

p_n(x)  f(x₀)l₀(x)  f(x₁)l₁(x)  f(x₀)

f(x₀)(x  x₁)  f(x₁)(x  x₀)

 f(x₁)

f(x₁)  f(x₀)

x₁ x₀



 f(x₀) 

(x  x₀)

x₀ x₁

Đây chính là PT đƣờng thẳng đi qua 2 điểm (x_0,y₀) và (x_1,y₁)

PHƢƠNG PHÁP SỐ - Bài 4

4

NỘI SUY BẰNG ĐA THỨC (4)

Ví dụ 2: Từ bảng các giá trị của tích phân sau, tính giá trị của đa thức

nội suy Lagrange K(3.5), biết K(1) = 1.5709, K(4) = 1.5727, và

K(6) = 1.5751

π/2

dx

Ta có

K(k) 

 _{[1 (sin k)}₂_sin₂_x]_1/2

0

(3.5 4)(3.56) 1.25

l₀(3.5) 

l₁(3.5) 

l₂(3.5) 



 0.08333

1.04167

 0.12500

(1 4)(16)

15

(3.51)(3.5 6) 6.25



(4 1)(4 6)

6

(3.51)(3.5 4) 1.25



(6 1)(6  4)

10

 K(3.5) ≈ (1.5709)(0.08333)+(1.5727)(1.04167)+(1.5751)((–0.12500)

= 1.57225

PHƢƠNG PHÁP SỐ - Bài 4

5

NỘI SUY BẰNG ĐA THỨC (5)

NHƯỢC ĐIỂM CỦA ĐA THỨC NỘI SUY Lagrange:

• Việc ƣớc lƣợng nó ở một điểm x cần ít nhất 2(n+1)

phép nhân/chia và (2n+1) phép cộng và trừ sau khi tất

cả các mẫu số của các đa thức nội suy Lagrange đã

đƣợc tính toán và chia vào trong các giá trị hàm tƣơng

ứng

• Việc dùng đa thức Lagrange dƣờng nhƣ là lãng phí, bởi

vì khi tính p_k(x) không dùng lại đƣợc các kết quả đã tính

ở p_k–1(x)

 Nên tìm đa thức nội suy dạng khác

PHƢƠNG PHÁP SỐ - Bài 4

6

ĐA THỨC NỘI SUY NEWTON (1)

Lập công thức

p_n(x) = A₀+ A₁(x – x₀) + A₂(x – x₀) (x – x₁) + …

+ A_n(x – x₀)(x – x₁) … (x – x_n–1)

= q_k(x) + (x – x₀)(x – x₁) … (x – x_k)r(x)

với q_k(x) = A₀+ A₁(x – x₀) + A₂(x – x₀) (x – x₁)

+ … + A_k(x – x₀)(x – x₁) … (x – x_k–1)

Nhận xét: p_n(x) = q_k(x) tại các điểm x₀, x₁, …, x_k,

nghĩa là q_k(x) nội suy f(x) tại x₀, …, x_k

PHƢƠNG PHÁP SỐ - Bài 4

7

ĐA THỨC NỘI SUY NEWTON (2)

Lập công thức: Xây dựng dãy đa thức có tính kế

thừa p₀(x),p₁(x), …

p_k(x) = p_k–1(x) + A_k(x – x₀)(x – x₁) … (x – x_k–1)

A_k= f[x₀, …, x_k] là hệ số của lũy thừa bậc cao nhất

x^kcủa p_k(x), chỉ phụ thuộc vào các giá trị của f(x) tại

các điểm, x₀, …, x_kđƣợc gọi là tỉ sai phân cấp k của

f(x) tại x₀, …, x_k

p_n(x) = f[x₀] + f[x₀, x₁](x – x₀) + f[x₀, x₁, x₂](x – x₀)(x – x₁)

+ … + f[x₀, x₁, … , x_n](x – x₀)(x – x₁) … (x – x_n–1)

PHƢƠNG PHÁP SỐ - Bài 4

8

ĐA THỨC NỘI SUY NEWTON (3)

Công thức tính tỉ sai phân

Với n = 1, công thức nội suy Newton sẽ là

p₁(x) = f[x₀] + f[x₀, x₁](x – x₀)

so sánh với công thức nội suy Lagrange

p₁(x) = f(x₀) + [f(x₁) – f(x₀)](x – x₀) / [x₁– x₀]

 f[x₀] = f(x₀)

f(x₁)  f(x₀) f[x₁]  f[x₀]

f[x₀, x₁] =



x₁ x₀

………….

f[x₁,...,x_k]f[x₀,...,x_k1]

x_k x₀

f[x₀, x₁, … , x_k] =

PHƢƠNG PHÁP SỐ - Bài 4

9

ĐA THỨC NỘI SUY NEWTON (3)

Bảng tỉ sai phân

f[, , ,]

f[, , , ,]

x_if[ ]=f( ) f[,]

f[, ,]

x₀f(x₀)

f[x₀, x₁]

x₁f(x₁)

x₂f(x₂)

f[x₀, x₁, x₂]

f[x₁, x₂, x₃]

f[x₁, x₂]

f[x₀, x₁, x₂, x₃]

f[x₁, x₂, x₃, x₄]

f[x₀, x₁, x₂, x₃, x₄]

f[x₂, x₃]

f[x₃, x₄]

x₃f(x₃)

x₄f(x₄)

f[x₂, x₃, x₄]

PHƢƠNG PHÁP SỐ - Bài 4

10

ĐA THỨC NỘI SUY NEWTON (4)

Ví dụ: Từ ví dụ 2 về đa thức nội suy Lagrange

x_iK[ ]=f( )

K[,]

K[, ,]

1.5709 1.5727

1 4

1.5727 1.5751

K(1,4) 

K(4,6) 

 0.0006

 0.0012

1 1.5709

0.0006

0.0012

4  6

4 1.5727

6 1.5751

0.00012

0.0006  0..0012

1 6

K(1,4,6) 

 0.00012

 p₂(x) = 1.5709 + 0.0006 (x – 1) + 0.00012 (x – 1) (x – 4)

thế x = 3.5 vào công thức nội suy Newton, ta nhận đƣợc

p₂(x) = 1.5709 + 0.0006 (2.5) + 0.00012 (2.5) (–0.5) = 1.57225

PHƢƠNG PHÁP SỐ - Bài 4

11

ĐA THỨC NỘI SUY NEWTON (5)

• Thuật toán tính các hệ số của đa thức nội suy Newton

Cho n + 1 điểm phân biệt x₀, x₁, …, x_n, và f(x₀), f(x₁), …, f(x_n)

tƣơng ứng, với f(x_i) đƣợc chứa trong vector d = (d_i), i =0, ..., n

Với k = 1, …, n, lặp công việc (tính d ở lần lặp k)

Với i = 0, …, n – k, lặp công việc:

d_i= (d_{i + 1}– d_i)/ (x_i+k– x_i)

Vậy f[x₀, … , x_k] = d₀, ở lần lặp thứ k

• Sai số của đa thức nội suy p_n(x) trên [a, b] chứa x₀,x₁, ,x_n:

x [a,b],ξ  ξ(x)(a,b) :

e_n(x)  f(x)  p_n(x)

f ^(n1)(ξ)

(n 1)!

n

^{ f[x ,..., x , x]}Π^{(x  x ) }

(x  x )



0

n

j

j0

PHƢƠNG PHÁP SỐ - Bài 4

12

ĐA THỨC NỘI SUY NEWTON (6)

Chƣơng trình:

double noiSuyNewton(vector<double> x,

vector<double> y, double x0) {

vector <double> d = y;

double tong = d[0], tich = 1;

for (unsigned k = 1; k <= d.size() – 1; k++) {

for (unsigned i = 0; i <= d.size() – k; i++)

d[i] = (d[i+1] – d[i])/(x[i+k] – x[i]);

tich *= (x0 – x[k – 1]);

tong += d[0] * tich;

}

return tong;

}

PHƢƠNG PHÁP SỐ - Bài 4

13

ĐA THỨC NỘI SUY NEWTON VỚI

MỐC CÁCH ĐỀU (1)

Giả sử f(x) đƣợc lập thành bảng đối với x_i= a + ih với các

giá trị f(x_i), i = 0, . . . , N đã biết, dùng phép đổi biến tuyến tính

x  x₀

s  s(x) 

 x  x(s) x₀ sh và f(x)  f(x₀ sh)  f_s

h

đƣa đa thức bậc n của x về đa thức bậc n của s theo

các tâm nguyên.

Định nghĩa các sai phân tiến

f

i  0







s

Δⁱf 

s

Δ(Δ^i1f_s)  Δ^i1f_s1 Δ^i1f_si  0

1

i!hⁱ

f[x_k, ..., x_ki]  Δⁱf_k i  0

PHƢƠNG PHÁP SỐ - Bài 4

14

ĐA THỨC NỘI SUY NEWTON VỚI

MỐC CÁCH ĐỀU (2)

Đa thức Newton bậc ≤ n nội suy f(x) tại x_k, . . . , x_k+ntrở thành

i1

n

1

p_n(x) 

Δⁱf_kΠ(x  x_kj), k  0,1, ...



_i0i!hⁱ

j0

Do (x – x_k+j) = x₀+ sh – [x₀+ (k + j) h] = (s – k – j) h nên ta có

công thức sai phân tiến

i1

n

p_n(x)  p_n(x₀ sh)  Δⁱf_kΠ^{s  k  j}



j0

j  1

i0

(s - k)(s- k - 1)

2

 f_k (s - k)f_k

Δ²f_k

(s - k)... (s - k - n  1)

 ... 

Δⁿf_k

n!

PHƢƠNG PHÁP SỐ - Bài 4

15

ĐA THỨC NỘI SUY NEWTON VỚI

MỐC CÁCH ĐỀU (3)

x_kf_k∆f_k∆²f_k∆³f_k∆⁴f_k

x₀f₀

△f₀

△²f₀

△²f₁

△²f₂

x₁f₁

x₂f₂

x₃f₃

x₄f₄

Bảng sai

phân tiến

△f₁

△f₂

△f₃

△³f₀

△³f₁

△⁴f₀

PHƢƠNG PHÁP SỐ - Bài 4

16

ĐA THỨC NỘI SUY NEWTON VỚI

MỐC CÁCH ĐỀU (4)

Công thức nội suy Newton tiến

Phép nội suy hàm f(x) tại x₀, . . . , x_nkhi k = 0, trở thành

f(s) f(x₀ sh) p_n(x₀ sh)

s (s-1)

 f₀ sf₀

Δ²f₀

2!

s(s-1)...(s- n  1)

 ...

Δⁿf₀

n!

Các hệ số ∆ⁱf₀ở công thức trên chỉ đơn thuần là hiệu số giữa

đầu vào phía dƣới bên trái và đầu vào phía trên bên trái.

PHƢƠNG PHÁP SỐ - Bài 4

17

ĐA THỨC NỘI SUY NEWTON VỚI

MỐC CÁCH ĐỀU (5)

2

3

4

x_kf_k∆ f_k∆ f_k

∆ f_k

Ví dụ:

-4

-2

0

-64

-8

0

Cho các giá trị của f(x) tại

các điểm cách đều như

bảng bên. Tính f(-3).

56

8

-48

0

Do x = - 3 ở đầu bảng giá

tri x_knên ta chọn x₀= -4.

48

0

 s = [-3 - ( -4 )]/2 = 0,5

f(-3) = -64 + 56.0,5

-48.0,5.(0,5-1)/2!

8

2

8

48

56

+ 48. 0,5.(0,5-1)(0,5-2)/3!

= -27

4

64

PHƢƠNG PHÁP SỐ - Bài 4

18

ĐA THỨC NỘI SUY NEWTON VỚI

MỐC CÁCH ĐỀU (6)

double noiSuyNewtonTien (vector <double> x,

vector <double> y, double x0) {

unsigned i, k, n = y.size();

vector<double> d = y;

double h = x[1] – x[0], s = (x0 – x[0]) / h, mauSo = 1. ;

double f = y[0], tich = s;

for (k = 1; k <= n – 1; k++) { // Tinh tong thu k

for (i = 0; i <= n – k; i++) d[i] = d[i+1] – d[i];// cac sf cap k

f += tich * d[0] * mauSo;

tich *= (s – k);

mauSo /= (k+1);

}

return f;

}

PHƢƠNG PHÁP SỐ - Bài 4

19

ĐA THỨC NỘI SUY NEWTON VỚI

MỐC CÁCH ĐỀU (7)

Công thức nội suy Newton lùi

Khi điểm cần tính nội suy x ở cuối bảng, ta lập đa thức nội suy

p_n(x) = A₀+ A₁(x – x_n) + A₂(x – x_n) (x – x_n-1) + …

+ A_n(x – x_n)(x – x_n-1) … (x – x₀)

Tƣơng tự nhƣ khi tính toán các hệ số A_icho công thức nội suy

ở đầu bảng, dẫn đến công thức

p_n(x) = f[x_n] + f[x_n-1, x_n](x – x_n) + f[x_n-2, x_n-1, x_n](x – x_n)(x – x_n-1)

+ … + f[x₀, x₁, … , x_n](x – x_n)(x – x_n-1) … (x – x₀)

Khi các mốc nội suy cách đều nhau một khoảng h, dùng phép

biến đổi tuyến tính

x  x_n

s  s(x)

 x  x(s) x_n sh và f(x) f(x_n sh) f_s

h

PHƢƠNG PHÁP SỐ - Bài 4

20