ADA(变治法高斯消去法与多项式计算).pptVIP

2007-2008-01《Design and Analysis of Algorithms》SCUEC Goals of the Lecture At the end of this lecture, you should Master the basic idea and all kinds of variations of transform and conquer technique Master the linear equation solving algorithm and its analysis Master the Polynomials calculating algorithm and its analysis Transform and Conquer (basic idea) Second, the modified instance is solved, we call this as a conquering stage 3 Types of Transform and Conquer Computing the least common multiple Linear programming Instance simplification - Presorting Also: Presorting is used in many geometric algorithms. Instance simplification: Linear equation – Examples and General form(p203-208) Standard method (cramer method) Instance simplification: Linear equation – Gauss Method Instance simplification: Linear equation – Elimination process Instance simplification: Linear equation – Backward substitution process Example of Gauss method Result: x1= 2, x2 = 1, x3 = 6 Algorithm Description Algorithm Description (cont.) Algorithm analysis So the total numbers of multiplications is: Thinking Is the algorithm described before always correct? Representation Change －Polynomial Evaluation (p230-233) p ? a0+ a1*x power ? x for i ? 2 to n do power ? power * x p ? p + ai * power return p Horner’s Rule Horner’s rule is based on recognizing that the polynomial equation can be factored into the following form: Example: p(x) = 2x4 - x3 + 3x2 + x - 5 The computations are obtained by simply arranging the coefficient in a table and proceeding as follows: coefficients 2 -1 3 1 -5 x=3 Algorithm Description Analysis HornersMethod(p[0…n], x) //Input: An array p[0…n] of coefficients of a polynomial of degree // n (stored from the lowest to the highest) and a number x //Output: The value of the polynomial at x result ? p[n] for i ? n-1 downto 0 do result ? result * x + p[i] return result Stand