| Line 1: | Line 1: | ||
| + | =QE2012_AC-3_ECE580-1= | ||
| − | |||
| + | '''1. (20 pts)''' | ||
| + | |||
| + | (i) (10 pts) Find the factor by which the uncertainty range is reduced when using the Fibonacci method. Assume that the last step has the form | ||
| + | |||
| + | <math> | ||
| + | \begin{align} | ||
| + | 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, | ||
| + | \end{align} | ||
| + | </math> | ||
| + | |||
| + | where <span class="texhtml">''N'' − 1</span> is the number of steps performed in the uncertainty range reduction process. | ||
| + | |||
| + | <br> | ||
| + | |||
| + | <br> Solution: | ||
| + | |||
| + | The reduction factor is <span class="texhtml">(1 − ρ<sub>1</sub>)(1 − ρ<sub>2</sub>)(1 − ρ<sub>3</sub>)...(1 − ρ<sub>''N'' − 1</sub>)</span> | ||
| + | Since | ||
| + | <math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math> | ||
| + | we have | ||
| + | <math> 1- \rho_{N-2} = \frac{F_{3}}{F_{4}}</math> and so on. | ||
| + | |||
| + | Then, we have | ||
| + | <math> (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}} \frac{F_{N-1}}{F_{N}} ... \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}}</math> | ||
| + | Therefore, the reduction factor is | ||
| + | <math>\frac{2}{F_{N+1}}</math> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | Solution 2: | ||
| + | |||
| + | The uncertainty interval is reduced by <math> (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}} \frac{F_{N-1}}{F_{N}} ... \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}}</math> | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | '''(ii)(10 pts)''' It is known that the minimizer of a certain function f(x) is located in the interval[-5, 15]. What is the minimal number of iterations of the Fibonacci method required to box in the minimizer within the range 1.0? Assume that the last useful value of the factor reducing the uncertainty range is 2/3, that is | ||
| + | |||
| + | <math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math> | ||
| + | |||
| + | <br> Solution: | ||
| + | |||
| + | Final Range: 1.0; Initial Range: 20. | ||
| + | |||
| + | <math> \frac{2}{F_{N+1}} \le \frac{1.0}{20}</math>, or <math> F_{N+1} \ge 40</math> | ||
| + | |||
| + | So, <span class="texhtml">''N'' + 1 = 9</span> | ||
| + | |||
| + | Therefore, the minimal iterations is N-1 or 7. | ||
| + | |||
| + | <br> | ||
| + | Solution 2: | ||
| − | + | Since the final range is <math> 1.0 </math> and the initial range is <math> 20 </math>, we can say | |
| + | <math> \frac{2}{F_{N+1}} \le \frac{1.0}{20} or equivalently F_{N+1}} \ge 40 </math> | ||
| + | From the inequality, we get <math> F_{N+1} \ge 40 , so N+1=9 </math>. Therefore the minimum number of iteration is N-1=7 | ||
Revision as of 19:00, 25 January 2013
QE2012_AC-3_ECE580-1
1. (20 pts)
(i) (10 pts) Find the factor by which the uncertainty range is reduced when using the Fibonacci method. Assume that the last step has the form
$ \begin{align} 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, \end{align} $
where N − 1 is the number of steps performed in the uncertainty range reduction process.
Solution:
The reduction factor is (1 − ρ1)(1 − ρ2)(1 − ρ3)...(1 − ρN − 1) Since $ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $ we have $ 1- \rho_{N-2} = \frac{F_{3}}{F_{4}} $ and so on.
Then, we have $ (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}} \frac{F_{N-1}}{F_{N}} ... \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}} $ Therefore, the reduction factor is $ \frac{2}{F_{N+1}} $
Solution 2:
The uncertainty interval is reduced by $ (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}} \frac{F_{N-1}}{F_{N}} ... \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}} $
(ii)(10 pts) It is known that the minimizer of a certain function f(x) is located in the interval[-5, 15]. What is the minimal number of iterations of the Fibonacci method required to box in the minimizer within the range 1.0? Assume that the last useful value of the factor reducing the uncertainty range is 2/3, that is
$ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $
Solution:
Final Range: 1.0; Initial Range: 20.
$ \frac{2}{F_{N+1}} \le \frac{1.0}{20} $, or $ F_{N+1} \ge 40 $
So, N + 1 = 9
Therefore, the minimal iterations is N-1 or 7.
Solution 2:
Since the final range is $ 1.0 $ and the initial range is $ 20 $, we can say $ \frac{2}{F_{N+1}} \le \frac{1.0}{20} or equivalently F_{N+1}} \ge 40 $ From the inequality, we get $ F_{N+1} \ge 40 , so N+1=9 $. Therefore the minimum number of iteration is N-1=7
