MathLabs

Toán ứng dụng và Tính toán

Giải gần đúng phương trình

Các phương pháp số như chia đôi và Newton, tìm nghiệm mà máy tính có thể tính từng bước.

Trực giácTrực giác: phóng to gần một nghiệm

Giả sử bạn đang tìm một nghiệm rr của phương trình f(x)=0f(x)=0, nhưng không có công thức đại số nào cho ra rr một cách chính xác. Một phương pháp số xây dựng một dãy các phỏng đoán x0,x1,x2,…x_0, x_1, x_2,\dots tiến gần rr hơn ở mỗi bước, giống như việc phóng to liên tục đồ thị của ff về phía điểm nó cắt trục hoành cho phép bạn đọc ra ngày càng nhiều chữ số thập phân đúng. Ba phương pháp dưới đây chỉ khác nhau ở cách chúng biến phỏng đoán hiện tại xnx_n thành phỏng đoán tốt hơn tiếp theo xn+1x_{n+1}.

Một đường cát tuyến qua hai điểm gần nhau trên đường cong xoay dần thành đường tiếp tuyến khi bước nhảy tiến về 0, minh họa ý tưởng hình học đằng sau phương pháp Newton.
Kéo bước nhảy hh của đường cát tuyến về gần 0 và quan sát nó tiến sát vào đường tiếp tuyến tại x0x_0 với hệ số góc f′(x0)f'(x_0): đây chính là đường tiếp tuyến mà phương pháp Newton đi theo để tới phỏng đoán tiếp theo x1=x0−f(x0)f′(x0)x_1 = x_0 - \dfrac{f(x_0)}{f'(x_0)}, thay vì hệ số góc cát tuyến thô hơn f(x0+h)−f(x0)h\dfrac{f(x_0+h)-f(x_0)}{h}.

Đại họcĐịnh nghĩa: ba phương pháp tìm nghiệm

Định nghĩa: Phương pháp chia đôi

Nếu một hàm liên tục ff thỏa mãn f(a)f(b)<0f(a)f(b)<0 trên khoảng [a,b][a,b], định lý giá trị trung gian đảm bảo có một nghiệm bên trong. Phương pháp chia đôi chia đôi khoảng này ở mỗi bước: tính điểm giữa c=a+b2c=\dfrac{a+b}{2}, tính f(c)f(c), rồi giữ lại nửa nào vẫn còn đổi dấu và lặp lại.

∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}}

Ở đây ∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}} chặn khoảng cách mà điểm giữa thứ nn, tức xnx_n, có thể cách nghiệm thực rr: vì chiều rộng khoảng L=b−aL=b-a giảm một nửa ở mỗi bước, sai số xấu nhất cũng giảm một nửa, nên chỉ sau n=4n=4 bước, độ bất định co lại còn L/32L/32. Tốc độ co lại đảm bảo, dự đoán được này chính là sức hấp dẫn của phương pháp chia đôi — nó không bao giờ thất bại trong việc hội tụ, dù chậm.

Định nghĩa: Phương pháp Newton

Phương pháp Newton thay đường cong gần xnx_n bằng đường tiếp tuyến của nó y=f(xn)+f′(xn)(x−xn)y=f(x_n)+f'(x_n)(x-x_n) và lấy phỏng đoán tiếp theo xn+1x_{n+1} là nơi đường tiếp tuyến đó cắt trục hoành, cho công thức lặp xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}. Nó cần đạo hàm f′f' ở mỗi bước nhưng hội tụ nhanh hơn nhiều so với chia đôi khi nó hoạt động.

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}

Cách nhìn thứ ba hợp nhất cả hai: viết lại phương trình thành bài toán điểm bất động x=g(x)x=g(x) với một hàm gg nào đó, sao cho một nghiệm của ff trở thành một điểm bất động của gg, rồi lặp xn+1=g(xn)x_{n+1} = g(x_n) bắt đầu từ bất kỳ x0x_0 nào. Cả chia đôi và Newton đều là trường hợp riêng của ý tưởng này với những lựa chọn khác nhau của gg.

So sánh ba phương pháp tìm nghiệm
Phương phápCông thức lặpBậc hội tụĐiều kiện
Chia đôic=a+b2c=\dfrac{a+b}{2}Tuyến tính (11)ff liên tục, f(a)f(b)<0f(a)f(b)<0
Newtonxn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}Bậc hai (22)ff khả vi hai lần, f′(r)≠0f'(r) \ne 0, x0x_0 gần rr
Lặp điểm bất độngxn+1=g(xn)x_{n+1} = g(x_n)Tuyến tính (11), nói chung∣g′(x)∣≤L<1|g'(x)| \le L < 1 gần rr

Đại họcCác định lý then chốt

Định lý: Sự hội tụ và chặn sai số của phương pháp chia đôi

Cho ff liên tục trên [a,b][a,b] với f(a)f(b)<0f(a)f(b)<0. Khi đó phương pháp chia đôi tạo ra các điểm giữa xn=an+bn2x_n=\dfrac{a_n+b_n}{2} với xn→rx_n \to r tới một nghiệm rr nào đó trong [a,b][a,b], và sai số sau nn bước thỏa ∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}}.

Vì sao đúng?

Mỗi bước đều nhốt nghiệm bên trong một hộp đang co lại, và một hộp co lại thành một điểm mà luôn chứa nghiệm bên trong thì phải co lại đúng ngay tại nghiệm đó.

Chứng minh

Bước 1 (bất biến). Đặt a0=aa_0=a, b0=bb_0=b. Ở bước nn, ta duy trì bất biến rằng f(an)f(bn)<0f(a_n)f(b_n)<0, tức nghiệm bị nhốt ở đâu đó trong [an,bn][a_n,b_n]. Điều này đúng ban đầu theo giả thiết. Từ [an,bn][a_n,b_n], tính điểm giữa xn=an+bn2x_n=\dfrac{a_n+b_n}{2} và tính f(xn)f(x_n): nếu nó trái dấu với f(an)f(a_n) thì đặt an+1=an, bn+1=xna_{n+1}=a_n,\ b_{n+1}=x_n, ngược lại đặt an+1=xn, bn+1=bna_{n+1}=x_n,\ b_{n+1}=b_n (nếu f(xn)=0f(x_n)=0 đúng bằng 0, thì xnx_n chính là nghiệm và quá trình dừng lại). Dù thế nào thì f(an+1)f(bn+1)<0f(a_{n+1})f(b_{n+1})<0 lại đúng, nên bất biến được bảo toàn bằng quy nạp.

Bước 2 (chiều rộng co lại). Theo cách xây dựng, mỗi khoảng mới đúng bằng một nửa khoảng trước, nên bn−an=b−a2nb_n-a_n = \dfrac{b-a}{2^n} với mọi n≥0n \ge 0. Vì nghiệm rr nằm trong [an,bn][a_n,b_n] ở mọi bước (theo Bước 1), và điểm giữa xnx_n cũng nằm trong [an,bn][a_n,b_n], cả hai cùng nằm trong một khoảng có chiều rộng b−a2n\dfrac{b-a}{2^n} so với nhau, nên ∣xn−r∣≤b−a2n|x_n - r| \le \dfrac{b-a}{2^n} đã đúng; một cách đếm chặt hơn một chút (đo từ điểm giữa tới một trong hai đầu mút) cho chặn đã nêu ∣xn−r∣≤b−a2n+1|x_n - r| \le \dfrac{b-a}{2^{n+1}}.

Bước 3 (hội tụ). Vì b−a2n+1→0\dfrac{b-a}{2^{n+1}} \to 0 khi n→∞n\to\infty, phép kẹp ở Bước 2 buộc xn→rx_n \to r. Phần này thậm chí không cần tính liên tục của ff ngoài điều kiện đổi dấu ban đầu — nó chỉ cần cho việc đảm bảo có một nghiệm tồn tại bên trong [a,b][a,b] ngay từ đầu, đó là định lý giá trị trung gian áp dụng ở bước 0.

Định lý: Sự hội tụ bậc hai của phương pháp Newton

Giả sử ff khả vi liên tục hai lần gần một nghiệm rr với f′(r)≠0f'(r) \ne 0. Khi đó tồn tại một lân cận của rr sao cho, nếu phép lặp Newton bắt đầu bên trong lân cận đó, các giá trị lặp hội tụ về rr và thỏa ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2 với một hằng số C=max⁡∣f′′∣2min⁡∣f′∣C=\dfrac{\max|f''|}{2\min|f'|} (giá trị lớn nhất và nhỏ nhất lấy trên lân cận đó).

Vì sao đúng?

Đường tiếp tuyến là một xấp xỉ tốt đến mức sai số nó gây ra tỉ lệ với bình phương khoảng cách đã đi qua, nên mỗi chữ số đúng gần như nhân đôi số chữ số đúng ở bước tiếp theo.

Chứng minh

Bước 1 (khai triển Taylor quanh phỏng đoán hiện tại). Vì ff khả vi hai lần, định lý Taylor với phần dư Lagrange cho f(r)=f(xn)+f′(xn)(r−xn)+12f′′(ξn)(r−xn)2f(r) = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2 với một ξn\xi_n between xnx_n and rr nào đó. Đây là đẳng thức chính xác, không phải xấp xỉ, vì số hạng dư mang toàn bộ sai số bậc hai.

Bước 2 (thay điều kiện nghiệm). Vì f(r)=0f(r)=0, vế trái triệt tiêu, còn lại 0=f(xn)+f′(xn)(r−xn)+12f′′(ξn)(r−xn)20 = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2. Chia cả hai vế cho f′(xn)f'(x_n) (khác 0 gần rr vì f′(r)≠0f'(r) \ne 0 và f′f' liên tục) tách được r−xnr - x_n: 0=f(xn)f′(xn)+(r−xn)+f′′(ξn)2f′(xn)(r−xn)20 = \dfrac{f(x_n)}{f'(x_n)} + (r-x_n) + \dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2.

Bước 3 (nhận ra bước Newton). Sắp xếp lại, r−(xn−f(xn)f′(xn))=−f′′(ξn)2f′(xn)(r−xn)2r - \left(x_n - \dfrac{f(x_n)}{f'(x_n)}\right) = -\dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2. Dấu ngoặc bên trái chính là bước cập nhật Newton xn+1x_{n+1}, nên với en=xn−re_n = x_n - r điều này viết thành r−xn+1=−f′′(ξn)2f′(xn) en2r - x_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2, tức en+1=−f′′(ξn)2f′(xn) en2e_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2.

Bước 4 (chặn hằng số). Lấy giá trị tuyệt đối và chặn ∣f′′(ξn)∣|f''(\xi_n)| và 1/∣f′(xn)∣1/|f'(x_n)| bởi các giá trị cực trị max⁡∣f′′∣\max|f''| và 1/min⁡∣f′∣1/\min|f'| trên lân cận cho ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2 với C=max⁡∣f′′∣2min⁡∣f′∣C=\dfrac{\max|f''|}{2\min|f'|}. Một khi C ∣x0−r∣<1C\,|x_0-r| < 1, đệ quy này buộc ∣xn−r∣|x_n - r| co lại về 00, chứng minh sự hội tụ, và việc bình phương trong ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2 chính là tốc độ bậc hai.

Định lý: Sự hội tụ của lặp điểm bất động

Cho g:[a,b]→[a,b]g:[a,b]\to[a,b] khả vi liên tục với ∣g′(x)∣≤L<1|g'(x)| \le L < 1 với mọi x∈[a,b]x\in[a,b]. Khi đó gg có một điểm bất động duy nhất rr trong [a,b][a,b], và với mọi điểm xuất phát x0∈[a,b]x_0 \in [a,b], phép lặp xn+1=g(xn)x_{n+1}=g(x_n) hội tụ về rr với ∣xn−r∣≤Ln∣x0−r∣|x_n - r| \le L^n |x_0 - r|.

Vì sao đúng?

Hệ số góc nhỏ hơn một về giá trị tuyệt đối nghĩa là mỗi lần áp dụng g đều ép các điểm lại gần nhau hơn, nên dù bắt đầu ở đâu, việc ép lặp đi lặp lại phải làm cả khoảng thu lại thành một điểm duy nhất.

Chứng minh

Bước 1 (tồn tại nhờ định lý giá trị trung gian). Đặt h(x)=g(x)−xh(x)=g(x)-x. Vì g(a)∈[a,b]g(a)\in[a,b] nên g(a)≥ag(a)\ge a tức h(a)≥0h(a)\ge0, tương tự g(b)≤bg(b)\le b cho h(b)≤0h(b)\le0. Vì hh liên tục, định lý giá trị trung gian cho một rr nào đó với h(r)=0h(r)=0, tức g(r)=rg(r)=r: tồn tại một điểm bất động.

Bước 2 (duy nhất nhờ định lý giá trị trung bình). Giả sử r1,r2∈[a,b]r_1,r_2\in[a,b] đều là điểm bất động với r1≠r2r_1\ne r_2. Định lý giá trị trung bình cho một cc nào đó nằm giữa chúng với g(r1)−g(r2)=g′(c)(r1−r2)g(r_1)-g(r_2) = g'(c)(r_1-r_2); vì g(r1)=r1g(r_1)=r_1 và g(r2)=r2g(r_2)=r_2, điều này viết thành r1−r2=g′(c)(r1−r2)r_1-r_2 = g'(c)(r_1-r_2), nên ∣r1−r2∣=∣g′(c)∣ ∣r1−r2∣≤L ∣r1−r2∣|r_1-r_2| = |g'(c)|\,|r_1-r_2| \le L\,|r_1-r_2|. Vì L<1L<1 và ∣r1−r2∣>0|r_1-r_2|>0, đây là một mâu thuẫn, nên r1=r2r_1=r_2.

Bước 3 (co lại ở mỗi bước). Với bất kỳ xn∈[a,b]x_n\in[a,b] nào, áp dụng định lý giá trị trung bình cho g(xn)−g(r)g(x_n)-g(r): có một cnc_n nào đó nằm giữa xnx_n và rr với g(xn)−g(r)=g′(cn)(xn−r)g(x_n)-g(r) = g'(c_n)(x_n-r). Vì g(r)=rg(r)=r và xn+1=g(xn)x_{n+1}=g(x_n), vế trái là xn+1−rx_{n+1}-r, nên ∣xn+1−r∣=∣g′(cn)∣ ∣xn−r∣≤L ∣xn−r∣|x_{n+1}-r| = |g'(c_n)|\,|x_n-r| \le L\,|x_n-r|.

Bước 4 (lặp lại sự co). Áp dụng Bước 3 nhiều lần từ n=0n=0 cho ∣x1−r∣≤L∣x0−r∣|x_1-r|\le L|x_0-r|, rồi ∣x2−r∣≤L∣x1−r∣≤L2∣x0−r∣|x_2-r|\le L|x_1-r|\le L^2|x_0-r|, và bằng quy nạp ∣xn−r∣≤Ln∣x0−r∣|x_n - r| \le L^n |x_0 - r| với mọi nn. Vì 0≤L<10\le L<1, vế phải tiến về 00 khi n→∞n\to\infty, chứng minh xn→rx_n\to r.

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Tìm nghiệm là động cơ ẩn phía sau vô số phép tính không có đáp án dạng đóng. Các kỹ sư dùng phương pháp Newton để giải hệ phi tuyến trong thiết kế kết cấu và mạch điện; ngành tài chính dùng nó để suy ra lãi suất chưa biết từ giá trái phiếu hoặc độ biến động ngụ ý từ giá quyền chọn; đồ họa máy tính dùng nó để tìm giao điểm của tia sáng với các mặt ẩn; và mọi máy tính khoa học đều tính 2\sqrt{2} hay căn bậc ba bằng cách chạy ngầm vài bước của phương pháp Newton. Chia đôi, vì luôn chắc chắn, là phương án dự phòng dùng bên trong các thư viện tìm nghiệm bất cứ khi nào phương pháp Newton có nguy cơ phân kỳ.

Ví dụ: Chia đôi cho một phương trình bậc ba không có công thức nghiệm đại số

Vị trí cân bằng của một hệ cơ học thỏa mãn x3−x−2=0x^3-x-2=0. Dùng khoảng [1,2][1,2] (nơi f(1)=−2<0f(1)=-2<0 và f(2)=4>0f(2)=4>0), thực hiện hai bước chia đôi và cho biết điểm giữa kết quả x2x_2.

Lời giải

Bước 1: tính điểm giữa đầu tiên. x0=1+22=1.5x_0 = \dfrac{1+2}{2} = 1.5, và f(1.5)=1.53−1.5−2=−0.125<0f(1.5) = 1.5^3 - 1.5 - 2 = -0.125 < 0, nên nghiệm nằm trong [1.5,2][1.5, 2] vì ff đổi dấu ở đó (f(1.5)<0f(1.5)<0, f(2)>0f(2)>0).

Bước 2: tính điểm giữa thứ hai. x1=1.5+22=1.75x_1 = \dfrac{1.5+2}{2} = 1.75, và f(1.75)=1.753−1.75−2=1.609375>0f(1.75) = 1.75^3 - 1.75 - 2 = 1.609375 > 0, nên nghiệm nằm trong [1.5,1.75][1.5, 1.75].

Bước 3: tính x2x_2. x2=1.5+1.752=1.625x_2 = \dfrac{1.5+1.75}{2} = 1.625.

Bước 4: diễn giải. Chỉ sau hai bước, khoảng tìm kiếm đã co từ chiều rộng 11 xuống 0.250.25, và x2=1.625x_2=1.625 đã cách nghiệm thực r≈1.5214r\approx1.5214 không quá 0.1250.125, phù hợp với chặn sai số ∣x2−r∣≤2−123=0.125|x_2-r|\le \dfrac{2-1}{2^{3}}=0.125 từ định lý chia đôi.

Ví dụ: Phương pháp Newton tính căn bậc hai bằng tay

Trước khi có máy tính, các kỹ sư tính căn bậc hai theo cách này: để tìm 5\sqrt{5}, áp dụng phương pháp Newton cho f(x)=x2−5f(x)=x^2-5 bắt đầu từ x0=2x_0=2, và tính x1x_1 và x2x_2.

Lời giải

Bước 1: thiết lập phép lặp. Ở đây f(x)=x2−5f(x)=x^2-5 và f′(x)=2xf'(x)=2x, nên công thức cập nhật Newton là xn+1=xn−xn2−52xnx_{n+1}=x_n-\dfrac{x_n^2-5}{2x_n}.

Bước 2: tính x1x_1. Với x0=2x_0=2: x1=2−22−52⋅2=2−−14=2.25x_1 = 2 - \dfrac{2^2-5}{2\cdot2} = 2 - \dfrac{-1}{4} = 2.25.

Bước 3: tính x2x_2. Với x1=2.25x_1=2.25: x2=2.25−2.252−52⋅2.25=2.25−0.06254.5≈2.236111x_2 = 2.25 - \dfrac{2.25^2-5}{2\cdot2.25} = 2.25 - \dfrac{0.0625}{4.5} \approx 2.236111.

Bước 4: diễn giải. Giá trị thực là 5≈2.236068\sqrt{5}\approx2.236068, nên x2x_2 đã đúng tới bốn chữ số thập phân chỉ sau hai bước — số chữ số đúng gần như nhân đôi từ x1x_1 tới x2x_2, đặc trưng của sự hội tụ bậc hai đã chứng minh ở trên.

Bắt đầu chia đôi trên [a,b]=[0,1][a,b]=[0,1] và thực hiện n=5n=5 lần lặp, chặn đảm bảo cho ∣x5−r∣|x_5 - r| là bao nhiêu?

Công thức nào đúng cho một bước của phương pháp Newton?

Một nhà giao dịch trái phiếu dùng phương pháp Newton để giải phương trình định giá phi tuyến P(y)=0P(y)=0 tìm lợi suất yy, bắt đầu từ phỏng đoán y0y_0. Tình huống nào có khả năng cao nhất khiến phép lặp không hội tụ?

Để phép lặp điểm bất động xn+1=g(xn)x_{n+1} = g(x_n) trên [a,b][a,b] được đảm bảo hội tụ về một điểm bất động với bất kỳ x0∈[a,b]x_0 \in [a,b] nào, điều kiện nào là cần thiết?