Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    Numerical Solution of Engineering and Scientific Problems David M. Rocke Department of Applied Science

    Uploaded by

    Aleli Paule
    This document discusses numerical methods for solving equations. It begins by explaining that while linear and quadratic equations can be solved exactly, higher-order polynomial equations generally have no closed-form solution. The document then focuses on iterative methods like bisection and false position for finding approximate roots of functions. It provides pseudocode examples of these methods and discusses modifications to improve convergence, including adjusting function evaluations and switching to bisection if convergence is slow. Numerical examples apply the methods to solve equations involving exponential and polynomial functions.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Numerical Solution of Engineering and Scientific Problems David M. Rocke Department of Applied Science

    Uploaded by

    Aleli Paule
    42 views51 pages
    This document discusses numerical methods for solving equations. It begins by explaining that while linear and quadratic equations can be solved exactly, higher-order polynomial equations generally have no closed-form solution. The document then focuses on iterative methods like bisection and false position for finding approximate roots of functions. It provides pseudocode examples of these methods and discusses modifications to improve convergence, including adjusting function evaluations and switching to bisection if convergence is slow. Numerical examples apply the methods to solve equations involving exponential and polynomial functions.

    Original Description:

    Mathematical methods of engineering

    Original Title

    Regula Falsi

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses numerical methods for solving equations. It begins by explaining that while linear and quadratic equations can be solved exactly, higher-order polynomial equations generally have no closed-form solution. The document then focuses on iterative methods like bisection and false position for finding approximate roots of functions. It provides pseudocode examples of these methods and discusses modifications to improve convergence, including adjusting function evaluations and switching to bisection if convergence is slow. Numerical examples apply the methods to solve equations involving exponential and polynomial functions.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    42 views51 pages

    Numerical Solution of Engineering and Scientific Problems David M. Rocke Department of Applied Science

    Uploaded by

    Aleli Paule
    This document discusses numerical methods for solving equations. It begins by explaining that while linear and quadratic equations can be solved exactly, higher-order polynomial equations generally have no closed-form solution. The document then focuses on iterative methods like bisection and false position for finding approximate roots of functions. It provides pseudocode examples of these methods and discusses modifications to improve convergence, including adjusting function evaluations and switching to bisection if convergence is slow. Numerical examples apply the methods to solve equations involving exponential and polynomial functions.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 51

    EAD 115

    Numerical Solution of Engineering


    and Scientific Problems
    David M. Rocke
    Department of Applied Science

    Solution of an Equation
    We learn how to solve (find roots of) linear
    and quadratic equations in
    elementary/high school. Solution methods
    for quadratics have been known for 4000
    years.
    Cubic and quartic equations have general
    solutions (known since 1500s)
    Quintic and higher polynomials have no
    general solution

    Quadratic Equations

    ax + bx + c = 0
    2

    -b b - 4ac
    x=
    2a
    2

    Equations with no Exact,


    Closed-Form Solution
    Consider the equation for the velocity of a
    parachutist.
    Find the drag coefficient so that the velocity at a
    specified time is a specified value

    gm
    -( c / m ) t
    v=
    (1- e
    )
    c
    gm
    -( c / m ) t
    f (c ) =
    (1- e
    )-v = 0
    c

    Bracketing Methods
    Find two points xL and xU so that f(xL) and
    f(xU) have opposite signs
    If f() is continuous, there must be at least
    one root in the interval
    Bracketing methods take this information,
    and produce successive approximations to
    the solution by narrowing the interval
    bracketing a/the root

    Behavior of Roots of Continuous


    Functions
    If the function values at two points have
    the same sign, then the number of roots
    between them is even, including possibly
    0.
    If the function values at two points have
    different signs, then the number of roots
    between them is odd, so cannot be 0.

    Exceptions
    Roots of multiplicity greater than one, count as
    multiple roots in this. The function
    f ( x ) ( x 1) 2

    has only one root at x = 1, even though the


    function does not change sign in the interval from
    0 to 2, but this counts as two.
    Discontinuous functions need not obey the rules.

    Computer Graphics Methods


    The function f(x) = sin 10x + cos 3x has
    opposite signs at x = 0 and x = 5
    This means that there exists at least one
    root in that interval.
    Excel, Matlab, or other computer graphics
    packages can be used to investigate this.

    Bisection Method
    Suppose a continuous function changes
    sign between xL and xU. Consider
    xM = (xL + xU)/2
    If f(xM) = 0, we have found a root.
    If f(xM) is not zero, it differs in sign from
    exactly one of the end points
    This gives a new interval of half the length
    which must contain a root

    gm
    -( c / m ) t
    f (c ) =
    (1- e
    )-v = 0
    c
    m = 68.1 kg
    Reaches velocity of 40 m/s at t = 10s.
    (9.8)(68.1)
    -( c / 68.1)10
    f (c ) =
    (1- e
    ) - 40 = 0
    c
    667.38
    -0.146843c
    f (c ) =
    (1- e
    ) - 40 = 0
    c

    f (12) = 6.06
    f (16) = -2.269
    f (14) = 1.569
    f (15) = -0.425
    f (14.5) = 0.5523
    f (14.7802) = 0

    True and Estimated Error


    Step

    14

    -0.780

    15

    0.220

    14.5

    -0.280

    0.5

    14.75

    -0.030

    0.25

    14.875

    0.095

    0.125

    Error Estimate for Bisection


    Interval at start of step i is 2x, the
    distance between the upper and lower
    bounds. We pick the middle of this interval
    as the ith guess
    The next interval has length x, has one
    end on the previous guess, and the other
    at one end or the other of the previous
    interval

    At step i the error cannot be greater than


    x and at step i+1 it cannot be greater
    than x/2
    The distance between the best guess at
    step i and the best guess at the next step
    is exactly x/2
    Thus, the error bound is the change in the
    best guess

    Function Evaluations
    In some applications, evaluation of the
    function to be minimized is expensive and
    may itself involve a large computation
    One example I am currently working on
    takes about 15 minutes for each function
    evaluation, each of which requires solving
    400,000 subproblems
    Optimize code to reduce function
    evaluations

    In n iterations, the first implementation


    uses 2n function evaluations.
    The second implementation use n + 1
    function evaluations
    Neither implementation contains a check
    that the function actually does change sign
    in the input interval

    Summary of Bisection
    The method is slow but sure for
    continuous functions
    There is a well-defined error bound,
    though the true error may be much less

    Method of False Position


    Also called linear interpolation or regula
    falsi.
    Bisection uses information that there is a
    root in the interval xL to xU but does not
    use any information from the function
    values f(xL) and f(xU) other than the signs.
    False position uses the insight that if |f(xL)|
    is smaller than |f(xU)|, one would expect
    the root to lie closer to xL.

    Fig 5.12

    The line through the two end points of the interval is


    f ( xL ) - f ( xU )
    ( y - f ( xU )) =
    ( x - xU )
    xL - xU
    This intersects the x axis where y is 0 and x satisfies
    f ( xL ) - f ( xU )
    - f ( xU ) =
    ( x - xU )
    xL - xU
    xL - xU
    f ( xU )
    ( x - xU ) = f ( xL ) - f ( xU )
    f ( xU )( xL - xU )
    xR = xU f ( xL ) - f ( xU )

    The new root estimate xR replaces


    whichever of the end points that has the
    same sign as f(xR), so that the two new
    endpoint still bracket the root.
    We use as an error estimate, the change
    in the best root estimate from one iteration
    to the next.
    This works well to the extent that the
    function is nearly linear in the interval and
    near the root.

    gm
    -( c / m ) t
    f (c ) =
    (1- e
    )-v = 0
    c
    m = 68.1 kg
    Reaches velocity of 40 m/s at t = 10s.
    (9.8)(68.1)
    -( c / 68.1)10
    f (c ) =
    (1- e
    ) - 40 = 0
    c
    667.38
    -0.146843c
    f (c ) =
    (1- e
    ) - 40 = 0
    c

    f (12) 6.0669
    f (16) 2.2688
    ( 2.2688)(12 16)
    xR 16
    14.9113
    6.0669 ( 2.2688)
    f (14.9113) 0.2543
    ( 0.2543)(12 14.9113)
    xR 14.9113
    14.7942
    6.0669 ( 0.2543)
    f (14.7942) 0.02727
    f (14.7802) 0

    Fig 5.13

    Bisection Error
    Step

    14

    -0.780

    15

    0.220

    14.5

    -0.280

    0.5

    14.75

    -0.030

    0.25

    14.875

    0.095

    0.125

    False Position Error


    Step

    14.9113

    0.131104

    14.7942

    0.013994

    0.117110

    14.7817

    0.001496

    0.012497

    14.78037

    0.000164

    0.001332

    14.78023

    0.000022

    0.000142

    Pitfalls of False Position


    If the function is very nonlinear in the
    bracketing interval, convergence can be
    very slow, and the approximate error
    estimate can be very poor.
    A possible solution is to use bisection until
    the function appears nearly linear, then
    switch to false position for faster
    convergence, or to use false position, but
    switch to bisection if convergence is slow.
    Another is to adjust a fixed endpoint

    Fig 5.14

    Code Examples
    We show pseudo code for modified false
    position with adjustment of endpoint
    function values
    Then we show VBA code for false position
    Then we show VBA code for the modified
    false position as in the above pseudocode
    Then VBA code for false position, with
    bisection steps whenever the signs do not
    change for a long time.

    Fig 5.15

    Option Explicit
    Function f(x)
    f = x ^ 10 - 1
    End Function
    Function FalsePos(xl, xu, es, imax)
    Dim fl As Double, fu As Double, fr As Double
    Dim xr As Double, xrold As Double, ea As Double, test As Double
    Dim iter As Integer
    iter = 0
    fl = f(xl)
    fu = f(xu)
    If fl * fu >= 0 Then
    MsgBox ("Function does not change sign in interval")
    Return
    End If

    Do
    xrold = xr
    xr = xu - fu * (xl - xu) / (fl - fu)
    fr = f(xr)
    iter = iter + 1
    If xr <> 0 Then
    ea = Abs((xr - xrold) / xr)
    End If
    test = fl * fr
    If test < 0 Then
    xu = xr
    fu = fr
    ElseIf test > 0 Then
    xl = xr
    fl = fr
    Else
    ea = 0
    End If
    If (ea < es) Or (iter >= imax) Then
    Exit Do
    End If
    Loop
    FalsePos = xr
    MsgBox ("ea = " & ea & " iter = " & iter)
    End Function

    Function Mod1FalsePos(xl, xu, es, imax)


    Dim fl As Double, fu As Double, fr As Double
    Dim xr As Double, xrold As Double, ea As Double, test As Double
    Dim iter As Integer, il As Integer, iu As Integer
    iter = 0
    il = 0
    iu = 0

    Do
    If test < 0 Then
    xu = xr
    fu = fr
    iu = 0
    il = il + 1
    If il >= 2 Then
    fl = fl / 2
    End If
    ElseIf test > 0 Then
    xl = xr
    fl = fr
    il = 0
    iu = iu + 1
    If iu >= 2 Then
    fu = fu / 2
    End If

    Function Mod2FalsePos(xl, xu, es, imax)

    il = 0
    iu = 0

    test = fl * fr
    If test < 0 Then
    iu = 0
    il = il + 1
    If il >= 3 Then
    xr = (xl + xr) / 2
    fr = f(xr)
    End If
    ElseIf test > 0 Then
    il = 0
    iu = iu + 1
    If iu >= 3 Then
    xr = (xr + xu) / 2
    fr = f(xr)
    End If
    End If
    test = fl * fr

    If test < 0 Then


    iu = 0
    xu = xr
    fu = fr
    ElseIf test > 0 Then
    il = 0
    xl = xr
    fl = fr
    Else
    ea = 0
    End If

    Results of Modified False Position


    With the function x10 1 and starting
    points 0 and 1.3, bisection takes 14
    iterations to achieve a relative error of
    0.0001 = 0.01%.
    False Position takes 39 iterations.
    The modifications of false position take 12
    iterations each.

    Modified False Position

    Modified False Position

    You might also like