Cơ sở dữ liệu - Hệ thức đệ qui

HỆ THỨC ĐỆ QUI 6/3/2015 1 ĐỊNH NGHĨA  Một hệ thức đệ qui tuyến tính cấp k là hệ thức có dạng: Trong đó: ak ≠ 0, a1,, ak-1 là các số thực {fn} là một dãy số thực cho trước {xn} là dãy ẩn nhận các giá trị thực 6/3/2015 2 ĐỊNH NGHĨA Trường hợp dãy fn = 0 với mọi n thì (1) trở thành: Ta nói (2) là một hệ thức đệ qui tuyến tính thuần nhất cấp k. 6/3/2015 3 NGHIỆM TỔNG QUÁT Mỗi dãy {fn} thỏa (1) được gọi là một nghiệm của (1). Nhận xét rằng mỗi nghiệm {xn} của (1) được hoàn toàn xác định bởi k giá trị đầu x0, x1, , xk-1  Họ dãy số { xn = xn(C1, C2, , Ck)} phụ thuộc vào k họ tham số C1, C2, , Ck được gọi là nghiệm tổng quát của (1) nếu mọi dãy của họ này đều là nghiệm của (1) 6/3/2015 4 NGHIỆM RIÊNG  Cho {xn} là nghiệm tổng quát của (1) và với mọi k giá trị ban đầu y0, y1, , yk-1, tồn tại duy nhất các giá trị của k tham số C1, C2, , Ck sao cho nghiệm {xn} tương ứng thỏa: x0 = y0, x1=y1, , xk-1 = yk-1 (*) Khi đó, nghiệm {xn} tương ứng được gọi là nghiệm riêng ứng với điều kiện ban đầu (*). 6/3/2015 5 MỤC ĐÍCH GIẢI HỆ THỨC ĐỆ QUI  Giải một hệ thức đệ qui là đi tìm nghiệm tổng quát của nó. Nếu hệ thức đệ qui có kèm điều kiện ban đầu, ta phải tìm nghiệm riêng thỏa điều kiện ban đầu đó. 6/3/2015 6 VÍ DỤ Ví dụ 1: (Dãy Fibonacci) Bài toán: Một đôi thỏ con (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một đực và một cái), mỗi đôi thỏ con, khi tròn hai tháng tuổi, lại mỗi tháng đẻ ra một đôi thỏ con và quá trình sinh nở cứ thế tiếp tục tiếp diễn. Tính Fn là số đôi thỏ có ở tháng thứ n? 6/3/2015 7 VÍ DỤ Giải: Tháng đầu tiên và tháng thứ 2 chỉ có một đôi thỏ. Sang tháng thứ 3, đôi thỏ này sẻ đẻ ra một đôi thỏ, vì thế tháng này sẽ có hai đôi thỏ. Với n>= 3, ta có Fn = Fn-1 + số đôi thỏ được sinh ra ở tháng thứ n. Do các đôi thỏ được sinh ra ở tháng thứ n-1 chưa đẻ con ở tháng thứ n, và ở tháng này mỗi đôi thỏ có ở tháng thứ n-2 sẽ đẻ ra được một đôi thỏ con nên số đôi thỏ được sinh ra ở tháng thứ n chính bằng Fn-2 6/3/2015 8 VÍ DỤ Như vậy, việc giải bài toán Fibonacci dẫn ta tới việc khảo sát dãy số (Fn), xác định bởi: F1=1 F2=1 Fn=Fn-1 + Fn-2 với n>2 6/3/2015 9 VÍ DỤ Ví dụ 2: Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm một hệ thức đệ qui cho xn . 6/3/2015 10 VÍ DỤ  Với n=1, ta có x1=1  Với n=2, ta có x2=2 Với n>2, để khảo sát xn ta chia thành hai trường hợp loại trừ lẫn nhau: 6/3/2015 11 VÍ DỤ Trường hợp 1: Bước đầu tiên gồm 1 bậc. Khi đó, cầu thang còn n-1 bậc nên số cách đi hết cầu thang trong trường hợp này là xn-1 6/3/2015 12 VÍ DỤ Trường hợp 2: Bước đầu tiên là 2 bậc. Khi đó, cầu thang còn n-2 bậc nên số cách đi hết cầu thang trong trường hợp này là xn-2 Theo nguyên lý cộng, số cách đi hết cầu thang là xn-1 + xn-2. Do đó ta có: xn= xn-1 + xn-2 6/3/2015 13 VÍ DỤ Vậy ta có hệ thức đệ quy tuyến tính thuần nhất cấp 2: 6/3/2015 14 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Xét hệ thức đệ qui tuyến tính thuần nhất Phương trình đặc trưng của (2) là phương trình bậc k định bởi: 6/3/2015 15 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Trường hợp k=1: Phương trình đặc trưng (*) trở thành λ – a1 = 0 nên có nghiệm là λ = a1 ; Khi đó, (2) có nghiệm tổng quát là: 6/3/2015 16 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Ví dụ: Hệ thức đệ qui Là một hệ thức đệ qui tuyến tính thuần nhất cấp 1. 6/3/2015 17 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Phương trình đặc trưng: 2λ - 3 = 0 có nghiệm là λ0 = 3/2 Do đó nghiệm tổng quát là: 6/3/2015 18 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Từ điều kiện ban đầu x1 = 1, ta có: C*3/2 = 1 Suy ra: C = 2/3 Do đó, nghiệm của hệ thức đệ qui đã cho là: xn = (3/2) n-1 6/3/2015 19 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Trường hợp k=2: Phương trình đặc trưng (*) trở thành: λ2 - a1λ - a2 = 0 (*) Nếu (*) có hai nghiệm thực phân biệt λ1 và λ2 thì (2) có nghiệm tổng quát là: 6/3/2015 20 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Nếu (*) có nghiệm kép thực λ0 thì (2) có nghiệm tổng quát là: 6/3/2015 21 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Nếu (*) có hai nghiệm phức liên hợp được viết dưới dạng lượng giác: Thì (2) có nghiệm tổng quát là: 6/3/2015 22 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Ví dụ: Giải các hệ thức đệ qui sau: Vd1: Vd2: Vd3: 6/3/2015 23 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT Xét hệ thức đệ qui tuyến tính không thuần nhất xn = a1xn-1 + + akxn-k + fn (1) Hệ thức đệ qui tuyến tính thuần nhất tương ứng là: xn = a1xn-1 + + akxn-k (2) Phương trình đặc trưng của (2) là: 6/3/2015 24 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT 6/3/2015 25 Nghiệm tổng quát của (1) Nghiệm tổng quát của (2) Một nghiệm riêng của (1) = + HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT Cách tìm một nghiệm riêng của (1) khi vế phải fn của (1) có dạng đặc biệt như sau: Dạng 1: fn = β nPr(n), trong đó Pr(n) là một đa thức bậc r theo n; β là một hằng số. Dạng 2: fn = Pm(n)cosnφ + Ql(n)sinn φ, trong đó Pm(n), Ql(n) lần lượt là các đa thức bậc m, l theo n; φ là hằng số. (φ khác ≠ kπ) Dạng 3: fn = fn1 + fn2 ++ fns ; trong đó, các fn1, fn2, fns thuộc 2 dạng đã xét ở trên 6/3/2015 26 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Dạng 1: fn = β nPr(n), Khi đó, ta xét 3 trường hợp nhỏ: TH1: β không là nghiệm của phương trình đặc trưng TH2: β là nghiệm đơn của phương trình đặc trưng TH3: β là nghiệm kép của phương trình đặc trưng. 6/3/2015 27 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Trường hợp 1: Nếu β không là nghiệm của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: xn = β nQr(n) 6/3/2015 28 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Trường hợp 2: Nếu β là nghiệm đơn của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: xn = nβ nQr(n) 6/3/2015 29 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Trường hợp 3: Nếu β là nghiệm kép của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: xn = n 2βnQr(n) 6/3/2015 30 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Chú ý: Qr(n) = Arn r + Ar-1n r-1 ++ A0 là đa thức tổng quát có cùng bậc r với Pr(n), trong đó Ar,Ar-1,, A0 là r+1 hệ số cần xác định. Ví dụ: Tìm nghiệm của hệ thức đệ qui: a/ 2xn-3xn-1+xn-2 = 4n+1 b/ xn+1-6xn+9xn-1 = (18n+12)3 n ; x0=2; x1=0. 6/3/2015 31 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Ví dụ (tt): 6/3/2015 32 Dạng 2: fn = Pm(n)cosnφ + Ql(n)sinnφ Khi đó, ta xét λ0 = cos φ ± isin φ. Có 2 trường hợp nhỏ: TH1: λ0 = cos φ ± isinφ không là nghiệm của phương trình đặc trưng TH2: λ0 = cos φ ± isin φ là nghiệm của phương trình đặc trưng 6/3/2015 33 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Trường hợp 1: λ0 = cos φ ± isin φ không là nghiệm của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: xn = Rk(n)cosnφ + Sk(n)sinnφ 6/3/2015 34 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT Trường hợp 2: Nếu λ0 = cos φ ± isin φ là nghiệm của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: xn = n(Rk(n)cosn φ + Sk(n)sinn φ) 6/3/2015 35 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Ghi chú: Rk(n), Sk(n) là các đa thức tổng quát theo n có bậc k = max{m,l} với 2k+2 hệ số cần xác định. Rk(n) = Akn k + Ak-1n k-1 ++ A0 Sk(n) = Bkn k + Bk-1n k-1 ++ B0 Ví dụ: 6/3/2015 36 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT  Dạng 3: fn = fn1 + fn2 ++ fns Bằng cách như trên ta tìm được nghiệm riêng xni (1≤ i ≤ s) của hệ thức đệ qui: a0xn + a1xn-1 + + akxn-k = fni Khi đó: xn = xn1 + xn2++ xns là một nghiệm riêng của (1) Ví dụ: 6/3/2015 37 HỆ THỨC ĐỆ QUI TUYẾN TÍNH KHÔNG THUẦN NHẤT BÀI TẬP Bài 1: a/ Tìm nghiệm tổng quát của hệ thức đệ qui: an = an-1 + 6an-2 b/ Tìm nghiệm thỏa điều kiện ban đầu a0=1, a1= 5 của hệ thức đệ qui: an = an-1 + 6an-2 + 50n3 n-1 6/3/2015 38 BÀI TẬP Bài 2: a/ Tìm nghiệm tổng quát của hệ thức đệ qui: an = 4an-1 – 4an-2 b/ Tìm nghiệm của hệ thức đệ qui an=4an-1- 4an-2+3.2 n+1 thỏa điều kiện ban đầu a0=4, a1=4 6/3/2015 39 BÀI TẬP Bài 3: a/ Tìm nghiệm tổng quát của hệ thức đệ qui: an = 6an-1 – 9an-2 b/ Tìm nghiệm của hệ thức đệ qui an=6an-1 - 9an-2+2.4 n thỏa điều kiện ban đầu a0=12, a1=8 6/3/2015 40 BÀI TẬP Bài 4: a/ Tìm nghiệm tổng quát của hệ thức đệ qui an=6an-2 - 9an-1 b/ Tìm nghiệm của hệ thức đệ qui an=6an-2 - 9an-1+n.3 n +1 thỏa điều kiện ban đầu a0=1, a1=3 6/3/2015 41 BÀI TẬP Bài 5: Giải các hệ thức đệ qui sau: 6/3/2015 42 BÀI TẬP 6/3/2015 43 BÀI TẬP 6/3/2015 44