Application: finite differencesLet us apply linear algebra to the boundary value problem−d2udx2= f( x), 0 6 x 6 1, u(0) = u(1) = 0.f( x)is given, and the goal is to find u(x).Physical interpretation: models steady-state temperature distribution in a bar (u(x) is temp eratureat pointx) under influence of an external heat source f(x) and with ends fixed at 0◦(ice cube atthe ends?).The boundary conditionu(0) = u(1) = 0 makes the solution u(x) unique.u(x)x 1We will approximat e this problem as follows:• replace u(x) by its values at equally spaced points in [0, 1]u0= 0u1= u(h)u2= u(2h)u3= u(3h)un= u(nh)un+1= 0. . .0 h 2h 3h nh 1• approx imated2udx2at these points (finit e differences)• replace differential equation with linear equation at each point• solve linear problem using Gaussian eliminationFinite differencesFinite differences for first derivative:dudx≈∆u∆x=u(x + h) − u(x)h@oru(x) − u(x − h)h@oru(x + h) − u(x − h)2hsymmetric and most accurateArmin [email protected] differences for secon d deri vative:d2udx2≈u(x + h) − 2u(x) + u(x − h)h2the only symmetric choice involving only u(x), u(x ± h)Question 1. Why does this approximated2udx2as h → 0?Setting up the linear equations−d2udx2= f( x), 0 6 x 6 1, u(0) = u(1) = 0.Usingd2udx2≈u(x + h) − 2u(x) + u(x − h)h2, we get:u0= 0u1= u(h)u2= u(2h)u3= u(3h)un= u(nh)un+1= 0. . .0 h 2h 3h nh 1at x = h:−u(2h) − 2u(h) + u(0)h2= f(h)2u1− u2= h2f(h) (1)atx = 2h:(2)atx = 3h:(3)at x = nh:(n)Armin [email protected] 2. In the case of six divisions (n = 5), we get:2 −1−1 2 −1−1 2 −1−1 2 −1−1 2Au1u2u3u4u5x=h2f(h)h2f( 2h)h2f( 3h)h2f( 4h)h2f( 5h)bSuch a matrix is called a band m atrix. As we will see next, such matrices always havea partic ularly simpl e LU decompositionGaussian eliminat ion:Armin [email protected] leads to the LU decomposition:Now, g i ven a n f, we can solve for u1,, u5by forward and back substitution .Ax = bGA=LULc = b and Ux = cLU decomposi tion vs matrix inverseIn many app lications, we don’t just solveAx = b for a single b, but for many differentb (th ink millions).Note, for instance, that in our example of “steady-state temperature distribution in a bar” the matrixA is always the same (it only depends on the kind of problem), whereas the vector b models theexternal heat (and thus changes for each specific instance).• That’s why the LU decomposition saves us from repe ating lots of computation incomparison with Gaussian eli mination.• What about comput ing A−1? [Not just here, using A−1is a bad idea!]Example 3. Using LU decom position, we solve, for each b,1−121−231−341−451c = b,2 −132−143−154−165x = cby forward and backward substitution.How many operations are needed in the n × n case?Armin [email protected] the other hand,A−1=165 4 3 2 14 8 6 4 23 6 9 6 32 4 6 8 41 2 3 4 5.How many operations are needed to compute A−1b?Conclu sions• Large matrices met in applications usually are not random but have some struct u r e(such as band matrices).• When solving linear equation s, we do not (try to) compute A−1.◦ It destroys structure in practical problems.◦ As a result, it can be orders of magnitude slower,◦ and require orders of magnitu de more memor y.◦ It is also numerically unstable.◦ LU decomposition can be adjusted to not have these drawbacks.Armin
View Full Document
Unlocking...