## Chapter 8: Exercises

1. 下列聯立方程式有無窮多組交點： $$\left\{ \begin{array}{l} y = 1/x\\ y = sin(x) \end{array} \right.$$
1. 假設這些交點可以表示成 $(x_1, y_1), (x_2, y_2), (x_3, y_3), \cdots$, 而且 $x_1 < x_2 < x_3 < \cdots$。請用 fzero 指令，找出 $x_1, x_2, x_3$。
2. 請畫出代表上述兩個方程式的曲線，並用小圓圈標示出 $(x_1, y_1), (x_2, y_2), (x_3, y_3)$ 的位置，以驗證你在前一小題的答案。
2. Find a point to minimize distance difference: Given two set of points A and B on a 2D space, find a point (x,0) on the X-axis such that the sum of distance to all points in A is equal to to sum of distance to all points in B. In other words, you need to write a function equalDistance.m with the following usage:
x = equalDistance(A, B);
where
• A is a matrix of 2 by m, representing m points in a 2D plane
• B is a matrix of 2 by n, representing n points in a 2D plane
• x is the returned output
Note that you can simply assume the solution of x always exists.

Here is a test example:

1. Example 1: 08-一般數學函數的處理與分析/equalDistance01.mA=[1.02425546496901 1.25358084802804 1.17951024589869 1.67572050678079 1.36894578489338 1.6749531972447 1.72228602412244 1.57044649311883 1.13258989974403 1.90017865546025; 1.50659089719153 1.83620274208373 1.54085325182511 1.7648613516281 1.53236552752797 2.00265451589403 1.63189442288142 1.52571664681234 1.61703687407616 1.82597937814431]; B=[-0.364218237058624 -0.627935085190556 -0.435555596054787 -0.97890906944334 -0.368512531286445 -0.558137538884114 -0.254487941788666 -0.300780054401997 -0.61814596238125 -0.570864465939227 -0.683820512711681 -0.471135644946428; -0.820567174888604 -0.905539415326849 -0.726200531441377 -0.995112554677464 -0.343980731337428 -0.332428485029845 -0.977633932802877 -0.584977211064341 -0.966664915591615 -0.556292501691081 -0.519141532920073 -0.964541521774489]; x=equalDistance(A, B); format long; x % Plotting plot(A(1,:), A(2,:), 'o', B(1,:), B(2,:), 'o'); grid on; axis image line(x, 0, 'marker', 'o', 'color', 'k'); legend('Set A', 'Set B', 'x', 'location', 'northOutside', 'orientation', 'horizontal'); title(['x =', mat2str(x)]); x = 0.793334860502017

Hint
• You need to use the function fzero.m.
• You can modify irrFind.m to make things easier.

3. Find a line to minimize distance difference: Given a set of points A on a 2D space, find a line y=alpha*x such that the sum of distance to all points above the line is equal to to sum of distance to all points below the line. In other words, you need to write a function equalDistanceFromLine.m with the following usage:
alpha = equalDistanceFromLine(A);
where
• A is a matrix of 2 by m, representing m points in a 2D plane
• alpha is the slope of the separating line
Note that you can simply assume the solution of alpha always exists.

Test cases

• A = [0.669615828536535 1.37831002494;0.255156313573849 0.700802957390634] ==> alpha = 0.46679388774826

• A = [1.0459613413713 1.64836240385754 0.668148281107254 1.24009361110736 1.76736994372824 0.514183249250956 1.22696476792286 1.87222221905272 1.58712322506665 0.899136620392806;0.995918733217741 1.57784235228208 0.949856035477784 1.1820334094137 1.46127638101438 0.816264168546478 0.872065204595773 1.35287364461043 0.445267025957944 1.00539440958911] ==> alpha = 0.854784493132274

Hint
• You need to use the function fzero.m.
• You can modify irrFind.m to make things easier.
• The distance of a point $(x_0, y_0)$ to a line $y=ax+b$ is $\frac{|y_0-ax_0-b|}{\sqrt{1+a^2}}$.
• For a good initial guess, you can set the initial value of alpha such that the mean vector of A will pass the line.

4. 在 XY 平面上給定三點 A、B、C，找出另外一點 X，使得 X 到 A、B、C 三點的距離和為最小。請寫一個函式 mindist.m 解決上述問題，此函式的輸出入格式如下：
x = mindist(a, b, c)
其中 a、b、c 為三點的座標，x 則是輸出點的座標，你必須使用 fminsearch 指令來進行最佳化。
• 當 a = [4 0]、b = [0 3]、c = [0 0] 時，mindist.m 所傳回的 x 值為何？對應的最短距離和為何？
• 在上小題中，當最短距離和發生時，角度 $\angle AXB$、$\angle BXC$、$\angle CXA$ 各是多少？
5. 在 XY 平面上給定三點 A、B、C，找出另外一點 X，使得 X 到 A、B、C 三點的距離平方和為最小。請寫一個函式 mindist2.m 解決上述問題，此函式的輸出入格式如下：
x = mindist2(a, b, c)
其中 a、b、c 為三點的座標，x 則是輸出點的座標，你必須使用 fminsearch 指令來進行最佳化。
• 當 a = [4 0]、b = [0 3]、c = [0 0] 時，mindist2.m 所傳回的 x 值為何？對應的最短距離平方和為何？
• 在上小題中，當最短距離平方和發生時，x-(a+b+c)/3 的長度是多少？
6. 在 XY 平面上給定一組行向量 x1, x2, ... xn，請找出一個單位向量 u，使得這一組向量在 u 方向的投影量平方和為最小。請寫一個函式 minProj.m 解決上述問題，此函式的輸出入格式如下：
u = minproj(X)
其中 X 的每一個直行即是行向量 xi, i = 1, ..., n，而 u 是一個長度為一的向量，代表最佳的投影方向。你必須使用 fminsearch 指令來進行最佳化。
7. Function for min. total distance to a set of points: Write a function minDist2points(A) that returns a point in a d-dimensional space such that the total distance between this point and all the other $n$ points is minimized, where these $n$ points can be packed into a d-by-n matrix A, with A(:,i) being the i-th point. The initial guess of the solution should be set to the mean of these $n$ points.

Test cases

• minDist2points([1 4 2;8 6 1]) returns [3.2438; 5.7910].
• minDist2points([1 4 2 3; 8 6 1 7; 5 9 0 1]) returns [ 2.2855; 6.3539; 3.6291].
(Note that you are not allowed to use any toolboxes in this exercise.)

Hint
• Since there is no analytic solution, you need to use "fminsearch" (with default options) to search for the point.
• Analytic solution of this problem exists if the "total distance" is replaced by "total squared distance".

8. Function for min. total distance to a set of hyperplanes: Write a function minDist2hyperplanes(A) that returns a point in a d-dimensional space such that the total distance between this point and all the other $n$ hyperplanes is minimized, where these $n$ hyperlines can be packed into a (d+1)-by-n matrix A, with A(:,i) being the coefficients of the i-th hyperplane: $A(1,i)*x_1+A(2,i)*x_2+\cdots+A(d,i)*x_d+A(d+1,1)=0$.

Hint
• Since there is no analytic solution, you need to use "fminsearch" (with default options) to search for the point.
• Analytic solution of this problem exists if the "total distance" is replaced by "total squared distance".

9. Circle fitting via DSS: A circle in 2D can be described by the following equation $$(x-a)^2+(y-b)^2=r^2,$$ where $(a, b)$ is the center and $r$ is the radius of the circle. Given a dataset $\{(x_i, y_i)|i=1, 2, ..., n\}$, the sum of distances of these points to the circle can be formulated as follows: $$f(a, b, r)=\sum_{i=1}^{n}\left|\sqrt{(x_i-a)^2+(y_i-b)^2}-r\right|$$ Write a function circleFitByDss.m that can find the best values of $[a, b, r]^T$ such that $f(a, b, r)$ can be minimized. The usage of the function is:
output = circleFitByDss(data)
where
• data: an 2-by-n dataset matrix, with each column being a sample data point.
• output: a column vector of the derived $[a, b, r]^T$ using Downhill Simplex Search (which is implemented as the function "fminsearch" in MATLAB).

Note that the initial guess of $[a, b, r]^T$ should be as close as possible to the minimizing point. One good choice is to set the center ($[a, b]^T$) as the mean of all the data points, and set $r$ as the average distance of the center to each data point.

Here is a test example:

1. Example 2: 08-一般數學函數的處理與分析/circleFit01.mdata=[12 -5 13 -3 -8 3 7 -4 7 -4 -4 -1 -5 2 13 -5 -6 5 -5 -8 -6 -7 2 9 -5 -4 -5 8 4 -1 12 1 7 11 11 -1 9 0 -5 14 -3 -8 -3 12 -1 -1 13 7 -6 -7 12 12 -8 10 6 14 -7 6 10 12 8 14 7 8 -1 10 9 13 3 13 -7 12 7 13 -5 -7 -2 9 10 -6 7 7 14 10 9 -6 11 -3 12 -6 8 12 9 10 11 11 1 1 -6 -4; 3 13 6 1 9 16 15 1 17 13 -1 -3 9 17 12 5 3 -2 0 7 6 10 15 -4 8 -1 0 14 17 16 12 -3 -3 6 11 -3 14 16 13 9 -2 6 12 7 -4 15 5 -3 12 4 7 5 4 2 -1 6 10 16 0 7 1 10 15 -1 17 0 14 5 16 9 0 1 -1 0 12 2 -1 16 0 13 -2 15 7 1 -2 11 11 3 6 10 15 0 15 7 0 4 -4 -1 5 1]; theta=circleFit(data); format long; theta % Plotting t=linspace(0, 2*pi); x1=theta(1)+theta(3)*cos(t); y1=theta(2)+theta(3)*sin(t); plot(data(1,:), data(2,:), '.', x1, y1, 'r'); axis image legend({'Sample data', 'Fitting circle'}, 'location', 'northOutside', 'orientation', 'horizontal'); theta = 2.500014916354736 6.500011175675343 9.924708551335694

10. Rectangle fitting via DSS: A rectangle in 2D can be described by 4 parameters $[x, y, \alpha, \beta]$, where $[x, y]$ is the center coordinate of the rectangle, $\alpha$ is the half width, and $\beta$ is the half height. (Thus the 4 corners of the rectangle can be represented by 4 points at $[x-\alpha, y-\beta]$, $[x-\alpha, y+\beta]$, $[x+\alpha, y+\beta]$, and $[x+\alpha, y-\beta]$.) Given a point in 2D, the distance of this point to the rectangle is defined as the shortest distance of this point to all possible data points on the rectangle. Write a function rectangleFit.m that can find the best values of $[x, y, \alpha, \beta]^T$ such that the total distance of a dataset to the rectangle can be minimized. The usage of the function is:
output = rectangleFit(data)
where
• data: an 2-by-n dataset matrix, with each column being a sample data point.
• output: a column vector of the derived $[x, y, \alpha, \beta]^T$ using Downhill Simplex Search (which is implemented as the function "fminsearch" in MATLAB).

Note that the initial guess of $[x, y, \alpha, \beta]^T$ should create a bounding box for the dataset.

Here is a test example:

1. Example 3: 08-一般數學函數的處理與分析/rectangleFit01.m% Create the sample data n=20; d1=[rand(1,n)/4+2; 3*rand(1,n)+2]; d2=[4*rand(1,n)-2; rand(1,n)/4+2]; d3=[4*rand(1,n)-2; rand(1,n)/4+5]; d4=[rand(1,n)/4-2; 3*rand(1,n)+2]; data=[d1, d2, d3, d4]; data=round(data*50); % Do the fitting theta=rectangleFit(data); fprintf('data=%s\n', mat2str(data)); fprintf('theta=%s\n', mat2str(theta)); % Plot the result plot(data(1,:), data(2,:), '.'); x1=theta(1)-theta(3); x2=theta(1)+theta(3); y1=theta(2)-theta(4); y2=theta(2)+theta(4); line([x1 x1 x2 x2 x1], [y1 y2 y2 y1 y1], 'color', 'r'); axis image legend({'Sample data', 'Final fitting rectangle'}, 'location', 'northOutside', 'orientation', 'horizontal');data=[101 110 105 104 104 112 111 112 107 106 106 106 105 110 108 109 101 112 109 108 81 -52 -63 -25 28 -21 -20 -75 -39 -22 -12 48 -44 -13 54 -52 85 29 -6 85 54 -33 -80 56 4 36 -23 -63 86 76 25 35 -30 -76 -5 -86 -63 73 -86 -46 -88 -96 -88 -95 -90 -92 -88 -98 -93 -92 -94 -96 -89 -92 -92 -97 -91 -88 -96 -98;136 240 208 191 157 179 124 137 235 230 186 163 134 176 103 103 111 123 225 234 100 107 105 110 109 105 103 102 112 102 103 108 101 109 110 112 102 111 101 101 253 260 253 259 251 251 258 255 256 252 257 257 259 252 256 261 261 255 258 253 222 170 231 228 222 112 136 230 147 110 139 193 197 174 159 209 141 129 149 151] theta=[7.29406018687973 180.499991163551 99.2940805465921 75.4999909043646]

MATLAB程式設計：進階篇