Tài liệu Một số phương pháp giải gần đúng hệ phương trình tuyến tính

Khóa luận tốt nghiệp Khoa Toán LỜI CẢM ƠN Tôi xin chân thành cảm ơn thầy giáo Nguyễn Văn Hùng đã tận tình hướng dẫn giúp đỡ tôi trong suốt thời gian thực hiện khóa luận. Xin chân thành cảm ơn các thầy, các cô trong tổ Giải tích-Khoa Toán, Trường Đại học Sư phạm Hà Nội 2 đã tạo mọi điều kiện giúp đỡ tôi hoàn thành khóa luận này. Xin chân thành cảm ơn gia đình và bạn bè đã tạo mọi điều kiện thuận lợi cho tôi trong quá trình thực hiện khóa luận. Tôi xin chân thành cảm ơn! Hà Nội, tháng 05 năm 2010 Sinh viên Nguyễn Thị Ngọc Nguyễn Thị Ngọc 1 Lớp K32C Khóa luận tốt nghiệp Khoa Toán LỜI CAM ĐOAN Tôi xin cam đoan khoá luận là công trình nghiên cứu của riêng tôi. Trong khi nghiên cứu, tôi đã kế thừa những thành quả nghiên cứu của các nhà khoa học, nhà nghiên cứu với sự chân trọng và biết ơn. Những kết quả nêu trong khoá luận chưa được công bố trên bất kỳ công trình nào khác. Hà Nội, tháng 05 năm 2010 Sinh viên Nguyễn Thị Ngọc Nguyễn Thị Ngọc 2 Lớp K32C Khóa luận tốt nghiệp Khoa Toán MỤC LỤC Nội dung Lời cảm ơn ...................................................................................................... 1 Lời cam đoan ................................................................................................... 2 Lời nói đầu ...................................................................................................... 4 Chương 1: Một số kiến thức cơ bản ................................................................ 6 1.1. Số gần đúng và sai số .............................................................................. 6 1.2. Hệ phương trình tuyến tính ..................................................................... 13 1.3. Phân tích sai số ........................................................................................ 15 Chương 2: Một số phương pháp giải gần đúng hệ phương trình tuyến tính. 17 2.1. Phương pháp Gauss ................................................................................ 17 2.2. Phương pháp Cholesky .......................................................................... 25 2.3. Phương pháp trực giao hóa .................................................................... 29 2.4. Phương pháp lặp đơn ............................................................................. 32 2.5. Phương pháp Jacobi ............................................................................... 37 2.6. Phương pháp Seidel ............................................................................... 41 2.7. Phương pháp Gauss-Seidel .................................................................... 46 Chương 3: Bài tập áp dụng ............................................................................. 49 Kết luận Tài liệu tham khảo Nguyễn Thị Ngọc 3 Lớp K32C Khóa luận tốt nghiệp Khoa Toán LỜI NÓI ĐẦU Toán học là một môn khoa học bắt nguồn từ nhu cầu giải quyết bài toán có nguồn gốc thực tiễn và quay trở lại phục vụ thực tiễn. Cùng với thời gian và sự tiến bộ của loài người toán học ngày càng phát triển và được chia thành hai lĩnh vực đó là toán học lý thuyết và toán học ứng dụng. Nói đến toán học ứng dụng phải kể đến Giải tích số-môn học nghiên cứu các phương pháp giải gần đúng các bài toán thực tế được mô hình hoá bằng ngôn ngữ toán học. Để có lời giải đúng cho bất kì bài toán nào cũng cần phải có dữ kiện của bài toán, xây dựng mô hình bài toán, tìm thuật toán hiệu quả nhất. Và cuối cùng là xây dựng chương trình trên máy tính sao cho tiết kiệm thời gian và bộ nhớ. Tuy nhiên trong thời gian sử lý số liệu không tránh khỏi sai số dù là rất nhỏ nhưng ảnh hưởng trực tiếp đến quá trình tính toán. Chính vì vậy phải sử dụng các thuật toán hữu hiệu để giảm thiểu sự sai số đồng thời thuận lợi cho công việc lập trình tiết kiệm số lượng các phép tính và thời gian tính toán. Phương pháp số có ý nghĩa rất lớn trong đại số tuyến tính, đặc biệt là đối với việc giải hệ phương trình tuyến tính. Khi số các phương trình lớn các phương pháp truyền thống nhiều khi gặp khó khăn, chúng ta không thể giải quyết một cách chính xác mà chỉ có thể đưa ra lời giải gần đúng cho một bài toán. Các nhà toán học đã tìm ra nhiều phương pháp để giải gần đúng hệ phương trình tuyến tính. Hệ phương trình tuyến tính có dạng tổng quát là hệ gồm m phương trình n ẩn. Trong khuôn khổ khoá luận này em xin trình bày mảng nhỏ đó là hệ n phương trình, n ẩn. Nguyễn Thị Ngọc 4 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Với lòng yêu thích toán học, đam mê nghiên cứu khoa học em đã quyết định chọn đề tài cho mình là: “Một số phương pháp giải gần đúng hệ phương trình tuyến tính”. Có khá nhiều phương pháp giải hệ phương trình tuyến tính nhưng do mới bước đầu làm quen với việc nghiên cứu khoa học và thời gian nghiên cứu còn ít nên trong khuôn khổ khoá luận này em xin trình bày một số vấn đề sau: Chương 1: Một số kiến thức cơ bản về sai số, làm tròn số, số gần đúng, hệ phương trình tuyến tính, tập nghiệm của hệ phương trình, số điều kiện của ma trận, phân tích sai số. Chương 2: Một số phương pháp giải gần đúng hệ phường trình tuyến tính. Chương này gồm 7 phương pháp giải gần đúng hệ phương trình tuyến tính gồm phương pháp trực tiếp và các phương pháp lặp được trình bày theo thứ tự: cơ sở lý thuyết, thuật toán, ứng dụng và đánh giá sai số (nếu có). Chương 3: Bài tập áp dụng. Nguyễn Thị Ngọc 5 Lớp K32C Khóa luận tốt nghiệp Khoa Toán CHƢƠNG 1: MỘT SỐ KIẾN THỨC CƠ BẢN 1.1. Số gần đúng và sai số 1.1.1 Định nghĩa * Trong thực tế tính toán ta thường không biết số đúng a mà chỉ biết * số đủ gần nó là a . 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 được gọi là sai số thực sự của a . * Do không biết a nên  cũng không biết nhưng ta có thể tìm được số a  0 cho a*  a  a (1.1) Hay a  a  a*  a Số ∆ a thoả mãn (1.1) được gọi là sai số tuyệt đối của a . Tỉ số  a  a được gọi là sai số tương đối của a . a Ví dụ 1.1.1.1. Cho số a*   ; a  3.14 3.14  a  3.15; a  0.01 3.14  a*  3.142; a  0.002 Trong phép đo nói chung sai số tuyệt đối càng nhỏ càng tốt. Ví dụ 1.1.1. 2. Đo độ dài hai đoạn đường ta được: a  100m; a  0.5m b  6km; b  20m a  0.5 1 20 1  ; b   100 200 6000 300 Nguyễn Thị Ngọc 6 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Nhận xét: Từ ví dụ trên ta thấy rằng phép đo b chính xác hơn phép do a mặc dù a  b . Như vậy độ chính xác của phép đo phản ánh qua sai số tương đối. 1.1.2. Sai số thu gọn Xét số thập phân a được biểu diễn dưới dạng: a     p10 p   p 110 p 1  ....   p q 10 p q  Trong đó: 0  i  9;  p  0; p  1  i  p  q  Nếu p  q  0 thì a là số nguyên.  Nếu -   p  q  0 thì a là số thập phân có phần lẻ gồm p  q chữ số  Nếu p  q   thì a là số thập phân vô hạn. Ví dụ 1.1.2.1. 4087  4  103  0  102  8  101  7  100 Ta thấy: p  q  0 nên a =4083 là số nguyên. Ví dụ 1.1.2.2. 31.8783  3  101  1 100  8  101  7  102  8  103  3  104 Ta thấy : p  q = 4 nên a =31.8783 là số thập phân có phần lẻ gồm 4 chữ số.  Thu gọn a là vứt bỏ một số các chữ số bên phải của a để được số ngắn gọn hơn nhưng vẫn đảm bảo độ chính xác cần thiết.  Quy tắc thu gọn Giả sử: a    p10 p   j 110 j 1  ...   j 10 j  ...   p q10 p q  Nguyễn Thị Ngọc 7 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Giả sử ta muốn giữ lại đến hàng thứ j, gọi phần bỏ đi là M. Khi đó ta được số thu gọn là:  a   p 10 p   p 110 p 1  ...   j 10 j   j  0  M  0.5 10 j   Trong đó:  j   j j  j 1  0.5 10  M  10  Nếu M=0.5  10j thì  j   j nếu  j là chẵn và  j   j 1 nếu  j là lẻ vì tính toán với số chẵn tiện hơn. Ví dụ 1.1.2.3.   3.141592654  3.14159265  3.1415926  3.141592  3.14159  3.1415  3.141  3.14  3.1  3  Giả sử số thu gọn của a là a . Ta có a  a  a a*  a  a*  a  a  a  a*  a  a  a  a  a . Từ đánh giá trên ta có nhận xét: Khi thu gọn số a thì sai số tuyệt đối * * của a với a lớn hơn hoặc bằng sai số tuyệt đối của a và a . 1.1.3. Chữ số có nghĩa, chữ số chắc. 1.1.3.1. Chữ số có nghĩa Chữ số có nghĩa là mọi chữ số khác 0 và cả chữ số 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.1.3.1.   0.000870190 Bốn chữ số 0 ở vị trí đầu tiên là những chữ số không có nghĩa, toàn bộ những chữ số còn lại là những chữ số có nghĩa. 1.1.3.2. Chữ số chắc p p 1 p q Xét số a     p10   p 110  ...   p q10  Nguyễn Thị Ngọc 8 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Chữ số  j được gọi là chữ số chắc nếu a    10i . Với  là 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. Ví dụ 1.1.3.2. a  1.70134 a  0.001  103 Khi đó: a  1  100  7  101  0  102  1  103  3  104  4  105 Chọn   1 thì a có bốn chữ số chắc là 1,7,0,1 còn lại hai chữ số không chắc là 3,4. Nếu chọn   1 thì a có ba chữ số chắc là 1,7,0 còn ba chữ số 1,3,4 là 2 không chắc. Ta xét việc chọn  . Giả sử a được viết dưới dạng: a     p10 p   p110 p1  ...   pq10 pq  Ta chọn  sao cho sau khi thu gọn đến bậc (i+1) thì i 1 vẫn là chắc Muốn vậy phải có: a  a    10i 1   10i  0.5  10i 1    10i 1   5  10    5 9 Trong thực tế người ta chọn   1 hoặc   1 2 Nếu   1 người ta nói chữ số là chắc theo nghĩa rộng, còn khi   người ta nói chữ số là chắc theo nghĩa hẹp. Nguyễn Thị Ngọc 9 Lớp K32C 1 2 Khóa luận tốt nghiệp Khoa Toán Lưu ý: Khi viết số gần đúng ta chỉ nên giữ lại một hai chữ số không chắc để khi tính toán sai số chỉ tác động đến những chữ số không chắc mà thôi. 1.1.4. Sai số tính toán Giả sử ta phải tính đại lượng y theo công thức: y  f  x1 , x2 ,..., xn  .   * * * * * * Gọi x   x1 , x2 ,..., xn  ; y  f x là các giá trị đúng. Giả sử ta không biết các giá trị đúng này, mà ta chỉ biết các giá trị x   x1, x2 ,..., xn  ; y  f  x  * * lần lượt là các giá trị gần đúng của x và y . Giả sử xi ; xi (với i=1,2,...,n) là các sai số tuyệt đối và tương đối của các đối số. Khi đó sai số của hàm y  f  x1, x2 ,..., xn  được gọi là các sai số tính toán. Giả sử f  x1, x2 ,..., xn  là hàm số khả vi liên tục thì: y  y  y*  f  x1 , x2 ,..., xn   f  x1* , x2* ,..., xn*  n       f x'i x1 , x2 ,..., xn xi  xi* 1 Với x  x1 , x2 ,..., xn là điểm nằm giữa x và x * . Vì f khả vi liên tục và xi  xi  x * i n ' khá bé nên y   f xi  x  xi với x   x1, x2 ,..., xn  i 1 y n     ln f  x  xi y Vậy: y i 1 xi và cũng có thể viết (1.1.4)  y   ln y 1.1.4.1. Sai số của phép toán cộng, trừ: n Nếu y   xi thì yx' i  1 với i=1,…,n. i 1 Nguyễn Thị Ngọc 10 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Vậy ta có: n n y   f xi  x1  x2  ...  xn   xi i 1 ' xi i 1 n (1.1.4.1) Chú ý rằng nếu tổng đại số y   xi bé về giá trị tuyệt đối thì i 1 y lớn, y phép tính sẽ kém 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. Ví dụ: y  2.01  2.00 Ta có: y  0.01 0.01   0.0035. 2.01  2.00 1.42  1.41 1.1.4.2. Sai số của phép toán nhân, chia:  Sai số của phép nhân Xét: y  x1 x2 ...xn Ta có: y  x1 x2 ... xn ln y  ln x1  ln x2  ...  ln xn Từ (1.1.4.1) ta có:  ln y   ln x1   ln x2  ...   ln xn  y   x1   x2  ...   xn Từ (1.1.4) suy ra: y  y  y Vậy sai số tương đối của một tích bằng tổng các sai số tương đối của các số hạng thành phần.  Sai số của phép chia Xét : y x1 x2 Nguyễn Thị Ngọc 11 Lớp K32C Khóa luận tốt nghiệp ' Ta có: yxi  Khoa Toán x 1 ' ; y x2  21 x2 x2 x2 x1  x1 x2 ;  y   x1   x2 x22 Suy ra: y  1.1.4.3. Sai số của phép tính luỹ thừa  Xét y  x    , x  0  , khi đó  y    x Như vậy nếu   1 thì độ chính xác là giảm đi, nếu   1 thì độ chính xác tăng lên. Nếu   1 (phép nghịch đảo) thì độ chính xác là không đổi, 1 * nếu   , k   (phép khai căn) thì độ chính xác tăng lên. k 1.1.4.4. Sai số của phép tính logarit. Xét y=lnx, ta có y   x Ví dụ: Biết diện tích hình vuông S=12.34 và S  0.01. Hãy tính cạnh của hình vuông. Gọi x là cạnh hình vuông, thì x  S  3.513 . Xét  S  S  0.008 , S 3 vậy x  1.4 10 , từ đó ta thấy rằng x có 3 chữ số chắc (trừ chữ số 3 cuối cùng). 1.1.5. Bài toán ngược của bài toán sai số Giả sử đại lượng y được tính theo công thức: y= f  x1 , x2 ,..., xn  . Cần tính xi để y   ; (   0 ) cho trước. Theo công thức tổng quát của sai số tính toán ta phải có: n y   i 1 f xi   xi suy ra xi   n f x'i Nguyễn Thị Ngọc 12 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Kết luận: Nếu các biến xi có vai trò “đều nhau” thì ta có thể lấy xi   n f x'i , khi đó y   . Ví dụ: Một hình trụ có chiều cao h  3m , bán kính đáy R  2m . Tìm h, R , số  để thể tích V được tính chính xác đến 0.1m3. Ta có: V =  R2h, nên có: Vậy   1.2 V V V   R 2 .. =R2h, =2  Rh, h R  0.1 0,1  0.03 ; R   0.001 ; h  0,1  0, 003 . 3 4  3 3.6 .2 3. .4 Hệ phƣơng trình đại số tuyến tính 1.2.1 Dạng tổng quát của hệ phương trình tuyến tính Một hệ phương trình tuyến tính tổng quát là hệ có m phương trình n ẩn. Ở đây ta chỉ xét những hệ n phương trình , n ẩn. Nghĩa là chỉ xét hệ có dạng: Ax  b (2.1) Trong đó: A  nn là ma trận cấp n  n b   n là vectơ cho trước x   n là vectơ nghiệm cần tìm Hay viết dưới dạng tường minh: a11 x1  a12 x2  ...  a1n xn  b1 a x  a x  ...  a x  b  21 1 22 2 2n n 2  .......... an1 x1  an 2 x2  ...  ann xn  bn 1.2.2. Định lý về sự tồn tại và duy nhất nghiệm Gọi det Ai là định thức suy ra từ định thức det A bằng cách thay cột thứ i bởi vế phải. Nguyễn Thị Ngọc 13 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Nếu det A =0 ta nói ma trận A suy biến và hệ (2.1) suy biến. Khi đó hệ phương trình vô nghiệm hoặc vô số nghiệm. Định lý (định lý Cramer): Nếu det A  0 tức là hệ không suy biến thì hệ (2.1) có nghiệm duy nhất cho bởi công thức: xi  det Ai với i=1,2,…,n det A 1.2.3. Biện luận về số nghiệm Cho hệ phương trình (2.1) với ma trận hệ số A và ma trận bổ sung  Nếu rank A  rank Abs thì hệ vô nghiệm.  Nếu rank A =rank Abs = r thì có 2 trường hợp: r = n và r < n 1. Trường hợp r = n Hệ phương trình đã cho có dạng: a11' x1  a12'  ...  a1' n  b1'  ' ' ' a22 x2  ...  a2 n  b2  ..... a '  b' n  nn ' ' ' Trong đó: a11 , a22 ,..., ann  0 Hệ này có nghiệm duy nhất. 2. Trường hợp r < n Hệ phương trình đã cho có dạng: a11' x1  a12' x2  ...  a1' n  b1'  ' ' ' a22 x2  ...  a2 n xn  b2  ..... a '  ...  a '  b' rn r  rr Nguyễn Thị Ngọc 14 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Cho các ẩn xr 1, xr 2 ,..., xn (là các ẩn tự do) những giá trị tuỳ ý ta tính được x1, x2 ,..., xr qua các ẩn tự do đó. Điều đó chứng tỏ hệ phương trình có vô số nghiệm. Tóm lại: - Nếu rankA  rankAbs : hệ vô nghiệm. - Nếu rankA  rankAbs  n : hệ phương trình có nghiệm duy nhất. - Nếu rankA  rankAbs  n : hệ phương trình có vô số nghiệm. 1.3. Phân tích sai số 1.3.1. Số điều kiện của ma trận Xét A   aij i , j 1 và x là một chuẩn nào đó của vectơ n Kí hiệu: M  sup x 0 x  Rn Ax Ax , m  inf x 0 x x Từ kết quả của giải tích hiện đại ta có: A  M , hơn nữa nếu m  0 thì ma trận A không suy biến, do đó ma trận A có ma trận nghịch đảo A1 và m  A1 1 Định nghĩa Đại lượng M  A A1 được gọi là số điều kiện của ma trận A và đại m lượng đó kí hiệu là cond ( A) . Ma trận A được gọi là ma trận điều kiện xấu nếu cond( A ) là khá lớn cond ( A)  1. Tính chất của số điều kiện: 1. cond ( A)  1 . 2. Nếu A là ma trận trực giao thì cond ( A)  1. 3. c  0 thì cond (cA)  cond ( A) Nguyễn Thị Ngọc 15 Lớp K32C Khóa luận tốt nghiệp Khoa Toán 4. Nếu D  diag  di i 1 thì cond  D   n max di min di 1.3.2. Phân tích sai số Giả sử x là nghiệm của phương trình: Ax  b (2.1) x '  x  x là nghiệm của phương trình Ax '  b' với b'  b  b Khi đó: x  Suy ra x  1 A  x  m Do đó x  1 b . m x  Vậy: A(x) 1 1 1 A(x) 1 x  inf x   A(x) m m x0 x m x m b 1 1 M x  Ax  . M M M x M b b   cond ( A) x mb b (3.2) Ước lượng (3.2) chứng tỏ rằng sai số tương đối của nghiệm có thể bằng tích của cond(A) với sai số của vế phải. Từ đó suy ra rằng với ma trận A điều kiện xấu thì nghiệm của nó thay đổi nhiều so với những thay đổi nhỏ ở hệ số và số hạng tự do. Như vậy, vấn đề giải hệ phương trình tuyến tính bằng số với ma trận điều kiện xấu và vế phải cho gần đúng là một bài toán khó của toán học tính toán. Nguyễn Thị Ngọc 16 Lớp K32C Khóa luận tốt nghiệp Khoa Toán CHƢƠNG 2: MỘT SỐ PHƢƠNG PHÁP GIẢI GẦN ĐÚNG HỆ PHƢƠNG TRÌNH TUYẾN TÍNH Cho hệ phương trình tuyến tính Ax  b (2.1) Giả thiết detA  0 hệ có nghiệm duy nhất. Ta có thể tìm nghiệm của hệ (2.1) theo phương pháp Cramer hoặc sử dụng ma trân nghịch đảo nhưng những cách này đòi hỏi phép tính khá lớn và không thuận lợi khi ma trận A điều kiện xấu. Nhằm khắc phục hạn chế đó trong chương này chúng ta xét một số phương pháp thực tế giải hệ phương trình (2.1) với đặc điểm là khối lượng tính toán được giảm nhẹ. Trong số các phương pháp đó có thể chia ra làm 2 nhóm lớn là: - Nhóm phương pháp trực tiếp: phương pháp Gauss, trực giao hoá Hilbert-Schmidt, Cholesky. - Nhóm phương pháp gián tiếp: lặp đơn, Jacobi, phương pháp Seidel và Gauss-Seidel. Đặc điểm: - Nhóm phương pháp trực tiếp là sau một số hữu hạn phép tính sẽ cho ta kết quả, vì vậy nhóm phương pháp này thường được áp dụng với các bài toán có kích cỡ nhỏ, và các số liệu ban đầu là đúng. Tuy nhiên, do phải thực hiện một số phép tính tương đối là lớn nên có nguy cơ tích lũy sai số, nhất là đối với trường hợp số liệu ban đầu không thật chính xác. - Nhóm phương pháp gián tiếp (phương pháp lặp) thường được áp dụng cho lớp các bài toán có kích cỡ lớn, số liệu ban đầu có sai số. 2.1. Phƣơng pháp Gausss 2.1.1. Cơ sở lý thuyết Cho hệ phương trình tuyến tính Ax  b (2.1) Dạng toạ độ của (2.1) là: Nguyễn Thị Ngọc 17 Lớp K32C Khóa luận tốt nghiệp n a x j 1 ij j Khoa Toán  ai ,n 1 (i=1,2,…,n) (2.1.1) Tư tưởng của phương pháp Gauss là đưa hệ phương trình (2.1) về dạng tam giác trên, khi đó nghiệm tìm được nhờ quá trình thế ngược. Quá trình đưa hệ phương trình (2.1) về một hệ tương đương dạng tam giác trên được gọi là quá trình xuôi. Như vậy phương pháp Gauss được thực hiện theo 2 quá trình sau đây: Quá trình xuôi: đưa hệ (2.1) về dạng tam giác nhờ phép biến đổi tương đương Quá trình ngược: Tìm từ hệ tam giác xn , xn1, ..., x1 . Các công thức tính toán: aij k   aij k 1  aik k 1bkj k 1  i, j  k   k 1 bkj (2.1.3) akj k 1   k 1 ( j  k ) akk (2.1.4)  Lưu ý: Phương pháp Gauss thực hiện được nếu akk k 1  0 k  1,..., n trong đó: a11   a11 0 Sau đây ta kiểm tra các công thức (2.1.2), (2.1.3), (2.1.4) cho trường hợp n=4. Hệ phương trình tuyến tính 4 phương trình, 4 ẩn có dạng: a11 x1  a12 x2  a13 x3  a14 x4  a15 a x  a x  a x  a x  a  21 1 22 2 23 3 24 4 25  a31 x1  a32 x2  a33 x3  a34 x4  a35 a41 x1  a42 x2  a43 x3  a44 x4  a45 (2.1.5) Giả sử a11  0. Chia hai vế của phương trình đầu trong hệ (2.1.5) cho a11 (phần tử dẫn) ta được: Nguyễn Thị Ngọc 18 Lớp K32C Khóa luận tốt nghiệp Khoa Toán x1  b12 0 x2  b13 0 x3  b14 0  b15 0   Trong đó: b1 j  0 a1 j a11 (2.1.6) (j>1) Như vậy công thức (2.1.4) với k=1 đã được chứng minh Từ (2.1.6) và (2.1.5) khử x1 : 1 1 1 1 a22 x2  a23 x3  a24 x4  a25  1 1 1 1 a32 x2  a33 x3  a34 x4  a35  1 1 1 1 a42 x2  a43 x3  a44 x4  a45 (2.1.5.1) Trong đó: aij1  aij  ai1b1 0j  (i,j  2)  Chia hai vế của phương trình đầu (2.1.5.1) cho phần tử dẫn a22 ta được 1 1 1 1 1 x2  b23 x3  b24 x4  b25 với b2 j  a21j 1 a22 (j>2) Khử x2 khỏi hệ (2.1.5.1) ta được:  2  2  2 a33 x3  a34 x4  a35   2  2  2 a43 x3  a44 x4  a45 Trong đó: aij 2 (2.1.5.2)  aij   ai2b2 j với (i,j  3) 1 1 1   Chia hai vế phương trình đầu của hệ (2.1.5.2) cho phần tử dẫn a33 ta 2 được: x3  b34 2  b35 2  2 b3 j  Trong đó: a3 2j  2 a33 với ( j> 3) Cuối cùng khử x3 khỏi phương trình thứ hai của (2.1.5.2) ta được     a44 x4  a45 3 Nguyễn Thị Ngọc 3 19 Lớp K32C Khóa luận tốt nghiệp Khoa Toán Trong đó: aij3  aij 2  ai32b3 2j  ; i, j  4 Từ (2.1.5.2) ta có: x4   3 a45  3  b45  3 a44 Bước thuận kết thúc. Thực hiện bước ngược ta tính lần lượt:  2 x3  b45  b34 2 x4 x2  b251  b241 x4  b231 x3 x1  b15 0  b14 0 x4  b13 0 x3  b12 0 x2 2.1.2. Sơ đồ tính toán Xét hệ phương trình tuyến tính Ax  b Hay viết dưới dạng tường minh: a11 x1  a12 x2  ....  a1n xn  b1 a x  a x  ....  a x  b  21 1 22 2 2n n 2  ............. an1 x1  an 2 x2  ....  ann xn  bn Quá trình xuôi: k 1 0 Nếu akk   0 k  1, 2,..., n (trong đó: a11   a11 ) thì dừng lại quá trình tính toán và thông báo hệ suy biến. k 1 Nếu tồn tại k để akk   0 thì áp dụng công thức (2.1.4) để đưa hệ đã cho về hệ tam giác trên: a11 n 1 x1  a12 n 1 x2  ....  a1nn 1 xn  b1 n 1   n 1 n 1 n 1 a22 x2  ....  a2 n  xn  b2   .............   n 1  n 1 ann xn  bn Ta viết gọn lại thành: Nguyễn Thị Ngọc 20 Lớp K32C