Phụ lục 2: Phương pháp Gauss giải hệ phương trình đại số tuyến tính
a ...
hay Ax = b (*)
A=aij=a11a12...a1na21a22...a2n............an1an2...ann size 12{A= left (a rSub { size 8{ ital "ij"} } right )= left (" " matrix { a rSub { size 8{"11"} } {} # a rSub { size 8{"12"} } {} # "." "." "." {} # a rSub { size 8{1n} } {} ## a rSub { size 8{"21"} } {} # a rSub { size 8{"22"} } {} # "." "." "." {} # a rSub { size 8{2n} } {} ## "." "." "." {} # "." "." "." {} # "." "." "." {} # "." "." "." {} ## a rSub { size 8{n1} } {} # a rSub { size 8{n2} } {} # "." "." "." {} # a rSub { size 8{ ital "nn"} } {} } " " right )} {}; b=b1b2...bn size 12{b= left (" " matrix { b rSub { size 8{1} } {} ## b rSub { size 8{2} } {} ## "." "." "." {} ## b rSub { size 8{n} } } " " right )} {}; x=x1x2...xn size 12{x= left (" " matrix { x rSub { size 8{1} } {} ## x rSub { size 8{2} } {} ## "." "." "." {} ## x rSub { size 8{n} } } " " right )} {}.
Nếu ma trận A size 12{A} {} không suy biến, tức
thì hệ (*) có nghiệm duy nhất. Có thể tính nghiệm theo công thức Cramer
xi=detAidetA size 12{x rSub { size 8{i} } " "=" " { {"det" A rSub { size 8{i} } } over {"det" A} } } {},
trong đó Ai− size 12{A rSub { size 8{i} } - {}} {} ma trận A size 12{A} {} với cột i size 12{i} {} bị thay thế bằng cột các số hạng tự do b size 12{b} {}.
Thí dụ cho hệ
a11x1+a12x2+a13x3+a14x4=a15a21x1+a22x2+a23x3+a24x4=a25a31x1+a32x2+a33x3+a34x4=a35a41x1+a42x2+a43x3+a44x4=a45}}} size 12{alignl { stack { left none a rSub { size 8{"11"} } x rSub { size 8{1} } +a rSub { size 8{"12"} } x rSub { size 8{2} } +a rSub { size 8{"13"} } x rSub { size 8{3} } +a rSub { size 8{"14"} } x rSub { size 8{4} } =a rSub { size 8{"15"} } {} # right rbrace left none a rSub { size 8{"21"} } x rSub { size 8{1} } +a rSub { size 8{"22"} } x rSub { size 8{2} } +a rSub { size 8{"23"} } x rSub { size 8{3} } +a rSub { size 8{"24"} } x rSub { size 8{4} } =a rSub { size 8{"25"} } {} # right rbrace left none a rSub { size 8{"31"} } x rSub { size 8{1} } +a rSub { size 8{"32"} } x rSub { size 8{2} } +a rSub { size 8{"33"} } x rSub { size 8{3} } +a rSub { size 8{"34"} } x rSub { size 8{4} } =a rSub { size 8{"35"} } {} # right rbrace left none a rSub { size 8{"41"} } x rSub { size 8{1} } +a rSub { size 8{"42"} } x rSub { size 8{2} } +a rSub { size 8{"43"} } x rSub { size 8{3} } +a rSub { size 8{"44"} } x rSub { size 8{4} } =a rSub { size 8{"45"} } {} # right rbra } } rbrace } {} (1)
Giả sử phần tử chính a11≠0 size 12{a rSub { size 8{"11"} } <> 0} {}. Chia phương trình thứ nhất cho a11 size 12{a rSub { size 8{"11"} } } {}, ta có
x1+b12x2+b13x3+b14x4=b15 size 12{x rSub { size 8{1} } +b rSub { size 8{"12"} } x rSub { size 8{2} } +b rSub { size 8{"13"} } x rSub { size 8{3} } +b rSub { size 8{"14"} } x rSub { size 8{4} } =b rSub { size 8{"15"} } } {}, (2)
với b1j=a1ja11(j=2,3,4,5) size 12{b rSub { size 8{1j} } = { {a rSub { size 8{1j} } } over {a rSub { size 8{"11"} } } } " " ( j=2, 3, 4, 5 ) } {}.
Dùng phương trình (2) để loại ẩn x1 size 12{x rSub { size 8{1} } } {} khỏi các phương trình số 2, 3, 4 của hệ (1): Muốn vậy, nhân phương trình (2) tuần tự với a21,a31,a41 size 12{a rSub { size 8{"21"} } , a rSub { size 8{"31"} } , a rSub { size 8{"41"} } } {} và tuần tự lấy các phương trình số 2, 3, 4 trừ đi các tích tương ứng vừa nhận được, ta có ba phương trình:
a22(1)x2+a23(1)x3+a24(1)x4=a25(1)a32(1)x2+a33(1)x3+a34(1)x4=a35(1)a42(1)x2+a43(1)x3+a44(1)x4=a45(1)}} size 12{alignl { stack { left none a rSub { size 8{"22"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{2} } +a rSub { size 8{"23"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{3} } +a rSub { size 8{"24"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{4} } =a rSub { size 8{"25"} } rSup { size 8{ ( 1 ) } } {} # right rbrace left none a rSub { size 8{"32"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{2} } +a rSub { size 8{"33"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{3} } +a rSub { size 8{"34"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{4} } =a rSub { size 8{"35"} } rSup { size 8{ ( 1 ) } } " " {} # right rbrace left none a rSub { size 8{"42"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{2} } +a rSub { size 8{"43"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{3} } +a rSub { size 8{"44"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{4} } =a rSub { size 8{"45"} } rSup { size 8{ ( 1 ) } } {} # right rbra } } rbrace } {} (3)
trong đó
aij(1)=aij−ai1b1j(i=2,3,4;j=2,3,4,5) size 12{a rSub { size 8{ ital "ij"} } rSup { size 8{ ( 1 ) } } =a rSub { size 8{ ital "ij"} } - a rSub { size 8{i1} } b rSub { size 8{1j} } " " ( i=2, 3, 4;" "j=2, 3, 4, 5 ) } {} (4)
Bây giờ chia phương trình thứ nhất của hệ (3) cho phần tử chính a22(1) size 12{a rSub { size 8{"22"} } rSup { size 8{ ( 1 ) } } } {} ta có:
x2+b23(1)x3+b24(1)x4=b25(1) size 12{x rSub { size 8{2} } +b rSub { size 8{"23"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{3} } +b rSub { size 8{"24"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{4} } =b rSub { size 8{"25"} } rSup { size 8{ ( 1 ) } } } {}, (5)
trong đó
b2j(1)=a2j(1)a22(1)(j=3, 4, 5) size 12{b rSub { size 8{2j} } rSup { size 8{ ( 1 ) } } = { {a rSub { size 8{2j} } rSup { size 8{ ( 1 ) } } } over {a rSub { size 8{"22"} } rSup { size 8{ ( 1 ) } } } } " " ( j=3 ital ", "4 ital ", "5 ) } {}.
Bằng cách tương tự như khi loại x1 size 12{x rSub { size 8{1} } } {}, bây giờ ta loại x2 size 12{x rSub { size 8{2} } } {} khỏi các phương trình thứ ba và thứ tư, ta có:
a33(2)x3+a34(2)x4=a35(2)a43(2)x3+a44(2)x4=a45(2)} size 12{alignl { stack { left none a rSub { size 8{"33"} } rSup { size 8{ ( 2 ) } } x rSub { size 8{3} } +a rSub { size 8{"34"} } rSup { size 8{ ( 2 ) } } x rSub { size 8{4} } =a rSub { size 8{"35"} } rSup { size 8{ ( 2 ) } } " " {} # right rbrace left none a rSub { size 8{"43"} } rSup { size 8{ ( 2 ) } } x rSub { size 8{3} } +a rSub { size 8{"44"} } rSup { size 8{ ( 2 ) } } x rSub { size 8{4} } =a rSub { size 8{"45"} } rSup { size 8{ ( 2 ) } } {} # right rbra } } rbrace } {}. (6)
trong đó
aij(2)=aij(1)−ai2(1)b2j(1)(i=3,4;j=3,4,5) size 12{a rSub { size 8{ ital "ij"} } rSup { size 8{ ( 2 ) } } =a rSub { size 8{ ital "ij"} } rSup { size 8{ ( 1 ) } } - a rSub { size 8{i2} } rSup { size 8{ ( 1 ) } } b rSub { size 8{2j} } rSup { size 8{ ( 1 ) } } " " ( i=3, 4;" "j=3, 4, 5 ) } {}. (7)
Chia phương trình thứ nhất của hệ (6) cho phần tử chính a33(2) size 12{a rSub { size 8{"33"} } rSup { size 8{ ( 2 ) } } } {}, ta có:
x3+b34(2)x4=b35(2) size 12{x rSub { size 8{3} } +b rSub { size 8{"34"} } rSup { size 8{ ( 2 ) } } x rSub { size 8{4} } =b rSub { size 8{"35"} } rSup { size 8{ ( 2 ) } } } {}, (8)
trong đó
b3j(2)=a3j(2)a33(2)(j=4,5) size 12{b rSub { size 8{3j} } rSup { size 8{ ( 2 ) } } = { {a rSub { size 8{3j} } rSup { size 8{ ( 2 ) } } } over {a rSub { size 8{"33"} } rSup { size 8{ ( 2 ) } } } } " " ( j=4, 5 ) } {}.
Sau đó nhờ (8) ta loại x3 size 12{x rSub { size 8{3} } } {} khỏi phương trình thứ hai của hệ (6), nhận được:
trong đó
a4j(3)=a4j(2)−a43(2)b3j(2)(j=4,5) size 12{a rSub { size 8{4j} } rSup { size 8{ ( 3 ) } } =a rSub { size 8{4j} } rSup { size 8{ ( 2 ) } } - a rSub { size 8{"43"} } rSup { size 8{ ( 2 ) } } b rSub { size 8{3j} } rSup { size 8{ ( 2 ) } } " " ( j=4, 5 ) } {} (9)
Như vậy ta đã đưa hệ (1) về hệ tương đương có ma trận các hệ số là ma trận tam giác
x1+b12x2+b13x3+b14x4=b15x2+b23(1)x3+b24(1)x4=b25(1)x3+b34(2)x4=b35(2)a44(3)x4=a45(3)}}} size 12{alignr { stack { left none x rSub { size 8{1} } +b rSub { size 8{"12"} } x rSub { size 8{2} } +b rSub { size 8{"13"} } x rSub { size 8{3} } +b rSub { size 8{"14"} } x rSub { size 8{4} } =b rSub { size 8{"15"} } " " {} # right rbrace left none x rSub { size 8{2} } +b rSub { size 8{"23"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{3} } +b rSub { size 8{"24"} } rSup { size 8{ ( 1 ) } } x rSub { size 8{4} } =b rSub { size 8{"25"} } rSup { size 8{ ( 1 ) } } " " {} # right rbrace left none x rSub { size 8{3} } +b rSub { size 8{"34"} } rSup { size 8{ ( 2 ) } } x rSub { size 8{4} } =b rSub { size 8{"35"} } rSup { size 8{ ( 2 ) } } " " {} # right rbrace left none a rSub { size 8{"44"} } rSup { size 8{ ( 3 ) } } x rSub { size 8{4} } =a rSub { size 8{"45"} } rSup { size 8{ ( 3 ) } } " " {} # right rbra } } rbrace } {} (10)
Từ (10) xác định các ẩn
x4=a45(3)/a44(3)x3=b35(2)−x4b34(2)x2=b25(1)−x4b24(1)−x3b23(1)x1=b15−x4b14−x3b13−x2b12}}} size 12{alignr { stack { left none x rSub { size 8{4} } = {a rSub { size 8{"45"} } rSup { size 8{ ( 3 ) } } } slash {a rSub { size 8{"44"} } rSup { size 8{ ( 3 ) } } ital " "} {} # right rbrace left none x rSub { size 8{3} } =b rSub { size 8{"35"} } rSup { size 8{ ( 2 ) } } - x rSub { size 8{4} } b rSub { size 8{"34"} } rSup { size 8{ ( 2 ) } } ital " " {} # right rbrace left none x rSub { size 8{2} } =b rSub { size 8{"25"} } rSup { size 8{ ( 1 ) } } - x rSub { size 8{4} } b rSub { size 8{"24"} } rSup { size 8{ ( 1 ) } } - x rSub { size 8{3} } b rSub { size 8{"23"} } rSup { size 8{ ( 1 ) } } ital " " {} # right rbrace left none x rSub { size 8{1} } =b rSub { size 8{"15"} } - x rSub { size 8{4} } b rSub { size 8{"14"} } - x rSub { size 8{3} } b rSub { size 8{"13"} } - x rSub { size 8{2} } b rSub { size 8{"12"} } ital " " {} # right rbra } } rbrace } {} (11)
Vậy thủ tục giải hệ phương trình đại số tuyến tính bậc nhất quy về hai quá trình:
a) Quá trình thuận: đưa hệ (1) về dạng tam giác (10);
b) Quá trình nghịch: tìm ẩn theo các công thức (11).
Nếu phần tử chính của hệ bằng không thì chỉ cần thay đổi chỗ của các phương trình trong hệ tương ứng để làm cho phần tử chính khác không.
Số phép tính số học N size 12{N} {} cần thực hiện trong phương pháp Gauss bằng
N=2n(n+1)(n+2)3+n(n−1) size 12{N= { {2n ( n+1 ) ( n+2 ) } over {3} } +n ( n - 1 ) } {}.
Vậy số phép tính số học xấp xỉ tỷ lệ với luỹ thừa bậc ba của số ẩn.
2. Phương pháp căn bậc giải hệ phương trình đại số tuyến tính trong trường hợp ma trận A size 12{A} {} là ma trận đối xứng
Phương pháp này thuận lợi trong trường hợp hệ phương trình
A x = b (12)
có ma trận A size 12{A} {} là ma trận đối xứng, điều thường gặp trong các bài toán kỹ thuật.
Theo phương pháp này ma trận A size 12{A} {} được biểu diễn thành tích của hai ma trận tam giác chuyển vị
A=T'T size 12{A= { {T}} sup { ' } T} {} (13)
trong đó
Nhân hai ma trận T' size 12{ { {T}} sup { ' }} {} và T size 12{T} {} và cho tích bằng ma trận A size 12{A} {}, ta suy ra cá công thức tính các phần tử tij size 12{t rSub { size 8{ ital "ij"} } } {}:
t11=a11,t1j=a1jt11(j>1)tii=aii−∑k=1i−1tki2(1<i≤n)tij=aij−∑k=1i−1tkitkjtii(i<j)tij=0khii>jalignl { stack { size 12{t rSub { size 8{"11"} } = sqrt {a rSub { size 8{"11"} } } ," "t rSub { size 8{1j} } = { {a rSub { size 8{1j} } } over {t rSub { size 8{"11"} } } } " " ( j>1 ) } {} # t rSub { size 8{ ital "ii"} } = sqrt {a rSub { size 8{ ital "ii"} } - Sum cSub { size 8{k=1} } cSup { size 8{i - 1} } {t rSub { size 8{ ital "ki"} } rSup { size 8{2} } } } " " ( 1<i <= n ) {} # t rSub { size 8{ ital "ij"} } = { {a rSub { size 8{ ital "ij"} } - Sum cSub { size 8{k=1} } cSup { size 8{i - 1} } {t rSub { size 8{ ital "ki"} } t rSub { size 8{ ital "kj"} } } } over {t rSub { size 8{ ital "ii"} } } } " " ( i<j ) {} # t rSub { size 8{ ital "ij"} } =0" " ital "khi"" "i>j {} } } {} (14)
Như vậy ta đã thay hệ (12) bằng hai hệ tương đương
T' y = b, T x = y 15)
hay
t11y1=b1t12y1+t22y2=b2.......................t1ny1+t2ny2+....+tnnyn=bn}}} size 12{alignl { stack { left none t rSub { size 8{"11"} } y rSub { size 8{1} } =b rSub { size 8{1} } {} # right rbrace left none t rSub { size 8{"12"} } y rSub { size 8{1} } +t rSub { size 8{"22"} } y rSub { size 8{2} } =b rSub { size 8{2} } {} # right rbrace left none "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." {} # right rbrace left none t rSub { size 8{1n} } y rSub { size 8{1} } +t rSub { size 8{2n} } y rSub { size 8{2} } + "." "." "." "." +t rSub { size 8{ ital "nn"} } y rSub { size 8{n} } =b rSub { size 8{n} } " " {} # right rbra } } rbrace } {} (16)
t11x1+t12x2+....+t1nxn=y1t22x2+...+t2nxn=y2.........................tnnxn=yn}}} size 12{alignr { stack { left none t rSub { size 8{"11"} } x rSub { size 8{1} } +t rSub { size 8{"12"} } x rSub { size 8{2} } + "." "." "." "." +t rSub { size 8{1n} } x rSub { size 8{n} } =y rSub { size 8{1} } " " {} # right rbrace left none t rSub { size 8{"22"} } x rSub { size 8{2} } + "." "." "." +t rSub { size 8{2n} } x rSub { size 8{n} } =y rSub { size 8{2} } " " {} # right rbrace left none "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." " " {} # right rbrace left none t rSub { size 8{ ital "nn"} } x rSub { size 8{n} } =y rSub { size 8{n} } " " {} # right rbra } } rbrace } {} (17)
Từ đó suy ra các công thức tính:
y1=b1t11,yi=bi−∑k=1i−1tkiyktii(i>1) size 12{y rSub { size 8{1} } = { {b rSub { size 8{1} } } over {t rSub { size 8{"11"} } } } ," "y rSub { size 8{i} } = { {b rSub { size 8{i} } - Sum cSub { size 8{k=1} } cSup { size 8{i - 1} } {t rSub { size 8{ ital "ki"} } y rSub { size 8{k} } } } over {t rSub { size 8{ ital "ii"} } } } " " ( i>1 ) } {} (18) xn=yntnn,xi=yi−∑k=i+1ntikxktii(i<n) size 12{x rSub { size 8{n} } = { {y rSub { size 8{n} } } over {t rSub { size 8{ ital "nn"} } } } ," "x rSub { size 8{i} } = { {y rSub { size 8{i} } - Sum cSub { size 8{k=i+1} } cSup { size 8{n} } {t rSub { size 8{ ital "ik"} } x rSub { size 8{k} } } } over {t rSub { size 8{ ital "ii"} } } } " " ( i<n ) } {} (19)
Vậy quá trình thuận gồm tính các phần tử của ma trận T size 12{T} {} theo các công thức (14). Quá trình nghịch là tính các ma trận cột y size 12{y} {} và x size 12{x} {} theo các công thức (18), (19).
