%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="ViewSettings" CONTENT="23">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="Title" CONTENT="Reference/Mathematics/Solving Systems -- Part II">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Fri Mar 28 16:14:20 1997}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=Reference.cst}
%TCIDATA{PageSetup=72,72,72,72,0}
%TCIDATA{<LINK REL="contents" HREF="..\Reference\ReferenceIndex.tex#Reference Index">}
%TCIDATA{<LINK REL="next" HREF="MA01_04.tex">}
%TCIDATA{<LINK REL="parent" HREF="MA_contents.tex">}
%TCIDATA{<LINK REL="previous" HREF="MA01_02.tex">}
%TCIDATA{AllPages=
%F=36,\PARA{038<p type="texpara" tag="Body Text" >\hfill \thepage}
%}


\input{tcilatex}
\begin{document}


\section{Solving Systems -- Forward Elimination, Gaussian Elimination\label%
{Solving Systems -- Forward Elimination, Gaussian Elimination}}

\subsubsection{Forward Elimination\label{forward elimination}}

Given an arbitrary linear system of equations, the goal of forward
elimination is to reduce the system to \hyperref{echelon form}{}{}{%
MA01_02.tex#echelon form}.

\begin{enumerate}
\item  If necessary, interchange equations so that the coefficient of the
first \textbf{\ }variable in the first \textbf{\ }equation is nonzero. This
first equation is called the \textbf{pivot equation\label{pivot equation}}
and the first variable in this equation is the \textbf{pivot variable\label%
{pivot variable}}.

\item  Use the first equation, along with the third \hyperref{basic operation%
}{}{}{MA01_02.tex#basic operations}, to eliminate the first variable from
all subsequent equations.

\begin{enumerate}
\item  If the system of equations following the first equation contains one
or more variables and more than one equation, apply steps one and two to
this smaller system of equations.

\item  If the smaller system of equations does not involve any variables or
involves only one equation, then the procedure is complete. The original
system is now in echelon form.
\end{enumerate}
\end{enumerate}

\subsubsection{Inconsistent Systems\label{inconsistent systems}}

If forward elimination produces a false equation $0=a$, where $a\neq 0$,
then the system is \textbf{\hyperref{\textbf{inconsistent}}{}{}{%
MA01_01.tex#inconsistent}}.

\subsubsection{Gaussian Elimination}

Given an arbitrary system of linear equations, the goal of Gaussian
elimination is to find all the solutions of the system.

\begin{itemize}
\item  Use forward elimination to reduce the system to echelon form.
\end{itemize}

\begin{enumerate}
\begin{enumerate}
\item  If there are inconsistent equations, the procedure is complete. The
system has no solution.

\item  If there are no \hyperref{free variables}{}{}{MA01_02.tex#free
variables}, use back substitution to find the values of the variables. There
will be one solution.

\item  If there are free variables, use \hyperref{back substitution}{}{}{%
MA01_02.tex#back substitution} to find the \hyperref{determined variables}{}{%
}{MA01_02.tex#determined variables} in terms of the free variables. There
will be an infinite number of solutions.
\end{enumerate}
\end{enumerate}

\begin{example}
\label{gaussian elimination}Suppose you have a linear system of equations$
\begin{array}{lllllll}
2u & + & v & + & w & = & 5 \\ 
4u & - & 6v &  &  & = & -2 \\ 
-2u & + & 7v & + & 2w & = & 9
\end{array}
$. To solve the system of equations, use Gaussian elimination:

\begin{enumerate}
\item[Step 1]  Forward elimination.

\begin{enumerate}
\item  Eliminate $u$ from the second and third equations. Replace the second
equation with its sum with $\left( -2\right) $ times the first equation.
Replace the third equation with its sum with the first row. This gives the
equivalent system 
\[
\begin{array}{lllllll}
2u & + & v & + & w & = & 5 \\ 
&  & -8v & - & 2w & = & -12 \\ 
&  & 8v & + & 2w & = & 14
\end{array}
\]

\item  Eliminate $v$ from the third equation. Replace the third equation by
its sum with the second equation to obtain the equivalent system 
\[
\begin{array}{lllllll}
2u & + & v & + & w & = & 5 \\ 
&  & -8v & - & 2w & = & -12 \\ 
&  &  &  & w & = & 2
\end{array}
\]
The system of equations is now in echelon form.
\end{enumerate}

\item[Step 2]  Back substitution. 

\begin{itemize}
\item  The last equation gives $w=2$. Substituting this into the second
equation gives $v=1$. Substituting the values for $v$ and $w$ into the first
equation gives $u=1$.
\end{itemize}
\end{enumerate}
\end{example}

\subsubsection{Homogeneous System\label{homogeneous}}

The system

\[
\begin{array}{lllllllll}
a_{11}x_{1} & + & a_{12}x_{2} & + & ... & + & a_{1n}x_{n} & = & 0, \\ 
a_{21}x_{1} & + & a_{22}x_{2} & + & ... & + & a_{2n}x_{n} & = & 0, \\ 
. &  & . &  & ... &  & . &  & . \\ 
. &  & . &  & ... &  & . &  & . \\ 
. &  & . &  & ... &  & . &  & . \\ 
a_{m1}x_{1} & + & a_{m2}x_{2} & + & ... & + & a_{mn}x_{n} & = & 0
\end{array}
\]

is called a \textbf{homogeneous system}.

\begin{itemize}
\item  Every homogeneous system has the solution $x_{1}=x_{2}=...=x_{n}=0$.
This solution is called the \textbf{trivial solution\label{trivial solution}}%
.

\item  If the homogeneous system has fewer equations than unknowns, it has
an infinite number of solutions; in particular, it has a nontrivial solution.
\end{itemize}

\subsubsection{Gauss-Jordan Elimination\label{Gauss-Jordan}}

In the Gauss-Jordan elimination procedure, the pivot equation is divided by
the coefficient of the pivot variable. The pivot variable is then eliminated
from all prior equations as well as subsequent equations.

\subsection{\ Related Reference Topics}

{\small \hyperref{Solving systems of linear equations by the substitution
method}{}{}{Al06_01.tex#Substitution method for solving systems of equations}%
}

{\small \hyperref{Solving systems of linear equations by the elimination
method}{}{}{Al06_01.tex#Elimination method for solving systems of equations}}

\subsection{\ Related Scientific Notebook Topics}

{\small \hyperref{Equations}{}{}{../../Help/DM8-4.tex#Systems of equations}}

{\small \hyperref{Gaussian elimination}{}{}{../../Help/DM8-3.tex#Matrices,
fraction-free Gaussian elimination}}

{\small \hyperref{Row Operations and Echelon Forms}{}{}{%
../../Help/DM8-3.tex#Matrices, row operations}}

\noindent \hrulefill

\begin{center}
\begin{tabular}{ccc}
{\small \hyperref{\FRAME{itbpF}{13.9375pt}{14.4375pt}{3pt}{}{}{nblogo.wmf}{%
\special{language "Scientific Word";type "GRAPHIC";maintain-aspect-ratio
TRUE;display "PICT";valid_file "F";width 13.9375pt;height 14.4375pt;depth
3pt;original-width 24.0625pt;original-height 24.8125pt;cropleft "0";croptop
"0.9959";cropright "0.9937";cropbottom "0";filename
'Nblogo.wmf';file-properties "XNPEU";}}Computing Techniques}{}{}{%
../../Help/DMindex.tex}} & {\small \hyperref{\FRAME{itbpF}{13.9375pt}{%
14.4375pt}{3pt}{}{}{nblogo.wmf}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "PICT";valid_file "F";width
13.9375pt;height 14.4375pt;depth 3pt;original-width
24.0625pt;original-height 24.8125pt;cropleft "0";croptop "0.9959";cropright
"0.9937";cropbottom "0";filename 'Nblogo.wmf';file-properties "XNPEU";}}%
General Information}{}{}{../../Help/Index.tex}} & {\small \hyperref{\FRAME{%
itbpF}{13.9375pt}{14.4375pt}{3pt}{}{}{nblogo.wmf}{\special{language
"Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
"PICT";valid_file "F";width 13.9375pt;height 14.4375pt;depth
3pt;original-width 24.0625pt;original-height 24.8125pt;cropleft "0";croptop
"0.9959";cropright "0.9937";cropbottom "0";filename
'Nblogo.wmf';file-properties "XNPEU";}}Reference Library}{}{}{%
../ReferenceIndex.tex}}
\end{tabular}
\end{center}

\noindent \hrulefill

\end{document}
