Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    16 LP 2 1 Substitution

    Uploaded by

    quangnhat1220
    This document discusses solving systems of linear equations using substitution. It provides an example showing how to use the first equation to express one variable in terms of others, substitute it into the second equation, and solve to find the values of the variables. It notes that for a system with more variables than equations, there will be a family of solutions parameterized by the free variables.

    Copyright:

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

    16 LP 2 1 Substitution

    Uploaded by

    quangnhat1220
    9 views24 pages
    This document discusses solving systems of linear equations using substitution. It provides an example showing how to use the first equation to express one variable in terms of others, substitute it into the second equation, and solve to find the values of the variables. It notes that for a system with more variables than equations, there will be a family of solutions parameterized by the free variables.

    Original Title

    _340bad8411ad88ec6ef85b199d4a12ae_16_LP_2_1_Substitution

    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 solving systems of linear equations using substitution. It provides an example showing how to use the first equation to express one variable in terms of others, substitute it into the second equation, and solve to find the values of the variables. It notes that for a system with more variables than equations, there will be a family of solutions parameterized by the free variables.

    Copyright:

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

    16 LP 2 1 Substitution

    Uploaded by

    quangnhat1220
    This document discusses solving systems of linear equations using substitution. It provides an example showing how to use the first equation to express one variable in terms of others, substitute it into the second equation, and solve to find the values of the variables. It notes that for a system with more variables than equations, there will be a family of solutions parameterized by the free variables.

    Copyright:

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

    Linear Programming:

    Solving Linear Systems

    Daniel Kane
    Department of Computer Science and Engineering
    University of California, San Diego

    Advanced Algorithms and Complexity


    Data Structures and Algorithms
    Learning Objectives
    Solve a system of linear equations.
    Say something about what the set of
    solution to a system of linear equations
    looks like.
    Last Time

    Linear programming: Dealing with systems


    of linear inequalities.
    Linear Algebra

    Today, we will deal with the simpler case, of


    systems of linear equalities.
    Linear Algebra

    Today, we will deal with the simpler case, of


    systems of linear equalities.
    For example:

    x +y = 5
    2x + 4y = 12.
    Method of Substitution

    Use rst equation to solve for one


    variable in terms of the others.
    Substitute into other equations.
    Solve recursively.
    Substitute back in to rst equation to
    get initial variable.
    Example

    x +y = 5
    2x + 4y = 12.
    Example

    x +y = 5
    2x + 4y = 12.
    First equation implies
    x = 5 − y.
    Example

    x +y = 5
    2x + 4y = 12.
    First equation implies
    x = 5 − y.
    Substituting into second:
    12 = 2x + 4y = 2(5 − y ) + 4y = 10 + 2y .
    Example

    x +y = 5
    2x + 4y = 12.
    First equation implies
    x = 5 − y.
    Substituting into second:
    12 = 2x + 4y = 2(5 − y ) + 4y = 10 + 2y .
    So y = 1, x = 5 − 1 = 4.
    Problem

    What is the value of x in the solution to the


    following linear system?

    x + 2y = 6
    3x − y = −3.
    Solution

    From the rst equation, we get

    x = 6 − 2y .
    Solution

    From the rst equation, we get

    x = 6 − 2y .

    Substituting into the second,

    −3 = 3(6 − 2y ) − y = 18 − 7y .
    Solution

    From the rst equation, we get

    x = 6 − 2y .

    Substituting into the second,

    −3 = 3(6 − 2y ) − y = 18 − 7y .

    Solving gives, y = 3, so x = 6 − 2 · 3 = 0.
    Another Example

    Consider the following system of equations:

    x +y +z = 5
    2x + y − z = 1.
    Another Example

    Consider the following system of equations:

    x +y +z = 5
    2x + y − z = 1.

    Solve by substitution.
    Solution

    From rst equation:

    x = 5 − y − z.
    Solution

    From rst equation:

    x = 5 − y − z.

    Substitute into second.

    2(5 − y − z) + y − z = 1,

    or
    y = 9 + 3z.
    Cannot Solve for z!

    No equations left.
    Cannot Solve for z!

    No equations left.However, for any z have


    solution

    y = 9 + 3z
    x = 5 − y − z = −4 − 4z.
    Cannot Solve for z!

    No equations left.However, for any z have


    solution

    y = 9 + 3z
    x = 5 − y − z = −4 − 4z.

    Have entire family of solutions. z is a free


    variable.
    Degrees of Freedom

    Your solution set will be a subspace.


    Dimension = number of free variables.
    Each equation gives one variable in
    terms of others.
    Generally, dimension equals

    num. variables − num. equations.


    Summary

    Can solve systems using method of


    substitution.
    Each equation reduces degrees of
    freedom by one.
    Next Time

    Systematize this to simplify notation and


    make into an algorithm.

    You might also like