Nghiên cứu ứng dụng thuật toán Gauss-Jourdal trong xử lý số liệu trắc địa công trình
Nghiên cứu khoa học công nghệ
NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN GAUSS-JOURDAL
TRONG XỬ LÝ SỐ LIỆU TRẮC ĐỊA CÔNG TRÌNH
Nguyễn Việt Hà1,*, Phạm Tuấn Cường2
Tóm tắt: Bài báo này đã ứng dụng thuật toán Gauss_Jordan để xử lý số liệu đo
trong trắc địa công trình. Cụ thể là ứng dụng thuật toán Gauss_Jordan để tiến hành
đồng thời giải bài toán tuyến tính và nghịch đảo ma trận trong bài toán bình sai và
đánh giá độ chính xác trị đo. Kết quả việc ứng dụng là giải thuật, modul phần mềm
tính toán bình sai và đánh giá độ chính xác trị đo, làm cho bài toán đơn giản hơn và
tính toán nhanh hơn trên máy tính, ngoài ra còn dễ dàng hơn cho việc quản lý, lập
chương trình và cập nhật chương trình trên máy tính.
Từ khóa: Xử lý số liệu trắc địa; Đánh giá độ chính xác; Nghịch đảo ma trận.
1. MỞ ĐẦU
Đối với công tác xử lý số liệu trắc địa công trình, tính đúng đắn của số liệu sau xử lý
không những phụ thuộc vào độ chính xác đo đạc thực địa, mà còn chịu ảnh hưởng rất lớn bởi
phương pháp xử lý số liệu. Từ trước đến nay đã có nhiều chương trình tính toán xử lý số liệu
trắc địa công trình như chương trình bình sai mặt bằng, độ cao; chương trình đánh giá độ
chính xác mặt bằng, độ cao; chương trình tính chuyển tọa độ,... các chương trình trên thường
có một nội dung tính toán rất quan trọng là giải bài toán tuyến tính và nghịch đảo ma trận
cho việc tính toán các hàm trọng số phục vụ đánh giá độ chính xác của các hàm ẩn số. Trước
đây, việc giải bài toán tuyến tính và nghịch đảo ma trận thường được tiến hành theo thuật
toán Gauss, thuật toán khai căn Choleski hoặc thuật toán truy hồi [1, 2, 4].
Với các thuật toán trên việc giải bài toán tuyến tính và nghịch đảo ma trận được tiến
hành độc lập và theo một thuật toán phức tạp, điều này sẽ làm cho bài toán dài hơn và chậm
hơn, ngoài ra còn gây khó khắn cho việc quản lý và lập chương trình và cập nhật chương
trình trên máy tính. Trong khuôn khổ của bài báo khoa học này, nhóm nghiên cứu chúng tôi
sẽ đề xuất phương pháp ứng dụng thuật toán Gauss_Jordal [2] để giải quyết bài toán giải
phương trình tuyến tính và nghịch đảo ma trận trên cùng một phép tính. Điều này mang lại
nhiều ưu điểm như tiết kiệm thời gian tính toán, thuật toán đơn giản, dễ quản lý, dễ hiểu.
2. BÀI TOÁN TUYẾN TÍNH VÀ CÁC PHƯƠNG PHÁP GIẢI
2.1. Bài toán tuyến tính trong trắc địa công trình
Trong toán học một hệ phương trình gồm n phương trình tuyến tính với n ẩn số x ,
1
x ,...,x có dạng như sau:
2
n
a11x1 a12x2 ... a1n xn b
a21x1 a22x2 ... a2n xn b
1
2
(1)
............................................
an1x1 an2x2 ... ann xn bn
Hệ phương trình tuyến tính trên có thể viết dưới dạng phương trình ma trận là AX = b,
trong đó:
a
a12 ... a
x
b
1
1n
1
11
b2
a21 a22 ... a2n
... .... ... ...
an1 an2 ... ann
x2
...
xn
A
X
b
;
;
...
bn
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CBES, 04 - 2018
225
Toán học, Cơ học & Ứng dụng
X A1b
Nếu det(A) ≠ 0 thì nghiệm của hệ (1) có thể tính theo công thức
. Áp dụng
công thức tính ma trận nghịch đảo ta có thể biến đổi và dẫn đến lời giải được diễn tả bằng
định lý Cramer như sau:
Định lý Cramer. Gọi A là ma trận nhận được từ ma trận A bằng cách thay cột thứ j bằng
j
cột b, khi đó hệ (1) có nghiệm duy nhất và x được tính bởi công thức
j
det(Aj )
(2)
xj
det(A)
Tuy nhiên, trong thực hành người ta không dùng công thức này để tính nghiệm vì số
phép tính quá lớn. Người ta dùng những phương pháp hữu hiệu hơn mà chúng tôi sẽ giới
thiệu sau đây.
2.2. Một vài phương pháp giải bài toán tuyến tính trong trắc địa công trình
a. Phương pháp khử Gauss
Phương pháp khử Gauss dùng cách khử dần các ẩn số để đưa hệ phương trình tuyến
tính về một dạng tam giác trên rồi giải hệ tam giác này từ dưới lên trên, không phải tính
một định thức nào. Phương pháp này được thực hiện qua các bước sau:
Quá trình xuôi:
- Bước 1: Dùng phương trình trên cùng để khử x trong n-1 phương trình còn lại. Giả
1
sử a ≠0. (Để cho đơn giản, trước khi khử ta có thể chia phương trình thứ nhất cho a ).
11
11
Cụ thể để khử x ở các hàng tiếp theo thứ k( k=2,3,…n) ta phải tính lại các hệ số a ở
1
kj
hàng thứ k (với j=1,2,..n+1) như sau: a =a -a *a /a
k1 11
kj
kj 1j
- Bước 2: Dùng phương trình thứ 2 để khử x trong n-2 phương trình còn lại tiếp theo.
2
Giả sử a ≠0. (Để cho đơn giản, trước khi khử ta có thể chia phương trình thứ hai cho a ).
22
22
Cụ thể để khử x ở hàng tiếp theo thứ k (k=3,4,…n) ta phải tính lại các hệ số a ở hàng
2
kj
thứ k (j=2,..n+1) như sau: a =a -a *a /a
k2 22
kj
kj 2j
- Bước i: Dùng phương trình i để khử x trong các phương trình tiếp theo thứ i+1,i+2,
i
..., n. Giả sử a ≠0. Để cho công thức đơn giản, trước khi khử ta có thể chia phương trình
ii
thứ i cho a .
ii
Cụ thể để khử x ở hàng thứ k (k=i+1,…n) ta phải tính lại các hệ số a ở hàng thứ k
i
kj
(j=i,..n+1) như sau: a =a -a *a /a
ki ii
kj
kj ij
- Bước n-1: Dùng phương trình thứ n-1 để khử x trong phương trình thứ n. Giả sử
n-1
a
≠0. (Để cho đơn giản, trước khi khử x ta có thể chia phương trình thứ n-1 cho a
n-1
n-1 n-1
n-1
)
n-1
Cụ thể để khử x ở hàng thứ n ta phải tính lại các hệ số a ở hàng thứ n (j=n-
n-1
nj
1,n,n+1) như sau: a =a -a *a /a
n-1i n-1n-1
nj
nj n-1j
Kết thúc quá trình khử.
Quá trình giải ngược
x = b /a hoặc ( x =b )
n
n
nn
n
n
. . .
x = (b -(aΣ+=nij1 x ) )/a ) hoặc (b -(aΣ+=nij1 x ) ), i =n-1, n-2, ..., 1
i
i
ij
j
ii
i
ij
j
Ta áp dụng các phép biến đổi sơ cấp như vừa trình bày để biến đổi ma trận chữ nhật
cấp nx(n+1) trên đây về dạng:
226
N. V. Hà, P. T. Cường, “Nghiên cứu ứng dụng thuật toán … số liệu trắc địa công trình.”
Nghiên cứu khoa học công nghệ
'
'
1 a12 ...... a 1n a 1n1
0
1
...... a'2n a'2n1
... ... ...... ...
...
...
... ... ...... ...
'
0
0
......
1
a nn1
b. Phương pháp khử Gauss-Jordan
Phương pháp khử Gauss-Jordan dùng cách khử dần các ẩn để đưa hệ phương trình
đã cho về một dạng ma trận đường chéo rồi giải hệ phương trình này, không phải tính một
định thức nào
Phương pháp này được thực hiện qua các bước sau:
- Bước 1: Dùng phương trình đầu tiên để khử x trong n-1 phương trình còn lại, cách
1
làm tương tự như phương pháp khử để tính định thức... (Để cho công thức đơn giản, trước
khi khử ta có thể chia phương trình thứ nhất cho a ).
11
Cụ thể để khử x ở hàng thứ k( k=2,3,…n) ta phải tính lại các hệ số a ở hàng thứ k
1
kj
(j=1,2,..n+1) như sau: a =a -a *a /a
k1 11
kj
kj 1j
- Bước i: Dùng phương trình i để khử x trong các phương trình thứ 1,2, i-
i
1,i+1,i+2,...,n.. (Để cho công thức đơn giản, trước khi khử ta có thể chia phương trình thứ
i cho a ).
ii
Cụ thể để khử x ở hàng thứ k (k=1,2, i-1,i+1,i+2,...,n.) ta phải tính lại các hệ số a ở
i
kj
hàng thứ k (j=i,..n+1) như sau: a =a -a *a /a
ki ii
.
kj
kj ij
- Bước n: Dùng phương trình thứ n để khử x trong phương trình thứ 1,2, ..., n-1.. (Để
n
cho công thức đơn giản, trước khi khử ta có thể chia phương trình thứ n cho a )
nn
Cụ thể để khử x ở hàng thứ k( k=1,2, ..,n-1.) ta phải tính lại các hệ số a ở hàng thứ k
n
kj
(j=n,n+1) như sau: a =a -a *a /a
kn nn
kj
kj nj
Tương tự phép khử Gauss tại mỗi bước, trước khi khử ta phải chọn trụ tối đại. Cụ thể
tại bước i ta luôn chọn hàng có phần tử a có giá trị tuyệt đối lớn nhất rồi đổi cho hàng thứ
ri
i cho hàng thứ r.
Hệ phương trình sau khi khử có dạng:
a11 x1
b1
b2
a22 x2
.......................................
ann xn bn
Hoặc nếu tại các bước (bước i) ta chia cho hệ số a :
ii
x
b1
b2
1
x2
.......................................
xn bn
Tức là ta đã có các nghiệm mà không cần phải tính toán thêm.
Cũng như trong phương pháp khử Gauss, khi cài đặt trên máy tính ta dùng một mảng
a thay cho cả ma trận A và vec tơ b. Tức là:
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CBES, 04 - 2018
227
Toán học, Cơ học & Ứng dụng
a
a12 ...... a1n
a
a
a12 ...... a1n
b
1n1
1
11
11
a21 a22 ...... a2n a2n1
a21 a22 ...... a2n b2
... ... ...... ...
... ... ...... ...
... ... ... ...... ... ...
...
... ... ...... ... ...
an1 an2 ...... ann ann1
an1 an2 ...... ann bn
Ta áp dụng các phép biến đổi sơ cấp như vừa trình bày để biến đổi ma trận chữ nhật
cấp nx(n+1) trên đây về dạng
'
1
0
0 ...... 0 a 1n1
1 ...... 0 a'2n1
... ... ...... ...
...
...
... ... ...... ...
'
0
0 ...... 1 a nn1
Vậy ta có x = a'
.
i,(n+1)
i
3. ÁP DỤNG PHƯƠNG PHÁP KHỬ GAUSS - JORDAN ĐỂ TÍNH MA TRẬN
NGHỊCH ĐẢO
Để giải hệ n phương trình n ẩn Ax = b, trong phương pháp khử Gauss-Jordan ta đã
dùng các phép biến đổi sơ cấp để đưa phương trình này về dạng:
Ex = b'
(3)
Vì Ex = x, do đó, ta có x=b'. Nếu B là một ma trận chữ nhật cấp n x k tùy ý, ta có thể
áp dụng phương pháp khử Gauss-Jordan để giải đồng thời k hệ n phương trình n ẩn:
AX = B
(4)
trong đó:
b
b12 ... b
x
x12 ... x
1k
1k
11
11
b21 b22 ... b2k
... ... ... ...
bn1 bn2 ... bnk
x21 x22 ... x2k
... ... ... ...
xn1 xn2 ... xnk
B
X
Ta viết ma trận B bên phải ma trận A như sau:
a
a12 ... a1n b11 b12 ... b
1k
11
a21 a22 ... a2n b21 b22 ... b2k
... ... ... ... ... ... ... ...
an1 an2 ... ann bn1 bn2 ... bnk
Nếu ma trận A không suy biến, ta có thể áp dụng các phép biến đổi sơ cấp để đưa ma
trận này về dạng:
1
0
0 ... 0 b'11 b'12 ... b'
1k
1 ... 0 b'21 b'22 ... b'2k
... ... ...
0 ... 1 b'n1 b'n2 ... b'nk
... ... ... ... ...
0
228
N. V. Hà, P. T. Cường, “Nghiên cứu ứng dụng thuật toán … số liệu trắc địa công trình.”
Nghiên cứu khoa học công nghệ
Khi đó, ta có:
x
x12 ... x
b'
b'12 ... b'
1k
1k
11
11
x21 x22 ... x2k
... ... ... ...
xn1 xn2 ... xnk
b'21 b'22 ... b'2k
X
;
...
... ... ...
b'n1 b'n2 ... b'nk
Đặt:
b'
b'12 ... b'
1k
11
b'21 b'22 ... b'2k
B'
...
... ... ...
b'n1 b'n2 ... b'nk
Xét trường hợp đặc biệt B = E, ta có ma trận B' chính là ma trận nghịch đảo của ma
trận A. Thật vậy, nếu X là nghiệm của (4) thì:
X = A-1B
(5)
Nếu B = E thì X = A-1. Do đó, việc tìm ma trận nghịch đảo của ma trận A tương
đương với việc giải phương trình
AX = E
(6)
Vậy để tính ma trận nghịch đảo ta cần thực hiện các bước sau:
• Viết thêm ma trận đơn vị E bên cạnh ma trận A
a
a12 ... a1n
1
0
0
1
...
...
0
0
11
a21 a22 ... a2n
... ... ... ... ... ... ... ...
an1 an2 ... ann
0
0
...
1
• Áp dụng phép biến đổi sơ cấp trên hàng cho đến khi ma trận có dạng
1
0
0 ... 0 c11 c12 ... c
1n
1 ... 0 c21 c22 ... c2n
... ... ... ... ... ... ... ...
0
0 ... 1 cn1 cn2 ... cnn
Khi đó ta có
c
c12 ... c
1n
11
c21 c22