"

21

21.1. Phép đo tam giác bằng ước lượng khoảng cách.

Trong nhiều ứng dụng như GPS, ta quan tâm đến việc suy ra vị trí của một bộ phát (ví dụ, một chiếc điện thoại di động) từ việc đo khoảng cách đến các điểm đã biết. Các khoảng cách này thu được bằng cách ước tính sự chênh lệch thời gian đến của một mặt sóng bắt nguồn từ bộ phát. Trong phép đạc tam biên, chỉ có ba điểm được sử dụng. Khi đó, ta phải tìm giao của ba mặt cầu. Bài toán sau đó có thể được rút gọn thành việc giải một phương trình tuyến tính, theo sau là một phương trình bậc hai một ẩn. Bài toán đạc đa biên, cho phép nhiều hơn ba điểm, cung cấp các phép đo chính xác hơn. (Nguồn.)

Ký hiệu [latex]x^i[/latex], [latex]i=1,2,3[/latex] là ba điểm đã biết và [latex]R_i[/latex] là các khoảng cách đo được đến bộ phát. Về mặt toán học, bài toán là giải hệ phương trình sau cho một điểm [latex]x[/latex] trong [latex]\mathbb{R}^3[/latex],

[latex]\begin{align*} ||x-x^i||_2^2 &= R_i^2, \quad i=1,2,3. \end{align*}[/latex]

Viết chúng ra:

[latex]\begin{align*} x^Tx - 2x^Tx^i + ||x^i||_2^2 &= R_i^2, \quad i = 1,2,3. \end{align*}[/latex]

Đặt [latex]t := (1/2)x^Tx[/latex]. Các phương trình trên kéo theo

[latex]\begin{align*} t - x^Tx^i = \gamma_i := (1/2)(R_i^2-||x^i||_2^2), \quad i = 1,2,3. \end{align*}[/latex]

Sử dụng ký hiệu ma trận, với [latex]X = [x^1, x^2, x^3][/latex] là ma trận các điểm, và [latex]\mathbf{1}[/latex] là véctơ gồm toàn số một:

[latex]\begin{align*} X^Tx = t \mathbf{1} - \gamma. \end{align*}[/latex]

Giả sử ma trận vuông [latex]X[/latex] có hạng đầy đủ, tức là khả nghịch. Phương trình trên kéo theo rằng

[latex]\begin{align*} x = x(t) := X^{-T}( t \mathbf{1} - \gamma). \end{align*}[/latex]

Nói cách khác: điểm này nằm trên một đường thẳng đi qua [latex]x^0 := -(X^T)^{-1}\gamma[/latex] và có véctơ chỉ phương là [latex]v:=(X^T)^{-1}\mathbf{1}[/latex].

Khi đó ta có thể giải phương trình theo [latex]t[/latex]:

[latex]\begin{align*} x(t)^Tx(t) &= 2t. \end{align*}[/latex]

Phương trình này là một phương trình bậc hai theo [latex]t[/latex]:

[latex]\begin{align*} (v^Tv) t^2 + 2 ((v^Tx^0) -1) t + ||x^0||_2^2 = 0 \end{align*}[/latex]

và có thể được giải dưới dạng tường minh. Các mặt cầu cắt nhau khi và chỉ khi có một nghiệm thực, không âm [latex]t[/latex]. Một cách tổng quát, nếu các mặt cầu có giao khác rỗng, sẽ có hai nghiệm dương, do đó có hai điểm trong phần giao. Điều này có thể hiểu được về mặt hình học: giao của hai mặt cầu là một đường tròn, và giao của một đường tròn với một mặt cầu thứ ba tạo ra hai điểm. Đường thẳng nối hai điểm đó chính là đường thẳng [latex]\{ x(t): t \in \mathbb{R} \}[/latex], như đã xác định ở trên.

21.2. Ước tính lưu lượng giao thông

Bài toán ước tính lưu lượng giao thông cơ bản bao gồm việc suy ra số lượng xe đi qua các nhánh dựa trên thông tin về số lượng xe đi qua các nhánh lân cận.

Đối với bài toán đơn giản ở trên, ta chỉ cần sử dụng một thực tế là tại mỗi giao lộ, lưu lượng vào phải bằng lưu lượng ra. Điều này dẫn đến các phương trình tuyến tính:

[latex]\begin{align*} \text{Intersection A:} && x_4 + 610 &= x_1 + 450, \\ \text{Intersection B:} && x_1 + 400 &= x_2 + 640, \\ \text{Intersection C:} && x_2 + 600 &= x_3, \\ \text{Intersection D:} && x_3 &= x_4 + 520. \end{align*}[/latex]

We can write this in matrix format: [latex]Ax = y,[/latex] with

[latex]\begin{align*} A &= \left( \begin{array}{cccc} -1 & 0 & 0 & 1 \\ 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -1 \\ \end{array} \right),\hspace{-1.5cm} & y &= \left( \begin{array}{c} -160 \\ 240 \\ -600 \\ 520 \\ \end{array} \right). \end{align*}[/latex]

Ma trận [latex]A[/latex] không gì khác chính là ma trận liên thuộc gắn với đồ thị có các giao lộ là các nút và các nhánh là các cạnh.

License

Icon for the Public Domain license

This work (Đại số tuyến tính by Tony Tin) is free of known copyright restrictions.