Tóm tắt bài giảng Phương pháp tính | Đại học Bách Khoa Hà Nội
Tóm tắt bài giảng Phương pháp tính | Đại học Bách Khoa Hà Nội. Tài liệu được biên soạn giúp các bạn tham khảo, củng cố kiến thức, ôn tập và đạt kết quả cao kết thúc học phần. Mời các bạn đọc đón xem!
Preview text:
Mục lục 1 Sai số 3
1.1 Số gần đúng và sai số . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Xác định sai số của hàm số biết sai số và đối số . . . . . . . . . . 4 1.2.1
Công thức tổng quát của sai số . . . . . . . . . . . . . . . 4 1.2.2
Sai số của tổng đại số . . . . . . . . . . . . . . . . . . . . . 4 1.2.3
Sai số của tích . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Giải phương trình f(x)=0 5
2.1 Khái niệm khoảng phân ly nghiệm . . . . . . . . . . . . . . . . . 5
2.2 Phương pháp chia đôi . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.1
Cách giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.2
Sai số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Phương pháp lặp đơn . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3.1
Cách giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3.2
Điều kiện hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3.3
Sai số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Phương pháp tiếp tuyến (Phương pháp Newton) . . . . . . . . . 6 2.4.1
Cách giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4.2
Điều kiện hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4.3
Sai số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.5 Phương pháp dây cung . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5.1
Cách giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5.2
Điều kiện hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Giải hệ phương trình 8
3.1 Phương pháp Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . 8 3.1.1
Phương pháp Gauss . . . . . . . . . . . . . . . . . . . . . 8 3.1.2
Phương pháp Gauss-Jordan . . . . . . . . . . . . . . . . . 9
3.2 Chuẩn của vector, chuẩn của ma trận . . . . . . . . . . . . . . . . 11 1 Trần Hiếu LATEX 3.2.1
Chuẩn của vector . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.2
Chuẩn của ma trận . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Những phương pháp lặp . . . . . . . . . . . . . . . . . . . . . . . 12 3.3.1
Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3.2
Phương pháp lặp đơn . . . . . . . . . . . . . . . . . . . . 12 3.3.3
Phương pháp lặp Jacobi . . . . . . . . . . . . . . . . . . . 13 3.3.4
Phương pháp lặp Gauss-Seidel . . . . . . . . . . . . . . . 14
4 Nội suy và phương pháp bình phương tối thiểu 15
4.1 Lược đồ Horner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.1.1
Chia đa thức cho đơn thức . . . . . . . . . . . . . . . . . 15 4.1.2
Nhân đa thức với đơn thức . . . . . . . . . . . . . . . . . 15 4.1.3
Sử dụng lược đồ Horner tính đạo hàm tại 1 điểm . . . . 16
4.2 Đa thức nội suy Lagrange . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Đa thức nội suy Newton . . . . . . . . . . . . . . . . . . . . . . . 18
4.4 Phương pháp bình phương tối thiểu . . . . . . . . . . . . . . . . 20 4.4.1
Dạng f(x) = Ax + B . . . . . . . . . . . . . . . . . . . . . 20 4.4.2
Dạng f(x) = Ax2 + Bx + C . . . . . . . . . . . . . . . . . 21 4.4.3
Dạng f(x) = Ag(x) + Bh(x) . . . . . . . . . . . . . . . . 21
5 Tính gần đúng đạo hàm và tích phân 22
5.1 Tính gần đúng đạo hàm . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Tính gần đúng tích phân . . . . . . . . . . . . . . . . . . . . . . . 23 5.2.1
Công thức hình thang . . . . . . . . . . . . . . . . . . . . 23 5.2.2
Công thức Simpson . . . . . . . . . . . . . . . . . . . . . . 23
6 Giải gần đúng PTVP 24
6.1 Phương pháp Euler . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2 Phương pháp Runge-Kutta bậc 3 (RK3) . . . . . . . . . . . . . . 25
6.3 Phương pháp Runge-Kutta bậc 4 (RK4) . . . . . . . . . . . . . . 25
6.4 Hệ phương trình vi phân . . . . . . . . . . . . . . . . . . . . . . . 26
6.5 PTVP bậc cao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2 Chương 1 Sai số
1.1 Số gần đúng và sai số
(a) Đại lượng ∆ = |a − A| được gọi là sai số tuyệt đối của số gần đúng a. Tuy
nhiên, do không biết số chính xác A, ta ước lượng một đại lượng tương
đương ∆a càng bé càng tốt thỏa mãn |a − A| 6 ∆a được gọi là sai số tuyệt
đối giới hạn của số gần đúng a.
A = a ± ∆a (b) Sai số tương đối: |A − a| ∆ δ a a = hoặc δ
.100% (Sai số tương đối giới hạn) |A| a = |A|
(c) Chữ số có nghĩa của một số là những chữ số của số đó kể từ chữ số khác
không đầu tiên tính từ trái sang phải.
(d) Làm tròn lên và làm tròn xuống. Ví dụ:
a < 3, 9236 làm tròn lên đến 2 chữ số ta được a < 3, 93
b > 8, 6789 làm tròn xuống đến 2 chữ số ta được b > 8, 67 (e) Chữ số đáng tin:
Cho a ≈ A. Chữ số αk trong phép biểu diễn dưới dạng thập phân được gọi
là đáng tin nếu ∆a 6 0, 5.10k và ngược lại.
Ví dụ: a = 3, 7284, δ 0, 0047 a = δ −2 −2 a = 0, 0047 = 0, 47.10 6 0, 5.10
nên a có 3 chữ số đáng tin là 3,7,2 và 2
chữ số không đáng tin là 8,4. 3 Trần Hiếu LATEX
1.2 Xác định sai số của hàm số biết sai số và đối số
1.2.1 Công thức tổng quát của sai số
Cho hàm số khả vi liên tục y = f (x1, x2, . . . , xn) và sai số tuyệt đối ∆x của các i đối số xi (a) Sai số tuyệt đối: n ∂ f ∆ y = ∑ .∆xi ∂x i= 1 i (b) Sai số tương đối: n ∂ f ∑ .∆ ∆ ∂x xi n y i ∂ ln f δ i=1 y = = = ∑ .∆ y ∂ xi f x i= 1 i
1.2.2 Sai số của tổng đại số ∂ f
Xét hàm số y = ±x
1 ± x2 ± . . . ± xn có
= 1. Do đó sai số tuyệt đối là ∂xi ∆y
∆y = ∆x + ∆ + . . . ∆ và sai số tương đối δ 1 x2 xn y = y
1.2.3 Sai số của tích ∂ 1 ∂ ∆
Xét hàm số y = x xi
1.x2 . . . xn có . ln y = ⇒ ln = δ y .∆x = i xi ∂x ∂ i |xi| xi |xi|
Do đó sai số tương đối của y là δ δ δ δ y = x + + . . . +
và sai số tuyệt đối là 1 x2 xn
∆y = δy. y 4 Chương 2
Giải phương trình f(x)=0
2.1 Khái niệm khoảng phân ly nghiệm
(a) Khái niệm: Khoảng (a; b) được gọi là một khoảng phân ly nghiệm x của
phương trình f (x) = 0 nếu trong khoảng đó phương trình f (x) = 0 chỉ
chứa một nghiệm thực x duy nhất.
(b) Định lý: Khoảng (a, b) được gọi là một khoảng phân ly nghiệm x của phương
trình f (x) = 0 nếu f (a) f (b) < 0 và f (x) = 0 là hàm số đơn điệu liên tục trong [a, b].
(c) Sai số tổng quát: Giả sử hàm f (x) = 0 liên tục trên [a, b], khả vi trong (a, b).
Nếu xn là nghiệm gần đúng của nghiệm x và m = min thì công thức f ′ (x)
đánh giá sai số tổng quát là: f (x | n) xn − x| ≤ m
2.2 Phương pháp chia đôi 2.2.1 Cách giải
Cho phương trình f (x) = 0, f (x) liên tục và trái dấu tại 2 đầu [a, b]. Giả sử
f (a) < 0, f (b) > 0 (nếu ngược lại thì xét − f (x) = 0). Cách tìm nghiệm x.
Đặt [a0, b0] = [a, b] và lập các khoảng lồng nhau [ai, bi] , (i = 1, 2, 3, . . .) a
nếu f ((ai−1+bi−1)) > 0 [ i a
−1 , (ai−1+bi−1) 2 2 i, bi] = (ai−1+bi−1) , b ) < 0 2
i−1 nếu f ( (ai−1+bi−1) 2 2.2.2 Sai số b − a
|xn − x| ≤ 2n 5 Trần Hiếu LATEX
2.3 Phương pháp lặp đơn 2.3.1 Cách giải
Biến đổi tương đương:
f (x) = 0 ⇔ x = g(x)
Chọn giá trị ban đầu xn ∈ (a, b). Xây dựng dãy xấp xỉ nghiệm theo công thức truy hồi
xn = g(xn−1)
Nếu dãy này hội tụ, ta được lim xn = x n→∞
2.3.2 Điều kiện hội tụ
Hàm g(x) xác định, khả vi trên [a, b] g : R −→ R
[a, b] 7−→ [a, b]
Khi đó nếu ∃q > 0 sao cho
g′(x) ≤ q < 1, ∀x ∈ (a, b) thì:
(i) Quá trình lặp hội tụ đến nghiệm không phụ thuộc vào ∀x0 ∈ [a, b].
(ii) Giới hạn lim xn = x là nghiệm duy nhất trên (a, b). n→∞ 2.3.3 Sai số - Sai số hậu nghiệm: q |xn − ¯x| ≤ |x
1 − q n − xn−1| - Sai số tiên nghiệm: qn |xn − ¯x| ≤ |x
1 − q 1 − x0|
2.4 Phương pháp tiếp tuyến (Phương pháp Newton) 2.4.1 Cách giải Công thức lặp: f (x x n−1)
n = xn−1 − f ′(xn−1) 6 Trần Hiếu LATEX
2.4.2 Điều kiện hội tụ
Giả sử [a, b] là khoảng nghiệm của phương trình f (x) = 0. Đạo hàm f ′(x) và
f ′′(x) liên tục, không đổi dấu, không triệt tiêu trên [a, b]. Khi đó ta chọn xấp xỉ
nghiệm ban đầu x0 ∈ [a, b] sao cho f (x0). f ′′(x) > 0 thì dãy số hội tụ đơn điệu
đến nghiệm đúng của phương trình f (x) = 0. 2.4.3 Sai số
∀x ∈ [a, b] nếu tồn tại m, M thỏa mãn:
f ′(x) ≥ m > 0
f ′′(x) ≤ M Khi đó ta có: M |xn − ¯x| ≤ (x 2m n − xn−1)2
2.5 Phương pháp dây cung 2.5.1 Cách giải Công thức lặp: d − x x n−1 n = xn−1 − f (x
f (d) − f (x n−1) n−1)
2.5.2 Điều kiện hội tụ
Giả sử [a, b] là khoảng nghiệm của phương trình f (x) = 0. Đạo hàm f ′(x) và
f ′′(x) liên tục, không đổi dấu, không triệt tiêu trên [a, b]. Chọn d = a nếu
f (a). f ′′(x) > 0
hoặc d = b trong trường hợp ngược lại thì dãy số hội tụ đơn điệu đến nghiệm
đúng của phương trình f (x) = 0. 7 Chương 3
Giải hệ phương trình
Xét hệ phương trình gồm n phương trình và n ẩn số và det A 6= 0 (hệ Cramer)
a11x1 + a12x2 + . . . + a
1i xi + . . . a1nxn = b1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ai1x1 + ai2x2 + . . . + aiixi + . . . ainxn = bi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
an1x1 + an2x2 + . . . + anixi + . . . annxn = bn
3.1 Phương pháp Gauss-Jordan
3.1.1 Phương pháp Gauss Trình tự giải
Bước 1: Viết ma trận mở rộng (A|B) của hệ.
Bước 2: Dùng các phép biến đổi sơ cấp trên hàng biến đổi ma trận mở rộng về ma trận bậc thang.
Bước 3: Viết hệ phương trình tương ứng với ma trận bậc thang.
Bước 4: Giải hệ phương trình ngược từ dưới lên, ta được 1 nghiệm duy nhất.
Ví dụ: Giải hệ phương trình x1 + 2x 2 + 2x3 = 9
2x1 + 4x2 + 9x3 = 23
3x1 + 7x2 + 8x3 = 31 8 Trần Hiếu LATEX Giải: 1 2 2 9 1 2 2 9
h2−2h1→h2
h3−3h1→h3 2 4 9
23 −−−−−−→ 0 0 5 5 3 7 8 31 0 1 2 4 1 2 2 9 x 1 = 3 h 2↔h3 −−−→ 0 1 2 4 ⇔ x2 = 2 0 0 5 5 x3 = 1
3.1.2 Phương pháp Gauss-Jordan
Định nghĩa: Phần tử trội là phần tử có trị tuyệt đối lớn nhất, sao cho không
cùng hàng và cột với những phần tử đã chọn trước.
Phương pháp Gauss-Jordan
(a) Chọn phần tử trội để biến đổi cho tất cả các phần tử trên cùng cột của phần tử trội bằng không.
(b) Qua n bước sẽ tìm được nghiệm cần tìm.
Ví dụ: Giải hệ phương trình
x1 − x2 + 2x3 − x 4 = −8 2x 2
1 − x2 + 3x3 − 3x4 = −20
x1 + x2 + x 3 = −2
x1 − x2 + 4x3 + 3x 4 = 4
Giải: Ma trận mở rộng: 1 −1 2 1 − −8 2 −2 3 3 − −20 1 1 1 0 −2 1 −1 4 3 4 9 Trần Hiếu LATEX
Chọn phần tử trội là a43 = 4 1 4h −1 0 5 − −20 3−h4→h3 4h 3 2− h4→h2 2h 5 −5 0 21 − −92 1−h4→h1 −−−−−−−→ 3 5 0 −3 −12 1 −1 4 3 4
Chọn phần tử không được nằm trên hàng 4 và cột 3 là phần tử a24 = −21 40 21h −4 4 0 0 1−5h2→h1 7h 3−h2→h3 7h 5 −5 0 21 − −92 4+h2→h4 −−−−−−−→ 16 40 0 0 8 12 −12 18 0 −64
Chọn phần tử không được nằm trên hàng 4,2 và cột 3,4 là phần tử a32 = 40 −56 0 0 0 392
10h1−h3→h1 8h 2+h3→h2 10h 56 0 0 168 − −728 4+3h3→h4 −−−−−−−→ 16 40 0 0 8 168 0 280 0 −616
Chọn phần tử không được nằm trên hàng 4,2,3 và cột 3,4,2 là phần tử a11 = −56 392 h −56 0 0 0 2+h1→h2 7h 2 3+ h1→h3 h 0 0 0 168 − −336 4+3h1→h4 −−−−−−−→ 0 280 0 0 840 0 0 280 0 560
Vậy hệ đã cho tương đương với hệ sau −56x x 1 = 392 1 = −7 −168x4 = −336 x2 = 3 ⇔ 280x 840 x 2 = 3 = 2 280x 560 3 = x4 = 2
Suy ra hệ đã cho có nghiệm duy nhất (x1, x2, x3, x4) = (−7, 3, 2, 2) 10 Trần Hiếu LATEX
3.2 Chuẩn của vector, chuẩn của ma trận
3.2.1 Chuẩn của vector
Định nghĩa: Trong không gian tuyến tính thực Rn. Chuẩn của vector X ∈ Rn
là một số thực không âm, ký hiệu kXk thỏa mãn các điều kiện sau:
(i) ∀X ∈ Rn, kXk > 0, 0 kXk = 0 ⇔ X =
(ii) ∀X ∈ Rn, ∀λ ∈ R, kλXk = kλk . kXk
(iii) ∀X, Y ∈ Rn, kX + Yk 6 kXk + kYk
Trong Rn có rất nhiều chuẩn, tuy nhiên chỉ xét chủ yếu 3 chuẩn thường dùng
sau: ∀X = (x1, x2, . . . , xn)T ∈ Rn
(i) kXk∞ = max |x1| , |x2| , . . . , |xn| = max |xk| k=1,n n (ii) kXk = 1
|x1| + |x2| + . . . + |xn| = ∑ |xk| k=1 1 1 !2 n (iii) k 2 Xk = = (chuẩn Euclide) 2 XTX ∑ |xi|2 i=1
Ví dụ: Cho X = (1, 2, 3, −5)T
kXk = 1 + 2 + 3 + 5 = 11 1
kXk∞ = max {1, 2, 3, 5} = 5 √ p kXk = 12 + 22 + 32 + 52 = 39 2
3.2.2 Chuẩn của ma trận
Định nghĩa: Chuẩn của ma trận A tương ứng với chuẩn vector X được xác định theo công thức: kAXk
kAk = max kAXk = max kXk=1 kXk6=0 kXk Tính chất:
kAXk ≤ kAk . kXk
Ak ≤ kAkk
Định lý: Chuẩn của ma trận A = aij
được xác định như sau: m×n m
• kAk = max ∑ - Chuẩn cột 1 aij 16j6n i=1 11 Trần Hiếu LATEX n • kAk ∑ - Chuẩn hàng ∞ = max aij 16i6m j=1 s m n 2 • kAk =
∑ ∑ a - Chuẩn Euclide 2 ij i=1 j=1
Nói một cách dễ hiểu chuẩn Euclide bằng căn bậc hai tổng bình phương tất cả
các phần tử của ma trận đó. 2 −1 4
Ví dụ: Cho A = 5 3 2 6 −7 3
kAk = max 2 + 5 + 6, 1 + 3 + 7, 4 + 2 + 3 13, 11, 9 1 { } = max { } = 13 √ kAk = 3 17 2 ≈ 12.3693169
kAk∞ = max {2 + 1 + 4, 5 + 3 + 2, 6 + 7 + 3} = max {7, 10, 16} = 16
3.3 Những phương pháp lặp 3.3.1 Định nghĩa ∞
Xét dãy các vector X(m)
với X(m) ∈ Rn. Dãy các vector này được gọi là m=0
hội tụ về vector X nếu và chỉ nếu X(m) − ¯
X → 0 khi m → +∞ (hội tụ theo chuẩn)
Định nghĩa ma trận chéo trội:
Ma trận A được gọi là ma trận chéo trội nếu nó thỏa mãn điều kiện n
∑ a < |a ij
ii| , ∀i = 1, n (chéo trội hàng) j=1,j6=i hoặc n
∑ a < a , ∀j = 1, n (chéo trội cột) ij jj i=1,i6=j Định lý:
Phương pháp lặp Jacobi, Gauss - Seidel cho hệ phương trình AX = B sẽ hội tụ
nếu A là ma trận chéo trội.
3.3.2 Phương pháp lặp đơn
Từ hệ AX = B, ta phân tích A = M − N, với M là ma trận dễ khả nghịch, khi đó ta có:
(M − N) X = B ⇔ MX = NX + B 12 Trần Hiếu LATEX
⇔ X = M−1NX + M−1B
Đặt C = M−1N, D = M−1B ⇒ X = CX + D ∞
Xuất phát từ vector ban đầu X(0) ta xây dựng dãy X(m) theo công thức m=0
X(m) = CX(m−1) + D Định lý: ∞
Nếu kCk < 1 thì dãy các vector X(m)
xác định theo công thức lặp sẽ hội m=0
tụ về vector nghiệm X của hệ với mọi vector ban đầu X(0). Khi đó công thức đánh giá sai số như sau: kCkm
X(m) − X ≤
. X(1) − X(0) 1 − kCk hoặc kCk
X(m) − X ≤
. X(m) − X(m−1) 1 − kCk
3.3.3 Phương pháp lặp Jacobi
Phương pháp cho ma trận chéo trội hàng
a11 a12 . . . a1n a 21 a22 . . . a Xét hệ phương trình 2
AX = B. Ta phân tích ma trận A = n . . . . . . . . . . . .
an1 an2 . . . ann thành a11 0 . . . 0 0
−a12 . . . −a1n 0 a 22 . . . 0 −a21 0 . . . −a2n A = − = P − Q . . . . . . . . . . . . . . . . . . . . . . . . 0 0 . . . ann
−an1 −an2 . . . 0
Do aii 6= 0, ∀i = 1, 2, . . . , n nên det P 6= 0. Như vậy 1 0 . . . 0 a11 0 1 . . . 0 P−1 = a22
. . . . . . . . . . . . 0 0 . . . 1 ann 13 Trần Hiếu LATEX Ta có:
AX = B ⇔ (P − Q) X = B
⇔ PX = QX + B
⇔ X = P−1QX + P−1B
Đặt Cj = P−1Q và Dj = P−1B. Khi đó công thức lặp có dạng: X(m) = C (m−1) jX
+ Dj (kCk∞ < 1)
Phương pháp cho ma trận chéo trội cột:
Biến đổi tuyến tính dạng z x i i = aii
sau đó tiến hành như phương pháp cho ma trận chéo trội hàng (kCk < 1). 1
3.3.4 Phương pháp lặp Gauss-Seidel
Phân tích Q = K + L với K là ma trận tam giác dưới và L là ma trận tam giác trên.
AX = B ⇔ (P − K − L) X = B
⇔ (P − K) X = LX + B
⇔ X = (P − K)−1LX + (P − K)−1B
Đặt Cg = (P − K)−1L và Dg = (P − K)−1B. Khi đó công thức lặp có dạng X(m) = C (m−1) gX + Dg 14 Chương 4
Nội suy và phương pháp bình phương tối thiểu
4.1 Lược đồ Horner
4.1.1 Chia đa thức cho đơn thức
P (x) = anxn + an−1xn−1 + . . . a1x + a0
Tìm Q(x) và r: P(x) = Q(x)(x − c) + r an an−1 an−2 . . . a1 a0 + 0 c.bn−1 c.bn−2 . . . c.b1 c.b0
c → bn−1 ր bn−2 ր bn−3 . . . b0 ր r
Ví dụ: P(x) = x5 + x4 − 1, c = 2 − 1 1 0 0 0 −1 + 0 −2 2 −4 8 −16 c = −2 1 −1 2 4 8 17 − −
Khi đó: Q(x) = x4 − x3 + 2x2 − 4x + 8 và r = −17
4.1.2 Nhân đa thức với đơn thức
P (x) = anxn + an−1xn−1 + . . . a1x + a0
Tìm Q(x) = P(x)(x − c)
c → an ց an a −1 ց n−2 ց . . . a1 ց a0 ց 0 - 0 c.an c.an c −1 . . . c.a2 c.a1 .a0 bn+1 bn bn−1 . . . b2 b1 b0 15 Trần Hiếu LATEX
Lúc này Q(x) = bn+1xn+1 + bnxn + . . . + b1x + b0
Ví dụ: P(x) = x5 + x4 − 1, c = 2 − c = −2 1 1 0 0 0 −1 0 − 0 −2 −2 0 0 0 2 1 3 2 0 0 2 −1 −
⇒ Q(x) = x6 + 3x5 + 2x4 − x − 2
4.1.3 Sử dụng lược đồ Horner tính đạo hàm tại 1 điểm
Giả sử ta tính đạo hàm của P(x) tại điểm x0 = c
P (x) = a0 + a1 (x − x0) + a2(x − x0)2 + . . . + an(x − x0)n
Theo công thức khai triển Taylor tại lân cận x0 = c f ′(x f ′′(x f (n)(x
P(x) = f (x 0) 0) 0) 0) + (x − x
(x − x0)2 + . . . +
(x − x0)n + o(x − x0)n 1! 0) + 2! n!
Đồng quy hệ số ta được f (n) (x a 0) n =
→ f (n) (x n! 0) = an.n!
Ví dụ: P (x) = x3 + 3x2 + 3x + 2, x = 1 1 3 3 2 P (1) = 9 c = 1 1 4 7 9
P′ (1) = 12 × 1! = 12 → c = 1 1 5 12
P′′ (1) = 6 × 2! = 12 c = 1 1 6
P(3) (1) = 1 × 3! = 3
4.2 Đa thức nội suy Lagrange Công thức chung n y L k
n(x) = ω(x). ∑
với ω (x) = (x − x0) (x − x1) . . . (x − xn) và D D
k = ω′ (xk) (x − xk) k=0 k 16 Trần Hiếu LATEX Bảng nội suy x x0 x1 . . . xn x0 x − x0
x0 − x1 . . . x0 − xn D0 x1 x1 − x0
x − x1 . . . x1 − xn D1 . . . . . . . . . . . . . . . . . .
xn xn − x0 xn − x1 . . . x − xn Dn ω (x) Công thức sai số
Giả sử hàm f (x) có đạo hàm đến cấp n + 1 liên tục trên đoạn [a; b]. Đặt M =
max f (n+1) (x), ta có: x∈[ a;b] M ω (
f (x) − Ln (x) ≤ x) ( n + 1)! Ví dụ
Cho hàm số y xác định bởi: x 1 2 3 4
y = ex 2,7183 7,3891 20,0855 54,5982
Lập đa thức nội suy, tính gần đúng và đánh giá sai số tại điểm x = 1, 5. Giải: Lập bảng nội suy: x 1 2 3 4 1 x − 1 −1 2 − −3 6(1 − x) 2 1 x − 2 −1 −2 2(x − 2) 3 2 1 x − 3 −1 2(3 − x) 4 3 2 1 x − 4 6(x − 4)
(x − 1)(x − 2)(x − 3)(x − 4) ⇒ Đa thức nội suy là: " # 2, 7183 7, 3891 20, 0855 54, 5982
L3 (x) = (x − 1)(x − 2)(x − 3)(x − 4) + + + 6 (1 − x) 2 (x − 2) 2 (3 − x) 6 (x − 4)
y (1, 5) ≈ L3 (1, 5) = 4, 9124
Có y(4) = ex → M = e4 e4 ⇒
y (1, 5) − L3 (1, 5) ≤ (1, 5 1, 5 1, 5 − 1) ( − 2) (
− 3) (1, 5 − 4) = 2, 1327 4! 17 Trần Hiếu LATEX
TH đặc biệt: Các điểm nút cách đều nhau với bước h = xk+1 − xk Đặt x − x q = 0 , khi đó ta có: h n n (−1)n−ky L k
n (x) = ∏ q − k ∑ k! (n − k)! q − k k=0 k=0
4.3 Đa thức nội suy Newton
Định nghĩa tỷ sai phân Trên đoạn x
k, xk+1 ta định nghĩa đại lượng y f x k+1 − yk k, xk+1 = xk+1 − xk
được gọi là tỉ sai phân cấp 1. Tương tự f x − f x f x k+1, xk+2 k, xk+1
k, xk+1, xk+2 = xk+2 − xk
được gọi là tỉ sai phân cấp 2. Bằng quy nạp, ta có tỉ sai phân cấp p h i h i f x − f x h i
k+1, xk+2, . . . , xk+p
k, xk+1, . . . , xk+p−1
f xk, xk+1, . . . , xk+p =
xk+p − xk
Xây dựng công thức x 1,0 1,3 1,6 1,9
Ví dụ: Xây dựng đa thức nội suy Newton: y 0,76 0,62 0,45 0,28 Giải:
Lập bảng tỷ sai phân: x k f (xk)
f xk, xk+1
f xk, xk+1, xk+2
f xk, xk+1, xk+2, xk+3 1,0 0,76 0,62 0,76 − = −7 1,3−1 15 −17 1,3 0,62 30 − −7 15 = −1 1,6−1 6 0,45 0,62 − 0 = −17 − −1 6 = 5 1,6−1,3 30 1,9−1 27 −17 1,6 0,45 30 − −17 30 = 0 1,9−1,3 0,28 0,45 − = −17 1,9−1,6 30 1,9 0,28 18 Trần Hiếu LATEX
Lúc đó sẽ có 2 cách xây dựng đa thức nội suy Newton: Công thức Newton tiến: 7 1 5 N (1) (x) = 0, 76 (x − 1)
(x − 1) (x − 1, 3) + 3 − −
(x − 1) (x − 1, 3) (x − 1, 6) 15 6 27 Công thức Newton lùi: 17 5 N (2) (x) = 0, 28 3 − (x − 1, 9) +
(x − 1, 9) (x − 1, 6) (x − 1, 3) 30 27
Công thức tổng quát (1) Newton tiến: N (1) n
(x) = y0 + f [x0, x1] (x − x0) + f [x0, x1, x2] (x − x0) (x − x1) + . . . +
f [x0, x1, . . . , xn] (x − x0) (x − x1) . . . (x − xn−1) (2) Newton lùi: N (2) n
(x) = yn + f [xn−1, xn] (x − xn) + f [xn−2, xn−1, xn] (x − xn) (x − xn−1) +
. . . + f [x0, x1, . . . , xn] (x − xn) (x − xn−1) . . . (x − x1) Sai số:
Rn (x) = f [x, x0, . . . , xn] (x − x0) (x − x1) . . . (x − xn)
hoặc dùng sai số của đa thức nội suy Lagrange.
TH đặc biệt: Các điểm nút cách đều nhau với bước h = xk+1 − xk (a) Định nghĩa sai phân: Sai phân tiến cấp 1
∆yj = yj+1 − yj Sai phân tiến cấp k+1 ∆k+1y ∆ j = kyj+1 − ∆kyj
(b) Công thức Newton tiến: Đặt x − x q = 0 h ∆y ∆2y ∆ny N (1) 0 0 0 n (x) = y0 + q +
q q − 1 + . . .
q q − 1 . . . q − n + 1 1! 2! n!
(c) Công thức Newton lùi: Đặt x − x p = n h ∆y ∆2y ∆ny N (2) n−1 n−2 0 n (x) = yn + p +
p p + 1 + . . . +
p p + 1 . . . p + n − 1 1! 2! n! 19 Trần Hiếu LATEX
4.4 Phương pháp bình phương tối thiểu
Bài toán xấp xỉ thực nghiệm
x x0 x1 . . . xn
y y0 y1 . . . yn
Tìm hàm f (x) xấp xỉ bảng x
k, yk theo phương pháp bình phương tối thiểu để
g f = ∑ f (x 2 k) − yk → min
Hàm f tổng quát rất đa dạng, dưới đây là một số dạng thường gặp
4.4.1 Dạng f(x) = Ax + B Khi đó n
g (A, B) = ∑ A + Bx 2 k − yk k=1
Bài toán quy về tìm cực tiểu hàm 2 biến: n ∂ ∑ = 0
g (A, B) = 2
A + Bxk − yk ∂ A k=1 n ∂
g (A, B) = 2 ∑ A + Bx x ∂ k − yk k = 0 B k=1 ! n n n A + ∑ xk B = ∑ y k ⇒ k=1 k=1 ! ! n n n ∑ x A + ∑ x2 B = ∑ x k k kyk k=1 k=1 k=1 x 1 1 2 2 2 3 3 4 5 6 Ví dụ: y 1 2 2 3 4 4 5 5 6 7 Giải: n n n n
Ta có n = 10, ∑ xk = 29, ∑ yk = 39, ∑ x2 = 109, ∑ x k
kyk = 140. Hệ phương k=1 k=1 k=1 k=1
trình xác định A, B có dạng: 10 A + 29B = 39 A = 0.7671 ⇒ 29 A + 109B = 140 B = 1.0803
⇒ f (x) = 1.0803x + 0.7671 20 Trần Hiếu LATEX
4.4.2 Dạng f(x) = Ax2 + Bx + C Khi đó n 2
g (A, B, C) = ∑ A + Bxk + Cx2k − yk k=1
Bài toán quy về tìm cực tiểu hàm 3 biến: n ∂ ∑ A + Bx = 0
g (A, B, C) = 2 k + Cx2 ∂ A k − yk k=1 n ∂
g (A, B, C) = 2 ∑ A + Bx x ∂B
k + Cx2k − yk k = 0 k=1 n ∂
g (A, B, C) = 2 ∑ A + Bx x2 = 0 ∂ k + Cx2 C k − yk k k=1 ! ! n n n n A + ∑ x B + ∑ x2 C = ∑ y k k k k=1 k=1 k=1 ! ! ! n n n n ⇒ ∑ xk A + ∑ x2 B + ∑ x3 C = ∑ xky k k k k=1 k=1 k=1 k=1 ! ! ! n n n n ∑ x2 A + ∑ x3 B + ∑ x4 C = ∑ x2y k k k k k k=1 k=1 k=1 k=1
4.4.3 Dạng f(x) = Ag(x) + Bh(x) Khi đó n
g (A, B) = ∑ Ag (x 2
k) + Bh (xk) − yk k=1
Bài toán quy về tìm cực tiểu hàm 2 biến: n ∂ 2 ∑ = 0
g (A, B) = 2g (xk)
Ag (xk) + Bh (xk) − yk ∂ A k=1 n ∂ 2
g (A, B) = 2h (x ∑ = 0 ∂ k)
Ag (xk) + Bh (xk) − yk B k=1 ! ! n n n
∑ g2 (xk) A +
∑ g (xk) h (xk) B = ∑ g (x k) yk ⇒ k=1 k=1 k=1 ! ! n n n ∑ g (x A + ∑ h2 (x B = ∑ h (x k) h (xk) k) k) yk k=1 k=1 k=1
Đối với các dạng khác ta làm tương tự theo cách đưa về bài toán tìm cực tiểu hàm nhiều biến 21 Chương 5
Tính gần đúng đạo hàm và tích phân
5.1 Tính gần đúng đạo hàm Bài toán: x x0 x Cho bảng giá trị 1 . . . xn
y = f (x) y0 y1 . . . yn
Tính gần đúng giá trị f ′(x) với x ∈ [x0, xn] Ý tưởng:
f ′(x) ≈ P′(x) trong đó P(x) là Đa thức nội suy sinh ra từ bảng giá trị.
Giả sử trong bảng giá trị các mốc nội suy cách đều nhau một khoảng h. n ∆jy P (t) = y 0 0 + ∑
t (t − 1) . . . t − j + 1 j! j=1 Khi đó dP (x) 1
dP (x) dt = . = P′ t dx x=x dt
dx t=t=x−x0 h h Ví dụ: x 50 55 60 Cho . Tính f ′(51) y 3,9120 4,0073 4,0943 Giải: ∆2y x − 50 P (t) = y 0 0 + ∆y0t +
t (t − 1) với t = . 2! 5 x y ∆ ∆2 50 3,9120 0,0953 -8,3.10−3 55 4,0073 0,0870 60 4,0943
P (t) = 3, 9120 + 0, 0953t − 4, 15.10−3t (t − 1) 1 1 f ′ (51) = P′ (0, 2) = 0, 0953 + 4, 15 8, 3.10 × 10−3 − −3.0, 2 = 0, 019558 5 5 22 Trần Hiếu LATEX
5.2 Tính gần đúng tích phân Bài toán: x x0 x Cho bảng giá trị 1 . . . xn
y = f (x) y0 y1 . . . yn b
Tính gần đúng I = R f (x) dx, a = x0, b = xn a
5.2.1 Công thức hình thang b
Gọi P(x) là đa thức nội suy sinh ra từ bảng giá trị. Khi đó I ≈ I∗ = R P (x) dx. a
Giả sử trong bảng giá trị các mốc nội suy cách đều nhau một khoảng h. xi+1 Z 1 h I i =
f (x) dx ≈ (x = yi+1 + y 2
i+1 − xi) yi+1 + yi 2 i xi xn Z h h i ⇒ I∗ =
f (x) dx = y 2
0 + yn + 2 y1 + y2 + . . . + yn−1 x0 Sai số: M2
I − I∗ ≤
(b − a) h2 trong đó M f ′′ (x) 12 2 = max [ a,b]
5.2.2 Công thức Simpson
Giả sử bảng giá trị có 2n + 1 mốc nội suy x0, x1, . . . , x2n cách nhau một khoảng đều là h. Khi đó: h h i I∗ = y + 4 y 3
0 + y2n + 2 y2 + y4 + . . . + y2n−2
1 + y3 + . . . y2n−1 Sai số: M4
I − I∗ ≤
(b − a) h4 trong đó M f (4) (x) 180 4 = max [ a,b] 23 Chương 6
Giải gần đúng PTVP
6.1 Phương pháp Euler Chia x − x [x 0
0, x] thành n đoạn có độ dài h = bởi các mốc x n
0, x1, . . . , xn (1) Công thức Euler hiện yo = y(x0) yi+1
= yi + h f (xi, yi)
(2) Công thức Euler cải tiến y o = y(x0) h h i yi+1 = yi +
f (xi, yi) + f (x 2 i+1, y∗ i+1) với = y y∗i+1
i + h f xi, yi Nhận xét:
Sai số 1 bước của CT Euler hiện là o(h2)
Sai số 1 bước của CT Euler cải tiến là o(h3) Ví dụ: 2x , 0 y′ = y −
≤ x ≤ 0, 2 (h = 0, 1) y y(0) = 1
Giải gần đúng sử dụng CT Euler cải tiến. Giải: 2 Ta có: x
f (x, y) = y − ; x 0, 1; y0 1; X = 0, 2 y 0 = 0; h = =
Áp dụng CT Euler cải tiến: 24 Trần Hiếu LATEX ! h 2x 2x y 0 0 1 = y0 + y + f , y . y 2 0 − x0 + h 0 + h 0 − y 0 y0 0, 1 = 1 +
1 + f (0, 1; 1, 1) 2 0, 1 2.0, 1 = 1 + 1 + 1, 1 − = 1, 0959091 2 1, 1 h y 2 = y1 + f x + f x 2 1, y1
1 + h, y1 + h. f x1, y1 0, 1 2.0, 1 = 1, 0959091 + 1, 0959091 − + f (0, 2; 1, 1872413) 2 1, 0959091 = 1, 184096
6.2 Phương pháp Runge-Kutta bậc 3 (RK3)
Sai số 1 bước là o(h4) y0 = y(x0) 1 y Ki i+1
= yi + 6 1 + 4Ki2 + Ki3
trong đó Ki1 = h f (xi, yi) ! h Ki Ki , 1 2 = h f xi + y 2 i + 2
Ki3 = h f xi + h, yi − Ki1 + 2Ki2
6.3 Phương pháp Runge-Kutta bậc 4 (RK4)
Sai số 1 bước là o(h5) y0 = y(x0) 1 y Ki i+1
= yi + 6 1 + 2Ki2 + 2Ki3 + Ki4
trong đó Ki1 = h f (xi, yi) ! h Ki Ki , 1 2 = h f xi + y 2 i + 2 ! h Ki Ki , 2 3 = h f xi + y 2 i + 2
Ki4 = h f xi + h, yi + Ki3 25 Trần Hiếu LATEX Ví dụ: y′
= x + y, 0 ≤ x ≤ 0, 1 y(0) = 1 với h = 0, 1 Giải:
Ta có: f (x, y) = x + y; x0 = 0; X = 0, 1; h = 0, 1; y 1. 0 = Áp dụng CT RK4 ta có: y0 = 1; 1 y
(K1 + 2K2 + 2K3 + K4) 1 = y0 + 6 trong đó K
1 = h f x0; y0 = 0, 1(0 + 1) = 0, 1 0, 1 0, 1 K2 = h f x0 + ; y
= 0, 1(0, 05 + 1 + 0, 05) = 0, 11 2 0 + 2 0, 1 0, 11 K3 = h f x0 + ; y
= 0, 1(0, 05 + 1 + 0, 05) = 0, 1105 2 0 + 2 K
4 = h f 0, 1 + x0; y0 + 0, 1105 = 0, 12105
Thay số ⇒ y1 = 1, 11034
6.4 Hệ phương trình vi phân
y′(x) = f (x, y, z)
z′(x) = g(x, y, z)
y(x0) = y0, z(x0) = z0
Lần lượt áp dụng các phương pháp cho mỗi phương trình, chú ý tính nghiệm y T i, zi
theo thứ tự các nút xi từ thấp đến cao. Ví dụ khi áp dụng phương pháp Euler, ta có:
y(xi+1) = y(xi) + h f (xi, y(xi), z(x i))
z(xi+1) = z(xi) + hg(xi, y(xi), z(xi))
y(x0) = y0; z(x0) = z0 26 Trần Hiếu LATEX 6.5 PTVP bậc cao
y′′(x) = f1(x)y′ + f2(x)y + f3(x) ′ ′
y(x0) = y0, y (x0) = y0
Thực hiện đổi biến y′ = z ⇒ y′′ = z′
PTVP được chuyển về hệ:
y′(x) = z(x)
z′(x) = f1(x)z + f2(x)y + f3(x)
y(x0) = y0, z(x0) = y′(x0) 27