Read odeboundaryvalue.pdf text version
BoundaryValue Problems
Com S 477/577 Nov 12, 2002
1
Introduction
Now we consider boundaryvalue 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 "random" 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 secondorder boundaryvalue problem is y (x) = y(x), y(0) = 0, y(1) = 1.
This is a classic exponential growth/decay problem. Another example is a fourthorder 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.
2
FiniteDifference Method
We will use a finitedifference 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 = ba . 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 x1 = 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 finitedifference 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  yn1 , 2h yn+1  2yn + yn1 h2 yn+2  4yn+1 + 6yn  4yn1 + yn2 . h4
Then we write down the differential equation once for each interior mesh point, using the finitedifference approximation. We also write down each of the boundary conditions, using the finitedifference 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+ 1
2
= m1 fk+1  m1 fk ,
2 2
m = 1, 3, 5, . . . , m = 2, 4, 6, . . .
m fk = m1 fk+ 1  m1 fk 1 , We use the approximation: D n fk = and compute 1 f 1
2
dn f dxn
x=xk
n fk , hn
for small h,
= 0 f1  0 f0 = f1  f0 ,
f0 = 1 f 1  1 f 1
2 2
2
= (f1  f0 )  (f0  f1 ) = f1  2f0 + f1 , f1
2
3
= 2 f1  2 f0 = (f2  2f1 + f0 )  (f1  2f0 + f1 )
1
Notice that this may force us to create exterior mesh points.
2
= f2  3f1 + 3f0  f1 , f0 = 3 f 1  3 f 1
2 2
4
= (f2  3f1 + 3f0  f1 )  (f1  3f0 + 3f1  f2 = f2  4f1 + 6f0  4f1 + f2 , f1
2
5
= 4 f1  4 f0 = (f3  4f2 + 6f1  4f0 + f1 )  (f2  4f1 + 6f0  4f1 + f2 ) = f3  5f2 + 10f1  10f0 + 5f1  f2 .
So the derivatives are approximated as D1 f 1
2
D 1 f0 D 2 f0 D3 f 1
2
D 3 f0 D 4 f0 D5 f 1
2
D5 D 6 f0 . . .
Example 1.
f1  f0 1 , for 2 steps, h f1  f1 , for full steps, 2h f1  2f0 + f1 , h2 f2  3f1 + 3f0  f1 , for 1 steps, 2 h3 f3  3f1 + 3f1  f3 , for full steps, 8h3 f2  4f1 + 6f0  4f1 + f2 , h4 f3  5f2 + 10f1  10f0 + 5f1  f2 , for 1 steps, 2 h5 f5  5f3 + 10f1  10f1 + 5f3  f5 , for full steps, 32h5 f3  6f2 + 15f1  20f0 + 15f1  6f2 + f3 , h6
Let us consider the following problem: y = y, with y(0) = 0, y(1) = 1.
A finitedifference approximation yields yn+1  2yn + yn1 = yn , h2 for n = 0, 1, . . . , N  1.
Rewrite the above equations and list them together the boundary conditions: yn1 + (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 1
0 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 + h2
0
0
Setting 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.01
0
0
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  ex . 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.0
xn 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 · 105 .
yn 0 0.08524 0.17134 0.25915 0.34955 0.44345 0.54178 0.64553 0.75574 0.87350 1.0
4
3
Relaxation
We 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 "relax" 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 an1 yn1 + dn yn + cn+1 yn+1 = bn , which can be rewritten as yn =
(i)
bn  an1 yn1  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  an1 yn1  cn+1 yn+1 (i+1) , i = 1, 2, . . . yn = dn · GaussSeidel 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  an1 yn1  cn+1 yn+1 (i+1) , i = 1, 2, . . . yn = dn From the GaussSeidel 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 + w
bn  an1 yn1  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 < w < 2.
5
To get overrelaxation, choose w > 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 .. .. .. . . . . aN2 cN 0 dN1 dN1 aN1 0 dN Then you may use w= 1+ 2 1  2 J
,
which tends to converge faster than GaussSeidel. 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 fixedpoint 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  < 1, then convergence is global.
4
The Shooting Method
The 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 tieddown 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 nonlinear 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 0
6 4 2 0 2 4 6 8 10 12 0.2
w1(x )
0.4
0.6
0.8
1.0
s2 100 80 60 40 20
s1
w2(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.
A
More on Relaxation
Suppose 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 .
2
Note 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 < 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 GaussSeidel 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

k1 j=1 akj xj
 bk
akk
,
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  < 1. So the role of convergence is governed by the largest , that is, the spectral radius of B.
References
[1] M. Erdmann. Lecture notes for 16811 Mathematical Fundamentals for Robotics. The Robotics Institute, Carnegie Mellon University, 1998. [2] S. D. Conte and Carl de Boor. Elementary Numerical Analysis. McGrawHill, Inc., 2nd edition, 1972. [3] F. B. Hildebrand. Finitedifference Equations and Simulations. PrenticeHall, 1968. [4] G. H¨mmerlin and K.H. Hoffman. Numerical Mathematics. SpringerVerlag New York, Inc., a 1991. [5] J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. SpringerVerlag New York, Inc., 2nd edition, 1993.
10
Information
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