Читать книгу Applied Numerical Methods Using MATLAB - Won Y. Yang - Страница 35

The execution speed of a program for a numerical solution depends mostly on the number of function (subroutine) calls and arithmetic operations performed in the program. Therefore, we like the algorithm requiring fewer function calls and arithmetic operations. For instance, suppose we want to evaluate the value of a polynomial

(1.3. 1)

It is better to use the nested (computing) structure (as follows) than to use the above form as it is

(1.3.2)

Note that the numbers of multiplications needed in Eqs. (1.3.2) and (1.3.1) are 4 and (4 + 3 + 2 + 1 = 9), respectively. This point is illustrated by the script “nm131_1.m”, where a polynomial of degree N = 10⁶ for a certain value of x is computed by using the three methods, i.e. Eq. (1.1), Eq. (1.2), and the MATLAB built‐in function ‘ polyval()’. Interested readers could run this script to see that the nested multiplication (Eq. (1.3.2)) and ‘ polyval()’ (fabricated in a nested structure) take less time than the plain method (Eq. (1.1)), while ‘ polyval()’ may take longer time because of some overhead time for being called.

%nm131_1.m: nested multiplication vs. plain multiple multiplication N=1000000+1; a=[1:N]; x=1; tic % initialize the timer p=sum(a.*x.̂[N-1:-1:0]); % Plain multiplication p time_plain=toc % Operation time for the sum of multiplications tic, pn=a(1); for i=2:N % Nested multiplication pn = pn*x +a(i); end pn, time_nested=toc % Operation time for the nested multiplications tic, polyval(a,x) time_polyval=toc % Operation time for using polyval()

Programming in a nested structure is not only recommended for time‐efficient computation, but also may be critical to the solution. For instance, consider a problem of finding the value

(1.3.3)

%nm131_2_1.m: nested structure lam=100; K=155; p=exp(-lam); tic S=0; for k=1:K p=p*lam/k; S=S+p; end S time_nested=toc

%nm131_2_2.m: not nested structure lam=100; K=155; tic S=0; for k=1:K p=lam̂k/factorial(k); S=S+p; end S*exp(-lam) time_not_nested=toc

The above two scripts are made for computing Eq. (1.3.3). Noting that this sum of Poisson probability distribution [W-4] is close to 1 for such a large K, we can run them to find that one works fine, while the other gives a quite wrong result. Could you tell which one is better?