`Boundary-Value ProblemsCom S 477/577 Nov 12, 20021IntroductionNow we consider boundary-value problems in which the conditions are specified at more than one point. The crucial distinction between initial values problems and boundary value problems is that in the former case we are able to start an acceptable solution at its beginning (initial values) and just march it along by numerical integration to its end (final values); while in the present case, the boundary conditions at the staring point do not determine a unique solution to start with -- and a &quot;random&quot; choice among the solutions that satisfy these (incomplete) starting boundary conditions is almost certain not to satisfy the boundary conditions at the other specified points. A simple example of a second-order boundary-value problem is y  (x) = y(x), y(0) = 0, y(1) = 1.This is a classic exponential growth/decay problem. Another example is a fourth-order system which has the form y (4) (x) + ky(x) = q with boundary conditions y(0) = y  (0) = 0 and y(L) = y  (L) = 0.This problem arises in the context of beam bending, Here y(x) represents the beam deflection at point x along its length, q represents a uniform load, and L is the beam's length. The first two boundary conditions say that one end of the beam (x = 0) is rigidly attached. The second two boundary conditions say that the other end of the beam (x = L) is simply supported.2Finite-Difference MethodWe will use a finite-difference method to obtain numerical solutions to boundary value problems. Our assumption is that the differential equation is linear. Suppose we are interested in a solution over some interval [a, b], with boundary conditions specified at the endpoints of this interval. We split the interval into N equal parts, each of width h = b-a . Next we set x0 = a and xN = b and define the interior mesh points as N xn = x0 + nh, n = 1, 2, . . . , N - 1.1Often it is useful to define exterior mesh points such as x-1 = x0 - h, xN +1 = xN + h, . . .As before, let y(xn ) denote the exact solution of y(xn ) at x = xn , and yn denote its approximate solution. Next, we set up a finite-difference approximation for each of the derivatives that appears in our differential equation. In order to achieve O(h2 ) error, we use central differences, for instance, y  (xn )  y  (xn )  y (4) (xn )  yn+1 - yn-1 , 2h yn+1 - 2yn + yn-1 h2 yn+2 - 4yn+1 + 6yn - 4yn-1 + yn-2 . h4Then we write down the differential equation once for each interior mesh point, using the finite-difference approximation. We also write down each of the boundary conditions, using the finite-difference approximations.1 In the end we will have created a system of linear equations Ay = b. If we have m mesh points total (interior, boundary, or exterior), then y is an m × 1 vector of unknowns, A is an m × m matrix, and b is an m × 1 constant vector. The coefficients of A are determined by the differential equation and the boundary conditions, as are the coefficients of b. For a second order system, A is tridiagonal. Now we introduce the scheme of central difference derivations:  0 fk = fk , m fk+ 12= m-1 fk+1 - m-1 fk ,2 2m = 1, 3, 5, . . . , m = 2, 4, 6, . . .m fk = m-1 fk+ 1 - m-1 fk- 1 , We use the approximation: D n fk = and compute 1 f 12dn f dxnx=xk n fk , hnfor small h,=  0 f1 -  0 f0 = f1 - f0 , f0 =  1 f 1 -  1 f- 12 22= (f1 - f0 ) - (f0 - f-1 ) = f1 - 2f0 + f-1 ,  f123=  2 f1 -  2 f0 = (f2 - 2f1 + f0 ) - (f1 - 2f0 + f-1 )1Notice that this may force us to create exterior mesh points.2= f2 - 3f1 + 3f0 - f-1 ,  f0 =  3 f 1 -  3 f- 12 24= (f2 - 3f1 + 3f0 - f-1 ) - (f1 - 3f0 + 3f-1 - f-2 = f2 - 4f1 + 6f0 - 4f-1 + f-2 ,  f125=  4 f1 -  4 f0 = (f3 - 4f2 + 6f1 - 4f0 + f-1 ) - (f2 - 4f1 + 6f0 - 4f-1 + f-2 ) = f3 - 5f2 + 10f1 - 10f0 + 5f-1 - f-2 .So the derivatives are approximated as D1 f 12D 1 f0  D 2 f0  D3 f 12D 3 f0  D 4 f0  D5 f 12D5  D 6 f0  . . .Example 1.f1 - f0 1 , for 2 steps, h f1 - f-1 , for full steps, 2h f1 - 2f0 + f-1 , h2 f2 - 3f1 + 3f0 - f-1 , for 1 steps, 2 h3 f3 - 3f1 + 3f-1 - f-3 , for full steps, 8h3 f2 - 4f1 + 6f0 - 4f-1 + f-2 , h4 f3 - 5f2 + 10f1 - 10f0 + 5f-1 - f-2 , for 1 steps, 2 h5 f5 - 5f3 + 10f1 - 10f-1 + 5f-3 - f-5 , for full steps, 32h5 f3 - 6f2 + 15f1 - 20f0 + 15f-1 - 6f-2 + f-3 , h6Let us consider the following problem: y  = y, with y(0) = 0, y(1) = 1.A finite-difference approximation yields yn+1 - 2yn + yn-1 = yn , h2 for n = 0, 1, . . . , N - 1.Rewrite the above equations and list them together the boundary conditions: -yn-1 + (2 + h2 )yn - yn+1 y0 yN = 0, = 0, = 1. n = 0, 1, . . . , N - 1,3or in matrix form  1 0 -1 2 + h2 .. . -1 .. .  -1 2 + h2   -1      0.. .0-1 2 + h2 0 y0    y1    y2   .  .  .   yN -1 -1  yN 1        =       0 10 0 0 . . .    .   From the boundary conditions we easily see that y0 = 0 and yN = 1. So the above system can be simplified to       2 + h2 -1 y1 0   2   y2   0   -1 2 + h -1       .   .   .. .. ..  .  =  . .  . . .  .   .     yN -2   0    -1 2 + h2 -1  yN -1 1 -1 2 + h200Setting h = 0.1, we get the following 9 × 9 system  2.01 -1  -1 2.01 -1    -1 2.01 -1   -1 2.01 -1   -1 2.01 -1    -1 2.01 -1   -1 2.01 -1   -1 2.01 -1 -1 2.0100               y1 y2 y3 y4 y5 y6 y7 y8 y9            =            0 0 0 0 0 0 0 0 1      .      We solve this system using, say, Gaussian elimination and compare the results to the true values. Note that an exact solution to the differential equation is y(x) = ex - e-x . e- 1 e y(xn ) 0 0.08523 0.17132 0.25912 0.34952 0.44341 0.54174 0.64549 0.75571 0.87348 1.0xn 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 The minimum error is about 5 · 10-5 .yn 0 0.08524 0.17134 0.25915 0.34955 0.44345 0.54178 0.64553 0.75574 0.87350 1.043RelaxationWe have seen how to construct a linear system Ay = b from a linear boundary value problem. The system Ay = b can be solved using any of the methods (LU decomposition, SVD, etc.) that we learned before. But sometimes, rather than use a direction method, we may wish to &quot;relax&quot; to a solution. The basic idea is to start with a guess to the solution of Ay = b, then use each of the constraint equations to update this guess. Consider, for instance, second order boundary values problems. Here A is a tridiagonal matrix:     d0 c1 b0  a0 d1  b1   c2       .   .. .. .. A= and b =  . . , . . .   .     bN -1  aN -2 dN -1 cN  aN -1 dN bN A typical interior row represents the equation an-1 yn-1 + dn yn + cn+1 yn+1 = bn , which can be rewritten as yn =(i)bn - an-1 yn-1 - cn+1 yn+1 . dn(1)Denote by yn the approximate solution to y(xn ) that we have obtained at the ith relaxation (0) (0) (0) step. So (y0 , y1 , . . . , yN ) constitute our initial guess. We update guesses using the formula (1). There are two common updating methods. · Jacobi iteration updates values at the (i + 1)-st stage using only values from the ith stage, namely, (i) (i) bn - an-1 yn-1 - cn+1 yn+1 (i+1) , i = 1, 2, . . . yn = dn · Gauss-Seidel iteration updates values at the (i + 1)-st stage using the most recently available values, independent of whether they were obtained in the ith stage or (i + 1)-st stage. The formula is (i+1) (i) bn - an-1 yn-1 - cn+1 yn+1 (i+1) , i = 1, 2, . . . yn = dn From the Gauss-Seidel method we can get a better algorithm if we make an overcorrection to the value y (i+1) , more specifically, if we use the following iteration formula:(i+1) (i) yn = (1 - w)yn + wbn - an-1 yn-1 - cn+1 yn+1 , dn(i+1)(i)i = 1, 2, . . .where w is the overrelaxation parameter. This method, referred to as successive overrelaxation (SOR), can be shown to converge for 0 &lt; w &lt; 2.5To get overrelaxation, choose w &gt; 1 to overshoot the correction term. There are ways of choosing w nicely. For instance, let J be the spectral radius of Jacobi method, i.e., the largest magnitude of all eigenvalues of the coefficient matrix on the right hand side of (1) for n = 0, 1, . . . , N :   c 0 d1 0  a0 0  c2  d1  d1   .. .. ..  . . . .   aN-2   cN 0  dN-1 dN-1  aN-1 0 dN Then you may use w= 1+ 2 1 - 2 J,which tends to converge faster than Gauss-Seidel. Relaxation methods are easy to implement and can handle boundary conditions. Their convergence, when exists, tends to be global. The drawback is that convergence may be very slow. It is also difficult for relaxation to handle differential equations whose solutions are highly oscillatory. The convergence is not always guaranteed. But there is an eigenvalue test for convergence. If this test is positive, then convergence is global. For second order boundary value problems, if the step size h is small enough, then convergence is global. Relaxation can be viewed as a form of fixed-point iteration: y (i+1) = By (i) + b , where B is a matrix determined by A and the type of relaxation. The rate of convergence is governed by the largest eigenvalue magnitude, ||, of B. If || &lt; 1, then convergence is global.4The Shooting MethodThe basic idea of the shooting method is this: Instead of tying a general solution to a boundary value problem down at both points, one only ties it down at one end. This leaves a free parameter (in the case of a second order problem). For a given value of this free parameter, one then integrates out a solution to the differential equation. Specifically, you start at the tied-down boundary point and integrate out just like an initial value problem. When you get to the other boundary point, the error between your solution and the true boundary condition tells you how to adjust the free parameter. Repeat this process until a solution matching the second boundary condition is obtained. The shooting method tend to converge very quickly and it also works for non-linear differential equations. The disadvantage is that convergence is not guaranteed. To begin, given a boundary value problem y  = f (x, y, y  ), y(a) = , y(b) = ,the idea is to find the absent initial value y  (a) that would enable y to attain  at x = b.6For each initial value s for y  (a), the initial value problem in general has a unique solution y(x)  y(x; s). So the original boundary value problem reduces to finding a zero s of the function F (s) = y(b; s) - .y ( x) y (b; s1)  y (b) =  y(b; s0) y(b; s0)  a b x s0 s* s1 s y(b; s ) y (b; s1) y (b) = But how to solve F (s) = 0? Use any method we learned before for solving nonlinear equations: bisection, secant, or even Newton's method. The difference is now each evaluation of F (s) involves solving a separate initial value problem for which y(a) = , y  (a) = s!Example 2. Consider the boundary value problem w = 3 2 w , 2 w(0) = 4, w(1) = 1.One finds the solution of the initial value problem w = 3 2 w , 2 w(0; s) = 4, w (0; s) = s.The graph of F (s) = w(1; s) - 1 is sketched in the left figure below.w (1; s) - 1 70 60 50 40 30 20 10 06 4 2 0 -2 -4 -6 -8 -10 -12 0.2w1(x )0.40.60.81.0s2 -100 -80 -60 -40 -20s1w2(x )In the best case, bisection would find two solutions s1 = -8.0 ¯ and s2 = -35.858548. ¯The right figure sketches the graphs of the two solutions wi (x) = w(x, si ), i = 1, 2, of the boundary value ¯ problem.7For systems of equations of higher order (or with multiple variables), the shooting method becomes considerably more complicated. Consider, for example, the following system of four equations x = f (x, y, z, w, t), y  = g(x, y, z, w, t), z  = h(x, y, z, w, t), w with two conditions at t = 0: x(0) = x0 , and two conditions at t = T : z(T ) = zT , w(T ) = wT . Let z(0) = , w(0) =  be the correct initial values of z and w, and let 0 , 0 be their guesses. Integrating the system with initial guesses 0 , 0 , we obtain the values of z and w at T : z(T ; 0 , 0 ) and w(T ; 0 , 0 ). Expand z(T ; , ) and w(T ; , ) into a Taylor series through linear terms: z z (T ; 0 , 0 ) + ( - 0 ) (T ; 0 , 0 ),   w w (T ; 0 , 0 ) + ( - 0 ) (T ; 0 , 0 ). w(T ; , )  w(T ; 0 , 0 ) + ( - 0 )   z(T ; , )  z(T ; 0 , 0 ) + ( - 0 ) Now approximate the partial derivatives by difference quotients z (T ; 0 , 0 )  z (T ; 0 , 0 )  w (T ; 0 , 0 )  w (T ; 0 , 0 )  = = = = z(T ; 0 + 0 , 0 ) - z(T ; 0 , 0 ) , 0 z(T ; 0 ,  + 0 ) - z(T ; 0 , 0 ) , 0 w(T ; 0 + 0 , 0 ) - w(T ; 0 , 0 ) , 0 w(T ; 0 ,  + 0 ) - w(T ; 0 , 0 ) , 0 (3) y(0) = y0 ,(2)= l(x, y, z, w, t),where z(T ; 0 + 0 , 0 ) and w(T ; 0 + 0 , 0 ) are obtained from system (2) with initial values x0 , y0 , 0 + 0 , 0 . And z(T ; 0 , 0 + 0 ) and w(T ; 0 , 0 + 0 ) are solved with initial values x0 , y0 , 0 , 0 + 0 .2 Let z(T ; , ) = zT and w(T ; , ) = wT in (3) and let the solution of  and  obtained from (3) be denoted by 1 , 1 . Repeat the entire procedure.AMore on RelaxationSuppose we start with a system Ax = b that appears to be too difficult to solve directly. So instead we look at M x = (M - A)x + b, for some M .2Note that we have solved system (2) three times already, each with a different combination of initial values.8Iterative methods solve the system as follows: M x(i+1) = (M - A)x(i) + b. The key is to choose M suitably. Introduce the decomposition A = L + D + U , where L, D, and U respectively include the lower diagonal, diagonal, and upper diagonal elements of A. · M = A: This gives us convergence in one step, but then we are doing the work we wanted to avoid. · M = I: This gives us fixed point iteration x(i+1) = Bx(i) + b, for some B = I - A.If the spectral radius B &lt; 1, the above is a contraction mapping and thus converges. · M = D: This yields the Jacobi method: Dx(i+1) = -(L + U )x(i) + b. · M = L + D: This yields the Gauss-Seidel method: (L + D)x(i+1) = -U x(i) + b. · To get successive overrelaxation (SOR), we first rewrite Gauss Seidel as (L + D)x(i+1) = (L + D)x(i) - (L + D + U )x(i) + b. So x(i+1) = x(i) - (L + D)-1 Ax(i) - b . Next, we overshoot by writing x(i+1) = x(i) - w(L + D)-1 Ax(i) - b . This gives(i+1) xk (j) N j=1 akj xj=(i) xk-w-k-1 j=1 akj xj- bkakk,where (L + D)x = Ax(i) - b. When does each method converge? And how fast if so? The answers are related to the eigenvalues of M -1 (M - A). Suppose we define the error term e(i) = x - x(i) . Then M e(i+1) = (M - A)e(i) and thus e(i+1) = Be(i) 9where B = M -1 (M - A) = I - M -1 A. It follows from the above that e(i) = B i e(0) . That e(i)  0 if any only if B i  0, if and only if every eigenvalue  of B satisfies || &lt; 1. So the role of convergence is governed by the largest ||, that is, the spectral radius of B.References M. Erdmann. Lecture notes for 16-811 Mathematical Fundamentals for Robotics. The Robotics Institute, Carnegie Mellon University, 1998.  S. D. Conte and Carl de Boor. Elementary Numerical Analysis. McGraw-Hill, Inc., 2nd edition, 1972.  F. B. Hildebrand. Finite-difference Equations and Simulations. Prentice-Hall, 1968.  G. H¨mmerlin and K.-H. Hoffman. Numerical Mathematics. Springer-Verlag New York, Inc., a 1991.  J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. Springer-Verlag New York, Inc., 2nd edition, 1993.10`

10 pages

#### Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

58180