《算法课件全121301ADA12变治法高斯消去法与多项式计算》由会员分享，可在线阅读，更多相关《算法课件全121301ADA12变治法高斯消去法与多项式计算（21页珍藏版）》请在金锄头文库上搜索。
1、Transform and Conquer (I),Chapter 6,Introduction to Transform-and-Conquer Its Application to Numerical Problem Linear Equation Calculating Polynomials,2019/6/21,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should Master the basic idea and
2、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,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Transform and Conquer (basic idea),Second, the modifie
3、d instance is solved, we call this as a conquering stage,Original instance,More amenable instance,Solution,transform,conquer,Transform and conquer deals with a group of design methods that are based on the idea of transformation,First, the original problems instance is modified to be more amenable t
4、o solve, we call this as a transformation stage,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,3 Types of Transform and Conquer,Computing the least common multiple Linear programming,Instance simplification: Transform to a simpler/more convenient instance of the same problem,Presorti
5、ng Solving linear equation,Representation change: Transform to a different representation of the same instance,Calculating polynomial Heap sort,Problem reduction: Transform to a different problem for which an algorithm is already available,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SC
6、UN,Instance simplification - Presorting,Also: Presorting is used in many geometric algorithms.,Many problems involving lists are easier when list is sorted.,searching,computing a mode,checking if all elements are distinct (element uniqueness),a value that occurs most often in a given list of numbers
7、,2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear equation Examples and General form(p203-208),Standard method (cramer method),Example: How to solve the problem of chickens and rabbits in the same cage?,Generally, a system of linear equations is a set of n equations
8、 with n unknown variables. Typically these equations can be written as: a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . an1x1 + an2x2 + + annxn = bn,2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear equation Gauss Method,Solve the latter by substitutions
9、starting with the last equation and moving up to the first one (Backward substitution),Transform to: An equivalent system of n linear equations in n unknowns with an upper triangular coefficient matrix (Elimination),2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear e
10、quation Elimination process,So the result would be:,From the first row to last row (k=1,2,n), we do the following transform (elementary operations):,2012-2013-01 Design and Analysis of Algorithm SCUN,Instance simplification: Linear equation Backward substitution process,So the result would be:,From
11、the last row to the first row (i=n,n-1,1), we can do the following backward substitution:,2012-2013-01 Design and Analysis of Algorithm SCUN,Example of Gauss method,Result: x1= 2, x2 = 1, x3 = 6,Solve 2x1 - 4x2 + x3 = 6 3x1 - x2 + x3 = 11 x1 + x2 - x3 = -3,2012-2013-01 Design and Analysis of Algorit
12、hm SCUN,Algorithm Description,void GSElimination(int n, double *a, double *b) int k, i, j; for(k=0; kn; k+) /Elimination process for(j=k+1; jn; j+) akj = akj/akk; bk = bk/akk; for(i=k+1; in; i+) for(j=k+1; jn; j+) aij = aij - aik*akj; bi = bi - aik*bk; ,2012-2013-01 Design and Analysis of Algorithm
13、SCUN,Algorithm Description (cont.),/Backward substitution process for(i=n-2; i=0; i-) for(j=i+1; jn; j+) bi = bi - aij*bj; / end of algorithm,2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,Algorithm analysis,So the total numbers of multiplications is:,The elimination process,The bac
14、kward substitution process,2019/6/21,15,2012-2013-01 Design and Analysis of Algorithm SCUN,Thinking,Is the algorithm described before always correct?,No. If Ai,i=0, we can not divide by it and hence cannot use the ith row as a pivot for the ith iteration of the algorithm,How to fix the above problem
15、?,We can use the first elementary transformation to exchange the ith row with some row below it that has a nonzero coefficient in the ith column.,Has any other problem?,Yes. If Ai,i is so small and consequently the scaling factor Aj,i/Ai,i so large that the new value of Aj,k might become distorted by a round-off error.,How to fix the above problem?,Always look for a row with the largest absolute value of coefficient in the ith column and exchange it with the ith row,16,2012-2013-01 Design and Analysis of Algorithm SCUN,Representation Change Polynomial Evaluat
