c17-3 (779603)
Текст из файла
762Chapter 17.Two Point Boundary Value Problemsfor (i=1;i<=n;i++) f[i]=f1[i]-f2[i];free_vector(y,1,nvar);free_vector(f2,1,nvar);free_vector(f1,1,nvar);}CITED REFERENCES AND FURTHER READING:Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America).Keller, H.B. 1968, Numerical Methods for Two-Point Boundary-Value Problems (Waltham, MA:Blaisdell).Stoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag),§§7.3.5–7.3.6.
[1]17.3 Relaxation MethodsIn relaxation methods we replace ODEs by approximate finite-difference equations(FDEs) on a grid or mesh of points that spans the domain of interest. As a typical example,we could replace a general first-order differential equationdy= g(x, y)dxwith an algebraic equation relating function values at two points k, k − 1:yk − yk−1 − (xk − xk−1 ) g 12 (xk + xk−1 ), 12 (yk + yk−1 ) = 0(17.3.1)(17.3.2)The form of the FDE in (17.3.2) illustrates the idea, but not uniquely: There are manyways to turn the ODE into an FDE. When the problem involves N coupled first-order ODEsrepresented by FDEs on a mesh of M points, a solution consists of values for N dependentfunctions given at each of the M mesh points, or N × M variables in all. The relaxationmethod determines the solution by starting with a guess and improving it, iteratively.
As theiterations improve the solution, the result is said to relax to the true solution.While several iteration schemes are possible, for most problems our old standby, multidimensional Newton’s method, works well. The method produces a matrix equation thatmust be solved, but the matrix takes a special, “block diagonal” form, that allows it to beinverted far more economically both in time and storage than would be possible for a generalmatrix of size (M N ) × (M N ). Since M N can easily be several thousand, this is crucialfor the feasibility of the method.Our implementation couples at most pairs of points, as in equation(17.3.2). More points can be coupled, but then the method becomes more complex.We will provide enough background so that you can write a more general scheme if youhave the patience to do so.Let us develop a general set of algebraic equations that represent the ODEs by FDEs.
TheODE problem is exactly identical to that expressed in equations (17.0.1)–(17.0.3) where wehad N coupled first-order equations that satisfy n1 boundary conditions at x1 and n2 = N −n1boundary conditions at x2 . We first define a mesh or grid by a set of k = 1, 2, ..., M pointsat which we supply values for the independent variable xk .
In particular, x1 is the initialboundary, and xM is the final boundary. We use the notation yk to refer to the entire set ofSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).There are boundary value problems where even shooting to a fitting point fails— the integration interval has to be partitioned by several fitting points with thesolution being matched at each such point. For more details see [1].76317.3 Relaxation Methodsdependent variables y1 , y2 , . . .
, yN at point xk . At an arbitrary point k in the middle of themesh, we approximate the set of N first-order ODEs by algebraic relations of the form0 = Ek ≡ yk − yk−1 − (xk − xk−1 )gk (xk , xk−1 , yk , yk−1 ),k = 2, 3, . . . , M (17.3.3)0 = E1 ≡ B(x1 , y1 )(17.3.4)0 = EM +1 ≡ C(xM , yM )(17.3.5)while at the second boundaryThe vectors E1 and B have only n1 nonzero components, corresponding to the n1 boundaryconditions at x1 . It will turn out to be useful to take these nonzero components to be thelast n1 components. In other words, Ej,1 6= 0 only for j = n2 + 1, n2 + 2, .
. . , N . Atthe other boundary, only the first n2 components of EM +1 and C are nonzero: Ej,M +1 6= 0only for j = 1, 2, . . . , n2 .The “solution” of the FDE problem in (17.3.3)–(17.3.5) consists of a set of variablesyj,k , the values of the N variables yj at the M points xk . The algorithm we describebelow requires an initial guess for the yj,k . We then determine increments ∆yj,k such thatyj,k + ∆yj,k is an improved approximation to the solution.Equations for the increments are developed by expanding the FDEs in first-order Taylorseries with respect to small changes ∆yk .
At an interior point, k = 2, 3, . . . , M this gives:Ek (yk + ∆yk , yk−1 + ∆yk−1 ) ≈ Ek (yk , yk−1 )+NXn=1NX∂Ek∂Ek∆yn,k−1 +∆yn,k∂yn,k−1∂yn,kn=1(17.3.6)For a solution we want the updated value E(y + ∆y) to be zero, so the general set of equationsat an interior point can be written in matrix form asNXSj,n ∆yn,k−1 +n=12NXSj,n ∆yn−N,k = −Ej,k ,j = 1, 2, .
. . , N(17.3.7)n=N +1whereSj,n =∂Ej,k,∂yn,k−1Sj,n+N =∂Ej,k,∂yn,kn = 1, 2, . . . , N(17.3.8)The quantity Sj,n is an N × 2N matrix at each point k. Each interior point thus supplies ablock of N equations coupling 2N corrections to the solution variables at the points k, k − 1.Similarly, the algebraic relations at the boundaries can be expanded in a first-orderTaylor series for increments that improve the solution. Since E1 depends only on y1 , wefind at the first boundary:NXSj,n ∆yn,1 = −Ej,1 ,j = n2 + 1, n2 + 2, .
. . , N(17.3.9)n=1whereSj,n =∂Ej,1,∂yn,1n = 1, 2, . . . , N(17.3.10)At the second boundary,NXn=1Sj,n ∆yn,M = −Ej,M +1 ,j = 1, 2, . . . , n2(17.3.11)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).The notation signifies that gk can be evaluated using information from both points k, k − 1.The FDEs labeled by Ek provide N equations coupling 2N variables at points k, k − 1.There are M − 1 points, k = 2, 3, .
. . , M , at which difference equations of the form (17.3.3)apply. Thus the FDEs provide a total of (M − 1)N equations for the M N unknowns. Theremaining N equations come from the boundary conditions.At the first boundary we have764Chapter 17.Two Point Boundary Value ProblemswhereSj,n =∂Ej,M +1,∂yn,Mn = 1, 2, . . . , N(17.3.12)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).We thus have in equations (17.3.7)–(17.3.12) a set of linear equations to be solved forthe corrections ∆y, iterating until the corrections are sufficiently small.
The equations havea special structure, because each Sj,n couples only points k, k − 1. Figure 17.3.1 illustratesthe typical structure of the complete matrix equation for the case of 5 variables and 4 meshpoints, with 3 boundary conditions at the first boundary and 2 at the second. The 3 × 5block of nonzero entries in the top left-hand corner of the matrix comes from the boundarycondition Sj,n at point k = 1. The next three 5 × 10 blocks are the Sj,n at the interiorpoints, coupling variables at mesh points (2,1), (3,2), and (4,3). Finally we have the blockcorresponding to the second boundary condition.We can solve equations (17.3.7)–(17.3.12) for the increments ∆y using a form ofGaussian elimination that exploits the special structure of the matrix to minimize the totalnumber of operations, and that minimizes storage of matrix coefficients by packing theelements in a special blocked structure.
(You might wish to review Chapter 2, especially§2.2, if you are unfamiliar with the steps involved in Gaussian elimination.) Recall thatGaussian elimination consists of manipulating the equations by elementary operations suchas dividing rows of coefficients by a common factor to produce unity in diagonal elements,and adding appropriate multiples of other rows to produce zeros below the diagonal. Herewe take advantage of the block structure by performing a bit more reduction than in pureGaussian elimination, so that the storage of coefficients is minimized. Figure 17.3.2 showsthe form that we wish to achieve by elimination, just prior to the backsubstitution step.
Only asmall subset of the reduced M N × M N matrix elements needs to be stored as the eliminationprogresses. Once the matrix elements reach the stage in Figure 17.3.2, the solution followsquickly by a backsubstitution procedure.Furthermore, the entire procedure, except the backsubstitution step, operates only onone block of the matrix at a time. The procedure contains four types of operations: (1)partial reduction to zero of certain elements of a block using results from a previous step,(2) elimination of the square structure of the remaining block elements such that the squaresection contains unity along the diagonal, and zero in off-diagonal elements, (3) storage of theremaining nonzero coefficients for use in later steps, and (4) backsubstitution.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
