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{a^2+b^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 circleFit.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 = circleFit(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


MATLAB程式設計:進階篇