Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 70
Текст из файла (страница 70)
Then solve this system, using a computerprogram based on Algorithm 4.3.412BOUNDARY-VALUE PROBLEMS IN ORDINARY DIFFERENTIAL EQUATIONS9.1-4 Show that the Gauss-Seidel iterative method can also be used to solve the system ofExample 9.1, and obtain this solution by iteration to four significant figures of accuracy. Forthis problem, is the direct method more efficient than the iterative method?9.1-5 Solve by difference methods the boundary-value problemy´´ + 2y´ + y = xy (0) = 0y (1) = 0using h = 1/8, h = 1/16, and improve the results by extrapolation.9.2 SHOOTING METHODSFor linear boundary-value problems, a number of methods can be used.The method of differences described above works reasonably well in suchcases.
Other methods attempt to obtain linearly independent solutions ofthe differential equation and to combine them in such a way as to satisfythe boundary conditions. For nonlinear equations, the latter methodcannot be used. Difference methods can be adapted to nonlinear problems,but they require guessing at a tentative solution and then improving this byan iterative process.
In addition to the complexity of the programmingrequired, there is no guarantee of convergence of the iterations. Theshooting method to be described in this section applies equally well tolinear and nonlinear problems. Again, there is no guarantee of convergence, but the method is easy to apply, and when it does converge, it isusually more efficient than other methods.Consider again the problem given in (9.1). We wish to apply theinitial-value methods discussed in Chap. 8, but to do so, we must knowboth y(0) and y´(0).
Since y´(0) is not prescribed, we consider it as anunknown parameter, say a, which must be determined so that the resultingsolution yields the prescribed value y(1) to some desired accuracy. Wetherefore guess at the initial slope and set up an iterative procedure forconverging to the correct slope. Let αo, αl be two guesses at the initialslope y´(0), and let y(α 0; 1), y(α1; 1) be the values of y at x = 1 obtainedfrom integrating the differential equation. Graphically, the situation maybe presented as in Figs.
9.1 and 9.2.In Fig. 9.1 the solutions of the initial-value problems are drawn, whilein Fig. 9.2, y( α; 1) is plotted as a function of a. A normally betterapproximation to α can now be obtained by linear interpolation. Theintersection of the line joining PO to P1 with the line y(1) = 1 has its acoordinate given by(9.12)We now integrate the differential equation, using the initial values y(0) =0, y´(0) = α2, to obtain y(α2; 1). Again, using linear interpolation based onαΙ, α2 , we can obtain a next approximation α3 . The process is repeated9.2Figure 9.1SHOOTING METHODS413Figure 9.2until convergence has been obtained, i.e., until y(α i ; 1) agrees with y(1) = 1to the desired number of places.
There is no guarantee that this iterativeprocedure will converge. The rapidity of convergence will clearly dependupon how good the initial guesses are. Estimates are sometimes availablefrom physical considerations, and sometimes from simple graphical representations of the solution.For a general second-order boundary-value problemy´´ = f(x,y,y´)y(0) = y0y(b) = y b(9.13)the procedure is summarized in Algorithm 9.1.Algorithm 9.1: the shooting method for second-order boundary-valueproblems1.
Let αk be an approximation to the unknown initial slope y´(0) = α.(Choose the first two α0, α1, using physical intuition.)2. Solve the initial-value problemy´´ = f(x, y, y´)y(0) = y0y´(0) = αkfrom x = 0 to x = b, using any of the methods of Chap. 8. Call thesolution y(α k; b) at x = b.3. Obtain the next approximation from the linear interpolationk = 1, 2, . . .4. Repeat steps 2 and 3 until |y(α k; b) - yb| < ε for a prescribed ε.The iteration used in Algorithm 9.1 is an application of the secantmethod described in Chap. 3.414BOUNDARY-VALUE PROBLEMS IN ORDINARY DIFFERENTIAL EQUATIONSFor systems of equations of higher order,considerably more complicated, and convergenceThe general situation for a nonlinear systemfollows, We consider a system of four equationsthis procedure becomesmore difficult to obtain.may be represented asin four unknowns:x´ = f(x, y, z, w, t)y´ = g(x, y, z, w, t)z´ = h(x, y, z, w, t)w´ = l(x, y, z, w, t)(9.14)where now t represents the independent variable.
We are given twoconditions at t = 0, sayx(0) = x0y(0) = y0and two conditions at t = T, sayz(T) = z Tw(T) = w TLet z(0) = α, w(0) = β be the correct initial values of z(0), w(0), and let α0 ,β 0 be guesses for these initial values. Now integrate the system (9.14), anddenote the values of z and w obtained at t = T by z(α0, β0; T) andw ( α0, β0; T).Since z and w at t = T are clearly functions of α and β, we mayexpand z(α, β; T) and w(α, β; T) into a Taylor series for two variablesthrough linear terms:(9.15)We may set z(α, β, T) and w(α, β; T) to their desired values zT and wT,but before we can solve (9.15) for the corrections α - α0 and β - β 0, wemust obtain the partial derivatives in (9.15).
We do not know the solutionsz and w and therefore cannot find these derivatives analytically. However,we can find approximate numerical values for them. To do so, we solve(9.14) once with the initial conditions x0, y0, α0, β0, once with the conditions x0, y0, α0 + ∆α0, β0, and then with the conditions x0, y0, α0, β0 +∆β0, where ∆α0 and ∆β0 are small increments. Omitting the variables x0, y09.2SHOOTING METHODS415which remain fixed, we then form the difference quotients:After replacing z( α, β; T) by zT and w(α, β; T) by wT, we can then solve(9.15) for the corrections δα0 = α - α0 and δβ0 = β - β 0, to obtain newestimates α1 = α0 + δα0, β1 = β 0 + δα0 for the parameters α and β.
Theentire process is now repeated, starting with x0 , y0 , α1 , β 1 as the initialconditions.Each iteration thus consists in solving the system (9.14) three times. Ingeneral, if there are n unknown initial parameters, each iteration willrequire n + 1 solutions of the original system. The method used here isequivalent to a modified Newton’s method for finding the roots of equations in several variables (see Sec. 5.2).Boundary-value problems constitute one of the most difficult classes ofproblems to solve on a computer.
Convergence is by no means assured,good initial guesses must be available, and considerable trial and error, aswell as large amounts of machine time, are usually required.Example 9.2 Solve the problem (9.1), using the shooting method. Start with the initialapproximations α0 = 0.3 and α1 = 0.4 to y´(0) and h = 0.1.The solution given below was obtained using the standard RK4 differentialequation solver described in Chap.
8, combined with linear interpolation based on(9.12). The iteration was stopped by the conditionkαky ( α k; 1)01230.300000000.400000000.850917120.850917120.352560770.470081030.999999990.99999999The correct value of y´ at x = 0 is sinh-1 1 = 0.85091813. Convergence for this problemis very rapid. Moreover, the indicated accuracy is exceptionally good, considering thecoarse step size used. To obtain comparable accuracy using the finite-differencemethods of Sec.
9.1 would require a step size h = 0.01. Nevertheless, the finite-differencemethod might still be computationally more efficient.416BOUNDARY-VALUE PROBLEMS IN ORDINARY DIFFERENTIAL EQUATIONSExample 93 Solve the nonlinear boundary-value problemyy´´ + 1 + y´2 = 0y (0) = 1y (1) = 2(9.16)by the shooting method.SOLUTION Let α0 = 0.5, α1 = 1.0 be two approximations to the unknown slope y´(0).Using again the RK4 package and linear interpolation with a step size h = 1/64 thefollowing results were obtained:αi0.50000000.99999991.70710711.95541181.99829681.99999402.0000035y (α i; 1)0.99999991.41421331.84775821.97757861.99914631.99999522.0000000The correct slope at x = 0 is y´(0) = 2.
After the seven iterations, the initial slope isseen to be correct to six significant figures, while the value of y at x = 1 is correct to atleast seven significant figures. After the first three iterations, convergence could havebeen speeded up by using quadratic interpolationThe required number of iteration will clearly depend on the choice of the initialapproximations α0 and α1 . These approximations can be obtained fromgraphical or physical considerations.EXERCISES9.2-l Find a numerical solution of the equationTake α0 = 0.5, α1 = 0.8 as initial approximations to y´(π/6), and iterate until the condition atx = π/2 is satisfied to five places.SOLUTION y = (sin x) 2; and the initial slope is9.2-2 In Example 9.3 use quadratic interpolation based on α0 α1 , α2 to obtain the nextapproximation.
How many iterations would have been saved?9.2-3 Solve the following problems, using the shooting method:(a) y´´ = 2y3, y(1) = 1, y(2) = 1/2, taking y´(1) = 0 as a first guess. (Exact solution:y = 1/ x .)(b) y´´ = ey, y(0) = y(1) = 0, taking y´(0) = 0 as a first guess.9.3 COLLOCATION METHODSIn recent years a great deal of interest has focused on approximationmethods for solving boundary-value problems in both one- and higherdimensional cases.
In those approximation methods, rather than seeking a9.3COLLOCATION METHODS417solution at a discrete set of points, an attempt is made to find a linearcombination of linearly independent functions which provide an approximation to the solution. Actually the basic ideas are very old, havingoriginated with Galerkin and Ritz [31], but more recently they have takennew shape under the term “finite element” methods (see Strang and Fix[31]), and they have been refined to the point where they are now verycompetitive with finite-difference methods.We shall sketch very briefly the basic notions behind these approximation methods focusing on the so-called collocation method (see Strang andFix [31]).For simplicity we assume that we have a second-order linearboundary-value problem which we write in the formLy = -y´´ + p(x)y´ + q(x)y = r(x)a < x < ba 0 y(a) - a 1 y´(a) = α(9.17a)(9.17b)b0y(b) + b1y´(b) = βLetbe a set of linearly independent functionsto be chosen in a manner to be described later.
An approximate solution to(9.17) is then sought in the form(9.18)The coefficients {cj} in this expansion are to be chosen so as to minimizesome measure of the error in satisfying the boundary-value problem.Different methods arise depending on the definition of the measure oferror.In the collocation method the coefficients are chosen so that U N(x)satisfies the boundary conditions (9.17b ) and the differential equation(9.17 a) exactly at selected points interior to the interval [a,b].
Thus the{cj} satisfy the equationsa 0 U N(a) - a 1 U´N(a) = αb 0 U N(b) + b 1 U´N(b) = βLU N (x) - r(x i ) = 0(9.19)i=1,...,N-2where the xi are a set of distinct points on the interval [a,b]. When writtenout (9.19) is a linear system of N equations in the N unknowns {cj}. Once(9.19) is solved, by, for example, the methods of Chap. 4, its solution {cj} issubstituted into (9.18) to obtain the desired approximate solution. Theerror analysis for this method is very complicated and beyond the scope ofthis book. In practice one can obtain a sequence of approximations byincreasing the number N of basis functions.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
