Tài liệu Phương pháp newton - raphson giải hệ phương trình phi tuyến

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 Trần Thị Phương Lan PHƯƠNG PHÁP NEWTON - RAPHSON GIẢI HỆ PHƯƠNG TRÌNH PHI TUYẾN LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Giải tích Mã số: 60 46 01 Người hướng dẫn: TS. Nguyễn Văn Hùng Hà Nội - 2010 LỜI CẢM ƠN Luận văn này được thực hiện và hoàn thành tại trường Đại học sư phạm Hà Nội 2. Trước hết, tác giả xin bày tỏ sự kính trọng, lòng biết ơn sâu sắc tới thầy giáo TS. Nguyễn Văn Hùng đã luôn hướng dẫn và chỉ bảo chu đáo, tận tình, nghiêm khắc trong suốt quá trình tác giả học tập và nghiên cứu luận văn. Tác giả xin chân thành cảm ơn Ban giám hiệu, phòng Sau đại học, trường Đại học sư phạm Hà Nội 2 cũng như toàn thể các thầy cô giáo trong trường đã quan tâm và dành cho tác giả những điều kiện tốt nhất trong thời gian học tập và nghiên cứu tại đây. Tác giả xin chân thành cảm ơn sự giúp đỡ, tạo điều kiện của Ban Giám Hiệu Trường THPT Tam Đảo, THPT Phúc Yên. Tác giả xin chân thành cảm ơn các ý kiến đóng góp xác đáng của các thầy giáo phản biện để luận văn được hoàn thiện hơn. Tác giả xin bày tỏ lòng biết ơn tới gia đình, người thân đã động viên và tạo mọi điều kiện để tác giả có thể hoàn thành bản luận văn này. Hà Nội, tháng 9 năm 2010 Tác giả LỜI CAM ĐOAN Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi, được hoàn thành dưới sự hướng dẫn của TS. Nguyễn Văn Hùng. Trong khi nghiên cứu luận văn, tôi đã kế thừa thành quả khoa học của các nhà khoa học nghiên cứu với sự trân trọng biết ơn. Hà Nội, tháng 9 năm 2010 Tác giả Mục lục Mở đầu 1 Chương 1. Một số kiến thức chuẩn bị 3 1.1. Sai số tuyệt đối, sai số tương đối . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Chữ số chắc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4. Sai số tính toán . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5. Sai số do phương pháp tính toán . . . . . . . . . . . . . . . . 8 1.2. Sai số thu gọn 1.6. Xấp xỉ ban đầu . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7. Ma trận nghịch đảo . . . . . . . . . . . . . . . . . . . . . . . . 13 1.8. Các định luật cơ bản của hóa học áp dụng cho các hệ trong dung dịch chất điện li . . . . . . . . . . . . . . . . . . . . . . 16 1.8.1. Định luật hợp thức . . . . . . . . . . . . . . . . . . . . 16 1.8.2. Định luật bảo toàn vật chất . . . . . . . . . . . . . . . 18 1.8.3. Định luật tác dụng khối lượng . . . . . . . . . . . . . . 20 Chương 2. Phương pháp Newton - Raphson giải hệ phương trình phi tuyến 23 2.1. Cơ sở lí thuyết . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.1. Phương pháp lặp Newton-Raphson . . . . . . . . . . . 23 2.1.2. Cách giải hệ phương trình phi tuyến bằng phương pháp lặp Newton - Raphson . . . . . . . . . . . . . . . . . . 24 2.2. Ví dụ áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Chương 3. Ứng dụng của phương pháp Newton - Raphson 32 3.1. Giải hệ phi tuyến 2 ẩn . . . . . . . . . . . . . . . . . . . . . . 32 3.2. Giải hệ phi tuyến 3 ẩn . . . . . . . . . . . . . . . . . . . . . . 40 3.3. Tính cân bằng trong các hệ oxi hóa- khử phức tạp . . . . . . . 46 Kết luận 57 Tài liệu tham khảo 58 MỞ ĐẦU 1. Lý do chọn đề tài Trong khoa học công nghệ và trong thưc tế có rất nhiều bài toán được chuyển thành bài toán giải hệ phương trình fi (x1 , x2 , . . . , xn ) = 0 (i = 1, 2, . . . , n) (1) Tuy nhiên, chỉ trong một số trường hợp đặc biệt ta mới có cách tìm nghiệm đúng của hệ phương trình đó, các trường hợp còn lại đều phải tìm cách giải gần đúng. Nếu hệ phương trình đó xuất phát từ bài toán thực tế thì biểu thức fi (x1 , x2 , . . . , xn )(i = 1, n) của hệ (1) thường cũng chỉ biết gần đúng. Vì thế việc giải đúng hệ phương trình đó chẳng những không thực hiện nổi mà nhiều khi không có ý nghĩa. Đối với lớp các bài toán đó thì việc xác định sai số là một vấn đề đáng quan tâm. Phương pháp Newton - Raphson giải hệ phương trình phi tuyến là phương pháp có lời giải hay, có thể áp dụng cho mọi hệ, đặc biệt những hệ càng phức tạp thì phương pháp này càng tỏ ra ưu việt. Hơn nữa, nếu lựa chọn xấp xỉ ban đầu tốt thì phương pháp này cho kết quả rất nhanh và chính xác. Qua nghiên cứu về phương pháp này chúng ta thấy mình hiểu biết về kiến thức giải tích ở phổ thông một cách rõ ràng, sâu sắc hơn trước rất nhiều. Đồng thời cũng thấy được một phần ứng dụng ưu việt của nó trong nghành hóa học phân tích khi tính cân bằng các hệ oxi hóa - khử phức tạp. Vì vậy với mong muốn tìm hiểu sâu sắc hơn nữa phương pháp này tôi mạnh dạn chọn nghiên cứu đề tài: "Phương pháp Newton - Raphson giải hệ phương trình phi tuyến ". 2. Mục đích nghiên cứu Nghiên cứu một cách có hệ thống kiến thức cơ bản của phương pháp Newton - Raphson giải hệ phương trình phi tuyến. Sau đó vận dụng phương pháp này giải một số hệ phương trình phi tuyến 2 ẩn, 3 ẩn, tính toán cân bằng các hệ oxi hóa khử phức tạp. 2 3. Nhiệm vụ nghiên cứu - Giải hệ phi tuyến bằng phương pháp Newton - Raphson. - Tính toán cân bằng các hệ oxi hóa khử theo phương pháp Newton Raphson . 4. Đối tượng và phạm vi nghiên cứu - Nghiên cứu một cách có hệ thống kiến thức cơ bản của phương pháp Newton - Raphson giải hệ phương trình phi tuyến. - Tính cân bằng các hệ oxi hóa khử theo phương pháp Newton - Raphson. Luận văn được chia làm 3 chương ( ngoài phần mở đầu, kết luận và tài liệu tham khảo ) Chương 1: Một số kiến thức bổ trợ. Chương 2: Phương pháp Newton - Raphson giải hệ phương trình phi tuyến. Chương 3: Ứng dụng của phương pháp Newton - Raphson. 5. Phương pháp nghiên cứu - Phương pháp giải gần đúng của lý thuyết giải tích số. - Phương pháp phân tích định tính và định lượng của hóa học. 6. Những đóng góp mới của đề tài - Tính cân bằng các hệ oxi hóa khử theo phương pháp Newton - Raphson giải hệ phương trình phi tuyến. Chương 1 Một số kiến thức chuẩn bị 1.1. Sai số tuyệt đối, sai số tương đối Trong tính toán, ta thường phải làm việc với các giá trị gần đúng của các đại lượng. Ta nói a là số gần đúng của a∗ , nếu a không sai khác a∗ nhiều. Đại lượng ∆a = |a − a∗ | gọi là sai số thật sự của a. Nói chung chúng ta không biết a∗ nên ta cũng không biết ∆a. Tuy nhiên ta có thể tìm được ∆a ≥ 0, gọi là sai số tuyệt đối của a, thỏa mãn điều kiện: |a − a∗ | ≤ ∆a (1.1) hay a − ∆a ≤ a∗ ≤ a + ∆a. Đương nhiên ∆a thỏa mãn điều kiện ( 1.1) càng nhỏ càng tốt. Hai số gần đúng có cùng sai số tuyệt đối sẽ có mức độ chính xác khác nhau nếu độ lớn của chúng khác nhau, số bé hơn sẽ có độ chính xác kém hơn. Để biểu diễn chính xác điều này người ta dùng khái niệm sai số tương đối, được kí hiệu là δa và xác định như sau: δa = ∆a |a| Ví dụ 1.1. Giả sử a∗ = π, a = 3, 14. Do 3, 14 ≤ a∗ ≤ 3, 15 = 3, 14 + 0, 01 nên ta có thể lấy ∆a = 0, 01. Mặt khác, 3, 14 ≤ π ≤ 3, 141 = 3, 14 + 0, 001 do đó có thể coi ∆a = 0, 001. Ví dụ 1.2. Đo độ dài hai đoạn thẳng AB, CD ta được a = 10cm và b = 1cm với ∆a = ∆b = 0, 01. Khi đó ta có δa = 0,01 10 = 0, 1% còn δb = 0,01 1 = 1% hay δa = 10δb. Hiển nhiên rằng phép đo a chính xác hơn hẳn phép đo b mặc dù 4 ∆a = ∆b. Như vậy độ chính xác của một phép đo phản ánh qua sai số tương đối. 1.2. Sai số thu gọn Một số thập phân a có dạng tổng quát như sau: a = ±(βp 10p + βp−1 10p−1 + · · · + βp−s 10p−s ) trong đó 0 ≤ βi ≤ 9(i = p − 1, p − s); βp > 0 là những số nguyên. Nếu p − s ≥ 0 thì a là số nguyên; p − s = −m(m ≥ 0) thì a có phần thập phân gồm m chữ số. Nếu s = ∞, a là số thập phân vô hạn. Thu gọn một số a là vứt bỏ một số các chữ số bên phải a để được một số a ngắn gọn hơn và gần đúng nhất với a. Quy tắc thu gọn: Giả sử a = βp 10p + · · · + βj 10j + · · · + βp−s 10p−s và ta giữ lại đến số hạng thứ j. Gọi phần vứt bỏ là µ, ta đặt a = βp 10p + . . . + βj+1 10j+1 + β̃j 10j trong đó ( β̃j = βj + 1 nếu 0, 5 × 10j < µ < 10j βj nếu 0 ≤ µ < 0, 5 × 10j Nếu µ = 0, 5 × 10j thì ( β˜j = βj nếu βj là chẵn βj + 1 nếu βj là lẻ Ví dụ 1.3. π ≈ 3, 141592 ≈ 3, 14159 ≈ 3, 1416 ≈ 3, 142 ≈ 3, 14 ≈ 3, 1 ≈ 3. Sai số thu gọn Γa thỏa mãn điều kiện: |a − a| ≤ Γa Vì a = βp 10p + . . . + βj 10j + µ 5 còn a = βp 10p + · · · + βj+1 10j+1 + β̃j 10j , nên |a − a| = |(βj − β̃j )10j + µ| < 0, 5 × 10j . Sau khi thu gọn, sai số tuyệt đối tăng lên: |a − a| ≤ |a∗ − a| + |a − a| ≤ ∆a + Γa . 1.3. Chữ số chắc Chữ số có nghĩa là mọi chữ số khác " 0 " và cả "0", nếu nó kẹp giữa hai chữ số có nghĩa hoặc nó đại diện cho hàng được giữ lại. Ví dụ 1.4. a = 0,0030140. Ba chữ số " 0 " đầu không có nghĩa. Mọi chữ số có nghĩa βi của a = ±(βp 10p + βp−1 10p−1 + · · · + βp−s 10p−s ) gọi là chữ số chắc, nếu ∆a ≤ ω × 10i trong đó ω là tham số cho trước. Tham số ω được chọn để một chữ số vốn đã chắc sau khi thu gọn vẫn là chữ số chắc. Giả sử chữ số chắc cuối cùng của a trước khi thu gọn là βi . Để βi+1 và các chữ số trước nó vẫn chắc, phải có ∆a + Γa ≤ ω × 10i+1 . Suy ra ω × 10i + 0, 5 · 10i+1 ≤ ω × 10i+1 hay ω ≥ 95 . Ta sẽ gọi chữ số chắc theo nghĩa hẹp (rộng) nếu ω = 0, 5(ω = 1). Khi viết số gần đúng, chỉ nên giữ lại một hoặc hai chữ số không chắc để khi tính toán, sai số chỉ tác động đến chữ số không chắc thôi. 1.4. Sai số tính toán Khi giải bài toán ta phải thực hiện các phép tính thông thường và luôn luôn phải làm tròn các kết quả trung gian. Sai số tạo ra bởi tất cả các lần làm tròn như vậy gọi là sai số tính toán. Trong tính toán ta thường gặp bốn loại sai số sau: 6 1. Sai số giả thiết: Do mô hình hóa, lí tưởng hóa các bài toán thực tế, sai số này không loại trừ được. 2. Sai số phương pháp: Các bài toán thường gặp rất phức tạp, không thể giải đúng được mà phải sử dụng các phương pháp gần đúng. Sai số này sẽ được nghiên cứu cho từng phương pháp cụ thể. 3. Sai số các số liệu: Các số liệu thường thu được bằng thực nghiệm do đó có sai số. Sai số của các số liệu gần đúng đã được nghiên cứu trong mục 1.1. 4. Sai số tính toán: Các số vốn đã có sai số, còn thêm sai số thu gọn nên khi tính toán sẽ xuất hiện sai số tính toán. Giả sử tìm được đại lượng y theo công thức: y = f (x1 , x2 , . . . , xn ) Gọi x∗i , y ∗ (i = 1, n) và xi , y(i = 1, n) là các giá trị đúng và gần đúng của đối số và hàm số. Nếu f khả vi liên tục thì ∗ |y − y | = |f (x1 , x2 , . . . , xn ) − f (x∗1 , x∗2 , . . . , x∗n )| = n X |fi0 ||xi − x∗i | i=1 trong đó fi0 là đạo hàm ∂f ∂xi tính tại các điểm trung gian. Do khá bé, ta có thể coi ∆y = n X |fi0 (x1 , x2 , . . . , xn )|∆xi . i=1 Do đó δy = ∆y |y| = n P | ∂x∂ i lnf |∆xi . i=1 Sau đây là sai số của phép tính cơ bản: a) Sai số các phép tính cộng, trừ: Giả sử tính y= n X xi ta có i=1 nên ∆y = n X i=1 ∂f =1 ∂xi ∆xi . ∂f ∂xi liên tục, ∆xi 7 Trường hợp tổng đại số rất nhỏ, nghĩa là |y| << 1 thì ∂y = n P ∆xi i=1 |y| >> 1, do đó kết quả không chính xác. Ta khắc phục bằng cách tránh công thức đưa đến hiệu của hai số gần nhau. b) Sai số của phép tính nhân chia: Giả sử x 1 . . . xp xp+1 . . . xn p n P P lny = lnxi − lnxj y= Khi đó i=1 suy ra δy = j=p+1 n P δxi . và ∆y = |y|δy. i=1 c) Sai số của phép tính lũy thừa, khai căn, nghịch đảo d lny|∆x = |α|δx. Cho y = xα , khi đó δy = | dx - Nếu α > 1 ( phép lũy thừa ) thì δy > δx, do đó độ chính xác giảm. - Nếu 0 ≤ α < 1 ta có phép khai căn, khi đó δy < δx, hay độ chính xác tăng. - Nếu α = 1, ta có phép nghịch đảo, δy = δx, nghĩa là độ chính xác không đổi. Ví dụ 1.5. Diện tích hình vuông S = 12,34; ∆S = 0, 01 tính cạnh a. √ Ta có a = S ≈ 3, 5128. Vì Nên ∂S = ∆S S = 0,01 12,34 ≈ 0, 0008 ∆a ≈ 3, 5128 × 0, 0004 ≈ 1, 4 × 10−3 Như vậy a có 4 chữ số chắc và a ≈ 3, 513. 8 Ví dụ 1.6. Hãy tính tổng: A= 1 1 1 1 1 1 − + − + − 13 23 33 43 53 63 Giải . A là tổng của 6 phân số. Ta có thể tính trực tiếp A mà không cần phải thay nó bằng một tổng đơn giản hơn. Vì vậy ở đây nó không có sai số phương pháp. Để tính A ta thực hiện phép chia đến ba chữ số thập phân và đánh giá các sai số quy tròn tương ứng: 1 13 1 23 1 33 1 43 1 53 1 63 = = = = = = 1 = 1, 000 với θ1 = 0 1 1 = 0, 125 với θ2 = 0 8 1 = 0, 037 với θ3 = 10−4 27 1 = 0, 016 với θ4 = 4 × 10−4 64 1 = 0, 008 với θ5 = 0 125 1 = 0, 005 với θ6 = 4 × 10−4 216 Vậy A ≈ a = 1, 000 − 0, 125 + 0, 037 − 0, 016 + 0, 008 − 0, 005 = 0, 899. |A − a| ≤ | 113 − 1| + | 213 − 0, 125| + | 313 − 0, 037| + | 413 − 0, 016| + | 513 − 0, 008| 1 − 0, 005| 63 ≤ θ1 + θ2 + θ3 + θ4 + θ5 + θ6 = 9 × 10−4 +| Do đó a = 0, 899 là giá trị gần đúng của A với sai số tính toán 9 × 10−4 . Ta viết A ≈ 0, 899 ± 9 × 10−4 1.5. Sai số do phương pháp tính toán Khi giải gần đúng một bài toán phức tạp ta phải thay một bài toán đã cho bằng một bài toán đơn giản hơn có thể giải được thông qua việc thực hiện 9 các phép tính thông thường. Phương pháp thay bài toán phức tạp bằng bài toán đơn giản hơn như thế gọi là phương pháp gần đúng. Sai số do phương pháp gần đúng tạo ra gọi là sai số phương pháp. Ví dụ 1.7. Hãy tính tổng P = 1 1 1 n−1 1 − + − · · · + (−1) ··· 13 23 33 n3 với sai số tuyệt đối không vượt quá 5 × 10−3 . Giải . Vế phải của P là một chuỗi số đan dấu hội tụ. Do đó việc tính P là hợp lí. Nhưng vế phải của P có vô hạn số hạng, ta không thể cộng hết số này đến số khác mãi được. Do đó để tính P ta phải sử dụng một phương pháp gần đúng, cụ thể P thay bằng tổng n số hạng đầu P ≈ 1 1 1 n−1 1 − + − · · · + (−1) . 13 23 33 n3 Bài tính Pn đơn giản hơn bài toán tính P . Lúc đó |P −Pn | là sai số phương pháp, và số n được chọn sao cho sai số phương pháp ấy cộng với sai số tính toán vẫn còn nhỏ hơn 5 × 10−3 . Ta có: |P − Pn | ≈ | 1 1 1 − + · · · | < . (n + 1)3 (n + 2)3 (n + 1)3 (theo lí thuyết chuỗi đan dấu). Vì vậy với n = 6 ta thấy : |P − Pn | ≤ 1 1 = < 3 × 10−3 . 3 7 343 Ta chú ý rằng P6 = A đã tính ở trên (xem ví dụ 1.6 ) P6 ≈ A ≈ 0, 899 ± 9 × 10−4 . Vậy có thể lấy P ≈ 0, 899. Để xét sai số ta có P − 0, 899 = P − P6 + A − 0, 899. |P − 0, 899| ≤ |P − P6 | + |A − 0, 899|. |P − 0, 899| ≤ |3 × 10−3 + 9 × 10−4 ≤ 4 × 10−3 . 10 Vậy ta tính đượcP ≈ 0, 899. với sai số tuyệt đối không vượt quá 4 × 10−3 P = 0, 899 ± 9 × 10−4 . Qua ví dụ 1.6 và ví dụ trên ta thấy sai số tổng hợp cuối cùng có phần của sai số phương pháp và có phần của sai số tính toán. 1.6. Xấp xỉ ban đầu Thông thường quá trình tìm nghiệm r của phương trình f (x) = 0 (1.2) ( ở đây f ( x ) là hàm thực một biến x ) được chia làm hai phần. Một là, phần xấp xỉ ban đầu của nghiệm ( thường được gọi là nghiệm xấp xỉ ). Hai là, tinh chế nghiệm xấp xỉ đó để có được một nghiệm xấp xỉ mới có độ chính xác mong muốn. Việc tìm xấp xỉ ban đầu x0 cho nghiệm r của phương trình (1.2) thường do sự dự đoán dựa trên thông tin về hàm f có được, hoặc bằng cách vẽ đồ thị tìm điểm x0 sao cho f (x0 ) ≈ 0. Ngoài ra, ta cũng có thể tìm được x0 dựa vào định lý sau: Nếu f ( x ) là một hàm thực liên tục trên [ a ; b], (a < b ), có f (a)·f (b) < 0 thì tồn tại ít nhất một nghiệm r của f( x ) trong khoảng (a;b). Việc tìm một đoạn [ a ; b] như vậy gọi là cô lập nghiệm. Bây giờ ta xét một số thuật toán tìm xấp xỉ ban đầu cho nghiệm thực của phương trình đại số có dạng: f (x) = Pn (x) = a0 xn + a1 xn−1 + · · · + an−1 x + an = 0 (1.3) với các hệ số thực ai (i = 0, n). Phương trình đại số (1.3) nói chung , có thể có các ngiệm thực khác nhau hoặc nghiệm thực kép. Nếu ta kí hiệu nghiệm của (1.3) là các số r1 , r2 , . . . , rn thì Pn (x) có thể viết dưới dạng: Pn (x) = a0 (x − r1 )(x − r2 )(x − r3 ) · · · (x − rn ) Giả thiết rằng: |r1 | > |r2 | > . . . > |rn | 11 Nếu các nghiệm ri có môđun khác nhau nhiều, thì xấp xỉ ban đầu của nghiệm có thể lấy từ định lý : X a1 = − ri ; a0 X a3 ri rj rk ; =− a0 X a2 = − ri rj ; a0 i - Xem thêm -