# Thuật toán Algorithms (Phần 10)

Chia sẻ: Tran Anh Phuong | Ngày: | Loại File: PDF | Số trang:10

0
56
lượt xem
6

## Thuật toán Algorithms (Phần 10)

Mô tả tài liệu

Tham khảo tài liệu 'thuật toán algorithms (phần 10)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Thuật toán Algorithms (Phần 10)

1. INTEGRATION 83 (Recall that the area of a trapezoid is one-half the product of the height and the sum of the lengths of the two bases.) The error for this method can be derived in a similar way as for the rectangle method. It turns out that sp f(x) dx = t- - + . . . . 2w3e3 4w5e5 Thus the rectangle method is twice as accurate as the trapezoid method. This is borne out by our example. The following procedure implements the trapezoid method in the common case where all the intervals are the same width: function inttrap(a, b: real; N: integer): real; var i: integer; w, t: real; begin t:=O; w:=(b-a)/N; for i:=l to N do t:=t+w*(f(a+(i--l)*w)+f(a+i*w))/2; inttrap:=t; end ; This procedure produces the following estimates for J12 dx/x: 10 0.6937714031754 100 0.6931534304818 1000 0.6931472430599 It may seem surprising at first that the rectangle method is more accurate than the trapezoid method: the rectangles tend to fall partly under the curve, partly over (so that the error can cancel out within an interval), while the trapezoids tend to fall either completely under or completely over the curve. Another perfectly reasonable method is spline quadrature: spline inter- polation is performed using methods we have discussed and then the integral is computed by piecewise application of the trivial symbolic polynomial in- tegration technique described above. Bel’ow, we’ll see how this relates to the other methods. Compound Methods Examination of the formulas given above for the error of the rectangle and trapezoid methods leads to a simple method with much greater accuracy, called Simpson’s method. The idea is to eliminate the leading term in the error
2. 84 CHAPTER 7 by combining the two methods. Multiplying the formula for the rectangle method by 2, adding the formula for the trapezoid method then dividing by 3 gives the equation s~bJ(~)d5=~(2r+t-2w5t5+.. ). The w3 term has disappeared, so this formula tells us that we can get a method that is accurate to within w5 by combining the quadrature formulas in the same way: If an interval size of .Ol is used for Simpson’s rule, then the integral can be computed to about ten-place accuracy. Again, this is borne out in our example. The implementation of Simpson’s method is only slightly more complicated than the others (again, we consider the case where the intervals are the same width): function intsimp(a, b: real; N: integer): real; var i: integer; w, s: real; begin s:=O; w:=(b-a)/N; for i:=l to Ndo s:=s+w*(f(a+(i-l)*w)+4*f(a-w/2+i*w)+f(a+i*w))/6; intsimp:=s; end ; This program requires three “function evaluations” (rather than two) in the inner loop, but it produces far more accurate results than do the previous two methods. 10 0.6931473746651 100 0.6931471805795 1000 0.6931471805599 More complicated quadrature methods have been devised which gain accuracy by combining simpler methods with similar errors. The most well- known is Romberg integration, which uses two different sets of subintervals for its two “methods.”